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

Examen du 7 septembre 2000

Le barême n'est donné qu'à titre indicatif. Les documents autorisés sont les notes de cours et de TD ainsi que les documents distribués en cours.

Exercice 1 (3 pts)

Soit la déclaration suivante, effectuée dans un environnement Env :

let f = function m -> function n ->
  let res = g (m * n) in 
    (((h res) = res), res);;

On cherche quelles sont les hypothèses minimales à faire sur Env pour que cette déclaration soit acceptable par le système CAML, en donnant à f le type le plus général (autrement dit, le plus polymorphe) possible. Donner votre réponse en la justifiant. Pour cela, vous construirez l'arbre de typage.

Exercice 2 (3 pts)

Soit la fonction :

let f = function (x,z,y)  ->
  let r = ref (!z) in 
    r := !r + 1;
    y := !y + 1 ; 
    if x then z := !r else failwith " erreur";;

Donnez le type de f et justifiez le. Soient les phrases suivantes:

let k = ref 1;;
let l = ref 2;;
f (true, k, l);;

Donnez la valeur de k et l.

Exercice 3 (3pts)

Soit les définitions suivantes.

let rec comp f n x = if n=0 then x else (f (comp f (pred n) x));;         

comp (function x -> x + 1) 3 ;;

let foo = comp (function x -> x + 1) 3 ;;

foo(3);;

Donnez, sans explication, le type de comp et de foo.

Détaillez la valeur des identificateurs f et x lors de l'évaluation de l'expression if n=0 then x else (f (comp f (pred n) x)) produite au premier appel récursif de l'évaluation de (comp succ 3 5).

11 pts

On définit le type lterm des -termes par :

type lterm = I of int | V of string | Fonc of string * lterm | App of lterm * lterm;;

Une constante est un -terme construit avec I. Une variable est un -terme construit avec V et le nom de la variable (V s) est s. Une fonction est un -terme de la forme Fonc (s, lt), s est le nom de la variable. Une l-appli est un -terme construit avec App.
1. (1 pt) Donner un exemple de -terme de chacune des catégories.
2. (1 pt) Écrire une fonction qui compte le nombre de variables (libres) dans un -terme.
3. (1,5 pt) La hauteur d'une constante et d'une variable est 1. La hauteur d'une fonction Fonc (s,lt) est celle du -terme lt ayant servi à la construire augmentée de 1. La hauteur d'une l-appli est la plus grande des hauteurs des deux -termes ayant servi à la construire, augmentée de 1. Écrire une fonction hauteur qui donne la hauteur d'un -terme. On rappelle que la fonction max fournit le plus grand de deux nombres.
4. (1,5 pt) Écrire une fonction sous_une_fun, qui prend une chaîne de caractères ch et un -terme lt en entrée et qui vaut true si ch est un nom abstrait dans lt.
5. (2 pts) Les -termes sont des sortes d'arbres. Un chemin dans un -terme est un mot sur l'alphabet {F, L, G, D}. On associe à tout -terme une liste de chemins construite par la fonction liste_chemins donnée ci-dessous :

let rec liste_chemins = function 
  | I _ -> ["F"]
  | V _ -> ["F"]
  | Fonc (_, lt) -> map (function ch -> "L" ^ ch) (liste_chemins lt)
  | App (lt_1, lt_2) -> 
     let sous_liste_droite = map (function ch -> "D"^ch) (liste_chemins lt_2)
     and sous_liste_gauche = map (function ch -> "G"^ch) (liste_chemins lt_1) in
       sous_liste_gauche @ sous_liste_droite;;

let un_l_terme = 
  let delta = Fonc ("x", App (V "x", V"x")) in
    App (delta,delta);;

let resultat = liste_chemins un_l_terme;;

Donner la valeur de resultat.

Démontrer que la hauteur d'un -terme un_lt est égale à la plus grande des longueurs des chaînes de caractères figurant dans liste_chemins un_lt.
6. (2 pts) On veut mettre en place un mécanisme de simplification des -termes. Pour cela, Un -terme de la forme App ((Fonc (s, t1)), t2) est remplacé par un nouveau -terme, construit à partir de t1, comme suit. On remplace dans t1 chaque variable (V s), ayant donc pour nom celui qui est abstrait, par le -terme t2. Par exemple, (App ((Fonc ("x", V "x")), I n)) se simplifie sur (I n) et (App ((Fonc ("x", V "y")), I n)) se simplifie sur (V "y").

Écrire d'abord une fonction remplace, qui prend en arguments une chaîne de caractères s (le nom de la variable à remplacer), un premier -terme t1 (le -terme où faire le remplacement) un second -terme t2 (le -terme qui remplace) et effectue le remplacement.
7. (2 pts) On veut écrire une fonction simplifie qui effectue, si possible, la simplification d'un -terme quelconque, en remplaçant un sous-terme de la forme App ((Fonc (s, t1)), t2) (s'il en existe) par sa version simplifiée. Donner votre solution en justifiant les choix que vous serez amenés à faire pendant la conception de cette fonction.

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