In [1]:
Sys.command "ocaml -version";;
print_endline Sys.ocaml_version;;
Out[1]:
Out[1]:
La question de programmation pour ce texte était donnée en fin de page 6 :
On est libre de choisir l'implémentation qui nous convient pour les expressions arithmétiques sous forme arborescente.
Je choisis de ne considérer que les variables et pas les valeurs (on aura des expressions en OCaml comme F("x") pour la variable $x$), et uniquement des arbres binaires.
Les noeuds N(t1, op, t2) sont étiquetées par un opérateur binaire op, dont on fournit à l'avance une liste fixée et finie, et les feuilles F(s) sont étiquetées par une variable s.
« Écrire une fonction qui reçoit en argument une expression algébrique donnée sous forme arborescente et décore cette expression en calculant pour chaque nœud interne quelle est la valeur du paramètre ρ et quelle branche doit être évaluée en premier selon l’algorithme d’Ershov. »
In [2]:
type operateur = Plus | Moins | MoinsDroite | Mul | Div | DivDroite | Modulo | Expo ;;
(* On utilisera MoinsDroite et DivDroite pour la compilation avec la méthode d'Ershov *)
Out[2]:
In [3]:
type ('a, 'b) arbre_binaire = N of (('a,'b) arbre_binaire) * 'b * (('a,'b) arbre_binaire) | F of 'a
Out[3]:
Par exemple pour l'expression $\frac{x - yz}{u - vw}$, c'est-à-dire (x - y*z)/(u - v*w) :
In [4]:
(* exp1 = (x - y*z) *)
let exp1 =
N(
F("x"),
Moins,
N(
F("y"),
Mul,
F("z")
)
)
;;
Out[4]:
In [5]:
(* exp2 = (u - v*w) *)
let exp2 =
N(
F("u"),
Moins,
N(
F("v"),
Mul,
F("w")
)
)
;;
Out[5]:
In [6]:
(* exp3 = (x - y*z)/(u - v*w) *)
let exp3 =
N(
exp1,
Div,
exp2
)
Out[6]:
In [7]:
let rec nombre_rho (expr : ('a, 'b) arbre_binaire) : int =
match expr with
| F _ -> 0
| N(t1, _, t2) ->
let d1, d2 = nombre_rho t1, nombre_rho t2 in
if d1 = d2 then
d1 + 1
else
max d1 d2
;;
Out[7]:
Pour comparer avec le calcul, plus simple, de la hauteur de l'arbre :
In [8]:
let rec hauteur (expr : ('a, 'b) arbre_binaire) : int =
match expr with
| F _ -> 0
| N(t1, _, t2) ->
let d1, d2 = hauteur t1, hauteur t2 in
1 + (max d1 d2)
;;
Out[8]:
Exemples qui concordent avec le texte :
In [9]:
let _ = hauteur exp1;;
let _ = nombre_rho exp1;;
Out[9]:
Out[9]:
In [10]:
let _ = hauteur exp2;;
let _ = nombre_rho exp2;;
Out[10]:
Out[10]:
In [11]:
let _ = hauteur exp3;;
let _ = nombre_rho exp3;;
Out[11]:
Out[11]:
On choisit d'ajouter une décoration de type 'c :
In [12]:
type ('a, 'b, 'c) arbre_binaire_decore = N2 of ('c * (('a, 'b, 'c) arbre_binaire_decore) * 'b * (('a, 'b, 'c) arbre_binaire_decore)) | F2 of 'a
Out[12]:
On a besoin d'attacher à chaque noeud son paramètre $\rho$ et un drapeau binaire permettant de savoir si l'algorithme d'Ershov indique d'évaluer en premier le sous-arbre gauche (premier_gauche = true) ou droite (= false).
In [13]:
type decoration = {
rho : int;
premier_gauche : bool;
};;
Out[13]:
In [14]:
let rec decore (expr : (('a, 'b) arbre_binaire)) : (('a, 'b, decoration) arbre_binaire_decore) =
match expr with
| F v -> F2 v
| N (t1, o, t2) ->
let d1, d2 = nombre_rho t1, nombre_rho t2 in
let d = if d1 = d2 then d1 + 1 else max d1 d2 in
N2({rho = d; premier_gauche = (d2<= d1)}, (decore t1), o, (decore t2))
;;
Out[14]:
Dans nos exemples, on voit que l'évaluation favorise en premier (avec des premier_gauche = false) les expressions les plus profondes (à droite) au sens du paramètre $\rho$ :
In [15]:
decore exp1;;
Out[15]:
In [16]:
decore exp2;;
Out[16]:
In [17]:
decore exp3;;
Out[17]:
Les deux fonctions présentées ci-dessus n'utilisent pas d'autre espace que l'arbre décoré, et la pile d'appel récursif.
On peut essayer d'implémenter une fonction qui afficherait ceci pour la méthode d'évaluation naturelle :
Et ceci pour la méthode d'Ershov :
Ce n'est pas trop difficile, mais ça prend un peu de temps :
Bien sûr, tout cela fait beaucoup trop pour être envisagé le jour de l'oral ! Mais un des points aurait pû être implémenté rapidement.
In [18]:
type ('a, 'b) contexte = ('a * 'b) list;;
let valeur (ctx : ('a, 'b) contexte) (var : 'a) = List.assoc var ctx;;
(* une Hashtbl peut etre utilisee si besoin de bonnes performances *)
Out[18]:
Out[18]:
In [19]:
let contexte1 : (string, int) contexte = [
("x", 1); ("y", 2); ("z", 3);
("u", 4); ("v", 5); ("w", 6)
];;
Out[19]:
In [20]:
let intop_of_op (op : operateur) : (int -> int -> int) =
match op with
| Plus -> ( + )
| Moins -> ( - )
| MoinsDroite -> (fun v1 -> fun v2 -> v2 - v1)
| Mul -> ( * )
| Div -> ( / )
| DivDroite -> (fun v1 -> fun v2 -> v2 / v1)
| Modulo -> ( mod )
| Expo ->
(fun v1 -> fun v2 -> int_of_float ((float_of_int v1) ** (float_of_int v2)))
;;
Out[20]:
In [21]:
let rec eval_int (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
match expr with
| F(s) -> valeur ctx s
| N(t1, op, t2) ->
let v1, v2 = eval_int ctx t1, eval_int ctx t2 in
(intop_of_op op) v1 v2
;;
Out[21]:
Par exemple, $x$ vaut $1$ dans le contexte d'exemple, et $x + y$ vaut $1 + 2 = 3$ :
In [22]:
let _ = eval_int contexte1 (F("x"));;
Out[22]:
In [23]:
let _ = eval_int contexte1 (N(F("x"), Plus, F("y")));;
Out[23]:
In [24]:
let _ = eval_int contexte1 exp1;;
Out[24]:
In [25]:
let _ = eval_int contexte1 exp2;;
Out[25]:
In [26]:
let _ = eval_int contexte1 exp3;;
Out[26]:
On voit la faiblesse de l'interprétation avec des entiers, la division / est une division entière !
On peut aussi interpréter avec des flottants :
In [27]:
let contexte2 : (string, float) contexte = [
("x", 1.); ("y", 2.); ("z", 3.);
("u", 4.); ("v", 5.); ("w", 6.)
];;
Out[27]:
In [28]:
let floatop_of_op (op : operateur) : (float -> float -> float) =
match op with
| Plus -> ( +. )
| Moins -> ( -. )
| MoinsDroite -> (fun v1 -> fun v2 -> v2 -. v1)
| Mul -> ( *. )
| Div -> ( /. )
| DivDroite -> (fun v1 -> fun v2 -> v2 /. v1)
| Modulo ->
(fun v1 -> fun v2 -> float_of_int ((int_of_float v1) mod (int_of_float v2)))
| Expo -> ( ** )
;;
Out[28]:
In [29]:
let rec eval_float (ctx : (string, float) contexte) (expr : (string, operateur) arbre_binaire) : float =
match expr with
| F(s) -> valeur ctx s
| N(t1, op, t2) ->
let v1, v2 = eval_float ctx t1, eval_float ctx t2 in
(floatop_of_op op) v1 v2
;;
Out[29]:
Par exemple, $x$ vaut $1$ dans le contexte d'exemple, et $x + y$ vaut $1 + 2 = 3$ :
In [30]:
let _ = eval_float contexte2 (F("x"));;
Out[30]:
In [31]:
let _ = eval_float contexte2 (N(F("x"), Plus, F("y")));;
Out[31]:
In [32]:
let _ = eval_float contexte2 exp1;;
Out[32]:
In [33]:
let _ = eval_float contexte2 exp2;;
Out[33]:
In [34]:
let _ = eval_float contexte2 exp3;;
Out[34]:
On va commencer par lire l'arbre en parcours postfix (cf. TP2 @ ENS Rennes 2017/18) et ensuite l'évaluer grâce à une pile.
In [35]:
type ('a, 'b) lexem = O of 'b | V of 'a;;
type ('a, 'b) parcours = (('a, 'b) lexem) list;;
Out[35]:
Out[35]:
In [36]:
let parcours_postfix (expr : ('a, 'b) arbre_binaire) : (('a, 'b) parcours) =
let rec parcours vus expr =
match expr with
| F(s) -> V(s) :: vus
| N(t1, op, t2) -> O(op) :: (parcours (parcours vus t1) t2)
in
List.rev (parcours [] expr)
;;
Out[36]:
On le teste :
In [37]:
parcours_postfix exp1;;
Out[37]:
In [38]:
parcours_postfix exp3;;
Out[38]:
In [39]:
let eval_int_2 (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
let vus = parcours_postfix expr in
let pile = Stack.create () in
let aux lex =
match lex with
| V(s) -> Stack.push (valeur ctx s) pile;
| O(op) ->
let v1, v2 = Stack.pop pile, Stack.pop pile in
Stack.push ((intop_of_op op) v1 v2) pile;
in
List.iter aux vus;
Stack.pop pile
;;
Out[39]:
Par exemple, $x - y*z$ avec $x = 1, y = 2, z = 3$ vaut $1 - 2 * 3 = -5$ :
In [40]:
let _ = exp1 ;;
let _ = eval_int_2 contexte1 exp1;;
Out[40]:
Out[40]:
In [41]:
let _ = exp2;;
let _ = eval_int_2 contexte1 exp2;;
Out[41]:
Out[41]:
On peut maintenant faire la même fonction mais qui va en plus afficher l'état successif de la pile (avec des valeurs uniquement).
In [42]:
let print f =
let r = Printf.printf f in
flush_all();
r
;;
Out[42]:
In [43]:
let print_pile pile =
print "\nPile : ";
Stack.iter (print "%i; ") pile;
print "."
;;
Out[43]:
In [44]:
let eval_int_3 (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
let vus = parcours_postfix expr in
let pile = Stack.create () in
let aux lex =
print_pile pile;
match lex with
| V(s) -> Stack.push (valeur ctx s) pile;
| O(op) ->
let v1, v2 = Stack.pop pile, Stack.pop pile in
Stack.push ((intop_of_op op) v1 v2) pile;
in
List.iter aux vus;
Stack.pop pile
;;
Out[44]:
In [45]:
let _ = exp1 ;;
let _ = eval_int_3 contexte1 exp1;;
Out[45]:
Out[45]:
In [46]:
let _ = exp3;;
let _ = eval_int_3 contexte1 exp3;;
Out[46]:
Out[46]:
Il y a un soucis dans l'ordre d'affichage des lignes, dû à Jupyter et pas à notre fonction.
On vérifie qu'on utilise au plus 4 valeurs sur la pile, comme représenté dans la figure de l'énoncé :
In [47]:
let print_aff (line : int) (i : int) (s : string) : unit =
print "\n%02i: R[%d] := %s ;" line i s;
;;
Out[47]:
In [48]:
let string_of_op (op : operateur) : string =
match op with
| Plus -> "+"
| Moins | MoinsDroite -> "-"
| Mul -> "*"
| Div | DivDroite -> "/"
| Modulo -> "%"
| Expo -> "^"
;;
Out[48]:
In [49]:
let print_op (line : int) (i : int) (j : int) (k : int) (op : operateur) : unit =
match op with
| MoinsDroite | DivDroite -> (* on gère ici les opérateurs "inverses" *)
print "\n%02i: R[%d] := R[%d] %s R[%d] ;" line i k (string_of_op op) j;
| _ ->
print "\n%02i: R[%d] := R[%d] %s R[%d] ;" line i j (string_of_op op) k;
;;
Out[49]:
In [50]:
let eval_int_4 (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
let vus = parcours_postfix expr in
let pile = Stack.create () in
let ligne = ref 0 in
let aux lex =
incr ligne;
match lex with
| V(s) ->
Stack.push (valeur ctx s) pile;
print_aff !ligne ((Stack.length pile) - 1) s;
| O(op) ->
let v1, v2 = Stack.pop pile, Stack.pop pile in
Stack.push ((intop_of_op op) v1 v2) pile;
print_op !ligne ((Stack.length pile) - 1) ((Stack.length pile) - 1) (Stack.length pile) op;
in
List.iter aux vus;
Stack.pop pile
;;
Out[50]:
Essayons ça :
In [62]:
let _ = exp1 ;;
let _ = eval_int_4 contexte1 exp1;;
Out[62]:
Out[62]:
In [66]:
let _ = exp3;;
let _ = eval_int_4 contexte1 exp3;;
Out[66]:
Out[66]:
On rappelle qu'on a obtenu un arbre binaire décoré, représenté comme tel :
In [53]:
decore exp1;;
Out[53]:
On modifie notre parcours postfix pour prendre en compte la décoration et savoir si on calcul d'abord le sous-arbre gauche ou droit.
In [54]:
let parcours_postfix_decore (expr : ('a, 'b, decoration) arbre_binaire_decore) : (('a, 'b) parcours) =
let rec parcours vus expr =
match expr with
| F2(s) -> V(s) :: vus
| N2(dec, t1, Moins, t2) when dec.premier_gauche = false ->
O(MoinsDroite) :: (parcours (parcours vus t2) t1)
| N2(dec, t1, MoinsDroite, t2) when dec.premier_gauche = false ->
O(Moins) :: (parcours (parcours vus t2) t1)
| N2(dec, t1, Div, t2) when dec.premier_gauche = false ->
O(DivDroite) :: (parcours (parcours vus t2) t1)
| N2(dec, t1, DivDroite, t2) when dec.premier_gauche = false ->
O(Div) :: (parcours (parcours vus t2) t1)
| N2(dec, t1, op, t2) when dec.premier_gauche = false ->
O(op) :: (parcours (parcours vus t2) t1)
| N2(_, t1, op, t2) ->
O(op) :: (parcours (parcours vus t1) t2)
in
List.rev (parcours [] expr)
;;
Out[54]:
In [55]:
let eval_int_ershov (ctx : (string, int) contexte) (expr : (string, operateur) arbre_binaire) : int =
let vus = parcours_postfix_decore (decore expr) in
let pile = Stack.create () in
let ligne = ref 0 in
let aux lex =
incr ligne;
match lex with
| V(s) ->
Stack.push (valeur ctx s) pile;
print_aff !ligne ((Stack.length pile) - 1) s;
| O(op) ->
let v1, v2 = Stack.pop pile, Stack.pop pile in
Stack.push ((intop_of_op op) v1 v2) pile;
print_op !ligne ((Stack.length pile) - 1) ((Stack.length pile) - 1) (Stack.length pile) op;
in
List.iter aux vus;
Stack.pop pile
;;
Out[55]:
Essayons ça :
In [56]:
let _ = exp1 ;;
let _ = eval_int_ershov contexte1 exp1;;
Out[56]:
Out[56]:
In [68]:
let _ = exp3;;
let _ = eval_int_ershov contexte1 exp3;;
Out[68]:
Out[68]:
Et voilà, ce n'était pas trop dur !
Voilà pour la question obligatoire de programmation, et un petit bonus.
On a fait pas mal de bonus, en interprétant les termes, d'abord via l'arbre et des appels récursifs, ensuite par une lecture postfix et une pile, qui nous a permis de vérifier l'évolution de la pile et de sa hauteur (avec le même exemple que dans le texte), et ensuite avec une espèce de "compilation" en visualisant les affectations dans ces registres. La "compilation" n'est pas réelle, on a uniquement affiché des choses, mais elle permet de vérifier que la méthode de Ershov aide effectivement à réduire le nombre de registre requis.
Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.
Vous auriez pu choisir de modéliser le problème avec une autre approche, n'hésitez pas à me contacter svp.
C'est tout pour aujourd'hui les amis, allez voir ici pour d'autres corrections, et que la force soit avec vous !