Ееей, дошли заключительной части) Сегодня разберем как же таки обойти рост стека при вызове рекурсивных функций, причем тут трамплины и так ли нужно все это в Python.
____________________________________________________________________________________
Как трамплины позволяют обойти рост стека?
Теперь мы готовы обсудить, зачем стоит помещать вызовы в хвостовую позицию, даже если наш язык не поддерживает TCO (оптимизацию хвостовой рекурсии). Инструмент, связывающий воедино все наши знания - трамплины.
Посмотрим, что нам говорит Википедия:
В некоторых Lisp-реализациях, трамплин - это цикл, который итеративно вызывает преобразованные функции. Программисты могут использовать трамплины, чтобы реализовать хвостовые вызовы в языках, ориентированных на стек.
Но что такое "преобразованная функция"?
Преобразователь (thunk) на жаргоне - какое-то выражение, обернутое в функцию без аргументов. Эта обертка задерживает исполнение выражения до момента вызова функции:
В примере мы сначала исполняем выражение, а затем обертываем его в преобразователь. В случае с Python мы используем просто lambda без аргументов. Сам по себе преобразователь - это всего лишь функция. Но когда мы его вызываем, срабатывает выполнение выражения. Преобразователи могут быть использованы, чтобы эмулировать ленивые вычисления, в языке, который изначально их не поддерживает (как Python / Clojure). В нашем случае преобразователь - главный инструмент для избегания переполнения стека.
Недостающая часть головоломки:
trampoline - функция. На вход она получает другую функцию и последовательность аргументов, на которую эту функцию нужно применить. По сути то же отложенное исполнение. Но есть ещё одна деталь - если функция возвращает вызываемый объект, трамплин предполагает, что это преобразователь и вызывает его. Так продолжается до тех пор, пока функция не возвращает какой-то не вызываемый объект.
Помните, как я рассказывал о неограниченных продолжениях и том, что в "обычных" языках вроде Python мы просто симулируем продолжения между вызовами функций? Трамплины позволяют сделать эту идею жизнеспособной без переполнения стека. Давайте разберем как. Как пример возьмем CPS (основанный на продолжениях стиль) версию факториала, которую мы опять немного преобразуем. Теперь функция возвращает преобразователь:
Трансформация в этом случае достаточно прямолинейна: мы просто оборачиваем хвостовой вызов в lambda функцию без аргументов. Чтобы правильно её использовать, мы должны теперь применить трамплин. Вот так будет выглядеть вычисление факториала 6:
А теперь откровение! Если вы сможете отследить выполнение этого трамплина, вы заметите - стек не растет! Вместо вызова самой себя fact_cps_thunked возвращает преобразователь, так что вызов выполняется трамплином. Если мы будем следить за вызовами рекурсивной функции, то получи что-то вроде:
Версия с преобразователем будет отличаться:
Помните, в прошлых частях мы пересекли максимальную глубину стека, вызвав fact_rec(1000)? С преобразованной версией таких проблем нет:
Чтобы лучше понять как использовать преобразователи и трамплины, вы можете посмотреть полный пример с числом Фибоначчи (<- ссылка на гитхаб автора статьи).
Надеюсь теперь отдельные кусочки пазла сошлись. С помощью комбинирования продолжений и трамплинов мы можем взять произвольную рекурсивную функцию и конвертировать её в функцию с хвостовой рекурсией, потребляющую ограниченную память стека. И все это в языке без автоматической оптимизации хвостовой рекурсии.
Трамплины и множественная рекурсия
Чтобы понять, насколько это все реалистично, вернемся к теме множественной рекурсии. Как уже упоминалось ранее, Clojure не поддерживает оптимизацию хвостовой рекурсии хоть это и Lisp. Чтобы обойти этот момент, рекомендуемый стиль программирования на Clojure - явные циклы, которые дают возможность легко и эффективно исполнять хвостовые вызовы. Но это не позволяет решить проблему множественной или косвенной рекурсии.
Вспомним глупый пример чет / нечет, на этот раз на Clojure:
В этом случае мы не справимся одними лишь циклами, но Clojure прямо из ядра предлагает нам реализацию трамплина! Вот преобразованная версия:
Исполняем:
Заметьте, насколько малы различия между версиями функций. Во многом благодаря крутому синтаксису анонимных функций, который предлагает Clojure. Преобразователь здесь выглядит как # (...).
Реализация трамплина в Clojure:
Назад в реальный мир
Описанные выше инструменты могут использоваться (и используются) как строительные блоки для компиляторов функциональных языков, но насколько они применимы в каждодневном программировании на языках вроде Python / Clojure?
ИМХО, ответ не очень, но они все еще стоят того, чтобы о них знали. Для Clojure например Rich Hickey нашел их достаточно значимыми, чтобы включить в язык. Т.к. в нем нет оптимизации хвостовой рекурсии, а итерирование хорошо только для прямой рекурсии, нужно было предоставить какие-то решения для множественной / косвенной рекурсии. Но как часто мы их используем?
Алгоритмы вроде сортировки слиянием или любые обходы деревьев скорее всего будут в порядке и с обычной рекурсией, т.к. поддерживаемая глубина более чем достаточна. Из-за логарифмического отношения глубины к общей величине вам потребуется всего около 30 повторений, чтобы обойти миллиард значений.
Тоже относится к анализу рекурсивным спуском. Однако стоит быть осторожным с некоторыми видами алгоритмов вроде обхода графов.
Другое важное применение - конечные автоматы, которые могут быть выражены через косвенные рекурсивные вызовы для передачи состояний. Вот пример кода (<- гитхаб автора). Гвидо упоминал эту проблему в посте об оптимизации хвостовой рекурсии в Python и предложил пользоваться трамплинами, как одним из возможных решений.
Корутины и генераторы в Python, как альтернатива
В любом случае, я верю, что у Pytohn есть лучшие решения для подобных задач. У меня уже был материал о использовании корутин для моделирования конечных автоматов. С тех пор Python добавил много полезных возможностей.
В Python 3.5 для поддержки корутин было добавлено еще больше. Когда-нибудь я найду время написать и об этом.
Скорее всего мы не найдем большого количества кейсов, для применения CPS и трамплинов в Python сейчас. Но не смотря на их полезность я был заворожен и чувствую, что они смогли помочь понять как некоторые языки программирования работают под капотом.
___________________________________________________________________________________
Здесь я полностью согласен с автором. Использование рекурсии и трамплинов в Python гораздо сложнее, менее наглядно и зачастую выглядит хуже чем генераторы и корутины. Он просто под это не заточен. Но знать эти концепцию нужно, ведь на них выстраивается дорога в чарующий и пугающий мир функциональщины).
Больше моих переводов и материалов можно найти здесь.
Если вам понравился материал, буду признателен за подписку на блог.
#программирование #Python3 #Рекурсия #функциональное программирование
