¿Python optimiza la recursividad de la cola?

206

Tengo el siguiente código que falla con el siguiente error:

RuntimeError: profundidad de recursión máxima excedida

Intenté reescribir esto para permitir la optimización de recursión de cola (TCO). Creo que este código debería haber tenido éxito si se hubiera producido un TCO.

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

print(trisum(1000, 0))

¿Debo concluir que Python no hace ningún tipo de TCO, o solo necesito definirlo de manera diferente?

Jordan Mack
fuente
11
@Wessie TCO es simple consideración de cuán dinámico o estático es el lenguaje. Lua, por ejemplo, también lo hace. Simplemente necesita reconocer las llamadas de cola (bastante simple, tanto a nivel de AST como a nivel de bytecode), y luego reutilizar el marco de pila actual en lugar de crear uno nuevo (también simple, en realidad incluso más simple en intérpretes que en código nativo) .
11
Oh, un punto crítico: hablas exclusivamente sobre la recursividad de la cola, pero usas el acrónimo "TCO", que significa optimización de llamadas de cola y se aplica a cualquier instancia de return func(...)(explícita o implícitamente), ya sea recursiva o no. TCO es un superconjunto adecuado de TRE, y más útil (por ejemplo, hace posible el estilo de pase de continuación, que TRE no puede), y no es mucho más difícil de implementar.
1
Aquí hay una manera hackea de implementarlo: un decorador que utiliza excepciones para generar marcos de ejecución: metapython.blogspot.com.br/2010/11/…
jsbueno
2
Si se limita a la recursión de la cola, no creo que un rastreo adecuado sea súper útil. Tiene una llamada foodesde dentro de una llamada foodesde adentro hacia adentro foodesde dentro de una llamada a foo... No creo que se pierda ninguna información útil por perder esto.
Kevin
1
Recientemente he aprendido sobre el coco, pero aún no lo he probado. Parece que vale la pena echarle un vistazo. Se afirma que tiene una optimización de recursión de cola.
Alexey

Respuestas:

216

No, y nunca lo hará, ya que Guido van Rossum prefiere poder tener los rastros adecuados:

Eliminación de recursión de cola (2009-04-22)

Palabras finales sobre llamadas de cola (2009-04-27)

Puede eliminar manualmente la recursividad con una transformación como esta:

>>> 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
John La Rooy
fuente
12
O si vas a transformarlo así, solo: from operator import add; reduce(add, xrange(n + 1), csum)¿?
Jon Clements
38
@JonClements, que funciona en este ejemplo en particular. La transformación a un ciclo while funciona para la recursividad de cola en casos generales.
John La Rooy
25
+1 Por ser la respuesta correcta, pero parece una decisión de diseño increíblemente descabellada. Las razones dadas parecen reducirse a "es difícil de hacer dada la forma en que se interpreta Python y no me gusta de todos modos, ¡así que ahí!"
Básico
12
@jwg Entonces ... ¿Qué? ¿Tiene que escribir un idioma antes de poder comentar sobre malas decisiones de diseño? Apenas parece lógico o práctico. ¿Asumo por su comentario que no tiene ninguna opinión sobre las características (o la falta de ellas) en algún idioma escrito alguna vez?
Básico
2
@ Básico No, pero tienes que leer el artículo que estás comentando. Parece muy fuerte que en realidad no lo leyó, considerando cómo se "reduce" a usted. (Desafortunadamente, es posible que necesite leer los dos artículos vinculados, ya que algunos argumentos se extienden sobre ambos). No tiene casi nada que ver con la implementación del lenguaje, sino con la semántica prevista.
Veky
179

Publiqué un módulo que realiza la optimización de llamadas de cola (manejando tanto el estilo de recursión de cola como el de paso de continuación): https://github.com/baruchel/tco

Optimizando la recursividad de cola en Python

A menudo se ha afirmado que la recursión de la cola no se adapta a la forma de codificación Pythonic y que a uno no debería importarle cómo incrustarlo en un bucle. No quiero discutir con este punto de vista; a veces, sin embargo, me gusta probar o implementar nuevas ideas como funciones recursivas de la cola en lugar de con bucles por varias razones (centrándome en la idea en lugar del proceso, teniendo veinte funciones cortas en mi pantalla al mismo tiempo en lugar de solo tres "Pythonic" funciones, trabajar en una sesión interactiva en lugar de editar mi código, etc.).

