Ricorsione generale alla ricorsione in coda

Question

Ricorsione generale alla ricorsione in coda

#1 da (5 voti)
#2 da (4 voti)

2

È teoricamente possibile trasformare ogni tipo di ricorsione generale in ricorsione di coda? Sono equivalenti per esempio dal punto di vista del lambda-calcolo? Questo è un dibattito tra me e un conoscente.

La mia opinione è che non è possibile ogni volta. Ad esempio, se si ha una funzione che si chiama in modo ricorsivo due o tre volte, non è possibile effettuare tutte le chiamate ricorsive in chiamate di coda, giusto? O esiste sempre un modo per ridurre il numero di chiamate ricorsive a una singola chiamata ricorsiva?

recursion tail-call lambda-calculus

posta user131411 17.07.2014 - 20:41

fonte

2 risposte

Leggi altre domande sui tag recursion tail-call lambda-calculus

Perché non sostituire HTML con JSON come tecnologia di progettazione web di base? [chiuso] Come riparare software mal progettato? [chiuso]

score 5 · Answer 1

Dovresti riuscire a farlo utilizzando lo stile di passaggio continuo .

In CPS, ogni funzione assume una funzione di continuazione esplicita che rappresenta il resto del calcolo. Invece di restituire direttamente un valore, una funzione in CPS passa invece il risultato alla continuazione.

Ad esempio se hai il seguente tipo di dati Tree :

type Tree = Empty | Node of Tree * int * Tree

e volevi sommare i valori, potresti scrivere la funzione per sommare a turno i sottoalberi sinistro e destro:

let rec sum_cps t f = 
    match t with
        | Empty -> f 0
        | Node(l, v, r) -> sum_cps l (fun lv ->
            sum_cps r (fun rv -> f (lv + v + rv)))

let sumT t = sum_cps t (fun i -> i)

score 4 · Answer 2

Puoi eseguire questa trasformazione utilizzando Stile passaggio continuo .

Leggi ad esempio A.Appel Compilare con continuazioni libro

Intuitivamente, sostituisci -after Trasformazione CPS - (quasi) ogni frame di chiamata del richiama lo stack con una continuazione allocata su heap frame (o "closure" quando si visualizzano le continuazioni come funzioni). (quindi potresti non vincere molto: i riquadri dello stack evitati vengono sostituiti da garbage collection frame di continuazione).

Vedi anche il vecchio documento di Appel: la garbage collection può essere più veloce dell'allocazione dello stack

^{(che potrebbe essere meno vero oggi, forse a causa di problemi cache )}