Accueil > Enseignement > Anciens cours (avant 2015-2016) > Programmation fonctionnelle (L3, 2013-2014) > Semaine 7 – Interprète d’un mini-langage (2)

Semaine 7 – Interprète d’un mini-langage (2)

mercredi 19 mars 2014, par Pierre

Semaine 7. Après les expressions, les instructions. L’affectation permet de fixer la valeur de variables impératives que l’on a commencé par représenter comme des cases d’un tableau d’entiers, l’état du programme. On améliore ensuite le langage et son interprète, avec également une petite adaptation de l’évaluateur d’expressions, de façon à manipuler des variables par leurs noms (une chaîne de de caractères). Les variables doivent être déclarées et elles ont désormais une portée. Une variable plus locale masque temporairement une variable de même nom déclarée dans un bloc de niveau supérieur.

Première version d’un interprète.

(* à ajouter à la fin du cours 6 *)
type instruction = Printstr of string
                 | Print of expression
                 | Block of instruction list
                 | Affectation of int * expression
                 | While of expression * instruction;;

let rec exec = function
  | Printstr s -> print_string s
  | Print e -> print_int (eval e)
  | Block [] -> ()
  | Block (x::xs) -> exec x;
                     exec (Block xs)
  | Affectation (n, e) when n < 4 && n >= 0 -> etats.(n) <- (eval e)
  | Affectation (n, e) -> raise Segfault
  | While (e, i) as w -> (match (eval e) with
                          | 0 -> ()
                          | _ -> exec i; exec w);;


"x = 10;
 while (x < 40) {
 print x;
 println;
 x = x + 10;
 }";;
let p = Block [
            Affectation (0, Ent 10);
            While ( Inf (Var 0, Ent 40),
                    Block [
                        Print (Var 0);
                        Printstr "\n";
                        Affectation (0, Plus ((Var 0), Ent 10))
                  ])
          ];;

exec p;;

[Non vu en cours]. On peut améliorer un peu ce travail en ne donnant à l’utilisateur de notre code que les déclarations de type et une fonction run, qui prendra en entrée un programme et une taille mémoire sur laquelle exécuter ce programme.
Attention, il y a une question bonus.

(* synthèse du mini-interprète cours 6 et tp 7 *)
type expression = Ent of int
                | Plus of expression * expression
                | Mult of expression * expression
                | Div of expression * expression
                | Moins of expression * expression
                | Opp of expression
                | Egal of expression * expression
                | Sup of expression * expression
                | Inf of expression * expression
                | Var of int (* une variable impérative est une *)
                             (* adresse mémoire *)
;;
 
type instruction = Printstr of string
                 | Print of expression
                 | Block of instruction list
                 | Affectation of int * expression
                 | While of expression * instruction
;;
 
(* erreur mémoire *)
exception Segfault;;
 
(* tout est dans la fonction run *) 
let run p k =
  let etats = Array.make k 0
  in
  let rec eval = function
    | Ent n -> n
    | Plus (e1, e2) -> (eval e1) + (eval e2)
    | Mult (e1, e2) -> (eval e1) * (eval e2)
    | Div (e1, e2) -> (eval e1) / (eval e2)
    | Moins (e1, e2) -> (eval e1) - (eval e2)
    | Opp e1 -> (-1) * (eval e1)
    | Egal (e1, e2) -> (match (eval e1) = (eval e2) with true -> 1
                                                       | false -> 0)
    | Sup (e1, e2)  -> (match (eval e1) > (eval e2) with true -> 1
                                                       | false -> 0)
    | Inf (e1, e2)  -> (match (eval e1) < (eval e2) with true -> 1
                                                       | false -> 0)
    | Var n when n < k && n >= 0 -> etats.(n)
    | Var n -> raise Segfault in
  let rec exec = function
    | Printstr s -> print_string s
    | Print e -> print_int (eval e)
    | Block [] -> ()
    | Block (x::xs) -> exec x;
                       exec (Block xs)
    | Affectation (n, e) when n < k && n >= 0 -> etats.(n) <- (eval e)
    | Affectation (n, e) -> raise Segfault
    | While (e, i) as w -> (match (eval e) with
                            | 0 -> ()
                            | _ -> exec i; exec w)
  in
  exec p;
  etats (* <-- on veut savoir dans quel état le programme termine *)
