Оптимизирует ли Python хвостовую рекурсию?

206

У меня есть следующий кусок кода, который завершается с ошибкой:

RuntimeError: превышена максимальная глубина рекурсии

Я попытался переписать это, чтобы учесть оптимизацию хвостовой рекурсии (TCO). Я считаю, что этот код должен был быть успешным, если бы имелась ТШО.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Должен ли я заключить, что Python не выполняет никаких типов TCO, или мне просто нужно определить его по-другому?

Джордан Мак
источник
11
@ Wessie TCO просто показывает, насколько динамичен или статичен язык. Lua, например, тоже делает это. Вам просто нужно распознать хвостовые вызовы (довольно просто, как на уровне AST, так и на уровне байт-кода), а затем повторно использовать текущий кадр стека вместо создания нового (также простого, фактически даже более простого в интерпретаторах, чем в собственном коде) ,
11
Ах, один кроткий: вы говорите исключительно о хвостовой рекурсии, но используете аббревиатуру "TCO", что означает оптимизацию хвостового вызова и применяется к любому случаю return func(...)(явному или неявному), независимо от того, рекурсивен он или нет. TCO является надлежащим расширенным набором TRE и более полезен (например, он делает возможным стиль передачи продолжения, чего не может TRE), и не намного сложнее в реализации.
1
Вот хакерский способ его реализации - декоратор, использующий повышение исключений для отбрасывания фреймов выполнения: metapython.blogspot.com.br/2010/11/…
jsbueno
2
Если вы ограничиваете себя хвостовой рекурсией, я не думаю, что правильная трассировка является супер-полезной. У вас есть звонок fooизнутри звонка fooизнутри fooвнутрь звонка foo... Я не думаю, что потеря этой полезной информации будет потеряна.
Кевин
1
Я недавно узнал о Кокосе, но еще не пробовал. На это стоит взглянуть. Утверждается, что есть оптимизация хвостовой рекурсии.
Алексей

Ответы:

216

Нет, и никогда не будет, так как Гвидо ван Россум предпочитает иметь надлежащие трассировки:

Исключение рекурсии хвоста (2009-04-22)

Заключительные слова о вызовах в хвост (2009-04-27)

Вы можете вручную исключить рекурсию с помощью преобразования, подобного этому:

>>> 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
Джон Ла Рой
источник
12
Или если вы собираетесь преобразовать это так - просто from operator import add; reduce(add, xrange(n + 1), csum):?
Джон Клементс
38
@JonClements, это работает в этом конкретном примере. Преобразование в цикл while работает для хвостовой рекурсии в общих случаях.
Джон Ла Рой
25
+1 За правильный ответ, но это кажется невероятно решительным дизайнерским решением. Приведенные причины, по- видимому, сводятся к тому, что «это трудно сделать, учитывая то, как интерпретируется python, и мне все равно это не нравится!»
Basic
12
@jwg Так ... что? Вы должны написать язык, прежде чем сможете комментировать плохие дизайнерские решения? Вряд ли кажется логичным или практичным. Я предполагаю из вашего комментария, что у вас нет мнения о каких-либо функциях (или их отсутствии) на каком-либо языке, когда-либо написанном?
Basic
2
@ Базовая Нет, но вы должны прочитать статью, которую вы комментируете. Кажется очень сильно, что вы на самом деле не читали его, учитывая, как он «сводится» к вам. (К сожалению, вам может понадобиться прочитать обе связанные статьи, так как некоторые аргументы распространяются на обе.) Это почти не имеет отношения к реализации языка, но связано с предполагаемой семантикой.
Веки
179

Я опубликовал модуль, выполняющий оптимизацию хвостового вызова (обрабатывая как хвостовую рекурсию, так и стиль продолжения продолжения): https://github.com/baruchel/tco

Оптимизация хвостовой рекурсии в Python

Часто утверждается, что хвостовая рекурсия не подходит к пиктоническому способу кодирования, и что не нужно заботиться о том, как встроить ее в цикл. Я не хочу спорить с этой точкой зрения; однако иногда мне нравится пробовать или реализовывать новые идеи в виде хвостовых рекурсивных функций, а не с помощью циклов по разным причинам (фокусируясь на идее, а не на процессе, имея на экране двадцать коротких функций одновременно, а не только три «Pythonic») функции, работающие в интерактивном сеансе вместо редактирования моего кода и т. д.).

