<expr> ::= <valoare> | <variabila> | <expr> + <expr> | <expr> * <expr> | (<expr>)
   <variabila> ::= string
   <valoare> ::= orice
   
   <prog> ::= <variabila> = <expr> | if <expr> then <prog> else <prog> | <prog> ; <prog> | return <variabila>

1. Definiti un tip de date care codifica expresii <expr> generate de gramatica BNF de mai sus
   • Tipul definit de voi va fi monomorfic sau polimorfic?
2. Inrolati tipul vostru in clasa Show. Definiti explicit o reprezentare (usor de urmarit)
3. Definiti o expresie formata cu intregi (care va fi folosita ulterior pentru testare)
4. Definiti un tip care reprezinta o multime de asocieri ale unor variabile la valori. Obiecte avand un astfel de tip sunt interpretari pentru o multime de variable. Interpretarea pentru o variabila consta intr-o valoare.
5. Definiti o functie eval care determina rezultatul unei expresii, pe baza unei interpretari:
   • scrieti signatura pentru eval
   • realizati implementarea efectiva
6. Definiti un tip de date care codifica expresii <prog> generate de gramatica BNF de mai sus.
   • Tipul definit de voi va fi monomorfic sau polimorfic?
7. Inrolati tipul definit de voi in clasa Show.
8. Definiti o clasa (type-class) Evaluable care modeleaza faptul ca o valoare de tip container poate fi evaluata la o valoare de tipul continut de containerul respectiv.
   • Clasa pune la dispozitie o singura operatie eval care generalizeaza operatia eval definita pentru expresii
   • Realizati o instanta a Evaluable pentru constructorul de tip al <expr>. Observati faptul ca implementarea procedurii de evaluare a fost realizata anterior.
   • Realizati o instanta a Evaluable pentru constructorul de tip al <program>. Mai exact, implementati evaluarea unui program.
     • In implementare, observati ca interpretarea se modifica pe masura ce programul este evaluat.
     • Asadar, aveti nevoie de o functie auxiliara, care construieste o interpretare, pe baza unui program

Solutii