Université Paris 6 Licence d'informatique	Module de Programmation Année 2000-2001

Travaux dirigés n° 7

Exercice 1 Typer les phrases :

type logique = Vrai | Faux ;;

let cond test si sinon = match test with
  | Vrai -> si
  |  _  -> sinon ;;

let cond_bis test = match test with
  | Vrai -> (function si -> si)
  |  _  -> (function sinon -> sinon) ;;

Exercice 2 On considère la déclaration :

let id = function x -> x ;;

typer les déclarations :

let cond test si sinon = 
  if (id test)
  then (id si)
  else (id sinon);;

let cond_bis id test si sinon =
  if (id test)
  then (id si)
  else (id sinon);;

On ajoute maintenant la déclaration :

let id_bis = id id ;;

Quel est le type de id_bis ? Typer la déclaration :

let cond test si sinon = 
  if (id_bis test)
  then (id_bis si)
  else (id_bis sinon);;

Quel est le type de id_bis ?

Exercice 3 (Expressions) On considère des expressions arithmétiques qui peuvent être soit des entiers, soit des sommes de deux expressions arithmétiques, soit des produits de deux expressions arithmétiques. Nous nommerons arbres d'évaluation de telles expressions.

1. Définir le type arbre_eval pour représenter ces arbres d'évaluation.
2. Écrire une fonction string_of_arbre_eval ( : arbre_eval -> string) qui transforme un arbre d'évaluation en une chaîne de caractères imprimables. On prendra soin de parenthèser complètement le résultat.

Écrire une fonction eval ( : arbre_eval -> int) qui évalue un arbre en effectuant toutes les opérations arithmétiques qu'il contient.

3. On définit la complexité d'un arbre d'évaluation comme étant le nombre d'opérations arithmétiques qu'il contient, c'est-à-dire le nombre d'opérations arithmétiques que la fonction eval doit effectuer pour simplifier un arbre d'évaluation en un entier.

Écrire cette fonction complexite ( : arbre_eval -> int).

On désire maintenant pouvoir réutiliser certains calculs en nommant certains arbres d'évaluation.
4. Modifier le type arbre_eval de façon à autoriser des ``variables'' représentées par des string (que nous nommerons leur nom) et des expressions de la forme soit X = A₁ dans A₂ que nous nommeront des decl. Nous nommerons des util les expressions terminales qui utilisent une variable de nom X; elles représentent la valeur de X.

5. Écrire une fonction liste_des_variables retournant la liste des noms des variables apparaissant dans une expression. Cette liste pourra contenir des doublons (plusieurs occurrence d'un même nom).

6. Proposez une nouvelle version de cette fonction retournant une liste sans doublons.

7. Écrire une fonction variables_libres retournant la liste des noms de variables libres. On rappelle que les variables libres d'une expression E sont définies ainsi:

Si E est un entier, il ne contient pas de variables libres.
Si E est une variable de nom X, X est sa seule variable libre.
Si E est une somme (ou un produit) de deux expressions E₁ et E₂, ses variables libres sont celles de E₁ ou de E₂.
Si E est une déclaration de la forme soit X = E₁ dans E₂, ses variables libres sont toutes celles de E₁ ou celles de E₂ privées de X.

8. Écrire une fonction variables_liees retournant la liste des variables qui ne sont pas libres. En déduire un prédicat expression_close qui est vrai si son argument ne contient pas de variables libres.

9. La complexité d'un arbre d'évaluation peut s'étendre à ces nouveaux arbres d'évaluation en disant que la complexité d'une ``decl'' est la somme de celles des deux sous-arbres qu'il contient. Réécrire la fonction complexite en tant compte de ces modifications.

10. On utilisera un environnement pour stocker les valeurs des variables. C'est une liste d'association du type (string * int) list. On pourra utiliser les différentes fonctions de la librairie standard de Caml pour manipuler ces listes.

Réécrire la fonction eval en ajoutant un paramètre d'environnement sur ces nouveaux arbres d'évaluation. On aura donc eval ( : (string * int) list -> arbre_eval -> int) qui s'applique à des expressions closes.

Ce document a été traduit de L^AT_EX par H^EV^EA.