Qual è l'approccio migliore per una funzione ottimizzata per la coda per il calcolo della lunghezza di un elenco?

Question

Ecco un esempio di un poster del forum, non so dire se questa coda sia stata ottimizzata. Inoltre, qualcuno potrebbe dare una descrizione dei laici di come una versione ottimizzata per la coda avrebbe la meglio sulla versione normale.

(defun mylength (s)
  (labels ((mylength-inner (s x)
            (if (car s) (mylength-inner (cdr s) (+ x 1)) x)))
          (mylength-inner s 0)))

Una versione non ottimizzata per la coda?

(defun l (s) (if (car s) (+ 1 (l (rest s))) 0))

Answer 1

Una funzione può essere ottimizzata per le chiamate in coda se restituisce una chiamata diretta a se stessa o nessuna chiamata a se stessa. La funzione mylength-inner restituirà x o (mylength-inner (cdr s) (+ x 1)) , e quindi può essere ottimizzato per la coda.

Ciò significa che il compilatore può trasformarlo in un ciclo invece di chiamare la funzione in modo ricorsivo. Restituisci x, oppure assegna (cdr s) a s, incrementa x e ricomincia da capo. (Lo standard Scheme richiede che le implementazioni siano in grado di eseguire questa ottimizzazione, mentre lo standard Common Lisp lo lascia all'implementazione. Naturalmente, questa ottimizzazione è una cosa molto utile, quindi la maggior parte delle implementazioni lo farà.)

Nella versione non ottimizzata, l non solo restituisce una chiamata a l, ma piuttosto il risultato di una chiamata a l con una aggiunta. Ciò significa che non può essere direttamente trasformato in un loop, quindi dovranno essere effettuate tutte le chiamate di funzione.

Supponiamo che il compilatore volesse trasformare l in un ciclo. Non ci sono problemi con l'assegnazione di (resto s) a s, ma dove inserisce (1 + ...) ?

Answer 2

FWIW, CL non garantisce che ottimizzerà le chiamate in coda; dipende dall'implementazione. SBCL lo supporta. Questo è diverso dallo Schema, dove le specifiche richiedono che il compilatore elimini le chiamate di coda. Se non lo fai, non sei Scheme.

Inoltre, la ricorsione della coda è piuttosto non idiomatica in CL. Abbiamo una macro loop , quindi usala :)

Answer 3

Le chiamate di coda possono essere ottimizzate per non aver bisogno di spazio aggiuntivo nello stack di chiamate e richiede che l'ultima operazione nella funzione sia la chiamata ricorsiva, che sembra essere il caso nell'esempio di provenienza del forum. L'ultima operazione nella versione non di coda è un'aggiunta, quindi la chiamata ricorsiva richiede un proprio frame di stack.

Questo segue un modello semplice, definisce una funzione interna che accetta un argomento accumulatore in aggiunta agli argomenti delle funzioni esterne e accumula la tua risposta mentre procedi. Quando arrivi alla fine, dai il valore accumulato.

Probabilmente c'è una spiegazione migliore qui:

http: // mitpress.mit.edu/sicp/full-text/book/book-ZH-11.html#%_sec_1.2.1

Answer 4

Schema "manuale" " esempio di lunghezza dell'elenco sarebbe qui: http: //www.scheme. com / tspl3 / start.html #. / start: h8 cerca " lunghezza. "