Esercitazione PR2
Giovedì 24 novembre 2016

TESTI

[1] Si consideri la seguente grammatica, che definisce un semplice linguaggio funzionale

(Programma)       Program Decl => Exp

(Dichiarazioni)   Decl ::= ε | fun Ide(Ide) {Exp} ; Decl

(Identificatori)  Ide ::= <definizione standard>

(Interi)          Int ::= <definizione standard>

(Booleani)        Bool ::= <definizione standard>

(Operatori)       Op ::= + | - | * | = | <=

(Espressioni)     Exp ::= Ide | Int | Bool 
                          | Exp and Exp | Exp or Exp | not Exp
                          | Op( Exp, Exp )
                          | if Exp then Exp else Exp
                          | Ide( Exp )

Una dichiarazione di funzione ha la forma fun f ( x ) { expr } dove f è il nome della funzione, x il parametro formale, ed expr una espressione dove x può comparire libera.
Si noti che, come in C, le dichiarazioni di funzioni occorrono solo al "top-level" e definiscono quindi un ambiente globale nel quale deve esser valutata l'espressione finale del programma.
Si definisca una semantica operazionale mediante regole di inferenza che rispetti le seguenti specifiche

l'applicazione funzionale deve essere valutata con riferimento all'ambiente globale determinato dalle dichiarazioni;
tutte le altre operazioni hanno il significato visto a lezione.

[2] Si verifichi la correttezza della semantica progettando ed eseguendo alcuni casi di test, sufficienti a testare tutti gli operatori.
In particolare, si valuti il seguente programma, tenendo a mente che il risultato deve essere 5

Program fun sub1 (n) { -(n, 1) };
        fun fib (n) { if =(n, 0) or =(n, 1) then n else +(fib(sub1(n)), fib (sub2(n))) };
        fun sub2 (m) { sub1(sub1(m)) }; ε
=>
fib (5)

[3] Si definisca una sintassi astratta per il linguaggio, introducendo opportuni tipi di dati OCaml.
Si definisca un interprete OCaml che corrisponda alla semantica introdotta in precedenza.
Si traducano nella sintassi astratta proposta i casi di test proposti in precedenza, in particolare il programma indicato, e si valutino con l'interprete.

Soluzione: il file interp.