Come un'immagine vale più di mille parole, scriviamo insieme un interprete! Certo, molto semplice. Usiamo OCaml per questo, ma se non conosci OCaml, questo va bene, perché scriveremo pochissimo codice e commentarlo comunque.
Per prima cosa definiamo cos'è un programma per noi. Consideriamo un linguaggio molto semplice, che consente di stampare testo, aggiungere numeri e testare se un numero è zero con un'istruzione if:
type statement =
| Print of string
| If of expr * statement * statement
| Sequence of statement list
and expr =
| Constant of int
| Plus of expr * expr
Il codice sopra è una dichiarazione del tipo e definisce qual è la nostra idea di programma. Definisce una forma simbolica astratta per i programmi - in contrapposizione alla forma tetual concreta - che è facile da manipolare in OCaml. Questa definizione di tipo è una semplice traduzione della descrizione inglese di cosa sia un programma, con l'aggiunta di una sequenza, per eseguire più operazioni. (Se rimuoviamo le operazioni Plus
e Sequence
otteniamo praticamente il linguaggio più piccolo possibile dimostrando un'istruzione If
, ma ho ritenuto che potesse essere un po 'troppo noioso!)
Nota sulla vita Nella vita reale, un programma contiene molte annotazioni. Un aspetto importante è che gli elementi del programma sono tipicamente annotati con la loro posizione in termini di file, riga, colonna, che è utile per segnalare errori.
Possiamo già scrivere un programma di intrattenimento nella nostra lingua:
let program = Sequence([
Print("Hello, world!");
If(Plus(Constant(1),Constant(0)),
Print("One is the truth"),
Print("One is a lie"));
Print("Oh, that was a tough one!");
])
Questo dovrebbe stampare il testo Hello, world!
per compiacere Dennis, quindi calcolare 1 + 0 e confrontare il risultato con 0 - come per la definizione di If
nella nostra lingua - se il risultato è diverso da 0, quindi il primo viene eseguito il branch e viene stampato il messaggio perlish One is the truth
, altrimenti viene stampato anche il messaggio perlish One is a lie
. Dopo una sfida così difficile, il nostro computer teso condividerà le sue sensazioni Oh, that was a tough one!
.
Nota di vita reale Nel mondo reale, è necessario scrivere un parser per tradurre il testo normale in un programma astratto come quello tenuto dalla variabile program
. Possiamo usare lex e yacc per questo e le loro varie derivate.
Ora scriviamo un interprete per la nostra lingua. (Se ti sei addormentato, svegliati ora, la risposta vera alla domanda sarà presto presentata!)
let rec interpreter = function
| Sequence(hd::tl) -> interpreter hd; interpreter(Sequence(tl))
| Sequence([]) -> ()
| Print(message) -> print_endline message
| If(condition, truebranch, falsebranch) ->
(* The answer to the question is here! *)
if (eval condition) <> 0 then
interpreter truebranch
else
interpreter falsebranch
and eval = function
| Constant(c) -> c
| Plus(a,b) -> (eval a) + (eval b)
La maggior parte di noi probabilmente non ha familiarità con OCaml, quindi passiamo delicatamente attraverso questa parte di codice:
let rec interpreter = function
| Sequence(head::tail) -> interpreter head; interpreter(Sequence(tail))
(* To interpret a list of statements, we interpret the first
and then interpret the tail of the list. *)
| Sequence([]) -> ()
(* To interpret an empty list of statements, we just do nothing.
Fair enough, right? *)
| Print(message) -> print_endline message
(* To print a message, we use the host-language printing facility. *)
| If(condition, truebranch, falsebranch) ->
(* The answer to the question is here!
We first evaluate the condition, with the eval function below
and use the host-language if facility to take the decision
of recursively calling the interpreter on the truebranch or
the falsebranch. *)
if (eval condition) <> 0 then
interpreter truebranch
else
interpreter falsebranch
and eval = function
| Constant(c) -> c
(* Constants evaluate to themselves *)
| Plus(a,b) -> (eval a) + (eval b)
(* A Plus statement evaluates to the sum of its parts. *)
Ora eseguiamo il programma:
let () = interpreter program
che causa l'output
Hello, world!
One is the truth
Oh, that was a tough one!
Vuoi provarlo, copia gli snippet di programma in un file interpreter.ml
ed esegui con ocaml dal prompt della shell:
% ocaml imterpreter.ml
Conclusione Quando scriviamo un interprete usando una rappresentazione astratta intermedia del programma come in questo piccolo esempio. L'istruzione If
è facilmente implementabile in termini di condizionali nella lingua dell'host. Altre strategie sono possibili, è perfettamente immaginabile compilare il programma "al volo" e nutrirlo con una macchina virtuale. (Alcune persone sostengono che non c'è essenzialmente alcuna differenza tra i due approcci.)