O Python otimiza a recursão da cauda?

206

Eu tenho o seguinte pedaço de código que falha com o seguinte erro:

RuntimeError: profundidade máxima de recursão excedida

Tentei reescrever isso para permitir a otimização da recursão de cauda (TCO). Acredito que esse código teria sido bem-sucedido se um TCO tivesse ocorrido.

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

print(trisum(1000, 0))

Devo concluir que o Python não faz nenhum tipo de TCO ou preciso apenas defini-lo de maneira diferente?

Jordan Mack
fonte
11
O @Wessie TCO é simples, considerando a dinâmica ou a estática da linguagem. Lua, por exemplo, também faz isso. Você só precisa reconhecer chamadas de cauda (bastante simples, tanto no nível AST quanto no bytecode) e, em seguida, reutilizar o quadro de pilha atual em vez de criar um novo (também simples, na verdade ainda mais simples em intérpretes do que em código nativo) .
11
Ah, um ponto: você fala exclusivamente sobre recursão de cauda, ​​mas usa o acrônimo "TCO", que significa otimização de chamada de cauda e aplica-se a qualquer instância de return func(...)(explícita ou implicitamente), seja recursiva ou não. O TCO é um superconjunto adequado do TRE, e mais útil (por exemplo, viabiliza o estilo de passagem de continuação, o que o TRE não pode) e não é muito mais difícil de implementar.
1
Aqui está uma maneira hackish para implementá-lo - um decorador usando levantamento exceção para lançar quadros de execução longe: metapython.blogspot.com.br/2010/11/...
jsbueno
2
Se você se restringir à recursão de cauda, ​​não acho que um retorno adequado seja super útil. Você tem uma ligação foode dentro de uma ligação para foode dentro para foodentro de uma ligação para foo... Acho que nenhuma informação útil seria perdida se você perdesse isso.
Kevin
1
Eu aprendi recentemente sobre o coco, mas ainda não o experimentei. Parece vale a pena dar uma olhada. Alega-se ter otimização de recursão da cauda.
Alexey19 /

Respostas:

216

Não, e nunca será, uma vez que Guido van Rossum prefere ter um rastreio adequado:

Eliminação da recursão da cauda (22-04-2009)

Palavras finais sobre chamadas de cauda (27-04-2009)

Você pode eliminar manualmente a recursão com uma transformação 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
fonte
12
Ou se você vai transformá-lo assim - apenas from operator import add; reduce(add, xrange(n + 1), csum):?
Jon Clements
38
@ JonClements, que funciona neste exemplo em particular. A transformação em um loop while funciona para recursão de cauda em casos gerais.
John La Rooy
25
+1 Por ser a resposta correta, mas esta parece ser uma decisão de design incrivelmente complicada. As razões apresentadas parecem resumir-se a "é difícil de fazer, dada a forma como o python é interpretado e eu não gosto de nada assim, por isso!"
Basic
12
@jwg Então ... o que? Você precisa escrever um idioma antes de poder comentar sobre más decisões de design? Dificilmente parece lógico ou prático. Pelo seu comentário, presumo que você não tem opinião sobre nenhum recurso (ou falta dele) em qualquer idioma já escrito?
Basic
2
@ Básico Não, mas você precisa ler o artigo que está comentando. Parece muito forte que você realmente não leu, considerando como "tudo se resume" a você. (Você pode realmente precisar ler os dois artigos vinculados, infelizmente, uma vez que alguns argumentos estão espalhados por ambos.) Não tem quase nada a ver com a implementação da linguagem, mas tudo a ver com a semântica pretendida.
Veky
179

Publiquei um módulo executando otimização de chamada de cauda (manipulando o estilo de recursão de cauda e de passagem de continuação): https://github.com/baruchel/tco

Otimizando a recursão da cauda em Python

Afirma-se frequentemente que a recursão da cauda não se adequa à maneira Python de codificar e que não se deve preocupar em incorporá-la em um loop. Não quero discutir com esse ponto de vista; às vezes, no entanto, gosto de tentar ou implementar novas idéias como funções recursivas de cauda em vez de com loops por várias razões (focando na ideia e não no processo, tendo vinte funções curtas na tela ao mesmo tempo, em vez de apenas três "Pythonic" funções, trabalhando em uma sessão interativa em vez de editar meu código etc.).

