Как сделать рекурсию (базовый случай)

Рекурсия — один из самых мощных инструментов для выражения вычислений над, возможно, бесконечным набором объектов в конечном выражении. В этой статье мы рассмотрим кажущуюся парадоксальной идею рекурсии и то, как мы можем реализовать рекурсивный механизм, используя эту идею.

Парадокс Карри

Начнем с простого утверждения: Если это утверждение верно, то 1 + 1 = кошка. На первый взгляд это кажется очевидным абсурдом, ведь все мы знаем, что 1+1=кот не имеет никакого смысла. Следовательно, само утверждение не должно быть истинным. Но при тщательном рассмотрении логики, если мы собираемся использовать формальную систему, чтобы попытаться опровергнуть 1 + 1 = кошка, возникает нечто неожиданное.

Чтобы немного упростить процесс рассуждений, мы можем использовать обозначение X -> Y для представления нашего утверждения. Здесь X — это предположение (которое является рассматриваемым утверждением), Y — это вывод (1 + 1 = кошка), а стрелка -› обозначает отношение «если… то…» между X и Y.

Начнем с того, что запишем X = X -> Y, то есть утверждение, которое у нас есть, если это утверждение верно, то 1 + 1 = кот. По закону тождества имеем X -> X, то есть все доказывает себя (тавтология). Это довольно интуитивно, если подумать, так как сказать что-то вроде Если завтра будет дождь, то завтра будет дождь — это, ну, черт. Заменив правую часть X -> X на X = X-›Y, мы получим X -> (X -> Y).

Еще раз, по закону сокращения, X -> (X -> Y) это просто X -> Y . Это также несколько интуитивно понятно, поскольку повторное использование предпосылки равнозначно использованию предпосылки только один раз. Например, можно сказать что-то вроде Если завтра пойдет дождь, то (Если завтра пойдет дождь, то завтра пойдет дождь). Очевидно, это странное предложение, поскольку в нашем естественном языке нет хорошего способа выразить вложенную логику. Однако это было бы равносильно высказыванию Если завтра будет дождь, то завтра будет дождь. Если вы все еще не уверены в этом, вы можете сравнить таблицы истинности обоих этих предложений и убедиться, что они действительно логически эквивалентны.

X -> Y — это просто X в соответствии с эквивалентностью X = X -> Д. Поскольку мы получили X, заменив его на X -> Y, что, в свою очередь, эквивалентно ряду истинные утверждения, полученные по законам логики (X -> X = X -> (X -> Y) = X -> Y = X), мы можем утверждать, что X также верно. Наконец, вернемся к нашему исходному утверждению, объединив тот факт, что X верно, и X -> Y , мы приходим к выводу, что Y верно. Следовательно, 1 + 1 = кошка…

Подождите минуту…

Парадокс возникает из-за, казалось бы, безобидной логической эквивалентности X = X -> Y. Вопрос в том, что такое X? В таком случае, к чему именно относится «это утверждение» в нашем предложении «Если это утверждение верно, то 1 + 1 = кошка»? Как работает X = X -> Y (важно отметить, что наше обозначение «=» здесь означает эквивалентность, а не присваивание)? Разве это не приведет к бесконечному циклу, в котором вы всегда можете заменить X на X -> Y с самим X -> Y?

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

Лямбда-исчисление

Несмотря на свое загадочное название и, возможно, недавний вводящий в заблуждение ребрендинг AWS Lambda, лямбда-исчисление просто направлено на создание набора обозначений или правил для работы с функцией, особенно с функцией без имени.

В компьютерных науках есть только две сложные вещи: инвалидация кеша и присвоение имен вещам.

— Фил Карлтон

Лямбда-исчисление решает и то, и другое: 1. инвалидации кеша нет, если нечего кешировать (если все ваши функции чистые, нет состояния для кеширования) 2. имени тоже нет!

Правила грамматики в лямбда-выражениях элегантно просты — у вас есть выражение, и вы привязываете выражение к некоторым переменным с помощью лямбда-оператора Ⲗ. Возьмем в качестве примера линейную функцию f(x)= x + 2. Вы должны записать ее как Ⲗx [x + 2]. Чему равно значение этой функции при x = 2? В лямбда-исчислении этот вопрос можно представить как (Ⲗx [x + 2])(2).

