Рекурсивные типы. Часть 1/5. Рекурсия05.12.2024 10:15

Привлекаем внимание к рекурсии.

Слово «рекурсия» происходит от латинского «recursio» — «круговорот, возврат». Применительно к вычислениям этот термин относится к алгоритмам, повторяющих какие-либо действия. Данный обзор посвящён типам, которые обслуживают рекурсивные алгоритмы.

Это вводная часть и собственно про типы здесь будет мало что сказано. Разве что будут рассмотрены типы Y-комбинаторов. Но здесь вводятся понятия, которые пригодятся при обсуждении рекурсивных типов.

Содержание первой части:

Если тема знакома, то можно сразу переходить к следующей части, а сюда можно будет вернуться в любой момент.

Другие части обзораДругие обзоры цикла

Вычислимые функции

Начало прошлого века ознаменовано бурным развитием теории вычислений. Зародившиеся тогда теория типов и λ-исчисление были призваны формализовать понятие алгоритма, чтобы можно было исследовать их корректность, сложность, вычислимость и другие свойства. Проблема вычислимости имеет тут очень большое значение, так как среди всевозможных алгоритмов есть такие, в которых единожды описанные действия должны повторяться, и не всегда очевидно, завершатся ли такие повторения, или будут продолжаться бесконечно.

Теория вычислимости берёт своё начало с работы Алана Тьюринга On Computable Numbers, With An Application to Entscheidungsproblem. Тьюринг ввел понятие абстрактной вычислительной машины и доказал фундаментальную теорему о неразрешимости задачи о её остановке. Совместно с Чёрчем они сформулировали критерий вычислимости — таковыми считаются функции, алгоритм вычисления которых можно записать как последовательность инструкций для машины Тьюринга.

Хотя такие алгоритмы обеспечивают практический способ определения вычислимых функций, но их сложно анализировать, в частности, классифицировать, исследовать их корректность и т.п. Возникает вопрос о более формальном описании вычислимых функций. Такие рассуждения обычно проводят в два этапа.

Сперва вводится понятие примитивной-рекурсивной функции. Не теряя общности, рассматриваются отображения только между целыми числами (ведь любые значения можно проиндексировать натуральными числами). Все такие примитивно-рекурсивные функции замкнуты относительно обычной композиции функций и специального комбинатора примитивной рекурсии $\eta$ . Например, если задано число и функция от двух чисел $\phi$ , то то оператор $\eta$ определяется так:

$\begin{split}\eta(0) &= r\\\eta(n) &= \phi(n,\;\eta(n-1))\end{split}$

В последней строчке видна суть рекурсии — можно сказать, что в процессе вычисления $\eta(n>0)» src=«https://habrastorage.org/getpro/habr/formulas/1/1d/1d3/1d3f4ebcb08ebdc68eac201c4adc782f.svg» />, ещё раз потребуется начать вычисление этой функции (но, уже с другими параметрами), в которой снова… ну, вы поняли)). Комбинатор примитивной рекурсии отражает идею математической индукции — если у нас есть значения <img alt=$ и если, имея $\eta(n)$ мы можем вычислить $\eta(n+1)$ , то мы всегда можем вычислить $\eta(n)$ для любого натурального . Другие детали и примеры примитивно-рекурсивных функций можно подсмотреть в Википедии.

Однако, есть множество вычислимых функций, которые невозможно записать посредством примитивной рекурсии, например, сиракузская последовательность, или функция Аккермана. Оказывается, что для учёта таких функций, достаточно к комбинаторам композиции и примитивной рекурсии добавить ещё один — оператор минимизации аргумента $\mu(f)$ , который вычисляет минимальное значение аргумента , обнуляющее :

$\begin{split}\mu(f) &= \min\left(Ker(f)\right), \text{ где}\\Ker(f) &= \{y,\;f(y)=0\}\; - \;\text{ядро функции $f$ (множество всех нулей)}\\\end{split}$

Оператор $\mu$ не всегда корректно определён, поскольку, например, функция может быть не равной нулю ни при каких значениях аргументов. Это означает, что для некоторых аргументов функция становится зацикленной, или расходящейся, что в реальном мире соответствует «зависанию», или сбою. Поэтому класс функций, замкнутый относительно этих трёх комбинаторов, называется частично определёнными рекурсивными функциями (или просто частично-рекурсивными функциями).

