Un interprète Pseudo-Pascal, solutions |
Les valeurs utilisées de façon interne par l’interprète (booléens, entiers et tableaux) sont représentées par un type somme. L’extension du type value est immédiate :
type value = VBool of bool VInt of int32 VArray of value array
La fonction d’évaluation des expressions est étendue à de nouveaux cas, en prenant en compte le type booléen pour les constantes, et les opérations unaires ou binaires sur des entiers ou des booléens.
let rec interpret_expression defs genv env = function EConst (ConstBool b) -> VBool b EConst (ConstInt i) -> VInt i EUnOp (UOpNeg, e) -> VInt (- (asInt (interpret_expression defs genv env e))) EBinOp (op, e1, e2) -> begin let i1 = asInt (interpret_expression defs genv env e1) in let i2 = asInt (interpret_expression defs genv env e2) in match op with OpAdd -> VInt (i1 + i2) OpSub -> VInt (i1 - i2) OpMul -> VInt (i1 * i2) OpDiv -> VInt (i1 / i2) OpLt -> VBool (i1 < i2) OpLe -> VBool (i1 <= i2) OpGt -> VBool (i1 > i2) OpGe -> VBool (i1 >= i2) OpEq -> VBool (i1 = i2) OpNe -> VBool (i1 <> i2) end _ -> failwith "Pas implémenté"
Un environnement est un ensemble de liaisons entre des noms de variables (de type string) et des cellules contenant chacune une valeur mutable (de type valeur ref) d’une part, des noms de fonctions ou procédures (de type string) et des procédures Pseudo-Pascal (de type procedure) d’autre part.
On l’implémente sous la forme de 3 tables d’association passées par paramètre aux fonctions qui en ont besoin :
La fonction lookup cherche d’abord dans l’environnement local env une liaison pour le nom de variable qui lui est passé en paramètre. Si cette recherche échoue, elle cherche alors cette liaison dans l’environnement global genv.
let lookup (genv : environment) (env : environment) (x : string) : value ref = try StringMap.find x env with Not_found -> try StringMap.find x genv with Not_found -> assert false
On utilise la fonction de librairie Map.find,
expliquée dans le manuel Objective Caml.
L’explication permet de savoir que Map.find
lève l’exception Not_found lorsqu’il n’y a pas de paire
(x,...) dans la table et de se servir de ce fait.
La fonction interpret prend la forme suivante :
let interpret p = let genv = StringMap.map allocate p.globals in interpret_instruction p.defs genv StringMap.empty p.main
où allocate est une fonction qui crée une valeur mutable ou ref en OCaml, qu’elle initialise à une valeur par défaut. Pour les entiers et les booléens, cette valeur par défaut est tout simplement 0 ou false ; pour les tableaux cela implique d’ajouter un nouveau type de valeur VNil pour les tableaux pas encore alloués.
type value = VBool of bool VInt of int32 VArray of value array VNil let default = function TypBool -> VBool false TypInt -> VInt 0l TypArray _ -> VNil let allocate typ = ref (default typ)
La lecture d’une variable nécessite de modifier interpret_expression pour lui ajouter le cas suivant :
EGetVar x -> !(lookup genv env x)
L’écriture d’une variable nécessite de modifier interpret_instruction pour lui ajouter le cas suivant :
ISetVar (x, e) -> (lookup genv env x) := (interpret_expression defs genv env e)
Le code de fabrication du nouvel environnement local est commun aux procédures et aux fonctions.
Il s’agit de redéfinir l’environnement env étendu par les nouvelles liaisons des variables locales à leur valeur par défaut ; et des noms des arguments (paramètres dits formels) à la valeur de l’argument correspondant (paramètres dits effectifs) :
let env = List.fold_right2 (fun (formal, _) actual env -> StringMap.add formal (ref actual) env ) proc.formals actuals StringMap.empty in let env = StringMap.addm (StringMap.map allocate proc.locals) env in
On utilise ici une fonction d’itération, qui implémente une boucle de manière fonctionnelle : la fonction de librairie List.fold_right2.
Dans le cas des fonctions on augmente l’environnement d’appel d’une liaison entre le nom de la fonction et une valeur par défaut correspondant au type de retour attendu. Cette liaison est celle de la variable résultat de la fonction. Rappelons en effet qu’en Pascal, on procède ainsi :
function fact (x : integer) : integer begin ... fact := ... end
Ainsi, pour finir de construire l’environnement d’appel d’une fonction :
La fonction Option.fold est implémentée dans le fichier option.ml.
Ensuite il reste à évaluer le corps de la fonction dans l’environnement si chèrement construit :
interpret_instruction defs genv env proc.body;
et à récupérer le résultat :
Option.map (fun _ -> !(StringMap.find f env)) proc.result
L’appel de procédure est identique, moins la gestion de la variable résultat.
L’évaluation d’une expression peut entraîner l’évaluation d’une instruction, à travers l’appel d’une fonction. Réciproquement, l’évaluation d’une instruction peut entraîner l’évaluation d’une expression, par exemple à travers l’évaluation de la condition dans une construction if. Donc les fonctions d’évaluation seront mutuellement récursives :
let rec interpret_call defs genv env callee actuals : value option = ... and interpret_expression defs genv env = function ... and interpret_condition defs genv env = function ... and interpret_instruction defs genv env = function ...
On utilise la librairie standard Array d’OCaml. Cela permet d’effectuer toutes les opérations autorisées par le langage Pseudo-Pascal sur les tableaux : création, lecture, écriture.
L’interprète a souvent besoin d’évaluer une expression dont le type est contraint : à int pour un index lors d’un accès tableau, à bool dans une expression conditionnelle, etc. Afin de partager du code (éviter d’écrire plusieurs fois le même code), on ajoute des fonctions utilitaires asBool, asInt et asArray.
Ensuite, rien de plus facile que d’évaluer une expression pour obtenir un résultat booléen, entier ou tableau :
and interpret_expression defs genv env = function ... EArrayGet (ea, ei) -> let a = asArray (interpret_expression defs genv env ea) in let i = asInt (interpret_expression defs genv env ei) in begin try Array.get a i ...
L’interprète Pseudo-Pascal complet se trouve dans interpretPP.ml.
Ce document a été traduit de LATEX par HEVEA