La optimización de la recursividad de cola en Python es, de hecho, bastante fácil. Si bien se dice que es imposible o muy complicado, creo que se puede lograr con soluciones elegantes, cortas y generales; Incluso creo que la mayoría de estas soluciones no usan las características de Python de lo que deberían. Las expresiones lambda limpias que funcionan junto con bucles muy estándar conducen a herramientas rápidas, eficientes y totalmente utilizables para implementar la optimización de recursión de cola.

Como conveniencia personal, escribí un pequeño módulo que implementa tal optimización de dos maneras diferentes. Me gustaría discutir aquí sobre mis dos funciones principales.

La forma limpia: modificar el combinador Y

los combinador Y es bien conocido; permite usar funciones lambda de manera recursiva, pero no permite incrustar llamadas recursivas en un bucle. El cálculo Lambda solo no puede hacer tal cosa. Sin embargo, un ligero cambio en el combinador Y puede proteger la llamada recursiva que se evaluará realmente. Por lo tanto, la evaluación puede retrasarse.

Aquí está la famosa expresión del combinador Y:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

Con un cambio muy leve, podría obtener:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))

En lugar de llamarse a sí misma, la función f ahora devuelve una función que realiza la misma llamada, pero como la devuelve, la evaluación se puede hacer más tarde desde afuera.

Mi código es:

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

La función se puede usar de la siguiente manera; Aquí hay dos ejemplos con versiones recursivas de cola de factorial y Fibonacci:

>>> 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

Obviamente, la profundidad de recursión ya no es un problema:

>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42

Por supuesto, este es el único propósito real de la función.

Solo una cosa no se puede hacer con esta optimización: no se puede usar con una función recursiva de cola que evalúa a otra función (esto se debe al hecho de que los objetos devueltos invocables se manejan como llamadas recursivas adicionales sin distinción). Como generalmente no necesito dicha función, estoy muy contento con el código anterior. Sin embargo, para proporcionar un módulo más general, pensé un poco más para encontrar una solución para este problema (consulte la siguiente sección).

En cuanto a la velocidad de este proceso (que no es el problema real sin embargo), resulta ser bastante bueno; las funciones recursivas de cola se evalúan incluso mucho más rápido que con el siguiente código utilizando expresiones más simples:

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

Creo que evaluar una expresión, incluso complicada, es mucho más rápido que evaluar varias expresiones simples, como es el caso en esta segunda versión. No mantuve esta nueva función en mi módulo, y no veo circunstancias en las que pueda usarse en lugar de la "oficial".

Continuar pasando estilo con excepciones

Aquí hay una función más general; es capaz de manejar todas las funciones recursivas de cola, incluidas las que devuelven otras funciones. Las llamadas recursivas se reconocen a partir de otros valores de retorno mediante el uso de excepciones. Esta solución es más lenta que la anterior; un código más rápido probablemente podría escribirse usando algunos valores especiales como "banderas" que se detectan en el bucle principal, pero no me gusta la idea de usar valores especiales o palabras clave internas. Hay alguna interpretación divertida del uso de excepciones: si a Python no le gustan las llamadas recursivas de cola, se debe generar una excepción cuando se produce una llamada recursiva de cola, y la forma pitónica será atrapar la excepción para encontrar algo limpio solución, que en realidad es lo que sucede aquí ...

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

Ahora se pueden usar todas las funciones. En el siguiente ejemplo, f(n)se evalúa la función de identidad para cualquier valor positivo de n:

>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42

Por supuesto, se podría argumentar que las excepciones no están destinadas a ser utilizadas para redirigir intencionalmente al intérprete (como una especie de gotodeclaración o probablemente como una especie de estilo de paso de continuación), lo cual debo admitir. Pero, de nuevo, me parece graciosa la idea de usar tryuna sola línea como una returndeclaración: tratamos de devolver algo (comportamiento normal) pero no podemos hacerlo debido a una llamada recursiva (excepción).

