Nella macchina SECD come funziona "rap"?

Question

Sto scrivendo un simulator of the SECD machine in C# guidato da description on Wikipedia. Ho completato le operazioni di base, ma non sono sicuro di come implementare l'istruzione rap.

su Wikipedia che dice di rap:

rap funziona come ap, solo che si sostituisce un evento di un ambiente fittizio con quello attuale, rendendo così funzioni ricorsive possibili

E per ap dice:

aps una chiusura e un elenco di valori di parametro dallo stack. La chiusura viene applicata ai parametri installando il suo ambiente come quello corrente, spingendo l'elenco dei parametri di fronte a quello, cancellando lo stack e impostando C sul puntatore della funzione di chiusura. I precedenti valori di S, E e il successivo valore di C vengono salvati sul dump.

Qui è la mia realizzazione di ap

public void ap() 
    { 
     Push(S, ref D); 
     Push(E, ref D); 
     Push(C, ref D); 
     List closure = Pop(ref S); 
     List paramlist = Pop(ref S); 
     E = closure.Tail; 
     Push(paramlist, ref E); 
     C = closure.Head; 
     S = List.Nil; 
    } 

noti che List è la mia realizzazione di uno stile di cella Lisp "contro".

Ciò che mi confonde è esattamente come rap differisce da ap? Ad esempio cosa succede esattamente al registro ambientale (E)? Trovo la definizione di Wikipedia un po 'ambigua, e non sono stato in grado di trovare nient'altro che lo spieghi bene.

Answer 1

SECD non è una coda ricorsiva, sebbene sia possibile creare a tail recursive SECD machine (PDF).

L'istruzione AP viene utilizzata per compilare un binding "let" mentre l'istruzione RAP viene utilizzata per compilare un binding "letrec".

"letrec" è diverso da "let" perché è possibile "vedere" l'ambiente in cui è definita la funzione ricorsiva, in modo da poterla chiamare in modo ricorsivo (quindi, ad esempio, si definisce una funzione "fattoriale" e può chiamarlo nel corpo della funzione).

RAP modifica l'ambiente chiamando rplaca (simile a setcar! In Schema). Una precedente istruzione DUM aggiunge all'ambiente un'auto "fittizia" (che non viene mai utilizzata) e RAP rimuove l'auto "fittizia" nell'ambiente e la sostituisce con quella appropriata.

transizioni di stato sono in questo modo:

 
((c'.e')v.s) e    (AP.c) d   => 
NIL   (v.e')   c'  (s e c.d) 

((c'.e')v.s) (?.e)   (RAP.c) d   => 
NIL   (setcar! e',v) c'  (s e c.d) 

Consulta anche Revisiting SECD and the power of Lisp, citando:

L'istruzione RAP è usato per supportare chiamate di funzione ricorsive e opere di sostituzione di un ambiente fittizio precedentemente creata in pila , chiamato OMEGA, con uno che contiene tutte le funzioni che sono visibili nell'ambito ricorsivo. La specifica utilizza RPLACA per denotare tale operazione di sostituzione, ed è quello che abbiamo usato anche nella nostra implementazione Lisp di SECD: ...

e

Quando si cerca di implementare RAP in Erlang, mi sono bloccato perché non ci sono operazioni distruttive sulle liste. Neanche nell'API standard, né apparentemente nell'API di sistema. Quindi, l'Erlang SECD è bello, solo che non funziona.

Answer 2

Si dovrebbe davvero prendere una copia del meraviglioso libro di Peter Henderson "Applicazione e programmazione della programmazione funzionale". In esso descrive meticolosamente e costruisce una macchina SECD e Lispkit Lisp.

Answer 3

Oltre all'eccellente risposta accettata, volevo fornire una spiegazione più dettagliata del motivo per cui è richiesto rap.

L'ambiente (lo E in SECD) memorizza tutte le entità persistenti (funzioni, costanti, variabili, ecc.). E è essenzialmente una pila di elenchi. Le cose nello E vengono caricate nello stack S e quindi eseguite o utilizzate dai comandi in C. Tutto in E viene fornito un id in modo che possa essere fatto riferimento in seguito. Questo ID è in genere una tupla (x,y), dove x rappresenta la posizione dell'elenco nello stack e rappresenta una posizione in tale elenco.

In una chiamata di funzione tipica, una nuova lista viene spinto E e ora tutte le variabili locali possono avere ID come (|E|, y), dove |E| indica la dimensione di E. Questo è molto problematico per le funzioni ricorsive, tuttavia, poiché le dimensioni dello stack aumentano con ogni chiamata di funzione, quindi non c'è modo di assegnare gli ID utilizzabili alle variabili locali.

Per risolvere questo problema, rap fa la maggior parte delle cose ap fa, ma invece di spingere un nuovo elenco nello stack ambiente, sostituisce tutto ciò che è a capo del E con il nuovo elenco ambiente.