Ho un problema nel comprendere le prestazioni di una funzione Common Lisp (sono ancora alle prime armi). Ho due versioni di questa funzione, che calcola semplicemente la somma di tutti gli interi fino a un dato n.Common Lisp: Perché la mia funzione ricorsiva di coda causa un overflow dello stack?
versione non-tail-ricorsiva:
(defun addup3 (n)
(if (= n 0)
0
(+ n (addup (- n 1)))))
Tail-recursive versione:
(defun addup2 (n)
(labels ((f (acc k)
(if (= k 0)
acc
(f (+ acc k) (- k 1)))))
(f 0 n)))
Sto cercando di eseguire queste funzioni in CLISP con ingresso n = 1000000. Ecco il risultato
[2]> (addup3 1000000)
500000500000
[3]> (addup2 1000000)
*** - Program stack overflow. RESET
posso funzionare sia con successo in SBCL, ma quello non-tail-ricorsiva è più veloce (solo da un po ', ma che sembra strano per me). Ho analizzato le domande StackOverflow per le risposte ma non ho trovato nulla di simile. Perché ottengo uno stack overflow sebbene la funzione ricorsiva di coda sia progettata per NON mettere tutte le chiamate di funzioni ricorsive nello stack? Devo dire all'interprete/compilatore di ottimizzare le chiamate di coda? (Ho letto qualcosa come (proclaim '(optimize (debug 1)) per impostare il livello di debug e ottimizzare al costo delle abilità di tracciamento, ma non so cosa faccia). Forse la risposta è ovvia e il codice è una cazzata, ma non riesco proprio a capirlo. L'aiuto è apprezzato.
Modifica: danlei ha sottolineato l'errore di battitura, dovrebbe essere una chiamata a addup3 nella prima funzione, quindi è ricorsivo. Se corretto, entrambe le versioni troppo pieno, ma non il suo unico
(defun addup (n)
"Adds up the first N integers"
(do ((i 0 (+ i 1))
(sum 0 (+ sum i)))
((> i n) sum)))
Mentre può essere un modo più tipico per farlo, trovo strano che la ricorsione in coda non è sempre ottimizzato, considerando miei istruttori piacerebbe dirmi che è molto più efficiente e roba del genere.
Come sottolineato da danlei, la prima funzione ha un errore di battitura, deve chiamarsi e non 'addup', che è essenzialmente la funzione che hai descritto. Se correggo l'errore di battitura, anche questo trabocca. Tuttavia, sono perplesso sul fatto che il costrutto 'do' sia più capace di quello ricorsivo. Non riesco a trovare nulla riguardo TCO per CLISP quando googlando e navigando le specifiche su clisp.org. Non sarebbe strano se la ricorsione della coda non fosse più potente della normale ricorsione? – oarfish
Non dovresti essere sorpreso. L'ottimizzazione delle chiamate tail fa semplicemente eseguire una definizione ricorsiva in uno spazio costante (stack), in modo che possa essere veloce come una definizione iterativa. Non c'è magia coinvolta che potrebbe renderlo più veloce di così. – Svante
In Barski's Land of Lisp, ho appena letto che in effetti CLISP ottimizza solo le chiamate di coda, quando si compila la funzione. In effetti, la coda ricorsiva è un po 'più veloce, quindi non c'è nessun mistero qui. – oarfish