Оптимизирует ли Python хвостовую рекурсию?
У меня есть следующий кусок кода, который завершается с ошибкой:
RuntimeError: превышена максимальная глубина рекурсии
Я попытался переписать это, чтобы учесть оптимизацию хвостовой рекурсии (TCO). Я считаю, что этот код должен был быть успешным, если бы имелась ТШО.
def trisum(n, csum):
if n == 0:
return csum
else:
return trisum(n - 1, csum + n)
print(trisum(1000, 0))
Должен ли я заключить, что Python не выполняет никаких типов TCO, или мне просто нужно определить его по-другому?
8 ответов
Нет, и никогда не будет, так как Гвидо предпочитает иметь возможность получать правильные следы
http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html
http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html
Вы можете вручную исключить рекурсию с помощью такого преобразования
>>> def trisum(n, csum):
... while True: # change recursion to a while loop
... if n == 0:
... return csum
... n, csum = n - 1, csum + n # update parameters instead of tail recursion
>>> trisum(1000,0)
500500
Редактировать (2015-07-02): Со временем мой ответ стал довольно популярным, и, поскольку изначально он был скорее ссылкой, чем чем-либо еще, я решил занять некоторое время и переписать его полностью (однако первоначальный ответ может быть найденным в конце).
Редактирование (2015-07-12): Наконец-то я опубликовал модуль, выполняющий оптимизацию хвостового вызова (обрабатывая как стиль хвостовой рекурсии, так и стиль продолжения продолжения): https://github.com/baruchel/tco
Оптимизация хвостовой рекурсии в Python
Часто утверждается, что хвостовая рекурсия не подходит к питоническому способу кодирования и что не нужно заботиться о том, как встроить ее в цикл. Я не хочу спорить с этой точкой зрения; однако иногда мне нравится пытаться или реализовывать новые идеи как хвостовые рекурсивные функции, а не с помощью циклов по разным причинам (фокусируясь на идее, а не на процессе, имея на экране двадцать коротких функций одновременно, а не только три "питонические") функции, работающие в интерактивном сеансе вместо редактирования моего кода и т. д.).
Оптимизация хвостовой рекурсии в Python на самом деле довольно проста. Хотя говорят, что это невозможно или очень сложно, я думаю, что этого можно достичь с помощью элегантных, коротких и общих решений; Я даже думаю, что большинство из этих решений не используют функции Python иначе, чем должны. Чистые лямбда-выражения, работающие вместе со стандартными циклами, приводят к быстрым, эффективным и полностью используемым инструментам для реализации оптимизации хвостовой рекурсии.
Для личного удобства я написал небольшой модуль, реализующий такую оптимизацию двумя различными способами. Я хотел бы обсудить здесь две мои основные функции.
Чистый путь: модификация Y комбинатора
Y комбинатор хорошо известен; он позволяет использовать лямбда-функции рекурсивно, но сам по себе не позволяет встраивать рекурсивные вызовы в цикл. Лямбда-исчисление само по себе не может сделать такую вещь. Небольшое изменение в Y-комбинаторе, однако, может защитить рекурсивный вызов от фактической оценки. Таким образом, оценка может быть отложена.
Вот знаменитое выражение для Y комбинатора:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
С очень небольшим изменением я мог получить:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))
Вместо того, чтобы вызывать себя, функция f теперь возвращает функцию, выполняющую тот же самый вызов, но, поскольку она ее возвращает, оценку можно выполнить позже извне.
Мой код:
def bet(func):
b = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args))))(func)
def wrapper(*args):
out = b(*args)
while callable(out):
out = out()
return out
return wrapper
Функцию можно использовать следующим образом; Вот два примера с хвостовой рекурсивной версией факториала и Фибоначчи:
>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55
Очевидно, глубина рекурсии больше не является проблемой:
>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42
Это, конечно, единственная реальная цель функции.
С этой оптимизацией нельзя сделать только одно: ее нельзя использовать с хвостовой рекурсивной функцией, выполняющей оценку другой функции (это связано с тем, что все возвращаемые объекты с возможностью вызова обрабатываются как дальнейшие рекурсивные вызовы без различия). Поскольку мне обычно не нужна такая функция, я очень доволен приведенным выше кодом. Однако, чтобы предоставить более общий модуль, я подумал немного больше, чтобы найти обходной путь для этой проблемы (см. Следующий раздел).
Что касается скорости этого процесса (который, однако, не является реальной проблемой), то он довольно хорош; хвостовые рекурсивные функции даже оцениваются гораздо быстрее, чем в следующем коде с использованием более простых выражений:
def bet1(func):
def wrapper(*args):
out = func(lambda *x: lambda: x)(*args)
while callable(out):
out = func(lambda *x: lambda: x)(*out())
return out
return wrapper
Я думаю, что вычисление одного выражения, даже сложного, происходит намного быстрее, чем вычисление нескольких простых выражений, что имеет место во второй версии. Я не сохранил эту новую функцию в своем модуле и не вижу обстоятельств, где ее можно было бы использовать вместо "официальной".
Продолжение прохождения стиля с исключениями
Вот более общая функция; он способен обрабатывать все хвостовые рекурсивные функции, включая те, которые возвращают другие функции. Рекурсивные вызовы распознаются из других возвращаемых значений с использованием исключений. Это решение медленнее, чем предыдущее; более быстрый код, вероятно, можно было бы написать, используя некоторые специальные значения в качестве "флагов", обнаруживаемых в основном цикле, но мне не нравится идея использования специальных значений или внутренних ключевых слов. Существует некоторая забавная интерпретация использования исключений: если Python не любит хвост-рекурсивные вызовы, то должно возникать исключение, когда происходит хвост-рекурсивный вызов, и питонский способ будет заключаться в том, чтобы перехватить исключение, чтобы найти некоторый чистый решение, которое на самом деле то, что происходит здесь...
class _RecursiveCall(Exception):
def __init__(self, *args):
self.args = args
def _recursiveCallback(*args):
raise _RecursiveCall(*args)
def bet0(func):
def wrapper(*args):
while True:
try:
return func(_recursiveCallback)(*args)
except _RecursiveCall as e:
args = e.args
return wrapper
Теперь все функции могут быть использованы. В следующем примере f(n) оценивается для функции тождества для любого положительного значения n:
>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42
Конечно, можно утверждать, что исключения не предназначены для преднамеренного перенаправления интерпретатора (как своего рода goto заявление или, скорее, своего рода продолжение прохождения стиля), который я должен признать. Но, опять же, я нахожу забавной идею использования try с одной линией, являющейся return утверждение: мы пытаемся что-то вернуть (нормальное поведение), но мы не можем этого сделать из-за рекурсивного вызова (исключение).
Первоначальный ответ (2013-08-29).
Я написал очень маленький плагин для обработки хвостовой рекурсии. Вы можете найти его с моими объяснениями там: https://groups.google.com/forum/?hl=fr
Он может встроить лямбда-функцию, написанную в стиле хвостовой рекурсии, в другую функцию, которая будет оценивать ее как цикл.
Самая интересная особенность этой маленькой функции, по моему скромному мнению, состоит в том, что эта функция основана не на грязном программировании, а на простом лямбда-исчислении: поведение функции меняется на другое при вставке в другую лямбда-функцию, которая выглядит очень похоже на Y-комбинатор.
С уважением.
Слово Гвидо находится по адресу http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html
Недавно я опубликовал в своем блоге Python History статью о происхождении функциональных возможностей Python. Дополнительное замечание о том, что не поддерживается удаление хвостовой рекурсии (TRE), сразу вызвало несколько комментариев о том, как жаль, что Python этого не делает, включая ссылки на последние записи в блогах других, пытающихся "доказать", что TRE можно добавить в Python. без труда. Итак, позвольте мне защитить свою позицию (то есть, я не хочу, чтобы TRE на языке). Если вам нужен короткий ответ, он просто не пифоничен. Вот длинный ответ:
CPython не поддерживает и, вероятно, никогда не будет поддерживать оптимизацию хвостовых вызовов на основе высказываний Гвидо по этому вопросу. Я слышал аргументы, что это затрудняет отладку из-за того, как он изменяет трассировку стека.
Помимо оптимизации хвостовой рекурсии, вы можете установить глубину рекурсии вручную:
import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
В Python нет встроенной оптимизации хвостовой рекурсии. Однако мы можем «перестроить» функцию с помощью абстрактного синтаксического дерева (AST), исключив там рекурсию и заменив ее циклом. Гвидо был абсолютно прав, этот подход имеет некоторые ограничения, поэтому я не могу рекомендовать его к использованию.
Однако я все же написал (скорее, в качестве обучающего примера) свою версию оптимизатора, и вы даже можете попробовать, как она работает.
Установите этот пакет через pip:
pip install astrologic
Теперь вы можете запустить этот пример кода:
from astrologic import no_recursion
counter = 0
@no_recursion
def recursion():
global counter
counter += 1
if counter != 10000000:
return recursion()
return counter
print(recursion())
Это решение нестабильно, и вы никогда не должны использовать его в производственной среде. О некоторых существенных ограничениях можно прочитать на странице в github (извините). Однако это решение вполне «настоящее», без прерывания кода и прочих подобных ухищрений.
Попробуйте экспериментальную реализацию TCO для определения размера.
Хвостовой вызов никогда не может быть оптимизирован для перехода в Python. Оптимизация — это преобразование программы, сохраняющее смысл программы. Устранение хвостового вызова не сохраняет смысла программ Python.
Одна из часто упоминаемых проблем заключается в том, что устранение хвостовых вызовов изменяет стек вызовов, а Python позволяет проводить самоанализ стека во время выполнения. Но есть еще одна проблема, о которой редко упоминают. Вероятно, в дикой природе есть много такого кода:
def map_file(path):
f = open(path, 'rb')
return mmap.mmap(f.fileno())
Призыв кmmap.mmapнаходится в хвостовом положении. Если бы он был заменен переходом, то текущий кадр стека был бы отброшен до того, как управление было бы передано . Текущий кадр стека содержит единственную ссылку на файловый объект, поэтому файловый объект может (и в CPython будет) быть освобожден до вызова, что закроет файловый дескриптор, сделав его недействительным до того, как он его увидит.
В лучшем случае код завершится ошибкой с исключением. В худшем случае файловый дескриптор может быть повторно использован в другом потоке, что приведет кmmapдля отображения неправильного файла. Таким образом, эта «оптимизация» была бы потенциально катастрофической вещью, если бы она была применена к огромному телу существующего кода Python.
Спецификация Python гарантирует, что таких проблем не возникнет, поэтому вы можете быть уверены, что никакая соответствующая реализация никогда не будет конвертироватьreturn f(args)в прыжок — если, возможно, у него нет сложного механизма статического анализа, который может доказать, что раннее отбрасывание объекта в этом случае не будет иметь видимых последствий.
Ничто из этого не помешает Python добавить синтаксис для явных хвостовых вызовов с семантикой перехода, такой как
return from f(args)
Это не сломает код, который его не использует, и, вероятно, будет полезен для автоматически сгенерированного кода и некоторых алгоритмов. GvR больше не BDFL, так что это может случиться, но я бы не стал задерживать дыхание.