Новичок в лямбда-исчислении? Я рекомендую прочитать Лямбда-исчисление в JavaScript, прежде чем продолжить!

Y Combinator - это функция высшего порядка с фиксированной точкой, используемая для реализации рекурсии на любом языке программирования, который не поддерживает ее изначально.
Она была введена математик и логик Haskell Curry в 1940-х годах и считается одной из самых красивых идей в программировании и логике.
Мы увидим, как реализовать этот удивительный фрагмент кода в 6 языки программирования:

  • JavaScript
  • Haskell
  • Java
  • Ракетка
  • Python
  • C

Оригинальный Y-комбинатор в лямбда-исчислении

Мы только что выразили одну из самых мощных концепций информатики менее чем 30 символами.
Как вы уже догадались, мы только что написали Y Абстракция.
Что такое его реальное применение?
Давайте воспользуемся типичным примером факториала.

Факториал числа n - это произведение всех положительных целых чисел от 0 до n.
Мы можем легко использовать рекурсию, чтобы найти факториал любого положительного целого числа (в псевдокоде):

Итак, давайте представим, что нам нужно вычислить факториал 3; приняв решение выше, мы будем выполнять нашу функцию следующим образом:

Как видите, мы вызываем функцию factorial внутри самой функции factorial. Это простой пример того, как работает рекурсия, и не каждый язык поддерживает такой стиль программирования!

А вот и Y Combinator. Начнем с реализации в JavaScript:

На самом деле это довольно просто! Как видите, это очень похоже на код, который мы написали выше с использованием нотации Lamba Calculus!
Теперь нам нужно реализовать нашу функцию, которая будет вычислять факториал заданного целого числа. :

Большой! Как видите, мы не берем целое число в качестве первого аргумента, а создаем функцию, которая возвращает анонимную функцию, которая принимает целое число в качестве единственного аргумента. Таким образом, мы параметризовали вызов f, который будет использоваться внутри нашей реализации Y.

Теперь давайте вызовем функцию factorial с помощью Y Combinator, который мы только что написали выше, и вот мы:

Теперь мы можем вызывать любую рекурсивную функцию внутри нашего Y Combinator, избегая исключений памяти времени выполнения!

Y Combinator в Haskell

Как видите, написать абстракцию Y-комбинатора в Haskell довольно просто, если вы исходите из нотации лямбда-исчисления!
Между прочим, этот код не будет компилироваться из-за (x x), который требует бесконечного типа.
По этой причине мы должны выбрать, хотим ли мы принять Небезопасное принуждение и сделать его работать, или изменить подход:

Использование небезопасного принуждения (небезопасно):

Принятие нерекурсивного решения (безопасно):

Для простоты мы будем использовать небезопасную версию, которую проще показать и объяснить. Давайте реализуем функцию факториала в Haskell!

Теперь мы можем вызвать факториальную функцию, используя ранее определенный Y Combinator:

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

Y Combinator в Java

Я должен признать: я не эксперт по Java, и это на самом деле самый сложный фрагмент кода, который я когда-либо писал ... но он работает! И он показывает вам альтернативу классическому императивному / объектно-ориентированному подходу в Java.
Я не говорю, что вы должны использовать этот подход каждый раз, когда вам нужно решить проблему с использованием рекурсии в Java: вместо этого я твердо уверен, что приведенный выше пример показывает, насколько лямбда-исчисление может быть таким же полным, как машина Тьюринга, которая является основой императивных и объектно-ориентированных языков, таких как Java!

Y Combinator в ракетке

Реализация Racket в основном такая же, как и реализация Лямбда-исчисления! На самом деле они очень похожи, и этот язык показывает, насколько он близок к нотации лямбда-исчисления, которая лежит в основе любого языка программирования LISP!

Y-комбинатор в Python

Y Combinator в Python на самом деле легко реализовать, но он немного «запутан» из-за своего лямбда-синтаксиса. Принцип его работы очевиден, и разработчики, работающие с Python, наверняка поймут, как Y Combinator работает под капотом!

Комбинатор Y в C

Наверное, это была худшая идея в моей жизни. Тем не менее, довольно приятно видеть, как язык, который на 100% основан на машине Тьюринга, все еще может реализовать такую ​​абстрактную концепцию, полученную из лямбда-исчисления!

Решение Pure C даже близко не похоже на определение лямбда-исчисления, но выполняет ту же работу с выдающимися характеристиками!

Заключение

Как мы видели в примерах Java и C, концепции лямбда-исчисления все еще могут быть выражены на языках, которые были рождены с совершенно другим подходом к их ядру.
Лямбда-исчисление - удивительная тема. и стоит потратить некоторое время на изучение. Это действительно меняет сознание!