Come viene implementato "letrec" senza usare "set!"?

Question

Come è possibile implementare letrec senza utilizzare set!?

Mi sembra che set! sia un costrutto di programmazione imperativo, e che usandolo si perdono i vantaggi della programmazione funzionale.

Answer 1

So che di solito chiediamo che il contenuto sia copiato ma non c'è una risposta breve alla tua domanda. http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Answer 2

No. Solo perché una funzionalità è implementata con codice imperativo dietro le quinte, ciò non rende la funzionalità imperativa. Le nostre macchine informatiche sono tutte indispensabili; quindi a un certo punto tutti i codici funzionali devono essere implementati mediante la traduzione in un codice imperativo!

La cosa fondamentale da capire è questo: la programmazione funzionale riguarda interfaccia, non implementazione. Un pezzo di codice è funzionale se il codice stesso non è in grado di osservare gli effetti collaterali, anche se gli effetti collaterali si verificano effettivamente dietro le quinte. Ad esempio, se si verifica il valore della stessa associazione della stessa variabile più volte, si otterrà lo stesso valore, anche se tale valore, dietro le quinte, è stato inserito da un valore di set!.

Nel caso di letrec, c'è un po 'fermo qui: il risultato è indefinito se la valutazione di una delle associazioni nel letrec provoca un altro per essere derefenced. Quindi, il risultato di questo codice è indefinito:

(letrec ((foo bar) 
     (bar 7)) 
    (cons foo bar)) 

Il valore della foo nel corpo del letrec è indefinito. Il risultato della seguente, invece, è definita:

(letrec ((foo (lambda() bar)) 
     (bar 7)) 
    (cons (foo) bar)) 

Questo perché la valutazione della lambda cattura il riferimento alla barra, ma il valore reale non viene guardato fino alla chiusura viene eseguito nel corpo.