Simplifier une expréssion arithmétique

Version imprimable

Bonjour,

Voilà j'essaye de faire une fonction "simplifier" qui avec une expression arithmétique contenant des variables, rend une simplification où tous les calculs ( d'entiers donc ) sont effectués

Voici mes déclarations:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(* Definition d'un arbre binaire *)
type ('a,'b) arbre_bin = Feuille of 'b
			 | Noeud of ('a,'b) noeud
 
and ('a,'b) noeud = { gauche : ('a,'b) arbre_bin;
		      op : 'a;
		      droite : ('a,'b) arbre_bin };;
 
(* Operateur arithmétique *)
type operateur = Plus | Moins | Mul | Div;; 
 
(* Type de valeur dans l'expression *)
type primaire = Variable of string | Entier of int;;
 
(* Expression arithmétique *)
type expr = (operateur, primaire) arbre_bin;;
 
(* Exemple d'expression *)
let e2 = Noeud({gauche = Feuille (Variable  "x"); op=Mul; droite =
		   Noeud({gauche = Feuille (Variable "y"); op = Moins ; droite = 
			     Noeud({gauche = Feuille (Entier 5); op = Div; droite = Feuille (Entier 4)})
			 })
	       });;

Et voici où je me suis arrêté. Je pense que mon problème est que je n'arrive pas à faire l'addition de 2 feuilles. Enfin bon je bloque

Code:

1
2
3
4
5
6
7
8
9
10
let evalOp = function 
    Plus -> (+)
  | Moins -> (-)
  | Mul -> fun x y -> x * y
  | Div -> (/);;
 
let rec simpl = function e -> match e with
    Feuille f -> f
  | Noeud n -> match (simpl(n.gauche),simpl(n.droite)) with 
	(Feuille (Entier i), Feuille (Entier j)) -> Feuille (Entier (evalOp (n.op) i j));;

Tout aide ou remarque sont le bienvenues ! Et merci à vous ;)

09/02/2011, 21h43
gorgonite

peux-tu détailler ce que tu souhaites réellement faire ?
histoire qu'on t'indique des algos adaptés ?

connais-tu le Global Value Numbering ou le Partial Expression Reduction, voire un mixte des deux appelé VNGPRE ?
09/02/2011, 21h49
Nollo

Non du tout. Sinon j'avais trouvé 2 ou 3 TDs sur les expressions arithmétiques en ocaml, mais l'approche est très différente de la mienne :calim2:

Sinon pour donner un exemple, je prends cette expression:

e = x * ( y - ( 5 / 4 ))

Après simplification
e simplifié = x * ( y - 1 ))
09/02/2011, 22h07
gasche

Voici la façon dont je procèderais, style "normalisation par évaluation":

1. Définir une "forme normale" pour tes expressions, c'est à dire la structure de ce que tu espères obtenir une fois que tu as simplifié au maximum; ici, il me semble que ce sont des polynomes multi-variables, donc par exemple une liste de couples (entier, liste de variables) interprétée comme une somme de produits : [(2, ["x"; "y"]); (3, ["z"]); (5, [])] pour 2*X*y+3*Z=5. Mais d'autres formes sont possibles (par exemple utiliser un (string set, int) map pour des raisons d'efficacité algorithmique).

2. Écrire une fonction d'évaluation qui évalue tout terme vers une forme normale (donc tu définis comment transformer un entier ou une variable en polynôme, et l'effet des opérations sur les polynomes, puis tu évalues récursivement ton arbre).

3. Ensuite si tu veux récupérer un arbre en sortie, écrire une fonction qui va dans l'autre sens, qui te redonne un arbre à partir d'une forme normale (donc ici qui "décompose" un polynôme en somme de produits).

La fonction de simplification est alors la composée des fonctions des étapes 2. et 3.

ta fonction simpl compile ?

avec cela plutôt ?
Code:

1 2 3 4 5 6 7 8 9 let rec simpl e = match e with Feuille f -> Feuille f | Noeud n -> match (simpl(n.gauche),simpl(n.droite)) with (Feuille (Entier i), Feuille (Entier j)) -> Feuille (Entier (evalOp (n.op ) i j)) | (g,d) -> Noeud({gauche=g; op=n.op ; droite=d}) ;;
après clairement ce n'est pas satisfaisant... parcourir systématiquement l'arbre, ne pas y éliminer les redondances, etc

peux-tu définir le type d'expressions à gérer ?
resteras-tu sur des opérations linéaires ? as-tu besoin de polynômes ? as-tu besoin d'expressions quelconques ?

09/02/2011, 22h22
Nollo

A vrai dire, je n'ai pas vraiment de consignes supplémentaires.

Ma fonction simpl ne marche pas ( sinon je ne serais pas ici :mrgreen: ). Ma fonction devait normalement évaluer si les feuilles sont des entiers, et dans ce cas effecuter l'opération.
09/02/2011, 22h28
gorgonite

Citation:

Envoyé par Nollo

A vrai dire, je n'ai pas vraiment de consignes supplémentaires.

alors, à quoi souhaites-tu te limiter ?

Citation:

Envoyé par Nollo

Ma fonction simpl ne marche pas ( sinon je ne serais pas ici :mrgreen: ). Ma fonction devait normalement évaluer si les feuilles sont des entiers, et dans ce cas effecuter l'opération.

j'ai remarqué ^^ la mienne passe en ne modifiant pas trop la tienne, et fait ce que tu souhaitais :P

mais il aurait été bon que tu regardes l'erreur, et tente de mieux voir pourquoi ça foirait... et clairement une énorme erreur de typage (et un filtrage non exhaustif)
09/02/2011, 22h37
Nollo

J'avoue que c'est un peu hardcore, mais je n'ai pas besoin de mettre tous les patterns dans mon filtrage vus que je travaille que sur les entiers.

Je vais potasser ça merci :)

