Exercices - Séance 1

Voici un analyseur syntaxique/interprète qui supporte un mini-langage dont les instructions sont :

1) soit des entiers positifs, tels que "100", "52",

2) soit une des trois variables "x", "y", et "z",

3) soit des additions de deux instructions, en utilisant le symbole "+", par exemple "20 + 10" ou "x + y + 100",

4) soit une instruction "set s=n" pour affecter à s la valeur n, où "s" est une des trois variables et "n" un entier positif, par exemple "set x=10",

5) ou une séquence de telles instructions, séparées par des nouvelles lignes et terminées par "END".

Expression analysée:

Expression évaluée (en supposant un contexte initial de {x:10,y:20,z:30}):

Le but de cette session d'exercices est d'implémenter un évaluateur pour ce mini-langage en OCaml, qui prend les expressions analysées renvoyées par l'analyseur ci-dessus et les évalue.

Exercice 0 - Addition

Dans cet exercice, nous implémenterons les fonctionnalités de base de notre mini-langage: les littéraux et l'addition. Pour ce faire, commençons par définir le type d'expressions de notre mini-langage :

type expr =
    | Literal of int
    | Add of expr * expr

En utilisant ce type, nous pouvons représenter des expressions telles que :

a) \(1\) : Literal 1,

b) \(2+3\) : Add (2,3).

Problème 0 : Ecrivez l'expression de type expr qui correspond à \((1+5)+2\).

Pour évaluer les expressions, nous allons implémenter trois fonctions eval_expr, eval_literal et eval_add, qui sont mutuellement récursives. La fonction eval_expr sert de point d'entrée pour l'évaluation et utilise les fonctions auxiliaires eval_literal et eval_add, chacune d'entre elles gérant les les expressions construites avec les constructeurs Literal et Add respectivement:

let rec eval_expr (e : expr) : int = match e with
    Literal x -> eval_literal x
    | Add (a,b) -> eval_add a b
and eval_literal x = ... 
and eval_add e1 e2 = ...

Problème 1 : Implémentez la fonction eval_add : expr -> expr -> int qui, etant donné deux valeurs e1 : expr, e2 : expr , renvoie la valeur obtenue en évaluant l'expression arithmétique représentée par leur addition. Exemple de résultat attendu :
```
# eval_add (Literal 5) (Literal 10);;
- : int option = 15
# eval_add (Literal 5) (Add (Literal 10, Literal 20));;
- : int option = 35
```

Exercise 1 - Constantes

Nous voulons maintenant enrichir notre calculatrice en lui donnant la possibilité d'utiliser un certain nombre de constantes prédéfinies. Supposons par exemple que nous disposons suffisamment d'espace dans notre mémoire pour stocker trois constantes: x, y et z.

Pour implémenter cela en OCaml, nous pouvons utiliser un type d'enregistrement avec trois entrées entières :

type context = {x : int, y : int, z : int}

Nous devrons également enrichir notre type expr pour permettre des représentations de ces constantes :

type expr = 
    | Literal of int
    | Add of expr * expr
    | Var of string

Nous pouvons maintenant représenter une expression telle que \(x + 20\) en utilisant notre nouveau constructeur: Add (Var "x", Literal 20).

Après avoir introduit le constructeur Var, nous devons aussi implémenter une fonction pour l'évaluer : eval_var qui prend en entrée un contexte cntxt : context et une chaîne de caractères, et retourne la valeur correspondante du contexte. Donc, à première vue, nous dirons que eval_var est de type context -> string -> int.

Mais que se passe-t-il si un utilisateur tape quelque chose comme \(w + 20\) ? Cette expression est bien formée selon la grammaire de notre mini-langage et est représentée par représentée par Var "w". Cependant, il n'y a pas d'entrée pour "w" dans notre contexte.

Pour gérer cette situation, nous allons utiliser le type option, défini comme suit :

type 'a option = 
    | None
    | Some of 'a

Nous utiliserons ce type pour modéliser les deux comportements possibles de lookup cntxt s en fonction de la chaîne s :

1) s est x, y, ou z.

2) s est une autre chaîne de caractères

Problème 1 : Implémenter une fonction eval_var de type context -> string -> int option telle que eval_var c "s" soit égale à Some c.s si s existe dans le contexte, sinon None.

# eval_var example_context "x";;
- : int option = Some 10
# eval_var example_context "y";;
- : int option = Some 20
# eval_var example_context "z";;
- : int option = Some 30
# eval_var example_context "w";;
- : int option = None

Devoir à rendre avant le 16 octobre 2023, 23h59, heure de Paris:

Problème 0 : Implémentez la fonctionnalité requise pour les variables et l'affectation des variables. Pour ce faire, vous devrez adapter la fonctionnalité que nous avons implémentée jusqu'à présent pour les constantes afin qu'elles deviennent des variables. En particulier, vous devrez modifier le type expr pour permettre des valeurs telles que Set ("x",10) (qui représente l'instruction set x=10 de notre calculatrice), et introduire une fonction eval_set pour les évaluer dans le schéma de récursion mutuelle. Exemples de résultats attendus :
```
# example_context;;
- : context = {x = 10; y = 20; z = 30}
# eval_expr example_context (Set ("x",500));;
- : int option = Some 500
# eval_expr example_context (Add (Var "x", Literal 100));;
- : int option = Some 600
```

Problème 1 : Implémentez la fonctionnalité requise pour évaluer des séquences d'instructions, représentées par des expressions telles que

Seq [(Add ((Literal 2) , (Literal 2))) ; (Add ((Literal 5) , (Var "x" ))]

qui correspond à la séquence d'instructions suivante séquence d'instructions:

2+2
5+x
END

La fonction eval_expr appliquée à une séquence doit donner None si l'un de ses composants est évalué à None, sinon elle renvoie la valeur de la dernière expression. Exemple de résultats attendus :

# example_context;;
- : context = {x = 10; y = 20; z = 30}
# let seq_0 = Seq [(Add ((Literal 2),(Literal 2)));(Add ((Literal 5),(Var "x" )));];;
val seq_0 : expr = Seq [Add (Literal 2, Literal 2); Add (Literal 5, Var "x")]
# eval_expr example_context seq_0;;
- : int option = Some 15
# let seq_1 = Seq [Set ("x", 100); Add (Var "x", Var "y")];;
val seq_1 : expr = Seq [Set ("x", 100); Add (Var "x", Var "y")]
# eval_expr example_context seq_1;;
- : int option = Some 120
# let seq_2 = Seq [Set ("w",100);(Add ((Var "x"),(Var "y")));];;
val seq_2 : expr = Seq [Set ("w", 100); Add (Var "x", Var "y")]
# eval_expr example_context seq_2;;
- : int option = None