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


Travaux dirigés n° 6





Exercice 1

Soit la déclaration suivante : 
let rec Ack (m, n) = 
  if m = 0 then n+1 else 
  if n = 0 then Ack (m-1, 1) else Ack (m-1, Ack (m, n-1));;

1. Typez cette déclaration.
2. Typez et évaluez Ack (1, 1).
Exercice 2

Soit le programme suivant:

type 'a untyp =  Vid | N of 'a * ('a list) ;;

let rec une_fct = function h -> function
| Vid -> []
| N(s, []) -> [h(s)]
| N (s, t :: r) -> h(t) :: (une_fct  h (N(s,r)) ) ;;

une_fct (function x -> x+3) (N(5, [10;11]));;

1. Effectuez complètement le typage de une_fct.
2. Que vaut (une_fct (function x -> x+3) (N(5, [10;11])) )? Définissez le calcul effectué par une_fct, à l'aide d'une famille d'équations.
3. Définissez une fonction récursive terminale qui retourne le même résultat que la fonction une_fct.
Exercice 3 (Les listes d'associations, épisode II)

Résumé de l'épisode précédent1 : Dans le dernier TD, le type list_assoc a été introduit pour manipuler des listes d'association. Deux fonctions, assoc et assoc_all, ont été écrites pour effectuer les 2 traitements de base que l'on a à faire avec ce genre de liste.
1. Soit la déclaration suivante qui représente une liste d'association où la clé est un entier et la valeur est une chaîne. 
let exemple = [ (1,"a") ; (2,"b") ; (3,"c") ] ;;
Après avoir donné la définition du type liste_assoc correspondant (pour vérifier qu'il est compatible avec celui que vous aviez défini lors de l'épisode I), typez cet exemple.


2. Soit la déclaration suivante issue de mon programme (qui ne marche pas): 
let x = "Hello";;
let exempleBug = [ (1,`a`) ; (2,x) ] ;;
Typez cette déclaration.


3. Pour essayer de trouver comment bien écrire mon exemple, j'ai piraté un extrait du code (qui marche) de la machine de mon voisin de devant: 
let exempleBon = [ (1, sqrt)) ; (2, f) ] ;;
Mais je n'ai pas pu voir le type de la variable f. Typez cette déclaration et donnez le type de f pour que le typage soit correct.


4. Comme j'ai moyennement confiance en mon voisin de devant, je suis allé voir si je ne pouvais pas copier le programme de notre experte en caml, mais, sur le chemin entre sa machine et la mienne je ne me suis rappelé que de ce bout de code : 
let myConst = mySqrt 6.0;;
let myFun = function x -> (myOldFun x) + (mySqrt x) + myConst;;
let myExemple = [ (1, mySqrt) ; (2, myFun) ] ;;
Typez cette déclaration et donnez tous les types nécessaires pour que le typage soit correct.

Exercice 4 (Des petites formules...)

On souhaite disposer d'un petit évaluateur de formules afin d'écrire des additions et des multiplications de nombres entiers, en disposant aussi de variables. Une formule F pourra être:
1. Définissez les types operateur et formules nécessaires à ce programme. Donnez des exemples de formules.
2. Écrivez une fonction egalesFormules qui teste si 2 formules passées en paramètres sont égales.
3. À partir d'une formule, on veux déterminer la liste de toutes les variables qui la composent. Après avoir défini le type listeVariables, écrivez une fonction allVariables qui construit la liste de toutes les variables de la formule passée en paramètre. Dans un premier temps, on pourra écrire une fonction dedans qui prend un élément de type 'a et une liste de type 'a list et qui retourne true si l'élément est dans la liste. Ainsi qu'une fonction additionnePropre qui additionne proprement 2 listes en évitant de dupliquer 2 fois le même élément.
4. Toujours plus gourmands, nous voudrions maintenant pouvoir posséder la liste de toutes les sous-formules composent une formule. Après avoir défini le type listeFormules, écrivez une fonction allSousFormules qui construit la liste de toutes les sous-formules composant la formule passée en paramètre.
5. On souhaite maintenant pouvoir remplacer, dans une formule, une variable par une formule. Pour cela, on va utiliser une liste d'association (string*formule) où l'index sera de type string et représentera une variable, et la valeur sera une formule. Définissez le type listeAffectation qui sert à définir des listes d'affectations.
6. Écrivez une fonction rechercheValeur qui recherche une variable dans une liste d'affectations et qui retourne la valeur associée à cette variable. Cette fonction lèvera l'exception Not_found si la variable n'est pas dans la liste d'affectations.
7. Écrivez une fonction substitue qui prend en paramètre une formule et une liste d'affectations et qui substitue toutes les variables de la formule par leur valeur associée dans la liste.
8. Écrire une fonction unifie qui prend 2 formules paramètres et qui retourne true si les 2 formules peuvent s'unifier. On rappelle que 2 formules f1 et f2 peuvent s'unifier si l'on peut trouver une liste d'affectations lAff telle que (substitue f1 lAff) = (substitue f2 lAff).
1
Si vous ne l'avez pas vu, il est toujours temps d'aller y faire un tour...
Ce document a été traduit de LATEX par HEVEA.