| Informatique 2 - Page principale - Environnement de développement - Syntaxe de Oz |
Ce mini-projet vise à vous faire implémenter un programme de taille plus conséquente que ce que nous avons fait durant les séances d'exercices. Dans ce projet vous allez utiliser les arbres, la récursivité et le pattern matching pour faire du calcul symbolique.
Le projet s'étend sur 2 semaines. C'est relativement court, ne tardez donc pas à vous y mettre!
| Evénement | Date FSA12 | Date SINF12 |
|---|---|---|
| Présentation du projet | jeudi 3/11 | jeudi 3/11 |
| Séance intermédiaire | mercredi 9/11 | mardi 8/11 |
| Séance intermédiaire | mercredi 16/11 | mardi 15/11 |
| Remise du projet | vendredi 18/11 à minuit au plus tard | |
Les deux séances intermédiaires vous permettent de poser des questions à votre tuteur. A l'échéance, chaque groupe devra remettre par e-mail à son tuteur
.oz,
commenté) ;L'objectif de ce projet est d'écrire un programme Oz permettant de
Notez que les trois premiers points sont relativement indépendants. Vous pouvez donc facilement vous répartir le travail, mais veillez à ce que chacun maîtrise suffisamment le travail des autres. Chaque étudiant doit pouvoir expliquer n'importe quelle partie du code de son groupe.
Les fonctions sont représentées sous forme d'arbres syntaxiques. La grammaire qui définit ces arbres est la suivante :
<Expr> ::= x | const(<Float>)
| '+'(<Expr> <Expr>) | '-'(<Expr> <Expr>) | '*'(<Expr> <Expr>) | '/'(<Expr> <Expr>)
| '-'(<Expr>) |'^'(<Expr> <Float>)
| sin(<Expr>) | cos(<Expr>) | tan(<Expr>)
| arctan(<Expr>) | exp(<Expr>) | ln(<Expr>)
L'atome x est l'unique variable de la fonction. Les
constantes doivent être des flottants (pour représenter "1", il faut
utiliser 1.0). Par ailleurs un nombre négatif est précédé
de "~", -1 s'écrit donc ~1.0.
Par exemple, la fonction x * cos(x+3)2 est représentée par l'arbre
'*'(x '^'(cos('+'(x const(3.0)) 2.0))
Toutes les représentations de <Expr> sont des
tuples. Donc pour accéder à une sous-expression, on peut utiliser
l'opération '.' ou le pattern matching.
Par exemple, avec la fonction
F = '+'(x const(3.0)),
F.1 donne x et
F.2 donne const(3.0).
Exercice 1. Transformez les fonctions suivantes en arbres syntaxiques. Vous pouvez utiliser le Parser ci-dessous pour vérifier vos réponses.
Exercice 2. Vérifiez si les enregistrements suivants respectent la grammaire définie ci-dessus. S'ils ne sont pas corrects, expliquez pourquoi.
'*'(x '^'(cos('+'(x const(3.0))) const(4.0)))'+'(sin(x) 3.0)'-'('-'(sin(x) cos('+'(const(2.0) x))))arctan('/'('+'(sin(x)) const(0.5)))
Vous allez devoir implémenter la dérivation des expressions
<Expr> définies par la grammaire ci-dessus.
Il vous faut donc écrire une fonction Derive qui prend une
expression en argument et qui renvoie la dérivée (par x) de cette
expression, qui est elle-même une expression.
Par exemple,
{Derive '+'('^'(x 2.0) x)} % la derivee de x^2+x
renvoie
'+'('*'(const(2.0) x) const(1.0)) % arbre syntaxique de 2*x+1
Ce résultat est un exemple. En effet, il existe plusieurs manières de
représenter la même expression. L'appel à Derive aurait pu
renvoyer
'+'(const(1.0) '*'(x const(2.0))) % 1+x*2
Votre première tâche est de définir précisément les règles de dérivation pour chaque type d'expression. Par exemple, pour l'addition,
{Derive '+'(E1 E2)}
est égal à
'+'({Derive E1} {Derive E2}).
Exercice 3. Définissez de la même façon la dérivation pour tous les autres cas. Vous êtes libres des choix possibles. Justifiez chaque cas en raisonnant par induction.
Exercice 4.
Implémentez la fonction {Derive Expr}.
Utilisez le pattern matching pour différencier chaque cas.
Les expressions obtenues par la dérivation peuvent comporter des
sous-expressions inutiles. Par exemple, l'expression
'+'(E1 const(0.0)) correspond à
E1.
Dans cette partie, vous allez simplifier les expressions. Vous devez
implémenter au moins les règles suivantes, mais vous pouvez en trouver
d'autres.
|
E + 0 → E 0 + E → E E - 0 → E 0 - E → -E |
E * 0 → 0 0 * E → 0 0 / E → 0 |
E * 1 → E 1 * E → E E / 1 → E |
C1 op C2 → C3 f(C1) → C2 |
| Légende. E est une expression, Ci est une constante, op est un opérateur binaire (+, -, *, /, ^), et f est un opérateur unaire (sin, cos, tan, arctan, exp, ln, -). | |||
Voici quelques exemples :
'*'('/'(const(3.0) const(4.0)) x) → '*'(const(0.75) x)
'-'(x sin(const(0.0))) → '-'(x const(0.0)) → x
'*'(x '*'(x const(0.0))) → '*'(x const(0.0)) → const(0.0)
Vous remarquerez dans les deux derniers exemples que l'ordre dans lequel
la simplification est faite est important. Le second exemple ne
correspond pas directement à un des cas présentés ci-dessus, mais
lorsque le cosinus est simplifié, il est remplacé par la constante 0.0,
ce qui permet de simplifier encore l'expression.
A votre avis, quelle est la règle à suivre pour l'ordre des
réductions ?
Exercice 5.
Ecrivez la fonction {SimplifyPlusZero Expr} qui prend une
expression en argument et renvoie l'expression dans laquelle ont étés
simplifiées toutes les expressions de la forme
'+'(E1 const(0.0)) ou
'+'(const(0.0) E1).
Considérez le sous-ensemble de la grammaire suivant :
<Expr> ::= x | const(<Float>) | '+'(<Expr> <Expr>)Testez cette fonction sur l'exemple suivant.
'+'('+'(const(0.0) const(0.0)) '+'(x const(0.0))) % (0+0)+(x+0) doit être simplifié en x
Exercice 6.
Ecrivez maintenant une fonction {SimplifyPlusOrMinusZero
Expr} qui simplifie une expression en supprimant les "+/-" zero.
Considérez la grammaire suivante.
<Expr> ::= x | const(<Float>) | '+'(<Expr> <Expr>) | '-'(<Expr> <Expr>)Testez votre fonction sur l'expression suivante.
'+'('-'('+'(const(0.0) const(0.0)) const(4.0)) '-'(x const(0.0))) % ((0+0)-4)+(x-0) est simplifié en -4+x
Exercice 7.
La même simplification doit être effectuée pour tous les autres cas.
Ecrivez la fonction {Simplify Expr} qui prend une
expression en argument et renvoie l'expression simplifiée. Ici, vous
devez évidemment considérer l'ensemble de la grammaire. Une fois de
plus, pensez à utiliser le pattern matching pour reconnaitre les cas où
se présentent chaque règle.
Testez votre fonction sur les expression suivantes.
sin('+'(const(0.0) '*'(x const(2.0)))) % sin(0+x*2) doit être simplifié en sin(x*2)
'/'(ln('*'(x const(1.0))) '-'(const(7.0) const(6.0))) % ln(x*1)/(7-6) doit être simplifié en ln(x)
Après avoir dérivé et simplifié les fonctions, il faut pouvoir les
évaluer. L'évaluation va vous permettre de dessiner le graphe de la
fonction. Le but est d'écrire une fonction {Evaluate Expr
X} qui prend en argument une expression et une valeur (en virgule
flottante) pour la variable x et qui renvoie la valeur de
la fonction en ce point.
Par exemple, l'appel {Evaluate cos(x) 0.0} renvoie
1.0 (en effet, cos(0) = 1).
Exercice 8. Comme dans la partie simplification, considérez la grammaire réduite suivante.
<Expr> ::= x | const(<Float>) | '+'(<Expr> <Expr>) | '-'(<Expr> <Expr>)Ecrivez la fonction Evaluate pour cette grammaire réduite.
Exercice 9.
Réécrivez votre fonction Evaluate pour prendre en compte
l'entièreté de la grammaire. Pour l'évaluation des fonctions sin, cos,
etc. utilisez les fonctions Sin, Cos,
Tan, Atan, Exp et
Log définies dans le module Float de Oz.
Pour l'évaluation de la fonction puissance, utilisez Pow.
Exercice 10.
En utilisant cette fonction Evaluate, écrivez une fonction
{EvaluateAll Expr List} qui prend en argument une
expression et une liste de flottants, et qui renvoie une liste de paires
de flottants qui correspondent à des points de la fonction.
{EvaluateAll cos(x) [0.0 1.0 2.0 3.0 4.0]} % renvoie [0.0#1.0 1.0#0.5403 2.0#~0.41615 3.0#~0.98999 4.0#~0.65364].
Il vous reste maintenant à dessiner le graphe d'une fonction et de ses
deux premières dérivées. Pour cela, nous vous fournissons le module
Graphic. Dès qu'une des fonctions ci-dessous est appelée,
une fenêtre apparaît.
declare
%% charger le module (une seule fois)
[Graphic]={Module.link ["http://www.info.ucl.ac.be/~pvr/ds/FSAB1402/tools/Graphic.ozf"]}
La procédure Graphic.curve prend en argument une
couleur et une liste de coordonnées, et dessine une courbe passant par
les points donnés. La couleur est un atome parmi white,
black, red, green,
blue, cyan, magenta,
yellow, grey. Les coordonnées sont des paires
X#Y, où X et Y sont des
flottants. Voici un exemple avec deux courbes.
%% dessine une courbe rouge et une courbe bleue
{Graphic.curve red [0.0#1.0 1.0#1.0 2.0#9.0 3.0#25.0]}
{Graphic.curve blue [~10.0#~1.0 ~5.0#7.3 10.0#10.0]}
La procédure Graphic.clear efface les courbes dans
la zone de dessin.
%% coup d'eponge
{Graphic.clear}
Par défaut, les bornes du graphique sont choisies pour que toutes les
courbes dessinées soient visibles. On peut cependant fixer les bornes
avec la procédure Graphic.setBounds. L'argument de
cette procédure est soit un enregistrement avec les bornes, soit l'atome
auto pour revenir au mode automatique.
%% fixer les bornes (x entre 0 et 10, y entre 0 et 15)
{Graphic.setBounds bounds(xmin:0.0 xmax:10.0 ymin:0.0 ymax:15.0)}
%% ajustement automatique des bornes
{Graphic.setBounds auto}
En bas de la fenêtre se trouve une zone de texte. Vous pouvez utiliser
cette zone pour taper l'expression d'une fonction. Lorsque
l'utilisateur clique sur le bouton "Draw", une procédure est
automatiquement appelée, avec comme argument la chaîne de caractères qui
se trouve dans la zone de texte. La procédure
Graphic.setAction vous permet de définir la procédure à
appeler. L'argument est le nom de la procédure à appeler. Ainsi, vous
pouvez lire l'expression tapée par l'utilisateur et dessiner la courbe
correspondante.
%% affiche la formule tapee par l'utilisateur
local
proc {AfficheArbre Texte}
{Inspect Texte}
end
in
{Graphic.setAction AfficheArbre}
end
Utilisez ce module pour dessiner le graphe de fonctions, et de leurs dérivées. Fixez vous-même l'intervalle sur lequel vous dessinerez les fonctions.
Un parseur est un outil qui analyse une chaîne de caractères et
produit un arbre syntaxique de cette chaîne. Dans le cas de ce projet,
nous vous fournissons un parseur pour des expressions mathématiques.
Le module Parser fournit une fonction
Parser.parse qui prend en argument une chaîne de
caractères et renvoie un arbre syntaxique. La chaîne de caractères
utilise les conventions habituelles.
declare
%% charger le module (une seule fois)
[Parser]={Module.link ["http://www.info.ucl.ac.be/~pvr/ds/FSAB1402/tools/Parser.ozf"]}
%% affiche '-'(sin('+'(x const(2.0))) cos(x))
{Inspect {Parser.parse "sin(x+2) - cos x"}}
%% affiche '*'(const(3.1416) arctan(ln(x)))
{Inspect {Parser.parse "pi * arctan(ln x)"}}
%% affiche '+'('^'(sin(x) 2.0) '^'(cos(x) 2.0))
{Inspect {Parser.parse "sin(x)^2 + cos(x)^2"}}
Note. Comme le montre le second exemple, le parseur reconnaît
"pi" et le remplace par la constante correspondante.
Nous vous fournissons un module permettant de lire un fichier ligne par
ligne. Le module Reader définit une fonction
Reader.lines qui prend en argument un nom de fichier
(une chaîne de caractères) et renvoie la liste des lignes du fichier.
Chaque ligne du fichier est une chaîne de caractères, c'est-à-dire une
liste de caractères (entiers).
declare
%% charger le module (une seule fois)
[Reader]={Module.link ["http://www.info.ucl.ac.be/~pvr/ds/FSAB1402/tools/Reader.ozf"]}
%% analyse la premiere ligne du fichier "toto"
local
Ls={Reader.lines "toto"}
in
{Inspect {Parser.parse Ls.1}}
end
Vous pouvez également lire l'entrée standard de votre programme
en spécifiant stdin comme nom de fichier. Pour utiliser
l'entrée standard, faites apparaître la fenêtre "Emulator" dans Emacs,
cliquez dedans et tapez ce que vous voulez. Chaque fois que vous
appuyez sur la touche Entrée, une nouvelle ligne apparaît dans
la liste renvoyée par Reader.lines.
%% L'utilisateur doit entrer son nom a l'entree standard
local
Ls={Reader.lines stdin}
in
{Inspect [bonjour Ls.1]}
end