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


Partiel - 3 décembre 1999
correction




Exercice 1

Un permis de conduire français contient, entre autres informations, l'identité de son possesseur et la liste des catégories de permis de cette personne.

Les catégories de permis considérés ici sont A (permis moto) et B (voiture).

Une personne est identifiée par son nom et sa ville donnée par son code postal.
1. Définir les types catégorie_permis, identité et permis. 
#type catégorie_permis = A | B ;;
Le type catégorie_permis est défini.
#type identité = { nom: string; ville: int };;
Le type identité est défini.
#type permis = { personne: identité; catégories: catégorie_permis list };;
Le type permis est défini.
Par la suite, nous considérerons qu'une personne qui n'a pas de permis de conduire dispose d'un élément de type permis, mais que la liste des catégories de permis qu'il possède est vide.
2. Écrire la fonction permis_voiture qui détermine si la personne détentrice d'un permis p peut conduire une voiture.

Écrire la fonction nouveau_permis qui met à jour le permis p d'une personne qui vient d'être reçue à l'examen du permis de conduire pour la catégorie c. 
#let permis_voiture p = mem B p.catégories;;
permis_voiture : permis -> bool = <fun>
#let nouveau_permis p c = 
   { personne = p.personne; catégories = c::p.catégories };;
nouveau_permis : permis -> catégorie_permis -> permis = <fun>

3. Sachant que le département se déduit du code postal en divisant ce dernier par 1000, écrire la fonction département_of_ville qui indique le département associé à la ville v. 
#let département_of_ville v = v / 1000;;
département_of_ville : int -> int = <fun>

4. À la suite d'un contrôle routier, un policier a relevé une liste de permis de contrevenants, il souhaite classer ces permis selon l'ordre alphabétique des noms de ces personnes. Écrire la fonction tri_alph_nom qui trie une liste de permis selon l'ordre alphabétique des noms de leurs détenteurs. Vous pourrez pour cela utiliser la fonction tri_insertion vue en cours ou bien la fonction sort du module sort qui fait partie de la bibliothèque standard de Caml. 
#let ordre_alph_nom p1 p2 = p1.personne.nom < p2.personne.nom;;
ordre_alph_nom : permis -> permis -> bool = <fun>
#
 let tri_alph_nom pl = sort__sort ordre_alph_nom pl;;
tri_alph_nom : permis list -> permis list = <fun>

5. Devant la variété d'origine de ces détenteurs de permis, ce policier décide de les classer d'abord par ordre de département et pour chaque département en ordonnant les noms des contrevenants. Écrire la fonction tri_plus_complexe associée. 
#let ordre_plus_complexe p1 p2 = 
   let d1 = département_of_ville p1.personne.ville 
   and d2 = département_of_ville p2.personne.ville in
     d1 < d2 || d1 = d2 && p1.personne.nom < p2.personne.nom;;
ordre_plus_complexe : permis -> permis -> bool = <fun>
#
 let tri_plus_complexe pl = sort__sort ordre_plus_complexe pl;;
tri_plus_complexe : permis list -> permis list = <fun>

6. Écrire une fonction détenteurs_permis_voiture qui extrait d'une liste de permis ceux qui permettent de conduire une voiture. On écrira cette fonction de deux façons différentes, tout d'abord directement récursivement, puis en utilisant l'itérateur filter vu en cours. 
#let rec détenteurs_permis_voiture pl = match pl with
   | [] -> []
   | p::pl' -> if permis_voiture p 
               then p::(détenteurs_permis_voiture pl')
               else détenteurs_permis_voiture pl';;
détenteurs_permis_voiture : permis list -> permis list = <fun>
#(* ou *)
 (* Rappel: *)
 let rec filter p l = match l with
 | [] -> []
 | e::l' -> if p e then e::(filter p l') else filter p l';; 