Такое определение лежит в основе тезиса Чёрча-Тьюринга, который в формулировке Клини звучит так:

Все функции, вычислимые посредством алгоритмов, являются частично рекурсивными.

Общерекурсивные функции

Отдельного упоминания заслуживает понятие общерекурсивных функций — это подкласс частично-рекурсивных функций, но возвращающих значения для любого своего аргумента (тотальные функции). Любая примитивно-рекурсивная функция относится к классу частично-рекурсивных и является тотальной. Но также существуют и тотальные не примитивно-рекурсивные функции, например, упомянутая выше функция Аккермана. Доказано, что общего алгоритма определения тотальности произвольной функции не существует — это связано с известной проблемой остановки. Например, до сих пор не известно, существуют ли такие натуральные числа, для которых сиракузская последовательность будет расходящейся, или же эта функция для любого числа вернёт единицу (гипотеза Коллатца).

Циклы и рекурсия

Абстрактная машина Тьюринга предполагает различные реализации, но обычно речь идёт

о ленте (возможно бесконечной в обе стороны) с данными на ней и
о головке, перемещающейся по ленте, и меняющей по определённым правилам как данные на ленте, так и собственное состояние.

Для нас сейчас важна способность головки свободно перемещаться по ленте «назад» — именно таким способом машина Тьюринга может многократно обрабатывать («исполнять») один и тот же отрезок ленты.

Концепция такой абстрактной машины легла в основу различных архитектур ЭВМ, в том числе и в наиболее известной архитектуре фон Неймана, использующейся (в различных модификациях) в большинстве современных компьютеров. В этой архитектуре исполнитель-процессор, выполняет команды по обработке данных, при чём и те, и другие хранятся в памяти вычислительной машины. Команды могут быть такими:

чтение данных из произвольной ячейки памяти в регистр (состояние) процессора,
запись данных из регистра в произвольную ячейку памяти,
арифметико-логические операции над данными в регистре,
(дополнительные инструкции, вроде работы с числами с плавающей запятой),
ввод/вывод данных — взаимодействие с окружением,
переход к любой ячейке памяти для выполнения хранящейся там команды.

Аналогия с «головкой на ленте» очевидна, только набор возможностей более детализирован и дополнен операциями ввода/вывода. А за повторение любого фрагмента программы здесь отвечает последняя команда из списка, так же известная как goto.

Набор возможных процессорных команд (с правилами их вызова) сам по себе определяет некий язык программирования. Такой язык будет «низкоуровневым», жёстко привязанным к архитектуре вычислительной машины, что иногда позволяет писать высокопроизводительные алгоритмы. Однако у такого подхода есть и недостатки.

Практика показала, что неограниченное использование команды goto приводит к тяжело читаемому, плохо предсказуемому спагетти-коду, хрупкому относительно внесения правок. Поэтому были разработаны более продвинутые языки за счёт добавления дополнительных инструкций:

условный переход,
вызов подпрограммы,
возврат из подпрограммы.

Каждая такая инструкция заменяет вызов goto в ограниченных, но наиболее востребованных сценариях.

Выделение подпрограмм (procedure myProc(аргументы) { тело }) позволило структурировать код, разбить его на слабо связанные блоки. В дальнейшем эта идея декомпозиции кода только развивалась и привела появлению более сложных синтаксических конструкций:

условный оператор if (условие) { "счастливый" блок кода } else { другой блок кода },
оператор цикла while (условие) { блок повторяяющихся действий }.

Реализация таких конструкций, совместно с семантикой вызова (call) процедур и возврата (return) из них, характеризует поколение языков высокого уровня. Новые операторы позволяли (практически) полностью исключить из кода необходимость упоминания небезопасного goto, что способствовало развитию парадигмы структурного программирования.

Про goto

Споры о вреде и пользе goto не затихают до сих пор. Плюсы goto по‑прежнему востребованы в низкоуровневых языках вроде C. Прочитать об этом можно, например, в хабр‑статье О вреде GOTO‑фобии (с примерами на C).

В структурном программировании «переход назад» (для повторения инструкций) реализуется двумя способами:

циклы — блок кода выполняется повторно, покуда успешно проходит проверка некоторого условия;
вызов процедур — процедура может вызвать себя (или любую другую процедуру выше по стеку вызовов), образуя, собственно, рекурсию.

