Essa é uma maneira genérica de converter qualquer procedimento recursivo em recursão de cauda?

13

Parece que eu encontrei uma maneira genérica de converter qualquer procedimento recursivo em recursão de cauda:

  1. Defina um subprocedimento auxiliar com um parâmetro "resultado" extra.
  2. Aplique o que seria aplicado ao valor de retorno do procedimento a esse parâmetro.
  3. Ligue para este procedimento auxiliar para começar. O valor inicial para o parâmetro "result" é o valor do ponto de saída do processo recursivo, para que o processo iterativo resultante comece de onde o processo recursivo começa a encolher.

Por exemplo, aqui está o procedimento recursivo original a ser convertido ( exercício 1.17 do SICP ):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Aqui está o procedimento recursivo de cauda convertido ( exercício 1.18 do SICP ):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

Alguém pode provar ou refutar isso?

nalzok
fonte
1
O(registron)
Segundo pensamento: a escolha bde ser uma potência de 2 mostra que a configuração inicial productde 0 não está certa; mas alterá-lo para 1 não funciona quando bé ímpar. Talvez você precise de 2 parâmetros diferentes de acumulador?
Jrandom_hacker 23/11
3
Você realmente não definiu uma transformação de uma definição recursiva não-cauda, ​​adicionar algum parâmetro de resultado e usá-lo para acumulação é bastante vago e dificilmente generaliza para casos mais complexos, por exemplo, travessias de árvores, nas quais você tem duas chamadas recursivas. Existe uma idéia mais precisa de "continuação", na qual você faz parte do trabalho e permite que uma função de "continuação" assuma o controle, recebendo como parâmetro o trabalho que você fez até agora. É chamado de estilo de passagem de continuação (cps), consulte en.wikipedia.org/wiki/Continuation-passing_style .
Ariel
4
Esses slides fsl.cs.illinois.edu/images/d/d5/CS422-Fall-2006-13.pdf contêm uma descrição da transformação cps, na qual você usa alguma expressão arbitrária (possivelmente com definições de função com chamadas não finais) e transformá-lo em uma expressão equivalente apenas com chamadas de cauda.
Ariel
@j_random_hacker Sim, eu posso ver que o meu "convertido" procedimento é de fato errado ...
nalzok

Respostas:

12

Sua descrição do seu algoritmo é realmente muito vaga para avaliá-lo neste momento. Mas, aqui estão algumas coisas a considerar.

CPS

De fato, existe uma maneira de transformar qualquer código em um formulário que use apenas chamadas de cauda. Essa é a transformação do CPS. O CPS ( estilo de passagem de continuação ) é uma forma de expressar código, passando para cada função uma continuação. Uma continuação é uma noção abstrata que representa "o restante de uma comparação". No código expresso no formato CPS, a maneira natural de reificar uma continuação é como uma função que aceita um valor. No CPS, em vez de uma função retornar um valor, ela aplica a função que representa a continuação atual ao ser "retornado" pela função.

Por exemplo, considere a seguinte função:

(lambda (a b c d)
  (+ (- a b) (* c d)))

Isso pode ser expresso no CPS da seguinte maneira:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

É feio e geralmente lento, mas tem certas vantagens:

  • A transformação pode ser completamente automatizada. Portanto, não há necessidade de escrever (ou ver) o código no formato CPS.
  • Combinado com batidas e trampolins , ele pode ser usado para fornecer otimização de chamada de cauda em idiomas que não fornecem otimização de chamada de cauda. (A otimização de chamada de cauda de funções diretamente recursivas de cauda pode ser realizada por outros meios, como converter a chamada recursiva em um loop. Mas a recursão indireta não é tão trivial para converter dessa maneira.)
  • Com o CPS, as continuações se tornam objetos de primeira classe. Como as continuações são a essência do controle, isso permite que praticamente qualquer operador de controle seja implementado como uma biblioteca sem exigir nenhum suporte especial do idioma. Por exemplo, saltar, exceções e encadeamento cooperativo podem ser modelados usando continuações.

TCO

Parece-me que a única razão para se preocupar com recursão de cauda (ou chamadas de cauda em geral) é para fins de otimização de chamada de cauda (TCO). Então, acho que uma pergunta melhor a ser feita é "minha transformação gera código que é otimizável por chamada de cauda?".

Se considerarmos novamente o CPS, uma de suas características é que o código expresso no CPS consiste apenas em chamadas de cauda. Como tudo é uma chamada final, não precisamos salvar um ponto de retorno na pilha. Portanto, todo o código no formato CPS deve ser otimizado para chamada final, certo?

Bem, não exatamente. Você vê, embora possa parecer que eliminamos a pilha, tudo o que fizemos foi apenas mudar a maneira como a representamos. A pilha agora faz parte do fechamento, representando uma continuação. Portanto, o CPS não magicamente otimiza todo o nosso código de chamada final.

Portanto, se o CPS não pode fazer tudo TCO, existe uma transformação específica para recursão direta que pode? Não, não em geral. Algumas recursões são lineares, mas outras não. Recursões não lineares (por exemplo, árvore) devem simplesmente manter uma quantidade variável de estado em algum lugar.

Nathan Davis
fonte
é um pouco confuso quando na subseção " TCO ", quando você diz "otimização de chamada final", na verdade você quer dizer "com uso constante de memória". O fato de o uso dinâmico da memória não ser constante ainda não nega o fato de que as chamadas são realmente finais e não há crescimento ilimitado no uso da pilha . O SICP chama esses cálculos de "iterativos", então dizer "embora seja TCO, ainda não o torna iterativo" pode ter sido uma redação melhor (para mim).
Will Ness
@WillNess Ainda temos uma pilha de chamadas, apenas representada de forma diferente. A estrutura não muda apenas porque estamos usando a pilha, e não a pilha de hardware . Afinal, existem muitas estruturas de dados baseadas na memória heap dinâmica que possuem "pilha" em seu nome.
Nathan Davis
o único ponto aqui é que alguns idiomas têm limites físicos para usar a pilha de chamadas.
Will Ness