Esercitazione PR2
Venerdì 23 novembre 2018

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 )
    
    Uuna 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.
    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 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.