Laborator 4—Implementarea imp.ml in OCaml.txt

# evaluate (test_config 10);;
- : e * (l * int) list = (Skip, [("x", 0); ("y", 55)])
Sintaxă abstractă

Putem observa că limbajul IMP este un fragment al limbajului OCaml.  De exemplu, putem scrie cu ușurință o expresie OCaml care să corespundă programului test_pgm:

y := 0 ;
while 1 <= !x do
   y := !y + !x;
   x := !x + -1
done
Pentru a inițializa locațiile x și y și pentru a putea vizualiza „starea memoriei“ la sfârșitul execuției, putem îmbrăca acest program în felul următor

 let x = ref 10
 and y = ref 0
  in y := 0 ;
     while 1 <= !x do
       y := !y + !x;
       x := !x + -1
     done
 ; [("x",!x);("y",!y)]
Partea de sus crează locațiile x și y, inițializate cu 10 și respectiv 0. Cuvântul cheie in declară că înițializările sunt vizibile doar în expresia care urmează.  Partea de jos compune programul cu o expresie care se va evalua la starea finală a memoriei programului văzută ca listă.

Dacă dorim să putem varia starea memoriei inițiale, putem crea o funcție de test:

let test n =
  let x = ref n
  and y = ref 0
  in y := 0 ;
     while 1 <= !x do
       y := !y + !x;
       x := !x + -1
     done
     ; [("x",!x);("y",!y)]
Această funcție ia ca parametru un număr n și îl inițializează pe x cu n în programul de mai sus.

În continuare ne folosi de această dualitate între IMP și un fragment al OCaml în sens invers:  vom scrie programe OCaml în fragmentul corespunzător lui IMP și le vom transforma apoi în programe IMP folosind sintaxa abstractă.

Exerciții

1.  a) Scrieți o expresie OCaml care să reprezinte un program IMP pentru înmulțirea a două numere aflate în locațiile x și y, punând rezultatul într-o locație z. Definiție o funcție inmulteste cu două argumente întregi asemănătoare funcției test de mai sus care ne permite testarea programului.

# inmulteste 7 8;;
- : (string * int) list = [("x", 0); ("y", 8); ("z", 56)]
b) Definiție o expresie inmulteste_pgm care să reprezinte programul de la punctul (a) folosind sintaxa abstractă IMP.  Scrieți o funcție inmulteste_config (cu două argumente) asemănătoare funcției test_config care crează configurația corespunzătoare programului inmulteste_pgm inițializănd valorile locațiilor x și y folosind argumentele date.

# evaluate (inmulteste_config 3 5);;
- : e * (l * int) list = (Skip, [("x", 0); ("y", 5); ("z", 15)])
2*. a) Folosind programul de la punctul 1 (a) ca subprogram, scrieți o expresie OCaml care să reprezinte un program IMP care se evaluează la factorialul unui număr aflat într-o locație n folosind locațiile x, y, z pentru înmulțire și o locatie suplimentară f pentru calcule intermediare.  Definiți o funcție fact cu un argument întreg asemănătoare funcției test din introducere care ne permite testarea programului

# fact 10;;
- : (string * int) list = [("n", 1); ("f", 3628800); ("x", 0); ("y", 3628800); ("z", 3628800)]
b) Definiție o expresie fact_pgm care să reprezinte programul de la punctul (a) folosind sintaxa abstractă IMP.  Scrieți o funcție fact_config (cu un argumente) asemănătoare funcției test_config sin introducere care crează configurația corespunzătoare programului fact_pgm inițializănd valoarea locației n folosind argumentele date și celelalte locații cu 0.

evaluate (fact_config 10);;
- : e * (l * int) list = (Int 3628800,  [("n", 1); ("f", 3628800); ("x", 0); ("y", 3628800); ("z", 3628800)])
Îmbogățirea Limbajului

Deși putem calcula orice cu limabjul IMP (sau, cel puțin, factorialul unui număr), limbajul IMP e cam sărac.  În continuare vom încerca să-l mai îmbogățim.

Exerciții

1. Adăugați la semantica limbajului IMP operația de înmulțire (constructor Mul).  

Indicație (luați ca model operația de adunare)

2. Adăugați la semantica IMP operația de incrementare (constructor PlusPlus) care incrementează valoarea de la o locație dată, întorcând valoarea dinaintea incrementării ( x++ din C ). Scrieți (rescrieți) programul care calculează factorialul folosind operația de incrementare.

Soluție posibilă:  rescrieți PlusPlus într-o expresie IMP folosind operatorii existenți.