Постигаем Y-комбинатор с помощью Elixir
В данной статье в общем смысле рассматривается само понятие Y-комбинатора и его получение на Elixir с помощью анонимных функций. Статья определённо не из лёгких, но, надеюсь, это никак не отразится на её интересности.
Зачем вам всё это?
Почему так важно знать о Y-комбинаторе? Честно говоря, это имеет значение лишь для продвинутых разработчиков. Преимущества от умения работать с Y-комбинатором в обычной веб-разработке практически незаметны.
Как бы то ни было, Y-комбинатор — интереснейшее явление IT-мира.
В самом простом понимании Y-комбинатор позволяет определять рекурсивные функции в лямбда-исчислении — там, где они изначально не поддерживаются. То, как он справляется со своей задачей, — невероятно красивое и самое разумное из всех решений, которые я когда-либо встречал.
Для меня Y-комбинатор — нечто сродни множеству Мандельброта или игре «Жизнь». Нечто, чем можно любоваться и восхищаться.
Y-комбинатор: начало
Начнём знакомство с Y-комбинатором с создания рекурсивной функции без использования рекурсии.
Воспользуемся классическим подходом:
def length([]), do: 0
def length([h|t]), do: 1 + length(t)
Функция length, объявленная как анонимная, вычисляет длину списка:
length([]) # 0
length([1]) # 1
length([1, 1]) # 2 и т. д. ...
Если функции передать пустой список, то она возвратит нулевое значение. В противном случае возвращается 1 плюс длина хвоста списка. Такой тип рекурсивного определения возможен благодаря использованию def и defp при задании функций, вследствие чего Elixir «разрешает» функциям осуществлять прямые вызовы самих себя.
Но что если попробовать задать рекурсивную анонимную функцию?
length = fn
[] -> 0
[h|t] -> 1 + length.(t)
end
Привязываем length к анонимной функции, в которой вызываем ту же length, создавая рекурсию. Поскольку функция length не находится в скоупе, возникает следующая ошибка компиляции:
** (CompileError) iex:9: undefined function length/0
(stdlib) lists.erl:1354: :lists.mapfoldl/3
(stdlib) lists.erl:1355: :lists.mapfoldl/3
Возможно ли вообще создать рекурсивную анонимную функцию? Создать рекурсивную функцию, при том, что ссылаться прямо на неё нельзя?
Да! Вот она, мощь Y-комбинатора!
Навстречу неизведанному
Прежде чем перейти к самому интересному, сделаем небольшое отступление и кое-что проясним. Несмотря на то, что рекурсивный вызов анонимной функции length не работает, часть функции всё же написана корректно.
Для наглядности вышесказанного уберём рекурсию из тела функции:
length = fn
[] -> 0
[h|t] -> 1 + (fn _ -> raise "oops" end).(t)
end
Очевидно, можно вычислить длину пустого списка и без использования рекурсии:
length.([]) # 0
length.([1]) # упс...
Можно обработать и список единичной длины, заменив функцию обработки исключений на точную копию функции length:
length = fn
[] -> 0
[h|t] -> 1 + (fn
[] -> 0
[h|t] -> 1 + (fn _ -> raise "oops" end).(t)
end).(t)
end
Теперь мы можем вычислить длину пустого списка и списка с одним элементом, но при большем количестве элементов возникает коллапс:
length.([]) # 0
length.([1]) # 1
length.([1, 2]) # упс...
Можно до бесконечности продолжать «обучать» функцию находить длину более объемных списков, прописывая одни и те же строки для каждого отдельного случая:
length = fn
[] -> 0
[h|t] -> 1 + (fn
[] -> 0
[h|t] -> 1 + (fn
[] -> 0
[h|t] -> 1 + (
...
).(t)
end).(t)
end).(t)
end
Схема рабочая, но совершенно безграмотная. А что если список будет состоять из 1000 элементов? Строить цепочку из огромного количества одинаковых функций?
Кроме того, при таком способе реализации функция всегда будет иметь верхнюю границу, и при её нарушении неизбежно возникнет ошибка.
Нужно другое решение.
Don’t Repeat Yourself
Если присмотреться, то можно заметить, что предыдущий пример пестрит повторами. На каждом уровне такой рекурсии происходит задание анонимной функции, очень похожей на изначальную функцию length.
Каждый уровень идентичен предыдущему, за исключением вызываемой функции: ещё одна функция типа length, либо функция обработки исключений в самом конце.
Но ведь можно избежать повторений в коде, определив функцию, которая сама бы создавала каждый новый уровень стека length. Новая функция make_length принимает в качестве аргумента изменяющийся на каждом уровне фрагмент кода и следующую по очереди функцию:
make_length = fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end
Теперь можем воспользоваться функцией make_length, чтобы вычислить длину пустого списка:
make_length.(fn _ -> raise "oops" end)
Аналогично для списков нулевой и единичной длины:
make_length.(make_length.(fn _ -> raise "oops" end))
Это работает, ведь мы создаём функцию для пустого списка и передаём функции make_length, которая оборачивает всё это в ещё одну length-подобную функцию make_length.
Можно сделать код чуть приятнее с помощью пайп-операторов:
(fn _ -> raise "oops" end)
|> (make_length).()
|> (make_length).()
Получается, теперь можно без привязок задать функцию length анонимно и вычислить длину списков, содержащих до трех элементов:
(fn
make_length ->
(fn _ -> raise "oops" end)
|> (make_length).() # support for length 1
|> (make_length).() # support for length 2
|> (make_length).() # support for length 3
end).(fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end)
Вот это уже интересно!
По сравнению с первой реализацией мы смогли избавиться от большей части повторений, но проблема ограниченного числа рекурсий осталась нерешённой.
По кирпичику за раз
На данный момент существует необходимость заранее определять максимально возможную длину списка.
Каждый новый вызов функции make_length добавляет новый слой в растущий стек. Но если список окажется слишком длинным, произойдет вызов функции обработки исключений, и подсчёт длины списка застопорится.
Чтобы довести дело до ума, нужно хорошенько поразмыслить о том, что вообще происходит в коде…
При каждом вызове нашей length-подобной функции принимается решение: нужна ли рекурсия. Если да, то вызывается функция length, привязанная к её замыканию, если нет, то возвращается значение, которое затем помещается в стек вызовов.
Проблема в том, что функция length может указывать на функцию обработки исключений.
Вместо возникновения ошибки при достижении последней функции в стеке хорошо бы добавить ещё один слой функции make_length и вызвать её. На деле, в стеке нам нужны лишь две функции: текущая и следующая.
Каждый слой рекурсии создаётся передачей функции make_length самой себе. Упростим создание стека: убрерём функцию обработки ошибок и просто добавим следующий слой:
(fn
make_length ->
make_length.(make_length) # Add another layer
end).(fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end)
Теперь можно даже переименовать аргумент length во второй анонимной функции, чтобы make_length сообщала нам, что именно в неё передаётся:
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length -> # We're being passed make_length
fn
[] -> 0
[h|t] -> 1 + make_length.(t)
end
end)
Но всё не так просто.
Попытки передать хвост списка t функции make_length не имеют никакого смысла. Функция make_length в качестве аргумента ожидает получить функцию, а возвращает функцию, которая на входе ожидает получить список.
Что же можно передать make_length, чтобы на выходе получить ещё один слой? Подождите, помнится, make_length полностью дублирует тело нашей второй анонимной функции:
(fn
make_length ->
fn
[] -> 0
[h|t] -> 1 + make_length.(t)
end
end)
Так может, передать make_length саму себя? Точно!
Передавая make_length самой make_length, мы получим новый слой length-подобной функции, которая в качестве аргумента принимает список:
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length ->
fn
[] -> 0
[h|t] -> 1 + (make_length.(make_length)).(t)
end
end)
Полученный слой имеет доступ к make_length, и, если понадобится рекурсия, ничего больше не препятствует создать и привести в действие новый слой length. Теперь не нужно заранее продумывать, какой высоты будет наша башня из функций length. Мы можем строить её постепенно, по одному кирпичику!
Как это прекрасно… Вы ещё не устали?
«Каждое поколение будет и сосудом, и его содержимым — эхом самовоспроизводящейся реверберации». — Тед Чан, «История твоей жизни»
Возвращаемся к функции length
Теперь наша реализация полностью функциональна. Мы можем вычислить длину списка любого размера:
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length ->
fn
[] -> 0
[h|t] -> 1 + (make_length.(make_length)).(t)
end
end).([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...])
Единственная проблема — это то, что мы отошли от изначального представления функции:
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
Мы модифицировали её таким образом, чтобы она содержала некие специфические для реализации вызовы make_length:
fn
[] -> 0
[h|t] -> 1 + (make_length.(make_length)).(t)
end
Если бы можно было вернуть функции length прежний вид, теоретически, мы могли бы «вынести её за скобки» и создать общую формулу, которая позволяла бы превращать любую функцию в рекурсивную без лишних движений.
Начнём с того фрагмента кода, где length((make_length.(make_length))) превращается в отдельную функцию:
fn
t ->
(make_length.(make_length)).(t)
end
Данная функция получает t в качестве аргумента и передаёт его следующему слою length, как только он создаётся.
Результат этой функции — сама length! Можно прописать ещё одно замыкание, которое принимало бы length в качестве аргумента и передавало бы в неё нашу новую функцию. Новая реализация получилась немного длиннее, но зато мы вернулись к изначальной функции length:
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length ->
(fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end).(fn
t ->
(make_length.(make_length)).(t)
end)
end)
Возрождённая функция length нигде не ссылается на make_length, а значит, ничего не мешает выпутать её из этого клубка анонимных функций.
Обернём весь блок в ещё одно замыкание, принимающее функцию length как аргумент:
(fn
length ->
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length ->
length.(fn
t ->
(make_length.(make_length)).(t)
end)
end)
end).(fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end)
Вынесем «общий множитель» length и приведём код в более традиционный, хотя и гораздо менее читабельный, вид:
y = fn
f ->
(fn
x ->
x.(x)
end).(fn
x ->
f.(fn
t ->
(x.(x)).(t)
end)
end)
end
Самое интересное здесь то, что полученная функция y сможет сделать абсолютно любую функцию рекурсивной! Вот, к примеру, рекурсивная функция для нахождения n-ого члена последовательности Фибоначчи:
y.(fn
fib ->
fn
0 -> 0
1 -> 1
n -> fib.(n-1) + fib.(n - 2)
end
end)
Как вы, наверное, уже догадались, то, что у нас получилось, имеет название. И это тот самый Y-комбинатор! С моей точки зрения, Y-комбинатор — одна из самых красивых структур во всей IT-вселенной.
Выводы и дополнительные материалы
Надеюсь, данная статья помогла вам разобраться с Y-комбинатором и показала всю его рекурсивную мощь.
Честно говоря, мне самому до сих пор не удаётся до конца в нём разобраться. Мне понятен порядок действий для его создания, но как только я сталкиваюсь лицом к лицу c присущей ему системой лямбда-исчисления, я не способен коротко и ясно объяснить, что он из себя представляет:
λf. (λx. f (x x))(λx. f (x x))
По-моему, это греческий.
Если у вас есть желание копнуть глубже по этой теме, я настоятельно рекомендую обратить внимание на книгу «The Little Schemer» Даниэля Фридмана и Мэттиаса Феллейсена. Это то, что позволило мне увидеть всю красоту Y-комбинатора и поразмыслить над другими не менее занимательными идеями. Рекомендую. Настоятельно.
Если книги не по вашей части, то можете обогатить свои знания при помощи вот этого краткого видео-введения в мир Y-комбинатора от Computerphile и этой довольно-таки исчерпывающей статьи.