Оптимизация хвостовой рекурсии в 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 не любит хвост-рекурсивные вызовы, то должно возникать исключение, когда происходит хвост-рекурсивный вызов, и Pythonic будет перехватывать исключение, чтобы найти некоторый чистый решение, которое на самом деле то, что происходит здесь ...

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#!topic/comp.lang.python/dIsnJ2BoBKs

Он может встроить лямбда-функцию, написанную в стиле хвостовой рекурсии, в другую функцию, которая будет оценивать ее как цикл.

Самая интересная особенность этой маленькой функции, по моему скромному мнению, заключается в том, что эта функция основана не на грязном программировании, а на простом лямбда-исчислении: поведение функции меняется на другое при вставке в другую лямбда-функцию, которая выглядит очень похоже на Y комбинатор.

Томас Барухель
источник
Не могли бы вы, пожалуйста, привести пример определения функции (предпочтительно аналогично обычному определению), которая с помощью вашего метода вызывает один из нескольких других функций на основе некоторого условия? Кроме того, может ли ваша функция обертывания bet0использоваться в качестве декоратора для методов класса?
Алексей
@ Алексей Я не уверен, что могу написать код в блочном стиле внутри комментария, но вы, конечно, можете использовать defсинтаксис для своих функций, и фактически последний пример выше опирается на условие. В моем посте baruchel.github.io/python/2015/11/07/… вы можете увидеть абзац, начинающийся с «Конечно, вы можете возразить, что никто не напишет такой код», где я привожу пример с обычным синтаксисом определения. Что касается второй части вашего вопроса, я должен подумать об этом немного больше, так как я не тратил время на это некоторое время. С уважением.
Томас Барухель
Вам следует позаботиться о том, чтобы в вашей функции происходил рекурсивный вызов, даже если вы используете реализацию не-TCO. Это связано с тем, что часть функции, которая возникает после рекурсивного вызова, является частью, которая должна храниться в стеке. Поэтому, делая вашу функцию хвостовой рекурсивной, минимизируется объем информации, которую вы должны хранить при каждом рекурсивном вызове, что дает вам больше места для больших стеков рекурсивных вызовов, если они вам нужны.
Иосия
21

Слово Гвидо находится по адресу http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elmination.html

Недавно я опубликовал в своем блоге Python History статью о происхождении функциональных возможностей Python. Дополнительное замечание о том, что не поддерживается удаление хвостовой рекурсии (TRE), сразу вызвало несколько комментариев о том, как жаль, что Python этого не делает, включая ссылки на последние записи в блоге других, пытающихся «доказать», что TRE может быть добавлено в Python. без труда. Итак, позвольте мне защитить свою позицию (то есть, я не хочу, чтобы TRE на языке). Если вам нужен короткий ответ, он просто не пифоничен. Вот длинный ответ:

Джон Клементс
источник
12
И в этом заключается проблема с так называемыми BDsFL.
Адам Донахью
6
@AdamDonahue вы были полностью удовлетворены каждым решением, которое приходит от комитета? По крайней мере, вы получите аргументированное и авторитетное объяснение от BDFL.
Марк Рэнсом
2
Нет, конечно нет, но они кажутся мне более беспристрастными. Это от рецептиста, а не дескриптиста. Ирония.
Адам Донахью
6

CPython не поддерживает и, вероятно, никогда не будет поддерживать оптимизацию хвостовых вызовов на основе Гвидо ван Россума высказываний по этому вопросу.

Я слышал аргументы, что это затрудняет отладку из-за того, как он изменяет трассировку стека.

рекурсивный
источник
18
@mux CPython является эталонной реализацией языка программирования Python. Существуют другие реализации (такие как PyPy, IronPython и Jython), которые реализуют один и тот же язык, но отличаются деталями реализации. Различие полезно здесь, потому что (теоретически) возможно создать альтернативную реализацию Python, которая делает TCO. Я не знаю никого, кто бы даже думал об этом, и полезность была бы ограничена, так как полагающийся на него код нарушал бы все другие реализации Python.
2

Помимо оптимизации хвостовой рекурсии, вы можете установить глубину рекурсии вручную:

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
zhenv5
источник
5
Почему бы вам просто не использовать jQuery?
Джереми Херт
5
Потому что он также не предлагает TCO? :-D stackoverflow.com/questions/3660577/…
Веки