Respuesta inicial (2013-08-29).

Escribí un complemento muy pequeño para manejar la recursión de cola. Puede encontrarlo con mis explicaciones allí: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Puede incrustar una función lambda escrita con un estilo de recursión de cola en otra función que la evaluará como un bucle.

La característica más interesante de esta pequeña función, en mi humilde opinión, es que la función no se basa en algún truco de programación sucio sino en un simple cálculo lambda: el comportamiento de la función se cambia a otro cuando se inserta en otra función lambda que se parece mucho al combinador Y.

Thomas Baruchel
fuente
¿Podría, por favor, proporcionar un ejemplo de definición de una función (preferiblemente de manera similar a una definición normal) que llama a una de varias otras funciones en función de alguna condición, utilizando su método? Además, ¿se bet0puede usar su función de ajuste como decorador para los métodos de clase?
Alexey
@Alexey No estoy seguro de poder escribir código en forma de bloque dentro de un comentario, pero, por supuesto, puede usar la defsintaxis para sus funciones, y en realidad el último ejemplo anterior se basa en una condición. En mi publicación baruchel.github.io/python/2015/11/07 /... puede ver un párrafo que comienza con "Por supuesto, podría objetar que nadie escribiría dicho código", donde doy un ejemplo con la sintaxis de definición habitual. Para la segunda parte de su pregunta, tengo que pensarlo un poco más, ya que no he pasado mucho tiempo en eso. Saludos.
Thomas Baruchel,
Debería importarle dónde ocurre la llamada recursiva en su función, incluso si está utilizando una implementación de lenguaje que no sea de TCO. Esto se debe a que la parte de la función que ocurre después de la llamada recursiva es la parte que debe almacenarse en la pila. Por lo tanto, hacer que su función sea recursiva al mínimo minimiza la cantidad de información que tiene que almacenar por llamada recursiva, lo que le da más espacio para tener grandes pilas de llamadas recursivas si las necesita.
josiah
21

La palabra de Guido está en http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Recientemente publiqué una entrada en mi blog de Historia de Python sobre los orígenes de las características funcionales de Python. Una observación al margen sobre no apoyar la eliminación de la recursividad de la cola (TRE) provocó de inmediato varios comentarios sobre la lástima de que Python no haga esto, incluidos los enlaces a las entradas recientes del blog de otros que intentan "probar" que se puede agregar TRE a Python fácilmente. Así que déjame defender mi posición (que es que no quiero TRE en el idioma). Si quieres una respuesta corta, simplemente no es pitónica. Aquí está la respuesta larga:

Jon Clements
fuente
12
Y aquí radica el problema con los llamados BDsFL.
Adam Donahue
66
@AdamDonahue, ¿has quedado perfectamente satisfecho con cada decisión tomada por un comité? Al menos obtienes una explicación razonada y autorizada del BDFL.
Mark Ransom
2
No, por supuesto que no, pero me parecen más imparciales. Esto de un prescriptivista, no un descriptivista. La ironía.
Adam Donahue
6

CPython no admite y probablemente nunca admitirá la optimización de llamadas de cola basadas en Guido van Rossum declaraciones de sobre el tema.

He escuchado argumentos de que dificulta la depuración debido a cómo modifica el seguimiento de la pila.

recursivo
fuente
18
@mux CPython es la implementación de referencia del lenguaje de programación Python. Hay otras implementaciones (como PyPy, IronPython y Jython), que implementan el mismo lenguaje pero difieren en los detalles de implementación. La distinción es útil aquí porque (en teoría) es posible crear una implementación alternativa de Python que haga TCO. Sin embargo, no conozco a nadie que lo piense, y la utilidad sería limitada ya que el código que se basa en él se rompería en todas las demás implementaciones de Python.
3

Pruebe la implementación experimental de macropy TCO para el tamaño.

Mark Lawrence
fuente
2

Además de optimizar la recursividad de la cola, puede establecer la profundidad de recursión manualmente al:

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
zhenv5
fuente
55
¿Por qué no usas jQuery?
Jeremy Hert
55
Debido a que también no ofrece TCO? :-D stackoverflow.com/questions/3660577/…
Veky