Come può Lisp produrre un processo iterativo da una procedura ricorsiva?

Question

Come può Lisp produrre un processo iterativo da una procedura ricorsiva?

#1 da (6 voti)

3

Sto iniziando a imparare Lisp, usando il libro SICP. Gli autori menzionano che una procedura (cioè la funzione) può essere ricorsiva o iterativa. Inoltre, il processo che tali procedure genereranno sarà anche ricorsivo o iterativo e, sorprendentemente, una procedura ricorsiva a volte può generare un processo iterativo.

L'esempio fornito è la procedura fattoriale, che è una procedura ricorsiva, ma che genera un processo iterativo:

(define factorial n)
    (iter 1 1 n))

(define (iter product counter max-count)
    (if (> counter max-count)
        product
        (iter (* counter product)
              (+ counter 1)
              max-count)))

Ed ecco una citazione dal libro:

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. The implementation of Scheme we shall consider does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure.

Domanda : ho compreso i principi coinvolti (cioè il cosa) ma non capisco ancora come l'interprete / compilatore Lisp genererà un processo iterativo da una funzione ricorsiva, potendo calcolarlo usando lo spazio costante e perché molte altre lingue non sono in grado di farlo.

lisp recursion c sicp

posta Daniel Scocco 03.02.2014 - 12:14

fonte

1 risposta

Leggi altre domande sui tag lisp recursion c sicp

Impostazioni dell'applicazione tramite iniezione del costruttore o contesto ambientale OOP cosa si intende per comunicazione oggetto-oggetto

score 6 · Accepted Answer

Essenzialmente con la ricorsione della coda, il problema con la ricorsione in generale è che ogni chiamata di funzione ottiene il proprio frame dello stack. In questo stack frame memorizzi tutte le tue variabili locali e quant'altro.

Quindi se si esegue una funzione come

  int fact(int n){
      if(n == 0)
           return 1;
      return n * fact(n-1);
  }

fact è chiamato n volte, allocando n stackframes. Se n è grande, è un lotto di memoria.

C'è comunque speranza, quando la nostra funzione è strutturata nella forma

 int f(int x){
     ...
     return g(foo); // Function call is in the final position
 }

Quindi possiamo buttare via il frame dello stack di f prima di inserire g , questo significa che non assegneremo troppi fotogrammi fintanto che usiamo chiamate tail tail. Compilerà in realtà a ciascuna funzione che ha la propria etichetta e jmp ing alla coda chiamata function, molto veloce.

Tutti gli schemi sono ricorsivi in coda, come lo sono le implementazioni di linguaggi più funzionali come quelli di SML, OCaml, Haskell, Scala e (tipo di) Clojure. Ciò significa che ogni volta che si ha una chiamata di funzione come ultima cosa assoluta nella propria funzione, non assegnerà un nuovo stack frame. Usando questo, possiamo scrivere un ciclo do-while come segue in Schema

  (define (do-while pred body)
     (body)                   ;; Execute the body
     (if (pred)               ;; Check the predicate
         (do-while pred body) ;; Tail call
         '()))                ;; Exit

E questo funziona esattamente nella stessa quantità di spazio del codice imperativo equivalente :) Abbastanza elegante.

Nota, Ottimizzazione chiamata coda / = Ricorsione coda

Un equivoco comune è che il TCO è strettamente limitato al caso in cui una funzione coda si chiama da sola. Questo è un sottoinsieme specifico di TCO e ciò che fornisce la maggior parte delle lingue JVM. Linguaggi come Scheme che non sono limitati dalle limitazioni della JVM sono correttamente TCO'd rendendo possibile dire scrivere un DFA che verrà eseguito in memoria costante mediante chiamate tail tra stati.