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

photo en cc-by-nc par Ryan Buterbaugh

, 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.

  1. (* à ajouter à la fin du cours 6 *)
  2. type instruction = Printstr of string
  3.                  | Print of expression
  4.                  | Block of instruction list
  5.                  | Affectation of int * expression
  6.                  | While of expression * instruction;;
  7.  
  8. let rec exec = function
  9.   | Printstr s -> print_string s
  10.   | Print e -> print_int (eval e)
  11.   | Block [] -> ()
  12.   | Block (x::xs) -> exec x;
  13.                      exec (Block xs)
  14.   | Affectation (n, e) when n < 4 && n >= 0 -> etats.(n) <- (eval e)
  15.   | Affectation (n, e) -> raise Segfault
  16.   | While (e, i) as w -> (match (eval e) with
  17.                           | 0 -> ()
  18.                           | _ -> exec i; exec w);;
  19.  
  20.  
  21. "x = 10;
  22. while (x < 40) {
  23. print x;
  24. println;
  25. x = x + 10;
  26. }";;
  27. let p = Block [
  28.             Affectation (0, Ent 10);
  29.             While ( Inf (Var 0, Ent 40),
  30.                     Block [
  31.                         Print (Var 0);
  32.                         Printstr "\n";
  33.                         Affectation (0, Plus ((Var 0), Ent 10))
  34.                   ])
  35.           ];;
  36.  
  37. exec p;;

Télécharger

