\documentclass{tp-caml} \tp{ title=MaCalc v42, number=12, date=Vendredi 28 mars 2014, class=MP } \usepackage{pstricks,pst-node,pst-tree} \begin{document} \begin{abstract} Aujourd'hui on va fabriquer une petite calculatrice, MaCalc v42. Elle ressemble beaucoup à celle que vous utilisiez au lycée (et que vous utilisez peut être même encore). \end{abstract} \begin{corpus} \section{Représentation sous forme d'arbre} Les expressions mathématiques que l'on va manipuler seront sous la forme d'arbres d'expressions, avec des variables, des constantes et des opérateurs (+,-,*,/). Par exemple, pour représenter $5/x*9+7$ on obtient l'arbre : \pstree[nodesep=2pt,levelsep=5ex]{\TR{+} }{ \pstree{\TR{*}}{ \pstree{ \TR{/} }{ \TR{5} \TR{x} } \TR{9} } \TR{7} }\\ \subsection{Le type} Vous devez utiliser le type : \begin{caml} type Expr = | Plus of Expr*Expr | Moins of Expr*Expr | Fois of Expr*Expr | Div of Expr*Expr | Const of float | Var of string \end{caml} \subsection{Manipulations simples} \begin{exo} Écrire une fonction qui prend en argument une \texttt{Expr} et retourne la valeur représentée. On peut déclencher une exception quand une variable apparait dans l'expression. \end{exo} \begin{solc} let rec eval = function | Plus(a,b) -> eval a +. eval b | Moins(a,b) -> eval a -. eval b | Fois(a,b) -> eval a *. eval b | Div(a,b) -> eval a /. eval b | Const f -> f | Var a -> failwith "variable" \end{solc} \begin{exo} Écrire une fonction qui prend en argument une \texttt{string} et une \texttt{Expr} et retourne une \texttt{Expr} correspondant à la dérivée de la fonction par rapport à la variable désignée par la \texttt{string}. On ne cherche pas à avoir l'expression la plus simple possible mais juste à avoir une expression correcte. Par exemple \texttt{Var("x")} par rapport à la variable "x" donne \texttt{Const(1)}; \end{exo} \begin{solc} let rec diff x = function | Plus(a,b) -> Plus(diff x a,diff x b) | Moins(a,b) ->Moins(diff x a,diff x b) | Fois(a,b) -> Plus(Fois(diff x a,b),Fois(diff x b,a)) | Div(a,b) -> Div(Moins(Fois(diff x a,b),Fois(diff x b,a)),Fois(a,b)) | Const(f) -> Const(0.) | Var a -> if a = x then Const(1.) else Const(0.) \end{solc} \subsection{Variables} Pour manipuler les variables, on va utiliser ce que l'on appelle un environnement. Un environnement c'est un objet qui donne la valeur que l'on attribue à chaque variable. Une manière simple de représenter l'environnement c'est d'avoir une $(string,float)~list$. Quand $("x",3.14159)$ apparait dans la liste, la liste ne contenant pas de doublon, c'est que $x$ vaut $3.14159$. Par chance, Camllight dispose d'une fonction \begin{prototype} List.assoc : : 'a -> ('a * 'b) list -> 'b \end{prototype} En appelant $assoc~x~liste$, on obtient, si elle existe, la valeur $y$ telle que $(x,y)$ soit dans la liste. \begin{exo}\textbf{Évaluation avec des variables} Reprendre votre solution à la question 1 en gérant les variables. Votre fonction doit maintenant prendre en paramètre un environnement et une \texttt{Expr}. \end{exo} \begin{solc} let rec eval2 env = function | Plus(a,b) -> eval2 env a +. eval2 env b | Moins(a,b) -> eval2 env a -. eval2 env b | Fois(a,b) -> eval2 env a *. eval2 env b | Div(a,b) -> eval2 env a /. eval2 env b | Const(f) -> f | Var a -> assoc a env \end{solc} \section{Tracer des expressions} Votre calculatrice de lycée vous permettait de tracer des courbes ? MaCalc peut aussi le faire ! \paragraph{Rappel sur les fonctions graphiques} Lancer \texttt{ocaml} avec la commande \texttt{ocaml Graphics.cma}. \begin{caml} open Graphics ;; (* a faire une fois *) open_graph "" (* pour ouvrir une fenetre *) set_color (rgb 255 0 0 ) ; (* change la couleur du pinceau *) moveto x y ; (* deplace le pinceau *) lineto x y ; (* deplace le pinceau en dessinant *) \end{caml} \begin{exo} Écrire un programme qui prend en argument $e$ une \texttt{Expr}, \texttt{x} une string, $a,b,c,d$ des $float$ et qui trace $e(x),x\in [a,b]$, pour une fenêtre qui a un intervalle de $y=[c,d]$. \end{exo} \begin{solc} let trace e v a b c d = open_graph " 800x800" ; set_color (rgb 0 0 255) ; moveto 0 400 ; lineto 800 400 ; moveto 400 0 ; lineto 400 800 ; set_color (rgb 255 0 0) ; moveto 0 (int_of_float (800./.(d-.c)*.(eval2 [v,a] e -. c))) ; for x = 1 to 800 do lineto x (int_of_float (800./.(d-.c)*.(eval2 [v,((float_of_int x)*.(b-.a)/.800.+.a)] e -. c))); done \end{solc} \section{Lecture des expressions} Dans votre calculatrice de lycée, vous ne tapiez pas $Plus(Fois(Const 2.,Var "x"),Const 5.)$, non ? On s'intéresse donc à la manière de récupérer les expressions de manière naturelle. Tout d'abord, il nous faut une fonction qui lit des entiers dans une chaine. \subsection{La notation polonaise} La notation polonaise est une manière d'écrire les calculs sans avoir besoin de mettre de parenthèse. Tout en étant relativement simple pour les humains, elle est surtout très simple à lire par ordinateur. La notation polonaise est une notation préfixée, c'est à dire qu'au lieu d'écrire $14+28$ on écrit + 14 28. Au lieu d'écrire $(3+4)*6$ on écrit * + 3 4 6. Elle peut sembler peut naturelle pour un humain mais en fait c'est celle qu'on emploie quand on lit le calcul (enfin presque). Pour $(3+4)*6$ on lit \textit{Produit de la somme de 3 et 4 avec 6}. \begin{exo} Transformer de notation polonaise à notation 'habituelle' ou l'inverse les expressions suivantes : \begin{itemize} \item + * - 3 5 + 5 6 8 \item + 2 + 6 + 5 7 \item 6*47+451+57*45*4+5*8/42 \end{itemize} \end{exo} \begin{exo} Écrire une fonction lit\_int qui lit un entier dans une chaine. C'est à dire, étant donné une chaîne $s$ et un entier $i$ renvoie $v$ et $j$ (avec $j$ maximal) de sorte que les caractères $i$ à $j-1$ correspondent à l'entier $v$ et que $j$ soit un espace. Pour savoir un caractère $c$ correspond à un entier on peut utiliser la condition suivante : \begin{caml} let is_int c = (c>'0' && c< '9') ;; \end{caml} Pour récupérer la valeur d'un chiffre on peut utiliser : \begin{caml} let intChar c = int_of_char c-int_of_char '0' ;; \end{caml} \end{exo} \begin{exo} Écrire une fonction lit\_var qui fonctionne de la même manière que lit\_int. On peut, de même, utiliser $c\geq `a` \&\& c\leq `z`$ et $string\_of\_char$. \end{exo} \begin{exo} En déduire une fonction lit\_expr qui lit une expression en notation polonaise dans une fonction. \end{exo} \begin{exo} Compiler les 3 fonctions précédentes en une fonction parse qui prend une chaîne de caractère et renvoie l'expression correspondante. \end{exo} \begin{solc} let parse spre = let s = spre ^" " in let rec lit_int v i = if s.[i]>=`0` && s.[i]<=`9` then lit_int (v*10+int_of_char s.[i]-int_of_char `0`) (i+1) else (Const (float_of_int v),i) in let rec lit_var deb i = if s.[i]>=`a` && s.[i]<=`z` then lit_var (deb^(string_of_char s.[i])) (i+1) else (Var deb,i) in let rec lit_expr i = let (v,ni) = lit_var "" i in if ni<>i then (v,ni) else let (v,ni) = lit_int 0 i in if ni <> i then (v,ni) else let (e1,i1) = lit_expr (i+2) in let (e2,i2) = lit_expr (i1+1) in (match s.[i] with | `+` -> Plus(e1,e2),i2 | `-` -> Moins(e1,e2),i2 | `*` -> Fois(e1,e2),i2 | _ -> Div (e1,e2),i2) in fst (lit_expr 0) \end{solc} \begin{exo} Écrire une fonction simplifie qui prend en argument une expression qui renvoie une expression simplifiée. On peut, par exemple, supprimer les multiplications par 1 ou 0, pré-calculer certaines branches, simplifier ... \end{exo} \section{Pour ceux qui s'ennuient} \begin{exo} Écrire la table des inverses des nombres de $\mathbb{Z}/17\mathbb{Z}$. \end{exo} \begin{solc} let divi p = let rec exp a = function | 0 -> 1 | n -> let s = exp a (n/2) in if n mod 2 = 0 then (s*s) mod p else (s*s*a) mod p in for y = 1 to p-1 do print_int (exp y (p-2)) ; print_string " " done let a = divi 17 \end{solc} \begin{exo} Écrire une quine, c'est à dire un programme qui affiche son propre code source. \end{exo} \begin{solc} (fun s -> print_string s ; print_char (char_of_int 34) ; print_string s ; print_char (char_of_int 34) ) "(fun s -> print_string s ; print_char (char_of_int 34) ; print_string s ; print_char (char_of_int 34) )" \end{solc} $\blacksquare$ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \end{corpus} \end{document} %%% Local Variables: %%% mode: latex %%% TeX-master: t %%% End: