В этой статье рассматривается один из способов избавления от хвостовых вызовов: trampoline. Он работает так: перед хвостовым вызовом удаляется текущий фрейм исполнения из стека. Это исключает наращивание стека.
- Фреймы исполнения и стек
- Предотвращение наращивания стека
- Как работает trampoline
- Пример: факториал
- Зачем использовать trampoline
Фреймы исполнения и стек
Чтобы понять, почему может возникнуть необходимость удалить фрейм исполнения, давайте посмотрим, что происходит при вызове функции. Рантайм языка нуждается в определённом месте для хранения внутренней информации и локальных переменных, которые использует функция. Поэтому среда исполнения выделяет ячейку памяти в стеке. Затем рантайм передаёт контроль над функцией. Когда функция завершает работу, она выполняет возврат. Возврат сообщает рантайму о необходимости удалить фрейм исполнения из стека и вернуть контроль над функцией вызывающему коду.
Но что происходит, если функция не делает возврат немедленно? Что, если она вместо возврата вызывает другую функцию? В этом случае рантайм создаёт новый фрейм исполнения для этого вызова и добавляет его в стек поверх текущего фрейма. Если функция рекурсивно вызывает себя после завершения, каждый новый вызов добавляет в стек фрейм исполнения. Это быстро приводит к переполнению стека.
Предотвращение наращивания стека
Чтобы избежать этой проблемы, некоторые языки программирования гарантируют, что они перезагружают текущий фрейм исполнения каждый раз, когда функция выполняет хвостовой вызов. То есть когда функция вызывает другую функцию или сама себя и возвращает результат вызова этой функции, речь идёт о хвостовом вызове. В этом случае рантайм перезагружает фрейм исполнения текущей функции перед передачей контроля другой функции. Благодаря этому другая функция возвращает результат напрямую вызывающему коду. Этот процесс называют удалением хвостового вызова.
Но в языках, которые не выполняют удаление хвостового вызова, каждый вызов добавляет фрейм исполнения в стек. К таким языкам относится Python. Поэтому нам надо каким-то способом удалить фрейм из стека перед хвостовым вызовом.
Но как? Единственный очевидный способ — возврат к вызывающему коду. Чтобы это работало, вызывающий код должен быть готов помочь нам. Именно здесь на сцену выходит trampoline. Это отличный инструмент для предотвращения наращивания стека.
Как работает trampoline
Вот как работает trampoline:
- Вызывает функцию
fи делает её текущим вызывающим кодом. - Когда
fсобирается выполнить хвостовой вызов, то есть вызвать саму себя, trampoline возвращает инструкциюcall(f)(*args, **kwds). В результате рантайм удаляет текущий фрейм исполнения из стека и возвращает контроль trampoline, передавая инструкции. - Trampoline интерпретирует инструкции и вызывает
fснова, передавая ей аргументы и назначая ее текущим вызывающим кодом. - Этот процесс продолжается до тех пор, пока
fне возвращает итоговый результатz. В этот момент она возвращает новую инструкциюresult(z). Как и ранее, рантайм удаляет текущий фрейм исполнения и возвращает контроль trampoline. - Trampoline после интерпретации новой инструкции возвращает
zвызывающему коду. На этом работа trampoline завершается.
Теперь можно понять, откуда возникло название trampoline (батут или трамплин в переводе с английского). Когда функция использует return, чтобы удалить фрейм исполнения из стека, trampoline возвращает ей контроль с новыми аргументами.
Вот простая реализация. В первую очередь оформим инструкции для trampoline в виде троек. Представим call(f)(*args, **kwds) в виде тройки (f, args, kwds), а rezult(z) в виде тройки (None, z, None).
def call(f):
"""Говорим trampoline вызвать f с переданными аргументами"""
def g(*args, **kwds):
return f, args, kwds
return g
def result(value):
"""Говорим trampoline прекратить итерации и вернуть значение"""
return None, value, None
Теперь создадим декоратор, чтобы обернуть функцию с trampoline, которая будет интерпретировать инструкции, которые возвращает функция.
import functools
def with_trampoline(f):
"""Оборачиваем trampoline в функцию"""
@functools.wraps(f)
def g(*args, **kwds):
h = f
# trampoline
while h is not None:
h, args, kwds = h(*args, **kwds)
return args
return g
Заметьте, trampoline умещается в три строки:
while h is not None:
h, args, kwds = h(*args, **kwds)
return args
По сути, trampoline вызывает любые функции в h, пока эта функция не возвращает инструкцию result(z). В этот момент завершается цикл и возвращается z. Оригинальные рекурсивные хвостовые вызовы превратились в цикл while. А рекурсия превратилась в итеративный процесс.
Пример: факториал
Разберём использование trampoline на примере факториала.
def factorial(n):
if n < 2:
return 1
return n * factorial(n - 1)
Первый шаг: конвертируем рекурсивный вызов:
def factorial(n, acc=1):
if n < 2:
return acc
return factorial(n - 1, acc * n)
Теперь можно создать эквивалентную функцию, которая использует идиомы trampoline:
def trampoline_factorial(n, acc=1):
if n < 2:
return result(acc)
return call(trampoline_factorial)(n - 1, n * acc)
Обратите внимание на трансформацию return.
Теперь можно обернуть функцию с помощью trampoline, чтобы получить вызываемую версию.
factorial = with_trampoline(trampoline_factorial)
Возьмём такой вариант:
>>> factorial(5)
120
Чтобы понять, что на самом деле происходит, используйте визуализатор. В нём можно отследить работу оригинальной функции, функции с хвостовыми вызовами и функции с trampoline.
Зачем использовать trampoline
Как отмечалось выше, если вы не можете превратить рекурсивные вызовы функции в хвостовые вызовы, что необходимо сделать для использования trampoline, можно использовать Simple Method для конвертации рекурсии в итерацию. Это позволяет избавиться сразу от всех вызовов. Например, вот так работает Simple Method с функцией поиска факториала.
def factorial(n, acc=1):
while n > 1:
(n, acc) = (n - 1, acc * n)
return acc
Эта версия проще и эффективнее по сравнению с версией с trampoline. Почему бы всегда не использовать Simple Method?
Проблема в том, что Simple Method сложно использовать с функциями, которые выполняют хвостовые вызовы внутри циклов. Надо помнить, что в такой ситуации тело функции находится в цикле, что заменяет хвостовые вызовы инструкцией continue. Но если в функции уже есть собственные циклы, замена хвостового вызова в одном из них инструкцией continue перезапустит внутренний цикл вместо внешнего. В этом случае нужно добавлять условные флаги, чтобы убедиться, что запускается нужный цикл. Поэтому использование trampoline может быть предпочтительным.
Тем не менее автор оригинальной публикации практически никогда не использует trampoline. Функция с хвостовыми вызовами — это девять десятых пути к результату. Если автор проходит эту часть пути, он стремится использовать версию с итерациями.
Зачем, в таком случае, нужно понимать trampoline? Есть две причины. Первая: trampoline мало кто умеет использовать, поэтому знание этого инструмента будет полезным для вас. Вторая причина: trampoline — ступень на пути к более мощному и известному инструменту. Речь о выражениях в стиле передачи продолжений (continuation-passing-style, CPC). О них стоит поговорить в отдельной статье.
Адаптированный перевод статьи Tricks of the trade: Recursion to Iteration, Part 4: The Trampoline by Tom Moertel. Мнение автора оригинальной публикации может не совпадать с мнением администрации Хекслета.
