Un interprète Pseudo-Pascal

Voici le cours correspondant. La solution est ici.

Présentation

Ce TD se présente comme le précédent : l’exercice consiste à écrire un fichier manquant pour un programme par ailleurs déjà complet.

Ici, le programme en question est un interprète pour Pseudo-Pascal. Vous n’avez à écrire ni analyseur syntaxique ni analyseur lexical, ni glue code pour assembler les morceaux. Tout cela est déjà fait et stocké dans l’archive pp.tar.gz. Le morceau manquant est en fait le noyau de l’interprète.

Il faut d’abord télécharger l’archive, puis la dépaqueter : 

# tar xvfz pp.tar.gz

Cette opération crée un sous-répertoire petit qui contient tout ce qui est nécessaire pour le TD, y compris en particulier un Makefile. 

# cd petit
# make
...
ocamlopt.opt -o compilo   integer.cmx misc.cmx ...

Cependant, l’interprète ainsi produit ne fonctionne pas : 

# ./compilo -ipp test/a.p
Fatal error: exception Failure("Pas implémenté")

Vous noterez en passant l’utilisation de l’option -ipp pour appeller l’interprète du langage Pseudo-Pascal.

Le fichier interpretPP.ml contient le code d’un interprète extrêmement incomplet qui ne traite que l’instruction writeln :

open Printf
open MIPSOps
open Primitive
open PP
open Integer

type value =
  | VInt of int32

let asInt = function
  | VInt i -> i

type environment = value ref StringMap.t
type definitions = PP.procedure StringMap.t
type 'a interpreter = definitions -> environment -> environment -> 'a

let interpret_primitive p actuals =
  match p, actuals with
  | Writeln, [ v ] -> fprintf stdout "%ld\n%!" (asInt v); None
  | _ -> failwith "Pas implémenté"

let interpret_expression defs genv env = function
  | EConst (ConstInt i) -> VInt i
  | _ -> failwith "Pas implémenté"

let interpret_call defs genv env callee actuals =
  let actuals = List.map (interpret_expression defs genv env) actuals in
  match callee with
  | CPrimitiveFunction p -> interpret_primitive p actuals
  | _ -> failwith "Pas implémenté"

let interpret_condition defs genv env = function
  | _ -> failwith "Pas implémenté"

let rec interpret_instruction defs genv env = function
  | IProcCall (callee, es) -> ignore (interpret_call defs genv env callee es)
  | ISeq (is) -> List.iter (interpret_instruction defs genv env) is
  | _ -> failwith "Pas implémenté"

let interpret p = interpret_instruction StringMap.empty StringMap.empty StringMap.empty p.main

Vous pouvez déjà vérifier que ça marche sur le programme ultra minimal trivial.p :

trivial.p On obtient: 

# ./compilo -ipp test/trivial.p
10

On pourra noter au passage que cet interprète incomplet ne considère que la suite d’instructions p.main qui constituent le point d’entrée du programme, ignorant les déclarations de variables globales et de fonctions p.globals et p.defs. L’interprète complet devra évidemment prendre celles-ci en compte.

Vous avez peut-être remarqué que les paramètres defs, genv et env ne sont pas utilisés : ils serviront justement plus tard à passer l’environnement (qui contient les variables globales et les fonctions) entre les fonctions de l’interprète. Si vous appellez vous-mêmes ces fonctions, n’oubliez pas de passer ces paramètres.

Ce qu’il faut faire

L’implémentation interpretPP.ml doit être conforme à l’interface interpretPP.mli :

interpretPPempty.mli

Elle doit donc fournir une fonction interpret qui, étant donnée une valeur de type PP.program, c’est-à-dire un arbre de syntaxe abstraite représentant un programme, l’exécute. Cette fonction ne renverra aucun résultat, mais son exécution pourra avoir des effets de bord : par exemple, elle pourra afficher une chaîne de caractères sur la sortie standard si le programme Pseudo-Pascal qu’on lui fournit contient une instruction writeln.

Pour écrire interpretPP.ml, on s’appuiera sur la syntaxe abstraite du langage Pseudo-Pascal, définie formellement dans PP.mli, et sur la description sémantique formelle big-step donnée dans le cours. On s’aidera également des signatures de fonctions données dans interpretPP.mli.

On suggère la démarche suivante:

  1. Commencer par définir complètement le type des valeurs (booléens, entiers, tableaux) en enrichissant le type value.
    Voir la solution.
  2. Définir l’évaluation des expressions arithmétiques sans variables ni appels de fonctions, à partir du type des expressions de PP.mli. Cela revient à enrichir le filtrage de motifs existant de la fonction interpret_expression, pour prendre en compte le cas des constructeurs EUnOp, EBinOp et EConst pour une constante booléenne.

    On peut alors essayer cet interprète minimal en lui proposant un programme très simple, par exemple trivial2.p :

    trivial2.p

    On obtient: 

    # ./compilo -ipp test/trivial2.p
10
    Voir la solution.
  3. Définir la fonction lookup qui recherche une variable par nom dans un environnement, avec la signature suivante :

    val lookup : environment -> environment -> string -> value ref

    L’environnement est constitué de trois composantes:

    Cet environnement est passsé par paramètre aux fonctions qui en ont besoin, d’où les signatures de fonctions dans l’interface interpretPP.mli.

    Voir la solution.
  4. Étendre la fonction interpret pour passer un environnement correct à la fonction interpret_instruction. Il faut déterminer l’environnement des fonctions defs et l’environnement des variables globales genv.

    Modifier l’évaluateur des expressions pour traiter le cas des variables, ainsi que l’évaluateur des instructions pour tenir compte de l’affectation de variable. Tester à l’aide d’un exemple simple, par exemple trivial3.p :

    trivial3.p

    On obtient encore: 

    # ./compilo -ipp test/trivial3.p
10
    Voir la solution.
  5. S’attaquer ensuite aux appels de fonctions et de procédures. Cela nécessite principalement de gérer l’environnement env. On pensera à traiter le cas des variables locales, des paramètres, ainsi que de la variable de retour (dans le cas des fonctions seulement).

    Compléter enfin l’interprète en traitant toutes les constructions et notamment les tableaux.

    Vous pouvez à tout moment lancer une procédure de test complète à l’aide de la commande make test. L’interprète est alors lancé sur une série de programmes (fact.p, …) pour une série d’entrées standard (fact.in, …). Le résultat obtenu sur la sortie standard est stocké dans un fichier (fact.ipp, …) qui est confronté au résultat attendu (fact.ispim, …). L’ensemble des fichiers utiles aux tests se trouve dans le sous-répertoire test.

    Voir la solution.
  6. Terminer par les aspects esthétiques : faire en sorte que le code soit élégant et commenté et que les erreurs soit correctement gérées. On distinguera les erreurs situées dans le programme interprété de celles situées dans l’interprète lui-même. Par exemple, si le programme interprété effectue un accès en dehors des bornes d’un tableau, on préférera un message d’erreur explicatif plutôt qu’un échec brutal de l’interprète (dû à une exception Caml non rattrapée).
Voir la solution.
Ce document a été traduit de LATEX par HEVEA