Существует теорема Клини о рекурсии, утверждающая, что для любой вычислимой функции найдутся эквивалентные ей рекурсивные реализации. Иначе говоря, везде где «переход назад» реализован посредством циклов, можно перейти от них к рекурсии. Верно и обратное — любую рекурсию можно переписать императивно, например, с помощью тех же циклов.

Квайны

Любопытный способ доказательства теоремы Клини заключается в написании квайна — программы способной вывести в консоль собственный код. Задача не столь проста, как может показаться на первый взгляд. В интернете есть множество реализаций квайнов на самых разных языках программирования, но если вы ещё не сталкивались с этой задачей, настоятельно рекомендую попробовать решить её самостоятельно. Возможность написания квайнов на некотором языке программирования считается доказательством тьюринг-полноты этого языка.

Рекурсивные алгоритмы зачастую оказываются более выразительными и лаконичными, чем решения через циклы. К сожалению, наивная рекурсия плохо сочетается с современной архитектурой ЭВМ, поэтому гораздо чаще для повторения действий применяются циклы. Рассмотрим эти тонкости в следующей разделе.

Cтек и хвостовая рекурсия

Внедрение концепции подпрограмм привела к усложнению устройства памяти ЭВМ. Каждый вызов подпрограммы требует выделения памяти для локальных переменных доступных только внутри подпрограммы, и после выхода из неё всю эту память необходимо освободить. Память — очень важный ресурс для работы всей ЭВМ, и если он будет исчерпан, произойдёт сбой, который остановит работу всех процессов. Многочисленные выделения/освобождения памяти при обращении к подпрограммам могут сильно фрагментировать память, усложняя и без того непростую работу диспетчера памяти.

У вызова процедур есть одна особенность — возврат осуществляется только из последней вызванной процедуры. А значит, и память под локальные переменные освобождается только та, которая была выделена (и ещё не освобождена) в последний раз. Тут просматривается структура данных, организованная по принципу LIFO, известная как стек. Выделение и освобождение памяти осуществляется всего лишь изменением единственной величины — адреса вершины стека.

При вызове функции указатель стека смещается вверх для размещения локальных переменных вызываемой функции, а также адреса, куда потом вернуть управление. При возврате стек очищается просто за счёт сдвига вершины стека.

Для лучшей оптимизации стек по возможности размещается в «быстрой» памяти, например, в процессорном кэше. В том числе и по этой причине максимальный размер стека весьма не велик в сравнении с прочей памятью, используемой приложением. И это ограничение вызывает проблемы при использовании рекурсии.

Наивное применение рекурсивных вызовов приводит к тому, что до первого освобождения стека он будет расти на каждом шаге. Когда требуется выполнять одни и те же действия тысячи раз, то рекурсия полностью исчерпает стек, что приведёт к знаменитому сбою Stack Overflow. Например,

def factorial(x: Int): Int =
  if x >= 1 then 1
  else x * factorial(x - 1) // небезопасно!

Пожалуй, пример факториала не очень удачен для демонстрации переполнения стека (арифметическое переполнение произойдёт гораздо быстрее), но это достаточно простая функция, которую мы часто будем использовать в качестве примера.

К счастью, существует возможность избежать разрастания стека при вызове функций. Если этот вызов происходит в самом конце (хвостовой вызов) — вызывающая функция возвращает результат вызываемой функции — компилятор может понять, что все локальные переменные вызывающей функции больше не нужны (кроме аргументов для вызываемой), а значит, в сетке можно сразу освободить занимаемое ими место под переменные вызываемой функции. Такая техника называется оптимизацией хвостового вызова (tail call optimization, TCO).

Наиболее важным случаем этой техники является оптимизация хвостовой рекурсии. Ведь когда функция возвращает результат выполнения… себя же (но с другими параметрами), то вообще нет необходимости в манипуляциях со стеком — все стековые переменные «наследуются» из вызывающего контекста!

Scala поддерживает оптимизацию хвостовой рекурсии «из коробки». Но в предыдущей реализации факториала рекурсивный вызов не является хвостовым, так как его результат приходится ещё домножать на x. Факториал же с хвостовой рекурсией выглядит так:

def factorial(x: Int): Int =
  def factorialHelper(         // Вспомогательная рекурсивная функции.
    accumulator: Int,          // Два аргумента функции определяют
    x: Int                     // состояние в каждой итерации.
  ): Int =
    if x >= 1 then accumulator // Условие прекращения итераций.
    else factorialHelper(      // "Хвостовой" вызов!
      accumulator * x,         // В следующей итерации
      x - 1                    // состояние будет уже другим.
    )
						
  factorialHelper(1, x)        // Вызов вспомогательной хвостово-рекурсивной функции.

При хвостовой рекурсии функция преобразует переданное ей состояние итерации и передаёт его далее себе же. На этот процесс можно взглянуть и с другой точки зрения — функция применяется к результатам вычисления самой себя, композируется с собой! Идея самоприменения ещё встретится нам в дальнейшем.

@tailrec

В Scala также есть аннотация @tailrec, установка которой перед определением функции гарантирует, что компилятор оптимизирует рекурсию как хвостовую, а если не сможет, то сразу выдаст ошибку.

Вследствие теорем о рекурсии, любую рекурсивную функцию можно переписать в «хвостовой» форме. А благодаря современным компиляторам, даже в существующей стековой архитектуре рекурсивные решения могут быть не менее производительными и надёжными, чем циклы. Но даже если компилятор какого-то языка не умеет в такую оптимизацию, хвостовую рекурсию всегда несложно переписать в императивном виде посредством обычного цикла. Продемонстрируем это для предыдущего фрагмента кода:

def factorial(n: Int): Int =
  var x = n                       // В этих двух переменых хранится
  var accumulator = n             // состояние текущей итерации.
  while !(x >= 1) do              // Условие прекращения итераций.
    x = x - 1                     // А в каждой итерации
    accumulator = accumulator * x // состояние меняется.
  accumulator

Если состояния в итерациях раньше хранилось в двух аргументах рекурсивной функции, то здесь они вынесены в две «переменные переменные», которые явно меняются в цикле, где указано то же самое условие прекращения итераций, что и раньше. Аналогичным способом можно любую рекурсию свести к циклу, что демонстрирует эквивалентность этих двух подходов.

Ссылки вперёд

Обычно рекурсивный вызов функции, реализуется посредством обращения в её теле к ней же самой по имени. В ФП имя функции не является её обязательным атрибутом. Ведь функции, как «объекты первого класса», можно размещать в переменных, или передавать другим функциям в качестве аргументов. Таким образом, в момент вызова функции её первоначальное имя может оказаться ненужным, а то и вовсе недоступным. Безымянные литералы функций будут рассмотрены в следующем разделе, посвящённом λ-исчислению, а сейчас уделим внимание рекурсивным вызовам функций по имени.

def fibonacci(x: Int): Int =
  if x > 2 then fibonacci(x - 1) + fibonacci(x - 2)
  else 1

Здесь литерал fibonacci в теле функции связывается с объявлением, для которого ещё не определено это самое тело функции! Это ключевой элемент рекурсии по имени — использование ссылок на то, что ещё не определено, но будет определено в дальнейшем (в данном случае, когда тело функции будет связано с её именем).

Обычно можно использовать только ранее инициализированные идентификаторы, то есть доступны только ссылки в одном направлении — «назад». Если разрешить использовать ссылки, действующие ещё и в обратном направлении, на «будущий код», то это приводит к появлению возможности повторения алгоритма, к рекурсии.

Например, этот фрагмент кода демонстрирует чуть более общий, чем «ссылки на себя», случай «ссылок вперёд»:

def odd (x: Int): Boolean = x != 0 && !even(x - 1)
def even(x: Int): Boolean = x == 0 || !odd (x - 1)

Здесь odd ссылается «вперёд» на ещё неизвестную к этому моменту функцию even, которая ссылается «назад» на известную odd. Образуется цикл рекурсивных вызовов, называемая »косвенной рекурсией» (или «взаимной рекурсией»). В этом случае оптимизация не сработает, но, как и для любой другой рекурсии, алгоритм всегда можно переписать через хвостовые вызовы:

def even(x: Int): Boolean = x match 
  case 0 => true
  case 1 => false
  case _ => even (x - 2) // обычная хвостовая рекурсия
def odd (x: Int): Boolean = !even(x)

Подобные «циклические зависимости» являются плохо предсказуемыми, потенциально опасными, аналогично оператору goto. Если всё же требуется именно такое поведение, то в некоторых языках предлагается использовать дополнительные синтаксические конструкции, явно разрешающие «ссылки вперёд». Например, в F# за это отвечает ключевое слово rec.

Y-комбинатор в λ-исчислении

λ-исчисление предоставляет формальный язык для конструктивного определения функций, как обычных, так и функций над типами — конструкторов типов. Для последних особенно важна рекурсия, так как на уровне типов привычные циклы не имеют смысла.

Сперва вспомним ключевые положения бестипового λ-исчисления. Основным объектом тут является функция единственного аргумента. И на входе, и на выходе у неё точно такие же функции. Ключевыми понятиями λ-исчисления являются $\lambda$ -абстракции с правилом аппликации (применения):

$\begin{split}f&{}:=& \lambda x.\;2\cdot x+1;\\f\;5\equiv f(5) & {} = {} & 2\cdot 5+1=11.\end{split}$

В первой строке вводится идентификатор f, которому присваивается безымянная функция, заданная с помощью $\lambda$ -абстракции. В последней строчке только что определённая функция f применяется к числу 5.

Числа, а также символы арифметических операций тоже можно определить через бестиповые функции одного переменного. Часто их записывают в базисе SKI (см. например, тут) — с помощью трёх функций-комбинаторов:

S a b c = a(c)(b(c))
K a b = a
I x = x

Помимо арифметики, посредством SKI формулируется булевская логика, ветвление, работа с парами значений и многое другое.

В бестиповом λ-исчислении не предусмотрены ссылки на ещё не определённые термы. Для реализации рекурсии используется специальный Y-комбинатор, поведение которого можно формально описать следующим образом (опять же, рекурсивно!):

$Y f = f\;(Y f)$

Из этой записи видно, что рекурсия, «повторение действий» выражается через идею самоприменения, упомянутую ранее. В SKI Y-комбинатор можно записать разными способами, например, так:

Y = S(K(SII))(S(S(KS)K)(K(SII)))

Y-комбинатор, действуя на некую функцию f возвращает значение p = Y f, которое эта функция уже изменить не сможет: f p = p. В математике такое значение называется неподвижной точкой (fixed point) отображения f. Мы рассмотрим это понятие далее.

Теперь же добавим в $\lambda$ -исчисление типы. В просто-типизированной системе $\lambda_{\rightarrow}$ у каждого терма должен быть определён его тип. И оказывается, что теперь уже не получится записать Y-комбинатор — в $\lambda_{\rightarrow}$ вообще никакое выражение, способное привести к незавершающемуся вычислению, невозможно типизировать исключительно средствами простых типов! (Напоминаю, что $\lambda$ -комбинаторы не могут содержать в теле свободные переменные.)

Система $\lambda_2$ , в которой появляются обобщённые функции, также не способна решить проблему полноты $\lambda$ -исчисления. Но решение уже было представлено выше, когда речь шла о частично определённых рекурсивных функциях — достаточно просто к квантору $\lambda$ добавить новый квантор $\mu$ действующий для функций, чьи области определения и значений совпадают:

$\begin{split}\mu y. f(y) \in \{y,\; f(y)=y\}\; &- \text{неподвижная точка функции $f$}\end{split}$

Теперь любую частично определённую рекурсивную функцию можно записать с помощью нового квантора $\mu$ . В $\lambda$ -исчислении он вводится аксиоматически, не подразумевая какой-либо «реализации». Однако в программировании требуется именно «функция высокого порядка», комбинатор неподвижной точки вида $Y f = \mu x.f(x)$ . Посмотрим, как можно реализовать его в Scala.

Реализация комбинатора неподвижной точки

Сперва рассмотрим объявление следующей функции:

def fix[A]: (A => A) => A

Как можно её реализовать? Про тип A мы знаем примерно ничего, и в теле точно не будут доступны его значения. Можно, конечно, оборвать вычисления, бросив исключение, но это не наш путь)).

Первое решение самое простое — используем «ссылку на себя»:

def fix[A]
  : (A => A) => A
  = f        => f(fix(f))

