1.Les expressions, dérivation formelle.

Les types somme et le filtrage facilitent grandement l'écriture de fonctions de manipulation symbolique. On se propose d'illustrer cela sur un petit programme de dérivation formelle d'expressions algébriques.

On considère un petit langage d'expression pour les polynômes à puissance et coefficients entiers. Plus précisément l'ensemble des expressions est récurivement défini par:

les constantes sont des expressions ;
les variables sont des expressions ;
si e est une expression et n un entier alors eⁿ est une expression ;
si e₁ et e₂ sont des expressions alors e₁+ e₂ et e₁ * e₂ sont des expressions.

1.1.

Définir un type exp pour ces expressions.
Donner des exemples d'expressions et de leur représentations.

1.2.

Écrire une définition de la fonction string_of_exp retournant la représentation d'une expression sous forme de chaîne de carctères.

1.3.

Les règles de dérivation formelles en x sont: :

dc/dx = 0 si c est une constante.
dx/dx = 1.
dy/dx = 0 si y est une variable différente de x.
d/dx(eⁿ) = ne^n-1de/dx si e est une expression et n un entier..
d/dx(u+ v) = du/dx + dv/dx.
d/dx(uv) = vdu/dx + udv/dx.

Définir la fonction deriv telle que (deriv x e) retourne la dérivée de l'expression e par rapport à la variable x.

2.Les S-expressions.

On veut représenter des expressions algébriques simples et constantes à l'aide des S-expressions.
Les expressions sont définies par :

un entier est une expression,
si e₁ et e₂ sont des expressions alors e₁ + e₂ et e₁ * e₂ sont des expressions.

On reprend une représentation des S-expressions voisine de celle du cours pour représenter ces expressions en utilisant deux formes d'atomes pour représenter les entiers et les opérateurs.

On utilisera le type Ocaml suivant :

type s_exp =
Nil
| N of int
| Op of char
| Cons of s_exp * s_exp ;;

2.1.Expressions et S-expressions

Donner des exemples de S-expressions représentant des expressions valides, suivant la définition des expressions données ci-dessus.
Donner des exemples de S-expressions syntaxiquement valides mais ne représentant pas une expression.

2.2.Écriture des S-expressions

2.2.1.Paires totalement parenthésés

Définir la fonction string_of_s_exp telle que (string_of_s_exp e) retourne la chaîne de caractères représentant la S-expression e avec les conventions suivantes :

Nil est représenté par "()",
les entiers par leur représentation décimale,
les opérateurs par la chaîne ne contenant que leur caractère,
les paires par les représentations des deux S-expressions séparées par une espace et placées entre parenthèses : par exemple "(1 ())".

2.2.2.Écriture à la "scheme"

Définir la fonction toString telle que (toString e) retourne la représentation sous forme de chaîne de caractères de l'expression e avec un parenthésage minimum des paires.
Par exemple :
Cons (N 1, Cons (N 2, Cons (N 3, Nil))) aura pour image "(1 2 3)" et
Cons (N 1, Cons (N 2, Cons (N 3, N 4))) aura pour image "(1 2 3 . 4)"
Indication : définir deux fonctions mutuellement recursives par let rec ... and ... ;;
Tester soigneusement votre implantation.

2.3.Evaluation des expressions

Définir la fonction eval : s_exp -> int telle que (eval se)

retourne la la valeur de l'expression e représentée par la S-expression se lorsque e est une expression valide ;
lève l'exception Failure appliquée à la chaîne de carctères "eval : " concaténée avec l'écriture de la sous-expression non évaluable, lorsque la S-expression se ne représente pas une expression e valide.

Tester soigneusement votre implantation. En particulier, vérifier l'evaluation des S-expressions représentant les expressions (3 * 2) + 1 et 3 * (2 + 1). Tester aussi leur écriture dans les deux formes.
Évaluer l'expression 3 * 2 + 2 * 5.
Indication : pour écrire les S-expressions représentant ces expressions, pensez à utiliser les déclarations locales pour écrire les sous-expressions.