Aller au contenu

DM de Pâques (MP2I 2021-2022) — Manipulation d'expressions

Devoir à la maison · MP2I · 2021-2022 · OCaml · partie III du devoir des vacances de Pâques

Cours : Arbres d'expressions

Autres parties : I. Dessin de graphes · II. Chasseurs de fantômes

L'objectif de ce devoir, à réaliser sur machine, est de manipuler informatiquement des expressions mathématiques. On a déjà vu cela avec l'évaluation d'expressions arithmétiques, on va ici prolonger ce qui a été fait en rajoutant :

  • des variables
  • des fonctions
  • des simplifications
  • des dérivées ou primitives formelles
  • \(\dots\)

Pour cela, on va utiliser un type d'expression qui va changer à mesure qu'on progresse dans ce devoir.

Expressions avec variables libres

On va utiliser le type expr suivant :

type bin_op = Add | Mult | Minus | Div
type un_op = Neg | Inv
type expr =
  | Const of int
  | Var of string
  | BinOp of expr * bin_op * expr
  | UnOp of un_op * expr

Ainsi, l'expression \(-\frac{x+1}{2+x^2}\) sera représentée par :

UnOp(Neg, BinOp(BinOp(Var "x",Add,Const 1),
                Div, BinOp(Const 2, Add, BinOp(Var "x", Mult, Var "x"))))

Les variables ici sont nécessairement libres : elles ne peuvent être liées comme dans \(\forall x, P(x)\) ou \(x \mapsto x+1\).

Question 16

Écrire une fonction variables_libres : expr -> string list qui renvoie la liste des variables apparaissant dans l'expression.

Corrigé 
let rec variables_libres e = match e with
  | Const _ -> []
  | Var x -> [x]
  | BinOp (e, _, e') -> variables_libres e @ variables_libres e'
  | UnOp (_, e) -> variables_libres e

Question 17

Écrire une fonction string_of_expr : expr -> string qui renvoie une expression sous la forme d'une chaîne de caractère lisible.

Dans l'exemple introductif, on renverra la chaîne : "-((x+1)/(2+(x*x)))".

Corrigé 
let string_of_bin_op op = match op with
  | Add -> "+" | Mult -> "*" | Minus -> "-" | Div -> "/"

let string_of_un_op op = match op with
  | Neg -> "-" | Inv -> "1/"

let rec string_of_expr e =
  let protect e =
    let s = string_of_expr e in
    match e with
    | Const _ | Var _ -> s
    | _ -> "(" ^ s ^ ")"
  in
  match e with
  | Const n -> string_of_int n
  | Var x -> x
  | BinOp(e, op, e') ->
    protect e
    ^ string_of_bin_op op
    ^ protect e'
  | UnOp(op, e) -> string_of_un_op op ^ protect e

Pour évaluer une telle expression, il est nécessaire de connaitre la valeur de chaque variable. Une association de valeurs aux variables est appelé un environnement d'évaluation. Pour simplifier, on va supposer qu'un environnement est une liste de couples \((variable, valeur)\).

type env = (string * float) list

Attention : dans l'expression, les constantes sont uniquement entières mais en raison de la présence de la division, il est nécessaire que l'évaluation se fasse avec des flottants.

Question 18

Écrire une fonction eval : env -> expr -> float qui évalue l'expression étant donné un environnement associant une valeur à chacune des variables.

Corrigé 
let rec eval env e =
  match e with
  | Const n -> float_of_int n
  | Var x -> List.assoc x env
  | BinOp(e, op, e') ->
    let v = eval env e in
    let v' = eval env e' in
    (match op with
     | Add -> v +. v'
     | Mult -> v *. v'
     | Minus -> v -. v'
     | Div -> v /. v')
  | UnOp(Neg, e) -> -. (eval env e)
  | UnOp(Inv, e) -> 1. /. (eval env e)

Si \(e, e'\) sont deux expressions et \(x\) est une variable, on note \(e[x \backslash e']\) l'expression déduite de \(e\) en substituant chaque occurrence libre (pour le moment elles le sont toutes) de \(x\) par l'expression \(e'\).

Exemple : si \(e = (2+x) - (x \times x)\) et \(e' = 4+y\) alors \(e[x \backslash e'] = (2+(4+y))-( (4+y) \times (4+y))\).

Si \(x\) n'est pas une variable libre de \(e\), alors \(e[x \backslash e'] = e\).

Question 19

Écrire une fonction subst : expr -> string -> expr -> expr telle que subst e x e' renvoie \(e[x \backslash e']\).

