Stack overflow dalla chiamata ricorsiva in Lisp

Question

Sto imparando Lisp dal libro "The Land of Lisp" di Conrad Barski. Ora ho colpito il mio primo ostacolo, in cui l'autore dice:

Chiamando se stessi in questo modo non è solo consentito in Lisp, ma è spesso fortemente incoraggiato

dopo aver mostrato la seguente funzione esempio a contare le voci di un elenco:

(defun my-length (list) 
    (if list 
    (1+ (my-length (cdr list))) 
    0)) 

Quando chiamo questa funzione my-length con una lista contenente un milione di articoli, ottengo un errore di overflow dello stack. Quindi non ti aspetti mai di avere una lista così lunga in Lisp (quindi forse il mio caso d'uso è inutile) o c'è un altro modo per contare gli elementi in una lista così lunga. Potresti forse far luce su questo? (Sto usando GNU CLISP su Windows, comunque).

Answer 1

La creazione di funzioni ricorsive per il funzionamento su datastructures ricorsive è davvero buona per il lisp. E una lista (in lisp) è definita come una base dati ricorsiva, quindi dovresti essere ok.

Tuttavia, come si è verificato, se si attraversa una struttura di dati con profondità di un milione di oggetti utilizzando la ricorsione, verranno allocati anche un milione di frame nello stack e si può prevedere un overflow dello stack a meno che non si richieda specificamente all'ambiente di runtime di allocare una quantità enorme di stack-space (non ho idea se o come potresti farlo in gnu clisp ...).

Prima di tutto, penso che questo dimostri che la list-datastructure non è realmente la migliore per tutto, e in questo caso un'altra struttura potrebbe essere migliore (tuttavia, potresti non essere arrivato ai vettori nella tua prenota ancora ;-)

Un'altra cosa è che per ricorrere a ricorsi di grandi dimensioni come questa, il compilatore dovrebbe ottimizzare le ricusazioni di coda e convertirle in iterazioni. Non so se Clisp abbia questa funzionalità, ma dovresti cambiare la tua funzione per essere effettivamente ottimizzabile. (Se "ottimizzazione ricorsione coda" non ha senso, per favore fatemelo sapere e posso scavare alcune referenze)

Per altri modi di iterazione, date un'occhiata a:

• http://www.lispworks.com/documentation/HyperSpec/Body/c_iterat.htm
• http://www.lispworks.com/documentation/HyperSpec/Body/06_a.htm

o altre strutture di dati:

• http://www.lispworks.com/documentation/HyperSpec/Body/t_vector.htm

Answer 2

Stai cercando ricorsione di coda. Al momento la funzione è definita come

(defun my-length (list) 
    (if list 
    (1+ (my-length (cdr list))) 
    0)) 

Si noti che dopo my-length stessa ha chiamato, ha bisogno di aggiungere uno al risultato prima di passare tale valore alla sua funzione di chiamata. Questa necessità di modificare il valore prima di restituirlo significa che è necessario allocare un nuovo stack frame per ogni chiamata, lo spazio utilizzato è proporzionale alla lunghezza dell'elenco. Questo è ciò che causa uno stack overflow su lunghi elenchi.

È possibile riscrivere in modo da utilizzare una funzione di supporto

(defun helper (acc list) 
    (if list 
    (helper (1+ acc) (cdr list)) 
    acc)) 

(defun my-length (list) 
    (helper 0 list)) 

la funzione di supporto richiede due parametri, un parametro accumuloacc, che memorizza la lunghezza della lista fino ad ora, e un elenco list che è la lista di cui stiamo calcolando la lunghezza.

Il punto importante è che helper viene scritto in modo ricorsivo, il che significa che chiamare se stesso è l'ultima cosa che fa. Ciò significa che non è necessario allocare un nuovo stack frame ogni volta che la funzione chiama se stesso - dal momento che il risultato finale verrà passato solo a monte della catena di frame dello stack, è possibile farla franca sovrascrivendo il vecchio stack frame con una nuova, quindi la tua funzione ricorsiva può operare in uno spazio costante.

Questa forma di trasformazione del programma - da una definizione ricorsiva (ma non a coda ricorsiva) a una definizione equivalente utilizzando una funzione di helper ricorsiva in coda è un idioma importante nella programmazione funzionale - uno che vale la pena trascorrere un po 'di tempo comprensione.

Answer 3

TCO (ottimizzazione chiamata coda) nel CLISP utilizzando l'esempio da Chris Taylor:

[1]> (defun helper (acc list) 
     (if list 
      (helper (1+ acc) (cdr list)) 
      acc)) 

(defun my-length (list) 
    (helper 0 list)) 

HELPER 

Ora compilarlo:

[2]> (compile 'helper) 
MY-LENGTH 
[3]> (my-length (loop repeat 100000 collect t)) 

*** - Program stack overflow. RESET 

Ora, al di sopra non funziona. Impostiamo il livello di debug basso. Ciò consente al compilatore di eseguire il TCO.

[4]> (proclaim '(optimize (debug 1))) 
NIL 

Compilare nuovamente.

[5]> (compile 'helper) 
HELPER ; 
NIL ; 
NIL 
[6]> (my-length (loop repeat 100000 collect t)) 
100000 
[7]> 

Opere.

Consentire al compilatore Common Lisp di eseguire il TCO è spesso controllato dal livello di debug. Con un livello di debug elevato, il compilatore genera un codice che utilizza uno stack frame per ogni chiamata di funzione. In questo modo è possibile tracciare ogni chiamata e visualizzarla in un backtrace. Con un livello di debug più basso il compilatore può sostituire le chiamate tail con i salti nel codice compilato. Questi chiamano quindi non verranno visualizzati in un backtrace, il che di solito rende più difficile il debug.

Answer 4

(DEFUN nrelem(l) 
    (if (null l) 
     0 
     (+ (nrelem (rest l)) 1) 
))