День добрый, сегодня вторая часть перевода статьи `On Recursion, Continuations and Trampolines`. Для тех кто пропустил, первая часть, в которой рассмотрели чем хвостовая рекурсия отличается от обычной.
В этой части речь пойдет о продолжениях и основанном на них стиле программирования. Продолжаем погружение.
___________________________________________________________________________________
Продолжения и стиль программирования
Продолжения - крутой концепт, существующий с первых дней функционального программирования. Есть куча информации о продолжениях. Моя скромная попытка их объяснения - всего лишь начало! Если вас заинтересует, обязательно погуглите дополнительную информацию.
Предположим у нас есть следующее выражение:
2 * (3 + 4)
Один из способов вычисления:
- вычислить `значение` = 3 + 4
- затем 2 * `значение` предыдущего этапа
Мы можем сказать, что `значение` + 100 - это продолжение 2 * (3 + 4). Может показаться немного абстрактным, давайте перепишем на Lisp-y синтаксис, чтобы перейти в плоскость программирования. Вот один из способов:
Теперь вызываем (expr) и получаем 14. Другой способ получить то же вычисление:
Мы представили продолжение как функцию, принимающую единственный аргумент - `значение`. Так же мы применяем абстрактную концепцию продолжения с apply-cont. Финальное продолжение end-cont получает результат всех вычислений и выводит его в консоль. Отметим как продолжения скомпозированы вместе: мы вызываем expr-cps, ожидающий продолжение. Мы используем make-double-cont конструктор, чтобы создать продолжение, удваивающее значение. Разберем, как это работает: оно уже знает, свое собственное продолжение и применяет (* 2 `значение`). По факту это просто синтаксический сахар, можно обойтись и без него.
Теперь посмотрим, как этот подход работает для более длинного выражения. Сохраним написанное ранее и добавим:
Что произошло в последнем примере?
- expr-cps было вызвано каким-то продолжением. Оно вычислило 3 + 4 и отправило результат в продолжение.
- Это продолжение прошло через удвоение и передало свой результат в следующее продолжение
- Следующее (plus 100) провело операцию `входное значение` + 100 и передало результат дальше
- Последнее продолжение end-cont вывело результат в консоль:114
Пока это все выглядит как мазохистское упражнение по выворачиванию стека (заметим, как скомпозированы продолжения - изнутри наружу), но скоро мы увидим смысл затеи. -cps суффикс для expr-cps означает "стиль основанный на продолжениях" или Continuation Passing Style (дальше будет использоваться CPS). Тот стиль написания кода, который мы видели только что (конвертация нормального кода в этот стиль и называется CPS-трансформацией или CPS-конверсией).
Вы должны начать улавливать смысл, после следующего наблюдения: все вызовы вычислений, выполненные в CPS выражениях находятся в хвосте. Что же это значит? Вот оригинальная функция, вычисляющая полное выражение
В хвостовом положении может быть только операция +. Обе операции * и внутреннее + не в хвостовой позиции. Однако, если вы внимательно изучите все выражения CPS подхода, будет понятно, что все вызовы операторов в хвостовой позиции. Их результаты были переданы через соответствующие продолжения без изменений и в этом случае мы не считаем продолжения как вызов функции. Эту прекрасную особенность CPS мы будем использовать очень скоро, но пока сделаем небольшое отступление в теорию.
Неограниченные и ограниченные продолжения
Формулировка end-cont, которую я использую в примере выше, может показаться вам странной. Функция просто выводит значение в консоль, но что если мы захотим делать с ним что-то еще? Странный print() - это трюк, чтобы эмулировать настоящее или неограниченное продолжение, в языке не поддерживающем его. Добавление продолжений - это не просто вызов ещё одной функции. Это передача контроля без надежды на его возвращение. Как корутина или longjump в C.
Неограниченные продолжения не возвращаются к вызывающему. Они выполняют поток вычислений, который идет только в одном направлении. Это выходит за рамки статьи, но когда неограниченные продолжения могут считаться значениями первого класса в языке - они становятся невероятно мощным инструментом, который позволяет воплотить практически любую концепцию контроля потока - исключения, треды, корутины и т.д. Для этого они периодически и используются в функциональных языках, где CPS-трансформация это один из шагов компиляции.
С удовольствием бы порассуждал об этой теме больше, но должен оставить на следующий раз. Если вас заинтересовало - погуглите и поэкспериментируйте с языком, поддерживающим настоящие продолжения. Например Scheme с его call/cc. Это весело и пугающе одновременно)
Хоть и большая часть языков не поддерживают настоящие продолжения, ограниченные продолжения - другое дело. Ограниченное продолжение - это просто функция, возвращающая что-то вызывающему. Мы так же можем использовать CPS, но должны четко осознавать реальность. Обращение к ограниченному продолжению - вызов функции, а значит стек будет расти.
По факту нам даже не нужно делать вид(apply-cont cont value), что наши операции отличаются от простого вызова (cont value), поэтому сейчас мы можем переписать наше CPS выражение более компактно:
Все еще выглядит немного странно, мы могли просто убрать (* 2 ` значение`) во внутренний вызов, но продолжим держать их отдельно, но это поможет нам в будущем.
Создаем хвостовой вызов с помощью CPS
В нашем арсенале появился новый инструмент и мы можем вернуться к некоторым Python функциям из начала статьи. Для факториала мы использовали дополнительный параметр, чтобы получить версию с хвостовым вызовом. Для Фибоначчи уже понадобилось 2. Для более нетривиальных примеров в принципе было сложно сориентироваться и понять, что происходит (вспомним сортировку слиянием). CPS трансформация уже здесь, чтобы помочь нам!
Похоже, что мы можем конвертировать любую функцию в функцию с хвостовым вызовом, вместо рекурсивной(прямой или непрямой), если будем следовать плану:
- Добавить в каждую функцию дополнительный параметр - cont.
- Если функция возвращает выражение, которое не содержит вызовов функций - отправляем его в продолжение.
- Если вызов функции происходит в хвостовой позиции, вызываем функцию с тем же продолжением - cont.
- Когда вызов функции происходит не в хвостовой позиции, вместо этого выполняем его в новом продолжении, которое дает название результату и продолжает выражение.
Звучит практически бессмысленно, нужны примеры. Первым разберем рекурсивный факториал:
Линия, отмеченная (1), отвечает за 2 шаг плана, а (2) за 4, т.к. вызов функции (fact_rec) находится в позиции операнда. Вот как мы трансформируем эту функцию в CPS:
С шагами 1-2 все достаточно просто, а вот к 4 нужно добавить немного объяснений. Т.к. вызов функции находится не в хвостовой позиции, мы извлекаем его и выполняем в новом продолжении. Это продолжение затем проходит через n * `значение` к оригинальному продолжению fact_cps. Уделите некоторое время, чтобы разобраться в том, что происходит в функции, вычислите факториал. Мы должны запустить функцию с end_contunuation, о котором уже говорили ранее:
Теперь сделаем так же с Фибоначчи. Здесь мы видим более сложный шаблон рекурсивной функции:
И опять 1-2 шаги достаточно просты. 4 шаг используется на линии (2), но дважды, т.к. у нас 2 вызова функции в позиции операнда. Сначала сделаем, как поступили с факториалом:
Все вызовы в fib_cps_partial в хвостовой позиции, но есть одна проблема. Продолжение, которое мы сделали из рекурсивного вызова само находится не в хвостовой позиции. Мы можем опять применить CPS трансформации и изменить выражение внутри lambda. Вот полностью измененное выражение:
И опять мы видим, что эта версия содержит только хвостовые вызовы. В противопоставление к преобразованиям, показанным в начале статьи - эта следует четкому рецепту. В принципе, это преобразование может быть выполнено автоматически даже компилятором или инструментом для трансформации исходного кода.
Чтобы убедиться, что наши знания полезны в более общих случаях, вернемся к сортировке-слиянием.У нас уже есть рекурсивная реализация (см перевод первой части статьи)с хитрой частью:
Но приведение к СPS виду будет не намного сложнее, чем трансформация Фибоначчи. Не будем заново повторять общие вещи и просто посмотрим на результат:
__________________________________________________________________________________________
На этом перевод второй части статьи закончен.
Вот мы уже вплотную подобрались к тому, как работать с этим всем богатством в Python и так ли это нам нужно? На мой взгляд, как концепцию, рекурсивный подход и CPS знать надо, а использовать те инструменты, которые больше подходят к ситуации и более читаемы. Мы же все-таки с людьми работаем)
Всем хороших выходных, не болейте.