Чтобы вычислить значение (Ⲗx [x + 2])(2), нужно просто подставить значения для замены переменных в выражении (хотя в этом есть некоторые нюансы) . (Ⲗx [x + 2])(2) = 2 + 2 (подставьте 2 вместо x) = 4

Мы также можем применить лямбда-выражение к другому лямбда-выражению, этому выражению (Ⲗy [y — 1])((Ⲗx [x + 2])(2) ) можно разбить на две части: слева у нас Ⲗy [y — 1], а справа у нас есть (Ⲗx [x + 2])(2). Еще раз, чтобы упростить это выражение, мы снова подставим значение y в y — 1, но в этом случае значение y — это другая лямбда (Ⲗx [x + 2] )(2), вычисление которого мы только что показали.

Это не что иное, как сказать: «Возьмите вывод x + 2, используя x = 2, и используйте его в качестве входных данных для y — 1». Формальным способом лямбда мы бы вычислили (Ⲗy [y — 1])((Ⲗx [x + 2])(2)) следующим образом:

(Ⲗ y [y — 1])((Ⲗ x [x + 2])(2))

= (Ⲗy [y — 1])(2 + 2), замените x на x + 2 на 2

= (Ⲗy [y — 1])(4), вычислить 2 + 2

= 4–1, замените y на y — 1 на 4

= 3

Быстрая математика!

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

Комбинатор Y

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

Ответ положительный, и способ реализации рекурсии в лямбда-исчислении лежит в парадоксе Карри. Рекурсия, по своей сути, является формой произвольной и, возможно, бесконечной самореференции.

Факториал — это классический пример рекурсии, в Python вы можете реализовать его следующим образом:

def factorial(n):
  if n == 0:
    return 1
  return n * factorial(n - 1)

Когда вы вызываете factorial(3), он порождает еще один вызов самого себя, используя 2 в качестве параметра, который, в свою очередь, порождает больше вызовов самого себя.

Комбинатор Y — это специальное выражение в лямбда-исчислении, Y = Ⲗf[(Ⲗx[f( xx)])(Ⲗx[f(xx)])]. Похоже, что кто-то просто набросал кучу случайных символов и окружил их несколькими парами круглых и квадратных скобок.

Итак, давайте посмотрим, что происходит, когда комбинатор Y применяется к чему-либо, скажем, к произвольному входу X. Давайте вычислим Y(X):

Y(X)

= (Ⲗf[(Ⲗx[f(xx)])(Ⲗx[f(xx)])])(X ), замените Y его выражением

= (Ⲗx[X(xx)])(Ⲗx[X(xx)]), замените f в (Ⲗx[ f(xx)])(Ⲗx[f(xx)]) с X

= X(Ⲗx[X(xx)])(Ⲗx[X(xx)]), замените x в X(xx) на Ⲗх[Х(хх)]

= X (X (Ⲗx[X(xx)])(Ⲗx[X(xx)])), заменить x в X(xx) на Ⲗx[X(xx)] еще раз

…

Я предлагаю записать это и фактически вставить значения вручную, если вы видите это впервые. Но если вы все еще следите за этим пунктом, вы, возможно, заметили довольно любопытное явление — уменьшение (Ⲗx[X(xx)])(Ⲗx[X (xx)]) возвращает нам исходный ввод X и себя, который есть X и он сам, который есть X и он сам, который есть X и он сам, …

И именно так мы достигаем рекурсии в лямбда-исчислении! Если мы хотим, чтобы функция вызывала сама себя, мы просто применяем к ней комбинатор Y. В Python мы можем реализовать комбинатор Y следующим образом:

Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))

Наконец, мы можем написать однострочную программу, которая будет печатать «Ну вот опять!» бесконечно, используя комбинатор Y.

Y((lambda : print("Here we go again!"))())

Бесконечность не предел

Если вы попытаетесь запустить указанную выше программу, вы, скорее всего, получите сообщение об ошибке RecursionError: превышена максимальная глубина рекурсии. В конце концов, нам по-прежнему нужен способ контролировать, сколько раз функция может рекурсивно вызывать себя. Однако это выходит за рамки данной статьи. Если вам интересно узнать больше о лямбда-исчислении, вот замечательный доклад Кевлина Хенни на YouTube и несколько полезных материалов.