;;
  
(* essai sur un petit programme *)
"x = 10;
 y = 0;
 println;
 while (x < 40) {
   print x;
   println;
   y = y + x;
   x = x + 10;
 }";;
let p = Block [
            Affectation (0, Ent 10);
            Affectation (1, Ent 0);
            Printstr "\n";
            While ( Inf (Var 0, Ent 40),
                    Block [
                        Print (Var 0);
                        Printstr "\n";
                        Affectation (1, Plus (Var 1, Var 0));
                        Affectation (0, Plus (Var 0, Ent 10))
                  ])
          ]
  and
    taille_memoire = 2
    in
    run p taille_memoire;;
  
(* question bonus : écrire une fonction qui prend en entrée un *)
(* programme (de type instruction) et détermine la taille mémoire *)
(* nécessaire pour l'exécuter sans SegFault *)

Et maintenant les variables ont des noms

Fichier tel qu’élaboré en cours et TD 7.

(* Qu'est ce qu'une variable ? Un enregistrement *)
(* un nom : string *)
(* une valeur mutable de type int *)
type variable = {nom: string; mutable valeur: int};;

(* Qu'est ce que l'état ? *)
(* Une liste de variables au départ la liste vide [] *)
(* lorsqu'on veut manipuler une variable non déclarée ... *)
exception VariableNonDeclaree;;

(* Pour lire la valeur d'une variable. *)
let rec valeur nom etat = match etat with
  | [] -> raise VariableNonDeclaree
  | x::xs when x.nom = nom -> x.valeur
  | x::xs -> valeur nom xs;;
(* exemples *)
valeur "x" [{nom = "x"; valeur = 34}];;
valeur "x" [{nom = "y"; valeur = 34}];;
valeur "retour de pause" [{nom = "retour de pause"; valeur = -1}];;
valeur "x" [{nom = "y"; valeur = 34};
            {nom = "x"; valeur = 10};
            {nom = "z"; valeur = 34};
            {nom = "t"; valeur = 34};
            {nom = "x"; valeur = 22}];;

(* représenter la déclaration *)
let declaration nom etat = {nom=nom; valeur = 0}::etat;;
(* exemples *)
let etat = declaration "x" [] in
declaration "x" etat;;


(* représenter l'affectation *)
let rec affectation nom valeur etat = match etat with
  | [] -> raise VariableNonDeclaree
  | x::xs when x.nom = nom ->  x.valeur <- valeur
  | x::xs -> affectation nom valeur xs;;

(* Exemples d'affectation *)
let etat = [{nom= "x"; valeur = 9}] in
affectation "x" 100 etat; etat;;
(*"retourne"  [{nom: "x", valeur: 100}] *)

let etat = [{nom= "y"; valeur= 9};{nom= "z"; valeur= 3}] in
affectation "x" 100 etat; etat;;
(*provoque une erreur VariableNonDeclaree *)

(*------ cas d'usage (pas du caml) --------*)
(* declarer une variable *)
etats = [x = 1]
"Block ["
"Declaration i;"
etats = [x = 1; i = 0 ]
"Affectation i := 4 + 5"
etats = [x = 1; i = 9 ]
"]"
etats = [x = 1] (* effet de portée *)

(* autre situation à traiter: redéclarer une variable *)
etats = [i = 1]
"Block ["
"Declaration i;"
etats = [i = 0] (* masquer une variable *)
"Affectation i := 4 + 5"
etats = [i = 9]
"]"
etats = [i = 1]

(* cas d'erreur *)
etats = [ x = 1; y = 2; z = 3; i = 9 ];;
"Affectation j := 4";;
raise VariableNonDeclaree;;

"
Declaration x;
Declaration y;
Affectation x 3;
While (y < 1) {
 Declaration x;
 Affectation x 5;
 Affectation y (Valeur x);
}
"
;;

type expression = Ent of int
                | Plus of expression * expression
                | Mult of expression * expression
                | Div of expression * expression
                | Moins of expression * expression
                | Opp of expression
                | Egal of expression * expression
                | Sup of expression * expression
                | Inf of expression * expression
                | Var of string
;;

let rec eval e etat = match e with
  | Ent n -> n
  | Plus (e1, e2) -> (eval e1 etat) + (eval e2 etat)
  | Mult (e1, e2) -> (eval e1 etat) * (eval e2 etat)
  | Div (e1, e2) -> (eval e1 etat) / (eval e2 etat)
  | Moins (e1, e2) -> (eval e1 etat) - (eval e2 etat)
  | Opp e1 -> (-1) * (eval e1 etat)
  | Egal (e1, e2) -> (match (eval e1 etat) = (eval e2 etat) with true -> 1
                                                    | false -> 0)
  | Sup (e1, e2)  -> (match (eval e1 etat) > (eval e2 etat) with true -> 1
                                                    | false -> 0)
  | Inf (e1, e2)  -> (match (eval e1 etat) < (eval e2 etat) with true -> 1
                                                    | false -> 0)
  | Var nom -> valeur nom etat
;;

(* exemples *)
(* dans l'environnement x <- 2 on évalue 4 + x *)
let etat = [{nom="x"; valeur = 2}] in
    let e = Plus (Ent 4, Var "x") in
    eval e etat;;
(* dans l'environnement x <- 2 on évalue 4 + y *)
let etat = [{nom="x"; valeur = 2}] in
    let e = Plus (Ent 4, Var "y") in
    eval e etat;;

type instruction = Printstr of string
                 | Print of expression
                 | Block of instruction list
                 | Declaration of string
                 | Affectation of string * expression
                 | While of expression * instruction
                 | Haut | Bas | Droite | Gauche
                 | If of expression * instruction
;;

let rec exec prog etat = match prog with
  | Printstr s -> print_string s;
                  etat
  | Print e -> print_int (eval e etat);
               etat
  | Block [] -> etat
  | Block (x::xs) ->
     let nouveletat = exec x etat in
     exec (Block xs) nouveletat
  | Declaration nom -> declaration nom etat
  | Affectation (nom, exp) ->
     let v = eval exp etat in
     affectation nom v etat;
     etat
  | While (exp, instruction1) as w ->
     (match (eval exp etat) with
      | 0 -> etat
      | _ -> let nouveletat = exec instruction1 etat in
             exec w nouveletat)
  | Haut | Bas | Droite | Gauche -> print_string "a implementer"; etat
  | If (exp, instr) -> (match (eval exp etat) with
      | 0 -> etat
      | _ -> exec instr etat)
;;

(* un petit exemple *)
"
 int x;
 x = 10;
 while (x < 40) {
   print x;
   if (x < 30) {
     printstr ,;
   }
   x = x + 10;
 }";;
let p = Block [
            Declaration "x";
            Affectation ("x", Ent 10);
            While ( Inf (Var "x", Ent 400),
                    Block [
                        Print (Var "x");
                        If (Inf (Var "x", Ent 390), Printstr ", ");
                        Affectation ("x", Plus ((Var "x"), Ent 10))
                  ]);
            Printstr "\n"
          ];;
  exec p [];;

Questions supplémentaires (à traiter pour la semaine 8) :
– écrire une version synthétique, de ce code, avec juste les types et une fonction run.
– faire en sorte que Haut, Bas, Droite, Gauche déplacent un point sur l’écran en traçant des segments à chaque déplacement.

Exemple de programme et d’affichage.

let p = Block [
            Declaration "x";
            Affectation ("x", Ent 0);
            While (Inf (Var "x", Ent 10),
                   Block [
                       Droite;
                       Haut;
                       Affectation ("x", Plus (Var "x", Ent 1))
                     ]);
            Affectation ("x", Ent 0);
            While (Inf (Var "x", Ent 10),
                   Block [
                       Haut;
                       Gauche;
                       Affectation ("x", Plus (Var "x", Ent 1))
                     ]);
            Affectation ("x", Ent 0);
            While (Inf (Var "x", Ent 10),
                   Block [
                       Gauche;
                       Bas;
                       Affectation ("x", Plus (Var "x", Ent 1))
                     ]);
            Affectation ("x", Ent 0);
            While (Inf (Var "x", Ent 10),
                   Block [
                       Bas;
                       Droite;
                       Affectation ("x", Plus (Var "x", Ent 1))
                     ]);
          ]
    in
    run p;;

Semaine 7 – Interprète d’un mini-langage (2)

Et maintenant les variables ont des noms

Portfolio