Un petit interpréteur pseudo-pascal, solution

1 La solution

La solution est un fichier source interpret.ml.

2 Quelques détails

2.1 Les valeurs et les environnements

Les valeurs utlisées de façon interne par l'interpréteur (booléns, entiers, tableaux et valeurs indéfinies) sont rendues par un bête type somme :

type valeur =
  | Vint of int
  | Vbool of bool
  | Varray of valeur array
  | Undefined

Au plus simple un environnement est un tas de liaisons entre des noms de variables (des string) et des cellules contenant chacune une valeurs (valeur ref). Le plus simple est de représenter tout ça par une liste de paires.

La stucture du langage interprété (fonctions globales) conduit à distinguer variables globales, fonctions (globales) et variables locales et à représenter les environnements par des enregistrements à trois champs :

type env_t = {
  fonctions : (string * definition) list ;
  globals : (string * valeur ref) list ;
  locals : (string * valeur ref) list
}

Pour trouver la cellule associée à une variable, on cherchera d'abord dans les variables locales puis dans les globales :

let trouve_var {globals = glob ; locals = loc } x =
  try List.assoc x loc with
  | Not_found ->
      try List.assoc x glob with
      | Not_found -> erreur (Inconnue ("variable: "^x))

On utilise la fonction de librairie List.assoc, expliquée à la section 17.14 du manuel OCaml. L'explication permet de savoir que List.assoc lève l'exception Not_found lorsque qu'il n'y a pas de paire (x,...) dans la liste et de se servir de ce fait.

Lors des appels de fonctions (ou de procédure) on aura besoin de fabriquer un nouvel environnement. Voici une fonction renvoie l'environnement env étendu d'une liaison locale entre la variable x et une nouvelle cellule contenant initialement la valeur v :

and extend x v env =
  {env with locals = (x,ref v) :: env.locals}

On utilise la copie d'enregistrement avec mise à jour, expliquée à la section 6.5 du manuel OCaml.

3 Structure de l'interpréteur

Initialement on sait que l'on aura à evaluer des expressions et des instructions, l'evaluation des expressions pouvant entraîner l'evaluation d'une instruction (appel de fonction) et réciproquement (evaluation de la condition dans un If). Soit :

let rec expr env = function
| Int i -> Vint i

and instr env = function 
| Set (x,e) -> ...

Pour évaluer un programme, il suffit de fabriquer un premier environnement, puis de lancer l'évaluation de l'instruction ``main'' :

let eval
    {global_vars = globs ;
      definitions = defs ;
      main = i} =
  let start_env =
    {globals = List.map (fun (x,_) -> x, ref Undefined) globs ;
      fonctions  = defs ;
      locals = []} in
  instr start_env i

4 Quelques astuces de structure

4.1 Partage de code

Afin de partager du code (d'éviter d'écrire dix fois le même code), on ajoute plein de fonctions. Par exemple, l'interpréteur à souvent besoin d'évaluer une expression comme un entier (primitives, accès aux tableaux...) on écrit donc une fonction utilitaire expr_int :

let expr env = function ...

and expr_int env e = match expr env e with
| Vint i -> i
| Undefined -> erreur PasDef
| v -> erreur (Type (Integer,v))

and instr env = function ...

Ensuite rien de plus facile que d'évaluer une expression vers un entier, un booléen ou un tableau :

let expr env = function
 ...
| Geti (et, ei) ->
    let vt = expr_array env et in
    let vi = expr_int env ei in
    vt.(vi)
  ...

4.2 Les primitives

Le code de l'évaluation des primitives est mis dans une fonction préliminaire qui prend en argument la primitive et deux entiers. Cette technique localise l'évaluation des primitives et permet des modifications plus aisées, si par exemple, on ajoute une primitive :

let binop op i1 i2 = match op with
| Plus -> Vint (i1 + i2)
| ...

let expr env = function
 ...
| Binop (op, e1, e2) -> binop op (expr_int env e1) (expr_int env e2)

5 Appel de fonction

Le code de fabrication du nouvel environnement est commun aux procédures et aux fonctions (fonction call_env). Il s'agit de renvoyer l'environnement global étendu par les nouvelles liaisons des variables locales à Undefined ; et des noms des arguments (paramètres dits formels) à la valeur de l'argument correspondant (paramètres dits effectifs) :

and env_locs env = function
| [] -> env
| (x,_) :: reste ->
      extend x Undefined (env_locs env reste)

and env_args env f xs es = match xs,es with
| [],[] -> take_globs env
| (x,t)::xs, e::es ->
    let v = expr env e in
    extend x v (env_args env f xs es)
| _ -> erreur (NumArgs f)

and call_env env f fdef es  =
  env_locs
    (env_args env f fdef.arguments es)
    fdef.local_vars

On notera l'appel récursif à expr dans le corps de env_args.

Dans le cas des fonctions on augmente l'environnement d'appel d'une liaison entre le nom de la fonction et Undefined, 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

Soit pour, par exemple construire l'environnement d'appel d'une fonction :

let rec expr env = function
  ...
| Function_call (f,e_args) ->
    let fdef = trouve_fun env f in
    let new_env =
      extend
        f Undefined (* variable re'sultat *)
        (call_env env f fdef e_args) in
  ...

Ensuite il reste à évaluer le coprs de la fonction dans l'environnement si chèrement construit :

  instr new_env fdef.body ;

et à récupérer le résultat :

  let fcell = trouve_var new_env f in (* recuperer le re'sultat *)
  !fcell

L'appel de procédure est identique, moins la manip sur la variable résultat.

6 Sur le typage

L'interpréteur présenté fait le minimum de tests de types : il ne vérifie le type des valeurs que lorsqu'il a réellement besoin de la valeur (par un appel à expr_int, expr_bool, etc.), par exemple pour tester une condition (booléen) ou accéder à un tableau (type tableau et entier).

Il n'est pas du tout exclu de faire plus de vérifications, par exemple, on peut vérifier le type des arguments lors de l'appel de fonction. Les erreurs de type seront alors détectées plus tôt et l'utlisateur de l'interprète corrigera son programme plus facilement.

7 Sur le pasage de paramètres

Dans notre interprète, les entiers et les booléens sont passés par valeur, tandis que les tableaux sont passés par référence.

Cela nous éloigne un peu de Pascal, mais nous rapproche de C, de Java, de Caml...

Ce document a été traduit de L^AT_EX par H^EV^EA.