Otimizar a recursão da cauda no Python é de fato bastante fácil. Embora se diga que é impossível ou muito complicado, acho que pode ser alcançado com soluções elegantes, curtas e gerais; Até acho que a maioria dessas soluções não usa os recursos do Python, do contrário. Expressões lambda limpas, trabalhando com loops muito padrão, levam a ferramentas rápidas, eficientes e totalmente utilizáveis ​​para implementar a otimização da recursão da cauda.

Como conveniência pessoal, escrevi um pequeno módulo implementando essa otimização de duas maneiras diferentes. Eu gostaria de discutir aqui sobre minhas duas funções principais.

A maneira limpa: modificando o combinador Y

O combinador Y é bem conhecido; permite usar funções lambda de maneira recursiva, mas não permite por si só incorporar chamadas recursivas em um loop. O cálculo lambda sozinho não pode fazer uma coisa dessas. Uma ligeira alteração no combinador Y, no entanto, pode proteger a chamada recursiva a ser realmente avaliada. A avaliação pode, portanto, ser adiada.

Aqui está a famosa expressão do combinador Y:

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

Com uma pequena mudança, eu pude obter:

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

Em vez de chamar a si mesma, a função f agora retorna uma função que executa a mesma chamada, mas, como ela retorna, a avaliação pode ser feita posteriormente de fora.

Meu código é:

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

A função pode ser usada da seguinte maneira; Aqui estão dois exemplos com versões recursivas de fatorial e 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, a profundidade da recursão não é mais um problema:

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

É claro que esse é o único objetivo real da função.

Somente uma coisa não pode ser feita com essa otimização: ela não pode ser usada com uma função recursiva de cauda avaliando para outra função (isso vem do fato de que objetos retornáveis ​​que podem ser chamados são todos manipulados como chamadas recursivas adicionais sem distinção). Como geralmente não preciso desse recurso, estou muito feliz com o código acima. No entanto, para fornecer um módulo mais geral, pensei um pouco mais para encontrar alguma solução alternativa para esse problema (consulte a próxima seção).

No que diz respeito à velocidade desse processo (que não é o problema real), ele é bastante bom; funções recursivas de cauda são avaliadas até mais rapidamente do que com o código a seguir, usando expressões mais 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

Penso que avaliar uma expressão, mesmo complicada, é muito mais rápida do que avaliar várias expressões simples, como é o caso nesta segunda versão. Eu não mantive essa nova função no meu módulo e não vejo circunstâncias em que ela possa ser usada, e não a "oficial".

Estilo de passagem de continuação com exceções

Aqui está uma função mais geral; é capaz de lidar com todas as funções recursivas da cauda, ​​incluindo aquelas que retornam outras funções. Chamadas recursivas são reconhecidas de outros valores de retorno pelo uso de exceções. Esta solução é mais lenta que a anterior; um código mais rápido provavelmente poderia ser escrito usando alguns valores especiais como "sinalizadores" sendo detectados no loop principal, mas não gosto da idéia de usar valores especiais ou palavras-chave internas. Há alguma interpretação engraçada do uso de exceções: se o Python não gostar de chamadas recursivas de cauda, ​​uma exceção deve ser levantada quando uma chamada recursiva de cauda ocorrer, e a maneira Pythonic será capturar a exceção para encontrar algumas informações limpas. solução, que é realmente o que acontece aqui ...

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

Agora todas as funções podem ser usadas. No exemplo a seguir, f(n)é avaliado para a função de identidade qualquer valor positivo de n:

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

Certamente, pode-se argumentar que as exceções não se destinam a ser usadas para redirecionar intencionalmente o intérprete (como um tipo de gotodeclaração ou provavelmente como um tipo de estilo de passagem de continuação), o que devo admitir. Mas, novamente, acho engraçada a ideia de usar tryuma única linha como uma returndeclaração: tentamos retornar algo (comportamento normal), mas não podemos fazê-lo por causa de uma chamada recursiva (exceção).