Corrigé 
let rec subst e x e' =
  match e with
  | Var y when x = y -> e'
  | BinOp(e1, op, e2) ->
    BinOp(subst e1 x e', op, subst e2 x e')
  | UnOp(op, e) -> UnOp(op, subst e x e')
  | _ -> e

On va essayer de simplifier des expressions en appliquant les règles suivantes :

  • \(e + 0 \rightarrow e\)
  • \(0 + e \rightarrow e\)
  • \(e - 0 \rightarrow e\)
  • \(0 - e \rightarrow -e\)
  • \(0 \times e \rightarrow 0\)
  • \(e \times 0 \rightarrow 0\)
  • \(1 \times e \rightarrow e\)
  • \(e \times 1 \rightarrow e\)
  • \(0 / e \rightarrow 0\)
  • \(e / 1 \rightarrow e\)
  • \(e \times (e'+e'') \rightarrow (e \times e')+(e \times e'')\)
  • \((e+e') \times e'' \rightarrow (e \times e'')+(e' \times e'')\)

Question 20

Écrire une fonction simpl : expr -> expr appliquant ces règles.

Corrigé 
let rec simpl e = match e with
  | BinOp(e, Add, Const 0)
  | BinOp(e, Mult, Const 1)
  | BinOp(e, Div, Const 1)
  | BinOp(Const 1, Mult, e)
  | BinOp(Const 0, Add, e) -> simpl e
  | BinOp(e, Minus, Const 0) -> simpl e
  | BinOp(Const 0, Minus, e) -> UnOp(Neg, simpl e)
  | BinOp(e, Mult, Const 0)
  | BinOp(Const 0, Mult, e)
  | BinOp(Const 0, Div, e) -> Const 0
  | BinOp(BinOp(e', Add, e''), Mult, e)
  | BinOp(e, Mult, BinOp(e', Add, e'')) ->
    let s_e = simpl e in
    simpl (BinOp(BinOp(s_e, Mult, simpl e'),
                 Add, BinOp(s_e, Mult, simpl e'')))
  | BinOp(e, op, e') ->
    let s_e = simpl e in
    let s_e' = simpl e' in
    let bin = BinOp(s_e, op, s_e') in
    if s_e <> e || s_e' <> e'
    then simpl bin (* pour propager *)
    else bin
  | UnOp(op, e) -> UnOp(op, simpl e)
  | _ -> e

Essayez d'améliorer au maximum votre fonction de simplification.

Dérivation formelle

Question 21

Écrire une fonction derive : string -> expr -> expr telle que derive x e renvoie l'expression correspondant à la dérivée de l'expression \(e\) par rapport à la variable \(x\).

Exemples :

  • derive "x" (BinOp(Var "x",Add,Const 1)) va renvoyer Const 1

  • derive "x" (BinOp(Var "x",Mult,Var "x")) va renvoyer

    BinOp(BinOp(Const 1,Mult,Var "x"),
      Add,BinOp(Var "x",Mult,Const 1))

  • derive "y" (BinOp(Var "x",Mult,Var "x")) va renvoyer Const 0

Corrigé 
let rec derive x e = match e with
  | Const _ -> Const 0
  | Var y -> Const (if x = y then 1 else 0)
  | BinOp(e, Mult, e') ->
    BinOp(BinOp(derive x e, Mult, e'), Add, BinOp(e, Mult, derive x e'))
  | BinOp(e, Div, e') ->
    BinOp(
      BinOp(BinOp(derive x e, Mult, e'), Minus, BinOp(e, Mult, derive x e')),
      Div, BinOp(e', Mult, e'))
  | BinOp(e, op, e') ->
    BinOp(derive x e, op, derive x e')
  | UnOp(Neg, e) -> UnOp(Neg, derive x e)
  | UnOp(Inv, e) -> UnOp(Neg, BinOp(derive x e, Div, BinOp(e, Mult, e)))

On peut rajouter des symboles de fonctions élémentaires comme \(\cos, \sin\dots\) et adapter la dérivation formelle.