Esercitazione PR2
Giovedì 2 Dicembre 2019

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 ) { exp } dove f è il nome della funzione, x il parametro formale, ed exp 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 3 
    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 (4)
    [3] Si definisca una sintassi astratta per il linguaggio, introducendo opportuni tipi di dati OCaML, e un interprete OCaML che corrisponde alla semantica operazionale introdotta.
    Si traducano poi 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 globaleFun.
    [4] Si estenda la precedente grammatica, in modo da aggiungere anche le definizioni di variabili globali 
    :
(Dichiarazioni)   Decl ::= ε | var Ide {Exp} ; Decl | fun Ide(Ide) {Exp} ; Decl
:
    Una dichiarazione di variabile ha la forma var x { exp } dove x è la variabile e exp l'espressione associata.
    Come in C, lo scope di una variabile è dal momento della sua definizione in avanti, e contribuiscono a definire l'ambiente globale nel quale deve esser valutata l'espressione finale del programma.
    Si definisca una semantica operazionale mediante regole di inferenza che estenda quella vista in precedenza.
    [5] 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 3 
    Program var base { 1 };
        fun sub1 (n) { -(n, base) };
        fun fib (n) { if =(n, 0) or =(n, 1) then n else +(fib(sub1(n)), fib (sub2(n))) };
        fun sub2 (m) { sub1(sub1(m)) }; 
        var test { 4 }
=>
fib (test)
    [6] Si definisca una sintassi astratta per il linguaggio, estendendo quella per la grammatica iniziale.
    Si definisca un interprete OCaML che corrisponda alla semantica introdotta in precedenza, e generalizzi quella proposta per il linguaggio iniziale.
    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 globaleFull.