Una macchina di riduzione per il λ-calcolo con valutazione dei costi

La macchina astratta SECD (Stack, Enviroment, Control, Dump) é un modello di calcolo realizzato da P.J. Landin, per ridurre le espressioni del calcolo. Essa rappresenta un modello base per l’implementazione dei linguaggi funzionali, inoltre, permette di chiarire, meglio di altri modelli, come la valutazione di un linguaggio funzionale si possa riportare ai meccanismi di calcolo tipici dell’architettura tradizionale (Macchina di Turing). ´E bene sottolineare, che tale macchina valuta termini chiusi (programmi). La macchina viene rappresentata dalla quadrupla i cui elementi sono descritti di seguito:
• Lo stack S: viene visto come i registri di una CPU. Esso contiene i risultati parziali e finali del calcolo.
• L’ambiente E: contiene liste di liste di valori da associare alle variabili di un programma. Ogni valore nell’ambiente viene identificato da una coppia di interi in cui il primo elemento individua la sottolista di E da considerare, e il secondo identifica l’elemento di questa sottolista. La coppia viene calcolata durante la fase di compilazione del programma.
• Il controllo C: é un’istruzione del programma SECD in esecuzione.
• Il dump D: é una quadrupla , in cui viene salvato lo stato della macchina. Quest’operazione viene effettuata, per esempio, quando viene invocata una funzione oppure quando viene eseguito un comando condizionale.