Y Combinator на Python

Y Combinator у функциональных программистов не менее священная корова, нежели монады (которые моноиды в категории эндофункторов), и метациклические интерпретаторы. Сейчас мы посмотрим, что у этой коровы внутри, с помощью лекций американского профессора Matt Might.

Начнём, как водится, издалека.

Лямбда.

Лямбда — это нотация для записи анонимных функций.

Мы можем задавать именованные функции:

def f(x):
return x + 1
f(11)

а можем и анонимные (если конечно язык программирования позволяет):

lambda x: x+1

Анонимную функцию мы можем присвоить переменной, и потом уже вызвать:

f = lambda x: x+1
f(11)

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

Лямбда-исчисления — это математическая теория, которую Алонзо Чёрч придумал в 1920-х годах для функционального описания логических выражений. В лямбда-исчислении, говоря языком программистов, задействованы лямбды (анонимные функции), переменные и аппликации функций. Все значения в этом языке — исключительно функции.
Математически доказано, что это минимально возможный универсальный язык программирования относительно аппликативных функций.

Лямбда-программирование.

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

Во-первых, нам потребуется «пустая» функция-значение:

VOID = lambda void: void

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

Если аргумент вообще задавать не надо, можем использовать «пустую функцию»:

f(VOID)

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

Например, есть лямбда-функция с двумя параметрами:

sum = lambda x, y: x + y

Вызывается она так:

sum(2,3)

А вот каррированная запись:

sum = lambda x: lambda y: x + y

Функция сразу не вычисляется, а возвращает функцию, которая получает второй аргумент и уже считает результат.

sum(2)(3)

далее — условный формализм МакКарти

Поделиться статьей ...Share on Facebook0Share on Google+0Tweet about this on TwitterShare on LinkedIn0Share on VKPrint this page

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *