Implementazione dell'inteprete Scheme
Introduzione - Analisi lessicale - Analisi sintattica - Valutazione - Estensione - Demo

Valutazione in Scheme

    Il valutatore può essere realizzato secondo una fra le seguenti due metodologie principali (cfr ling98exp.htm):

    La metodologia funzionale è preferibile in quanto solitamente un linguaggio è caratterizzato da un'unica grammatica e molteplici funzioni di interpretazione. Tuttavia sarebbe opportuno mantenere i vantaggi della programmazione ad oggetti.
    Una terza possibilità, nata per conciliare metodologia funzionale e programmazione ad oggetti è il Visitor. Il pattern Visitor prevede la creazione di una oggetto, il Visitor, che ha il compito di effettuare la valutazione. In esso si definiscono tanti metodi quante sono le classi della gerarchia e ciascuno si occupa della valutazione degli oggetto della classe corrispondente. Tutte le classi vengono poi dotare di un metodo, che può essere chiamato accept() e che riceve come parametro l'oggetto Visitor: chiamando questo metodo si richiede all'oggetto di valutarsi. L'oggetto in realtà si limita a richiamare dal metodo accept il metodo corrispondente alla sua classe all'interno del Visitor che gli è stato passato, metodo che potremo chiamare visit_nomeDellaClasse() o semplicemente visit(). Inoltre passa se stesso a questo metodo. In questo modo il Visitor effettua la valutazione. Questa tecnica di programmazione si chiama double dispatch.
    L'interprete Scheme presentato in questa relazione segue proprio il pattern Visitor. Però non ha una gerarchia completamente specializzata come già si è osservato nella precedente pagina a proposito della classe ConsSexp. Si è detto in quell'occasione che la soluzione adottata e quella alternativa di utilizzare una classe diversa per ogni operatore presentano entrambe vantaggi e svantaggi. Vediamo ora quali sono:     Conclusioni:     La nostra scelta è stata per utilizzare la sola classe ConsSexp. Tale scelta è in effetti supportata anche dall'osservazione che il Lisp è stato pensato come list processor, dunque l'unica struttura essenziale è la lista e quindi esistono solo delle cons, oltre atomi e nil (elemento nullo). Tutto deve essere una lista: non c'è distinzione tra dati e funzioni. In verità la lista stessa è definita come coppia e quindi non aggiunge alcuna capacità computazionale ad un linguaggio che già possiede il concetto di coppia. Tuttavia ciò su cui qui preme porre l'attenzione è la rappresentazione esterna di coppia e lista. Essendo la lista una coppia sarebbe naturale fornirne una rappresentazione esterna uguale a quella della coppia. Per esempio la lista (1 2 3) potrebbe essere rappresentata come (1 . (2 . (3 . nil))). Questa è però una rappresentazione un po' scomoda e poco pratica e quindi non la si utilizza. La rappresentazione esterna è quindi (1 2 3). La costruzione di quella lista avviene con il seguente codice:
    (cons 1 (cons 2 (cons 3 nil))).
Il nil finale fa sì che quella creata sia effettivamente una lista, ovvero una vera lista, tant'è che quella struttura è chiamata true list. Se invece si scrive:
    (cons 1 (cons 2 3))
si crea una struttura chiamata dotted list, che in Lisp viene stampata come segue:
    (1 2 . 3).
True list e dotted list sono stampate in modo analogo, l'unica differenza è l'inserimento nelle dotted di un punto prima del secondo elemento dell'ultimo coppia. Quindi il punto serve semplicemente a differenziare le rappresentazioni esterne di true e dotted list. Ne segue che l'utilizzo del punto non è necessario in input e la possibilità di utilizzarlo è data solo per uniformità con l'output scelto.
    Un'altra possibile rappresentazione esterna poteva essere quella di stampare tutte le strutture composte usando il formato lista ed esplicitando l'evetuale nil finale. Ovvero la true list sarebbe rappresentata come (1 2 3 nil), mentre la dotted list si scriverebbe come (1 2 3). La true list sarebbe quindi quella struttura composta il cui ultimo elemento è un nil, in tutti gli altri casi le strutture composte sarebbero delle dotted list (la coppia (cons a b) invece che (a . b) si scriverebbe (a b)). Così facendo si eviterebbe l'utilizzo del punto sia in input che in output e la grammatica diventerebbe LL(1) senza bisogno di trasformazioni: 
        Program  ::=    Sexp            Program
        Sexp     ::=    AtomeSexp       ConsSexp
        AtomSexp ::=    Ident
        ConsSexp ::=    ( SexpList
        SexpList ::=    )               Sexp SexpList
        Ident    ::=    <lettera>       <lettera> Ident
     Completato il discorso sul problema dell'utilizzo del punto elenchiamo ora le varie primitive e gli operatori implementati nell'interprete Scheme costruito:
 
Nome Note
quote consente di denotare un simbolo senza che venga valutato
' (apice) 'x equivale a (quote x): è stato introdotto per comodità
cons costruisce una coppia, ovvero una struttura composta
car seleziona la testa di una struttura composta
cdr seleziona la testa di una struttura composta
cond istruzione condizionale
atom verifica se il suo argomento è un atomo
null verifica se il suo argomento è un nil
lambda lambda expression;
consente di denotare delle chiusure lessicali (in Lisp la lambda expression è una notazione e non una forma e valutata dà errore perché all'interno dell'interprete Lisp la lambda non è ricosciuta come una funzione predefinita, invece in Scheme essa è una forma, ovvero una s-expression, e valutata restituisce una chiusura lessicale)
define non necessaria ma utile: crea un binding permanente
defmacro per la definizione di macro
` (backquote) macro che consente di costruire strutture complesse apartire da uno scheletro: la struttura segue il backquote viene restituita così com'è eccetto dove compare la virgola
, (comma) macro:  la forma che segue la virgola viene valutata e l'oggetto restituito viene inserito nella struttura
,@ (comma-at) macro:  la forma che segue il comma-at viene valutata per produrre una lista di oggetti che viene inserita senza parentesi nella struttura
eq ed equal confrontano oggetti
eval rende disponibile all'utente la funzione di valutazione Scheme
set e setq per assegnamento di valori a variabili
let zucchero sintattico per introdurre legami lessicali
print e prin1 stampa e stampa senza "NewLine"
read consente di leggere dallo standard input
file consente la consultazione di un file che si trovi nella directory padre della directory Interpreter
+ - * / operatori aritmetici
> = < operatori relazionali

Osservazione
    L'interprete mette a disposizione la primitive lambda, define e defmacro così che sia possibile definire nuove operazioni ed associare ad esse un simbolo. Per esempio se non esistesse la primitiva let sarebbe comunque possibile definirla facendo uso delle primitive esistenti. Per ogni forma let esiste una lambda expression equivalente. Allora si potrebbe pensare di definire la let usando la primitiva lambda. Tuttavia se si prova a farlo ci si accorgerà che tale definizione non è possibile se si vuole usare la sola lambda. Per la definizione della let è necessaria la defmacro, infatti per utilizzare la let si scrive:
    (let ((a '3)) (+ a a))
ma se la let fosse una lambda ((a '3)) e (+ a a) verrebbero valutati all'inizio (valutazione degli argomenti della funzione let).
Sarebbe dunque necessario scrivere:
    (let '((a '3)) '(+ a a))
e non è ciò che vogliamo.

La soluzione che fa uso di defmacro può essere (usiamo mylet perché in realtà la let esiste già):

(defmacro mylet( varList  body )
    `((lambda ( ,@(cars varList ) )
    ,body)  ,@(cdrs varList ) ))

(define cars (lambda (L)
    (cond    ((null L) nil)
                (t (cons (car (car L)) (cars (cdr L)))))))
(define cdrs (lambda (L)
    (cond    ((null L) nil)
                (t (cons (car (cdr (car L))) (cdrs (cdr L)))))))

A questo punto si può effettuare la chiamata:

    (mylet ((a (+ 1 2) )(b 4)) (+ a b))

ottenendo il risultato atteso, cioè 7. Dopo questa chiamata (macro-call) le variabili a e b non sono più legate, tant'è che se si chiama la valutazione di a o b si ottiene un'eccezione di identificatore sconosciuto. Allo stesso modo se prima di effettuare la macro-call si definisce il simbolo "a" al valore 10 (con l'istruzione "(define a 10)" ) e dopo la macro-call si chiede il valore di a si ottengono sempre i risultati attesi, ovvero:

(define a 10)                                             ;produce il bind (a . 10) e lo aggiunge all'environmente globale
(mylet ((a (+ 1 2))(b 4)) (+ a b))                ;produce 7
a                                                            ;produce 10

    A tal proposito sarebbe da notare che nell'esempio sopra la mylet associa un valore al simbolo a dopo che questo è stato legato da una define ad un altro valore. La define definisce una costante, ovvero indica all'interprete che il simbolo "a" è una costante che denota il valore 10. Allora poteva essere corretto vietare l'utilizzo dello stesso simbolo "a" per associargli altri legami tramite per esempio la let. Si è però preferito lasciare questa possibilità. Non solo, ma è non è stata vietata neppure la ridefinizione tramite una nuova define. In questo caso viene però generato un warning:

>    (define a 3)
restituisce a

>    (define a 3)
produce:

Warning: define redefines identifier a. Old value=3
The overwriting is supported only to correct typing errors.
If you intend to change the value of a variable you'd better use "set" and "setq".
e restituisce a

>    a
restituisce 5