filter : ('a -> bool) -> 'a list -> 'a list = <fun>
#(* *)
 let détenteurs_permis_voiture pl = filter permis_voiture pl;;
détenteurs_permis_voiture : permis list -> permis list = <fun>
Exercice 2

La session débute dans l'environnement de typage global E0. Les environnements seront ensuite nommés E1, E2,...
1. 
#let x = 1;;
x : int = 1
E0 |- 1:int

E1 = ë (x,int) <| E0 û.


2. 
#let f1 = function y -> y + x;;
f1 : int -> int = <fun>
E1' |- y:ty E1' |- x:int
ë (y,ty) <| E1 û |- y+x:int
ty = int
E1 |- fun y ® y+x : int ® int

E2 = ë (f1,int ® int) <| E1 û.


3. 
#let f2 =
   function x -> function y ->
     if x > y then x+y else f1(x-y);;
f2 : int -> int -> int = <fun>
E2' |- x:tx E2' |- y:ty
E2' |- x>y:bool
tx = ty
E2' |- x:tx E2' |- y:tx
E2' |- x+y : int
tx = int
(**)
E2' = ë (y,ty), (x,tx)<| E2 û |- if x>y then x+y else f1(x-y):int
E2 |- fun x y ® if x>y then x+y else f1(x-y): int ® int ® int
avec (**):
E2' |- f1:int ® int E2' |- x-y:int
E2' |- f1(x-y):int

E3 = ë (f2,int ® int ® int) <| E2 û.


4. 
#let deriv f dx x = (f(x +. dx) -. f(x)) /. dx;;
deriv : (float -> float) -> float -> float -> float = <fun>
(**) (***)
E3' |- (f(x +. dx) -. f(x)):float
t4 = float
E3' |- dx:float
E3' = ë (x,t1), (dx,t2)<| ë (f,t3) <| E3 û û |- (f(x +. dx) -. f(x)) /. dx:float
E3 |- fun f dx x ® (f(x +. dx) -. f(x)) /. dx: (float ® float) ® float ® float ® float
avec (**):

E3' |- f:t3
E3' |- x:t1 E3' |- dx:t2
E3' |- x +. dx:float
t1 = t2 = float
E3' |- f(x +. dx):t4
t3 = float ® t4
avec (***):

E3' |- f:float ® t4 E3' |- x:float
E3' |- f(x):t4

E4 = ë ((float ® float) ® float ® float ® float) <| E3 û.


5. 
#let partielle = deriv (function x -> x *. x) 0.001;;
partielle : float -> float = <fun>
(**) E4 |- 0.001 : float
E4 |- deriv (fun x ® x *. x) 0.001 : float ® float
avec (**):
E4 |- deriv: (float ® float) ® float ® float ® float E4 |- (fun x ® x *. x) : float ® float
E4 |- deriv (fun x ® x *. x): float ® float ® float

E5 = ë (partielle,float ® float) <| E4 û.
6. Donnez, sans détailler, le type de cette fonction et de son application: 
#let rec iter f n =
   if n = 0 then 1 else f (iter f (n-1));;
iter : (int -> int) -> int -> int = <fun>
#iter f1 1000;;
- : int = 1001
Exercice 3

Typez complètement chacune de ces déclarations en montrant également l'évolution de l'environnement. On supposera que fst : 'a * 'b -> 'a et snd : 'a * 'b -> 'b.


1. 
#let copie x = (x,x);;
copie : 'a -> 'a * 'a = <fun>
Eo' |- x: tx Eo' |- x: tx
E0' = ë (x,tx) <| E0 û |- (x,x): tx * tx
E0 |- fun x ® (x,x):tx ® tx * tx
Le type est généralisé.

E1 = ë (copie, " tx.tx ® tx * tx) <| E0 û
2. 
#let f (g,x) = g(snd x),g(fst x);;
f : ('a -> 'b) * ('a * 'a) -> 'b * 'b = <fun>
(**) (***)
E1' = ë (g,tg), (x,tx)<| E1 û |- g(snd x),g(fst x) : t * t
E1 |- fun (g,x) ® g(snd x),g(fst x): (t1 ® t) * (t1 * t1) ® (t * t)
avec (**):
E1' |- g:tg
E1' |- snd: t1 * t2 ® t2 E1' |- x: tx
E1' |- sndx: t2
tx = t1 * t2
E1' |- g(snd x) : t
tg = t2 ® t
avec (***):
E1' |- g:t2 ® t
E1' |- fst: t3 * t4 ® t3 E1' |- x: t1 * t2
E1' |- fstx: t1
t1 = t3 , t2 = t4
E1' |- g(fst x) : t
t1 = t2
On généralise le type.

E2 = ë (f," t1,t.(t1 ® t) * (t1 * t1) ® (t * t)) <| E1 û.
3. 
#let h x = f (copie,x);;
h : 'a * 'a -> ('a * 'a) * ('a * 'a) = <fun>
E2' |- f: (t ® t1) * (t * t) ® (t1 * t1) (**)
E2' = ë (x,tx) <| E2 û |- f (copie,x): (t *t) * (t *t)
t = t2, t1 = t2*t2,tx = t *t
E2 |- fun x ® f (copie,x): (t * t) ® (t *t) * (t *t)
avec (**):
E2' |- copie: t2 ® (t2 * t2) E2' |- x: tx
E2' |- (copie,x):(t2 ® (t2 * t2)) * tx
On généralise le type.

E3 = ë (h," t.(t * t) ® (t * t) * (t * t)) <| E2 û.
4. 
#let m x = h (x+1,x-1);;
m : int -> (int * int) * (int * int) = <fun>
E3' |- f: (t * t) ® (t *t) * (t *t) E3 |- (x+1,x-1):int * int
E3' = ë (x,tx) <| E3 û |- h(x+1,x-1): (int * int) * (int * int)
t = int
E3 |- fun x ® h(x+1,x-1): int ® (int * int) * (int * int)

E4 = ë (m,int ® (int * int) * (int * int)) <| E3 û.
5. Expliquez la différence (du point de vue du typage) entre les deux expressions suivantes: 
#let id = function x -> x;;
id : 'a -> 'a = <fun>
#if id true then id 1 else id 2;;
- : int = 1
et: 
#let id = function x -> x;;
id : 'a -> 'a = <fun>
#(function f -> if f true then f 1 else f 2) id;;
Entrée interactive:
>(function f -> if f true then f 1 else f 2) id;;
>                                ^
Cette expression est de type int,
mais est utilisée avec le type bool.
Ces deux programmes calculent bien la même chose mais le premier est bien typé alors que le second ne l'est pas.

Voyons le typage du premier programme. id a le type polymorphe " t.t ® t. Ensuite:

E |- id:t1 ® t1
E |- idtrue:bool
t1 = bool
E |- id:t2 ® t2
E |- id1:int
t2 = int
(**)
E = ë (id," t.t ® t) <| E0 û |- if id true then id 1 else id 2:int
avec (**):
E |- id:t3 ® t3
E |- id2:int
t3 = int
La fonction polymorphe id a trois instances de type.

Par contre, la deuxième version est mal typée. En effet:

E1 |- f:tf E1 |- true:bool
E1|- ftrue:bool
tf = bool ® tf'
E1 |- f:bool ® tf' E1 |- 1:int
E1 |- f1:?
E1 = ë (f,tf) <| E û |- if f true then f 1 else f 2:?
E |- (fun f ® if f true then f 1 else f 2): ?
E |- (fun f ® if f true then f 1 else f 2) id:?
Ce programme est mal typé parce que le type de f doit être à la fois égal à bool ® bool et int ® int.

Remarque: Un tel programme pourrait être bien typé à condition de pouvoir affirmer que la fonction:
fun f ® if f true then f 1 else f 2
a le type:
(" t.t ® t) ® int
c'est-à-dire indiquant que le type de f doit être un schéma de type. Un tel type n'est pas définissable en Caml.

Ce document a été traduit de LATEX par HEVEA.