[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.

  1. (* synthèse du mini-interprète cours 6 et tp 7 *)
  2. type expression = Ent of int
  3.                 | Plus of expression * expression
  4.                 | Mult of expression * expression
  5.                 | Div of expression * expression
  6.                 | Moins of expression * expression
  7.                 | Opp of expression
  8.                 | Egal of expression * expression
  9.                 | Sup of expression * expression
  10.                 | Inf of expression * expression
  11.                 | Var of int (* une variable impérative est une *)
  12.                              (* adresse mémoire *)
  13. ;;
  14.  
  15. type instruction = Printstr of string
  16.                  | Print of expression
  17.                  | Block of instruction list
  18.                  | Affectation of int * expression
  19.                  | While of expression * instruction
  20. ;;
  21.  
  22. (* erreur mémoire *)
  23. exception Segfault;;
  24.  
  25. (* tout est dans la fonction run *)
  26. let run p k =
  27.   let etats = Array.make k 0
  28.   in
  29.   let rec eval = function
  30.     | Ent n -> n
  31.     | Plus (e1, e2) -> (eval e1) + (eval e2)
  32.     | Mult (e1, e2) -> (eval e1) * (eval e2)
  33.     | Div (e1, e2) -> (eval e1) / (eval e2)
  34.     | Moins (e1, e2) -> (eval e1) - (eval e2)
  35.     | Opp e1 -> (-1) * (eval e1)
  36.     | Egal (e1, e2) -> (match (eval e1) = (eval e2) with true -> 1
  37.                                                        | false -> 0)
  38.     | Sup (e1, e2)  -> (match (eval e1) > (eval e2) with true -> 1
  39.                                                        | false -> 0)
  40.     | Inf (e1, e2)  -> (match (eval e1) < (eval e2) with true -> 1
  41.                                                        | false -> 0)
  42.     | Var n when n < k && n >= 0 -> etats.(n)
  43.     | Var n -> raise Segfault in
  44.   let rec exec = function
  45.     | Printstr s -> print_string s
  46.     | Print e -> print_int (eval e)
  47.     | Block [] -> ()
  48.     | Block (x::xs) -> exec x;
  49.                        exec (Block xs)
  50.     | Affectation (n, e) when n < k && n >= 0 -> etats.(n) <- (eval e)
  51.     | Affectation (n, e) -> raise Segfault
  52.     | While (e, i) as w -> (match (eval e) with
  53.                             | 0 -> ()
  54.                             | _ -> exec i; exec w)
  55.   in
  56.   exec p;
  57.   etats (* <-- on veut savoir dans quel état le programme termine *)
  58. ;;
  59.  
  60. (* essai sur un petit programme *)
  61. "x = 10;
  62. y = 0;
  63. println;
  64. while (x < 40) {
  65.   print x;
  66.   println;
  67.   y = y + x;
  68.   x = x + 10;
  69. }";;
  70. let p = Block [
  71.             Affectation (0, Ent 10);
  72.             Affectation (1, Ent 0);
  73.             Printstr "\n";
  74.             While ( Inf (Var 0, Ent 40),
  75.                     Block [
  76.                         Print (Var 0);
  77.                         Printstr "\n";
  78.                         Affectation (1, Plus (Var 1, Var 0));
  79.                         Affectation (0, Plus (Var 0, Ent 10))
  80.                   ])
  81.           ]
  82.   and
  83.     taille_memoire = 2
  84.     in
  85.     run p taille_memoire;;
  86.  
  87. (* question bonus : écrire une fonction qui prend en entrée un *)
  88. (* programme (de type instruction) et détermine la taille mémoire *)
  89. (* nécessaire pour l'exécuter sans SegFault *)

Télécharger

Et maintenant les variables ont des noms

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

  1. (* Qu'est ce qu'une variable ? Un enregistrement *)
  2. (* un nom : string *)
  3. (* une valeur mutable de type int *)
  4. type variable = {nom: string; mutable valeur: int};;
  5.  
  6. (* Qu'est ce que l'état ? *)
  7. (* Une liste de variables au départ la liste vide [] *)
  8. (* lorsqu'on veut manipuler une variable non déclarée ... *)
  9. exception VariableNonDeclaree;;
  10.  
  11. (* Pour lire la valeur d'une variable. *)
  12. let rec valeur nom etat = match etat with
  13.   | [] -> raise VariableNonDeclaree
  14.   | x::xs when x.nom = nom -> x.valeur
  15.   | x::xs -> valeur nom xs;;
  16. (* exemples *)
  17. valeur "x" [{nom = "x"; valeur = 34}];;
  18. valeur "x" [{nom = "y"; valeur = 34}];;
  19. valeur "retour de pause" [{nom = "retour de pause"; valeur = -1}];;
  20. valeur "x" [{nom = "y"; valeur = 34};
  21.             {nom = "x"; valeur = 10};
  22.             {nom = "z"; valeur = 34};
  23.             {nom = "t"; valeur = 34};
  24.             {nom = "x"; valeur = 22}];;
  25.  
  26. (* représenter la déclaration *)
  27. let declaration nom etat = {nom=nom; valeur = 0}::etat;;
  28. (* exemples *)
  29. let etat = declaration "x" [] in
  30. declaration "x" etat;;
  31.  
  32.  
  33. (* représenter l'affectation *)
  34. let rec affectation nom valeur etat = match etat with
  35.   | [] -> raise VariableNonDeclaree
  36.   | x::xs when x.nom = nom ->  x.valeur <- valeur
  37.   | x::xs -> affectation nom valeur xs;;
  38.  
  39. (* Exemples d'affectation *)
  40. let etat = [{nom= "x"; valeur = 9}] in
  41. affectation "x" 100 etat; etat;;
  42. (*"retourne"  [{nom: "x", valeur: 100}] *)
  43.  
  44. let etat = [{nom= "y"; valeur= 9};{nom= "z"; valeur= 3}] in
  45. affectation "x" 100 etat; etat;;
  46. (*provoque une erreur VariableNonDeclaree *)
  47.  
  48. (*------ cas d'usage (pas du caml) --------*)
  49. (* declarer une variable *)
  50. etats = [x = 1]
  51. "Block ["
  52. "Declaration i;"
  53. etats = [x = 1; i = 0 ]
  54. "Affectation i := 4 + 5"
  55. etats = [x = 1; i = 9 ]
  56. "]"
  57. etats = [x = 1] (* effet de portée *)
  58.  
  59. (* autre situation à traiter: redéclarer une variable *)
  60. etats = [i = 1]
  61. "Block ["
  62. "Declaration i;"
  63. etats = [i = 0] (* masquer une variable *)
  64. "Affectation i := 4 + 5"
  65. etats = [i = 9]
  66. "]"
  67. etats = [i = 1]
  68.  
  69. (* cas d'erreur *)
  70. etats = [ x = 1; y = 2; z = 3; i = 9 ];;
  71. "Affectation j := 4";;
  72. raise VariableNonDeclaree;;
  73.  
  74. "
  75. Declaration x;
  76. Declaration y;
  77. Affectation x 3;
  78. While (y < 1) {
  79. Declaration x;
  80. Affectation x 5;
  81. Affectation y (Valeur x);
  82. }
  83. "
  84. ;;
  85.  
  86. type expression = Ent of int
  87.                 | Plus of expression * expression
  88.                 | Mult of expression * expression
  89.                 | Div of expression * expression
  90.                 | Moins of expression * expression
  91.                 | Opp of expression
  92.                 | Egal of expression * expression
  93.                 | Sup of expression * expression
  94.                 | Inf of expression * expression
  95.                 | Var of string
  96. ;;
  97.  
  98. let rec eval e etat = match e with
  99.   | Ent n -> n
  100.   | Plus (e1, e2) -> (eval e1 etat) + (eval e2 etat)
  101.   | Mult (e1, e2) -> (eval e1 etat) * (eval e2 etat)
  102.   | Div (e1, e2) -> (eval e1 etat) / (eval e2 etat)
  103.   | Moins (e1, e2) -> (eval e1 etat) - (eval e2 etat)
  104.   | Opp e1 -> (-1) * (eval e1 etat)
  105.   | Egal (e1, e2) -> (match (eval e1 etat) = (eval e2 etat) with true -> 1
  106.                                                     | false -> 0)
  107.   | Sup (e1, e2)  -> (match (eval e1 etat) > (eval e2 etat) with true -> 1
  108.                                                     | false -> 0)
  109.   | Inf (e1, e2)  -> (match (eval e1 etat) < (eval e2 etat) with true -> 1
  110.                                                     | false -> 0)
  111.   | Var nom -> valeur nom etat
  112. ;;
  113.  
  114. (* exemples *)
  115. (* dans l'environnement x <- 2 on évalue 4 + x *)
  116. let etat = [{nom="x"; valeur = 2}] in
  117.     let e = Plus (Ent 4, Var "x") in
  118.     eval e etat;;
  119. (* dans l'environnement x <- 2 on évalue 4 + y *)
  120. let etat = [{nom="x"; valeur = 2}] in
  121.     let e = Plus (Ent 4, Var "y") in
  122.     eval e etat;;
  123.  
  124. type instruction = Printstr of string
  125.                  | Print of expression
  126.                  | Block of instruction list
  127.                  | Declaration of string
  128.                  | Affectation of string * expression
  129.                  | While of expression * instruction
  130.                  | Haut | Bas | Droite | Gauche
  131.                  | If of expression * instruction
  132. ;;
  133.  
  134. let rec exec prog etat = match prog with
  135.   | Printstr s -> print_string s;
  136.                   etat
  137.   | Print e -> print_int (eval e etat);
  138.                etat
  139.   | Block [] -> etat
  140.   | Block (x::xs) ->
  141.      let nouveletat = exec x etat in
  142.      exec (Block xs) nouveletat
  143.   | Declaration nom -> declaration nom etat
  144.   | Affectation (nom, exp) ->
  145.      let v = eval exp etat in
  146.      affectation nom v etat;
  147.      etat
  148.   | While (exp, instruction1) as w ->
  149.      (match (eval exp etat) with
  150.       | 0 -> etat
  151.       | _ -> let nouveletat = exec instruction1 etat in
  152.              exec w nouveletat)
  153.   | Haut | Bas | Droite | Gauche -> print_string "a implementer"; etat
  154.   | If (exp, instr) -> (match (eval exp etat) with
  155.       | 0 -> etat
  156.       | _ -> exec instr etat)
  157. ;;
  158.  
  159. (* un petit exemple *)
  160. "
  161. int x;
  162. x = 10;
  163. while (x < 40) {
  164.   print x;
  165.   if (x < 30) {
  166.     printstr ,;
  167.   }
  168.   x = x + 10;
  169. }";;
  170. let p = Block [
  171.             Declaration "x";
  172.             Affectation ("x", Ent 10);
  173.             While ( Inf (Var "x", Ent 400),
  174.                     Block [
  175.                         Print (Var "x");
  176.                         If (Inf (Var "x", Ent 390), Printstr ", ");
  177.                         Affectation ("x", Plus ((Var "x"), Ent 10))
  178.                   ]);
  179.             Printstr "\n"
  180.           ];;
  181.   exec p [];;

Télécharger

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.

  1. let p = Block [
  2.             Declaration "x";
  3.             Affectation ("x", Ent 0);
  4.             While (Inf (Var "x", Ent 10),
  5.                    Block [
  6.                        Droite;
  7.                        Haut;
  8.                        Affectation ("x", Plus (Var "x", Ent 1))
  9.                      ]);
  10.             Affectation ("x", Ent 0);
  11.             While (Inf (Var "x", Ent 10),
  12.                    Block [
  13.                        Haut;
  14.                        Gauche;
  15.                        Affectation ("x", Plus (Var "x", Ent 1))
  16.                      ]);
  17.             Affectation ("x", Ent 0);
  18.             While (Inf (Var "x", Ent 10),
  19.                    Block [
  20.                        Gauche;
  21.                        Bas;
  22.                        Affectation ("x", Plus (Var "x", Ent 1))
  23.                      ]);
  24.             Affectation ("x", Ent 0);
  25.             While (Inf (Var "x", Ent 10),
  26.                    Block [
  27.                        Bas;
  28.                        Droite;
  29.                        Affectation ("x", Plus (Var "x", Ent 1))
  30.                      ]);
  31.           ]
  32.     in
  33.     run p;;

Télécharger

Encore plus simple que du Logo !

Recherche

Enseignement

Administration

Université Sorbonne Paris Nord Des services numériques pour étudier
Curriculum Vitæ [pdf]
Comment me contacter

Autres réalisations (logiciels, etc.)

Bluehats & UnivMobile , Présentation de la démarche design employée pour UnivMobile faite à la rencontre bluehats du 11 décembre 2019. [pdf, jpg]
Mon université en 2030, Texte d'une intervention que j'ai faite dans le cadre d'une soirée Cap 2030, organisée par le EdFab à Cap Digital le 27 février (...)
Thymio, Python et Asebamedulla
des QCM en ligne grâce à org-mode (et jQuery, et MathJax), org-mode [org, html, css]

Café

Expérience du désir
Enseigner la programmation
Revenu et logement, Je livre ici quelques éléments de comparaison concernant mon niveau de vie, pour couper court à quelques idées reçues, et un condensé de nombreuses (...)
Revenu et travail d’un enseignant-chercheur, Cet article complète l'article Revenu et logement, en détaillant un peu le budget de mon ménage, mon parcours d'enseignant-chercheur en terme de (...)
Paris 13 Villetaneuse, pas encore la vélorution !
Cybersyn (el systemo synco), Au café, mardi 5 avril 2011, j'ai bien vu que, mis à part Antoine Allombert, personne ne connaissait l'histoire de l'extraordinaire projet chilien (...) [jpg, jpg, png]

Divers

Affiche CiE 2016
Augmenter l’espace de stockage d’un hote GNU/Linux (VirtualBox etc.)
AperoTIC sur les réseaux sociaux
ADULLACT, Pour être un peu moins seul à défendre l'usage et le développement de logiciels libres dans mon travail (et autour), j'ai adhéré à l'ADULLACT en tant (...)
Hacker l’éducation (Open bidouille camp 2 // Fac lab de Gennevilliers)
Expo : et l’Homme… créa le robot
MathJax
Onglets dans un rapport $\LaTeX$ [gz, png, pdf, gz]
Logo LIPN et accessoires [svg, svg, png, tex, pdf, tif, zip, png, eps, svg]
Ventilo pour ibook (retrouvé) [jpg]