Возможно, такого ответа будет даже достаточно на собеседованиях. Однако, для любой переданной на вход функции такой алгоритм приведёт к бесконечной рекурсии (которая завершится Stack Overflow). Всё дело в том, что Scala, как и большинство других языков программирования, реализует «жадную» модель вычислений — выражения, передаваемые как аргументы, вычисляются предварительно независимо от того, будут ли эти значения использованы в теле функции.

Чтобы сделать вычисление выражения fix(f) ленивым, f должна принимать на вход другую функцию — тогда уже f будет принимать решения, вычислять ли эту функцию-аргумент или нет. Но при этом должна сохраниться исходная сигнатура fix:

def fixf[A, B]
  : ((A => B) => (A => B)) => (A => B)           // (F => F) => F,  где F = A => B
  = f                      => f(a => fixf(f)(a)) // λ-выражение необходимо для "ленивости"

Здесь тип аргумента f немного усложнился: (A => B) => (A => B). На вход f принимает функцию того же типа, что и возвращает. То есть, чтобы получить на выходе функцию A => B нужно передать на вход… по сути, её же! И fixf как раз замыкает эту функцию саму на себя. Вот пример использования такой реализации для вычисления членов последовательности Фибоначчи:

type Int3 = (Int, Int, Int)
def fib: (Int3 => Int) => (Int3 => Int) =
  self => { case (n, a, b) => n match
    case 0 => a
    case 1 => b
    case _ => self(n-1, b, a + b)
  }

def fibonacci(n: Int) = fixf(fib)(n, 0, 1) // 0, 1, 1, 2, 3, 5, 8, 13, ...

В реализации fib просматривается преимущество новой сигнатуры — «обратную ссылку» self можно вызывать столько раз, сколько потребуется.

Есть ли способ как-то ещё перехитрить систему и реализовать fix без «ссылки на себя»? Можно, например, сделать так:

def fix[A]: (A => A) => A =
  f => {
    val seflF =
      [Z, X, Y] => (z: Z) => f((
        (a: X) => z.asInstanceOf[Z => (X => Y)](z)(a)
      ).asInstanceOf[A])
      
    f(seflF(seflF))
  }

Последний вызов asInstanceOf утверждает, что $Y^X \cong A$ , и нужен лишь для достижения простой сигнатуры fix: [A] => (A => A) => A. От этого вызова можно избавиться, упростив код, но перейдя к чуть более сложной сигнатуре [X, Y] => ((X => Y) => (X => Y)) => (X => Y). В то же время первый вызов asInstanceOf с ноги проламывает статическую типизацию, объявляя, что $Z \cong \left(Y^X\right)^Z \cong A^Z$ .

Здесь просматривается аналогия с бестиповым $\lambda$ -исчислением, где любой терм условно имеет тип

type F = F => F // В Scala не скомилируется!

Именно такая рекурсивная природа «типов» термов бестипового $\lambda$ -исчислением позволяет успешно реализовать там Y-комбинатор безо всяких костылей. Более того, оказывается, что не используя «ссылки на себя» правильно типизировать рекурсивные функции можно только с помощью рекурсивных типов.

Больше деталей можно найти здесь:

Промежуточный итог

Среди чистых функций встречаются частично-рекурсивные, которые для некоторых входящих параметров могут зациклиться и не завершиться.
Современная архитектура ЭВМ определяет два основных способа (помимо goto) реализации повторения действий в языках программирования — циклы и рекурсивный вызов подпрограмм.
Любые циклы могут быть переписаны через рекурсию и наоборот.
Рекурсивные вызовы упираются в ограничения стека, но любую рекурсию всегда можно переписать в «хвостовой» форме, которую умеют оптимизировать многие компиляторы.
Рекурсию привычнее всего организовывать, ссылаясь на ещё неопределённые функции (в т.ч. на саму себя);
Но «ссылки вперёд», в частности, косвенная рекурсия, размазывают повторение действий по коду, их нет в λ-исчислении и поддерживаются они не везде (в следующей части будут использоваться псевдонимы типов, для которых подобная рекурсия запрещена).
Взамен в λ-исчисление добавляется комбинатор неподвижной точки — любую рекурсию и циклы можно убрать из кода, перенеся концепцию повторения действий в Y-комбинаторы.
Были рассмотрены некоторые способы реализации и использования Y-комбинатора в Scala.