Resposta inicial (29/08/2013).

Eu escrevi um plugin muito pequeno para lidar com a recursão da cauda. Você pode encontrá-lo com minhas explicações aqui: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Ele pode incorporar uma função lambda escrita com um estilo de recursão de cauda em outra função que a avaliará como um loop.

O recurso mais interessante nessa pequena função, na minha humilde opinião, é que a função não depende de algum truque de programação sujo, mas de mero cálculo lambda: o comportamento da função é alterado para outro quando inserido em outra função lambda que parece muito com o combinador Y.

Thomas Baruchel
fonte
Você poderia, por favor, fornecer um exemplo de definição de uma função (de preferência semelhante à definição normal) que chama uma das várias outras funções com base em alguma condição, usando seu método? Além disso, sua função de agrupamento pode bet0ser usada como um decorador para métodos de classe?
Alexey
@ Alexey Não sei se posso escrever código em estilo de bloco dentro de um comentário, mas é claro que você pode usar a defsintaxe para suas funções e, na verdade, o último exemplo acima depende de uma condição. No meu post baruchel.github.io/python/2015/11/07/…, você pode ver um parágrafo começando com "Claro que você poderia objetar que ninguém escreveria esse código", onde eu dou um exemplo com a sintaxe de definição usual. Para a segunda parte da sua pergunta, tenho que pensar um pouco mais, pois não passo tempo nisso há um tempo. Saudações.
Thomas Baruchel
Você deve se preocupar onde a chamada recursiva ocorre em sua função, mesmo se você estiver usando uma implementação de idioma não-TCO. Isso ocorre porque a parte da função que ocorre após a chamada recursiva é a parte que precisa ser armazenada na pilha. Portanto, tornar sua função recursiva de cauda minimiza a quantidade de informações que você precisa armazenar por chamada recursiva, o que lhe dá mais espaço para ter grandes pilhas de chamadas recursivas, se você precisar delas.
Josias
21

A palavra Guido está em http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Recentemente, publiquei uma entrada no meu blog Histórico do Python sobre as origens dos recursos funcionais do Python. Uma observação lateral sobre não apoiar a eliminação da recursão da cauda (TRE) imediatamente provocou vários comentários sobre a pena que o Python não faz isso, incluindo links para entradas recentes do blog de outros que tentam "provar" que o TRE pode ser adicionado ao Python facilmente. Então, deixe-me defender minha posição (que é que eu não quero o TRE no idioma). Se você quer uma resposta curta, é simplesmente não-tônico. Aqui está a resposta longa:

Jon Clements
fonte
12
E aqui reside o problema com os chamados BDsFL.
Adam Donahue
6
@AdamDonahue, você ficou perfeitamente satisfeito com todas as decisões que vieram de um comitê? Pelo menos você recebe uma explicação fundamentada e autorizada do BDFL.
Mark Ransom
2
Não, claro que não, mas me parecem mais imparcial. Isso é de um prescritivista, não de um descritivista. A ironia.
Adam Donahue
6

O CPython não suporta e provavelmente nunca suportará a otimização da chamada de cauda com base nas declarações de Guido van Rossum sobre o assunto.

Ouvi argumentos de que isso torna a depuração mais difícil por causa de como ela modifica o rastreamento da pilha.

recursivo
fonte
18
@mux CPython é a implementação de referência da linguagem de programação Python. Existem outras implementações (como PyPy, IronPython e Jython), que implementam a mesma linguagem, mas diferem nos detalhes da implementação. A distinção é útil aqui porque (em teoria) é possível criar uma implementação alternativa do Python que faça o TCO. Não estou ciente de que alguém sequer pense nisso, e a utilidade seria limitada, pois o código contido nele seria interrompido em todas as outras implementações do Python.
3

Experimente a implementação de TCO de macropia experimental para obter o tamanho.

Mark Lawrence
fonte
2

Além de otimizar a recursão da cauda, ​​você pode definir a profundidade da recursão manualmente:

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
zhenv5
fonte
5
Por que você não usa apenas jQuery?
Jeremy Hert
5
Porque também não oferece TCO? :-D stackoverflow.com/questions/3660577/…
Veky