Au cas où ça intéresserait des gens:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
(* Formes normales *)
module SumMap (M : Map.OrderedType) = struct
  include Map.Make(M)
  let singleton x v = add x v empty
  let sum f m1 m2 =
    fold (fun k v1 m ->
      let v2 = try Some (find k m) with Not_found -> None in
      match f v1 v2 with
        | None -> m
        | Some v -> add k v m)
      m1 m2
end
 
let sum v1 = function
  | None -> Some v1
  | Some v2 ->
    match v1 + v2 with
      | 0 -> None
      | v -> Some v
 
(* produit de variables avec multiplicité : X*Y²*Z *)
module Monome = SumMap(String)
type monome = int Monome.t
 
(* somme de monomes avec coefficients : 2*X + 3*Z*Y + 5 *)
module Polynome =
  SumMap(struct
    type t = int Monome.t
    let compare = Monome.compare Pervasives.compare
  end)
type polynome = int Polynome.t
 
let poly_add p1 p2 =
  Polynome.sum sum p1 p2
 
(* multiplication d'un polynome par un monome et un scalaire *)
let mono_mult m1 c1 p =
  Polynome.fold
    (fun m2 c2 acc -> Polynome.add (Monome.sum sum m1 m2) (c1 * c2) acc)
    p Polynome.empty
 
(* multiplication de polynomes *)
let poly_mult p1 p2 =
  Polynome.fold (fun monome coeff p -> 
    poly_add p (mono_mult monome coeff p2)
  ) p1 Polynome.empty
 
 
(* fonction d'évaluation des arbres vers les polynomes;
   c'est le cœur de la simplification *)
let rec eval : expr -> polynome = function
  | Feuille (Entier n) ->
    Polynome.singleton Monome.empty n
  | Feuille (Variable v) ->
    Polynome.singleton (Monome.singleton v 1) 1
  | Noeud {gauche=g; op=op; droite=d} ->
    (match op with
      | Plus -> poly_add
      | Mul -> poly_mult
      | Moins | Div -> failwith "unsupported")
      (eval g) (eval d)
 
(* fonction de retour des polynomes vers les arbres; le code est un
   peu compliqué car on essaie de gérer intelligemment les cas où le
   coefficient est 1, il n'y a pas de variables, etc.
*)
let noeud op v1 v2 =
  Noeud {gauche = v1; op = op; droite = v2}
let noeud' op v1 v2 = match v1, v2 with
  | None, None -> None
  | Some v, None | None, Some v -> Some v
  | Some v, Some v' -> Some (noeud op v v')
 
let return : polynome -> expr = fun p ->
  let return_monome m =
    let rec return_var var coeff = match coeff with
      | 0 -> None
      | 1 -> Some (Feuille (Variable var))
      | n -> noeud' Mul (return_var var 1) (return_var var (n - 1)) in
    Monome.fold
      (fun var coeff acc ->
        noeud' Mul (return_var var coeff) acc)
      m None in
  match
    Polynome.fold (fun monome coeff acc ->
      noeud' Plus acc
        (let c = match coeff with
          | 1 -> None
          | n -> Some (Feuille (Entier n)) in
         let m = return_monome monome in
         noeud' Mul c m)
    ) p None
  with
    | Some e -> e
    | None -> Feuille (Entier 0)
 
(* fonctions commodes pour des tests *)
let i n = Feuille (Entier n)
let v v = Feuille (Variable v)
let (+!) a b = noeud Plus a b
let ( *!) a b = noeud Mul a b
 
let test =
  (* (2X + 3X + 4x * 5Y + 2) * 6 + 1 = 13 + 30X + 120XY *)
  return (eval ((i 2 *! v "x"
                 +! i 3 *! v "x"
                 +! i 4 *! v "x" *! i 5 *! v "y"
                 +! i 2) *! i 6
                +! i 1));;

Bien sûr, on peut obtenir un résultat équivalent en restant dans les arbres de départ, et en choisissant les bonnes règles de ré-écriture. Le fait de rendre la forme normale explicite permet de mieux contrôler la sémantique de la simplification (on est au clair sur la forme du résultat), et permet souvent un meilleur contrôle des performances de la simplification.

10/02/2011, 07h14
Nollo

Merci à vous 2, je passe en résolu car je pense tenir une solution et vous avez donné pas mal d'éléments et de pistes :ccool:
10/02/2011, 11h39
TropMDR

Citation:

Envoyé par gorgonite

connais-tu le Global Value Numbering ou le Partial Expression Reduction, voire un mixte des deux appelé VNGPRE ?

Ah ouais, violent :p Il n'a pas d'affectation, le global value numbering ne s'applique pas du tout :)
10/02/2011, 12h23
gorgonite

Citation:

Envoyé par TropMDR

Ah ouais, violent :p Il n'a pas d'affectation, le global value numbering ne s'applique pas du tout :)

il pourrait en vouloir à terme... :aie: (en tout cas, j'aime bien VNGPRE dans les premières phases du middle-end d'un compilo )
10/02/2011, 13h37
Nollo

Nan du tout.

C'est vraiment un truc bête et méchant, c'est la dernière question d'un TP d'ocaml, et étant donné qu'on a pas de correction, je voulais de mon côté trouver une solution. J'ai fais le reste du TP sans grosse difficulté et je trouvais bizarre de coincer à la dernière question comme ça.