Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Sujet de devoir surveillé de 2021
Lambda-calcul
A1 (1.5 points)
Décomposez le terme suivant en abstractions (encadrez-les en pointillés) et applications (encadrez-les en trait plein).
\[a \; b \; \lambda x . \; \lambda y . \; x \; a \; y \; \lambda a . \; a \; b
\]

A2 (1.5 points)
Dans le terme suivant, entourez les occurrences libres de variables et reliez par des traits les occurrences liées entre elles.
\[a \; b \; \lambda x . \; \lambda y . \; x \; a \; y \; \lambda a . \; a \; b
\]

A2 (2 points)
Pour chacune des paires de termes suivantes, indiquez si les termes sont équivalents. Répondez par oui ou non.
- \(a\lambda b. ab\) et \(a\lambda c. ac\)
- \(a\lambda b. ab\) et \(b\lambda b. bc\)
- \(\lambda x.\lambda f. f (fx)\) et \(\lambda x.\lambda f. f f x\)
- \(\lambda x.\lambda f. f (fx)\) et \(\lambda f.\lambda x. x (x f)\)
- \(a \lambda x.x\) et \(a \lambda y. y\)
- \(\lambda x .xy \lambda x . x\) et \(\lambda x .yx \lambda y . y\)
- oui
- non
- non
- oui
- oui
- non
A2 (5 points)
Évaluez chacun des termes suivants. Encadrez le redex utilisé à chaque étape.
\[(\lambda w. ww) a a
\]
- \((aa)a\) équivalent à \(aaa\)
\[(\lambda w.waw)\lambda x.x
\]
- \((\lambda x .x) a (\lambda x . x)\)
- \(a(\lambda x . x)\) équivalent à \(a \lambda x.x\)
\[u(\lambda w.waw)(\lambda x.x)bb
\]
Il n’y a aucun redex car le terme se décompose en :
\[[\;[\;[\;[u(\lambda w.waw)](\lambda x.x)\;]b\;]b\;]
\]
\[(\lambda w . \lambda y. aw)\lambda x.yb
\]
- Un renommage est nécessaire : \((\lambda w . \lambda t. aw)\lambda x.yb\)
- \(\lambda t. a(\lambda x.yb)\)
\[(\lambda g.\lambda y.gy)(\lambda f.\lambda x.fx)
\]
- \(\lambda y.(\lambda f.\lambda x.fx)y\)
- \(\lambda y.\lambda x.yx\)
CAML
B1 (1.5 points)
Soit les fonctions suivantes :
let rec fn f n x =
if(n <= 0) then x
else fn f (n-1) (f x);;
let h x = 2*x;;
Donnez les valeurs retournées par :
fn h 0 1;;
fn h 1 1;;
fn h 2 1;;
1
2
4
B2 (3 points)
Réalisez une fonction revconc telle que si a et b sont des listes (contenant des éléments de même type), alors revconc a b retourne la liste obtenue en concaténant le miroir de a avec b. Voici un exemple d’utilisation.
revconc [1;2;3] [10;20;30];;
int list = [3;2;1;10;20;30]
Le principe est le suivant :

let rec revconc a b =
match a with
|[] -> b
|t::q -> revconc q (t::b)
;;
B3 (1.5 points)
On définit le type arbre qui représente des arbres binaires dont les nœuds sont étiquetés par des entiers.
type arbre = Vide | Noeud of int * arbre * arbre ;;
On dit qu’un tel arbre t est trié si et seulement si t est une feuille (représenté par Vide) ou t est un nœud d’étiquette x, de fils gauche g et de fils droit d respectant les conditions suivantes :
-
les valeurs des étiquettes de
gsont toutes strictement inférieures àx, -
les valeurs des étiquettes de
dsont toute supérieures ou égale àx, -
detgsont triés.

La fonction insert permet d’insérer une valeur dans un arbre trié. Si t est un arbre trié et x un entier, alors insert x t produit un arbre trié contenant x et les valeurs de t.
let rec insert x t = match t with
|Vide->Noeud(x,Vide,Vide);
|Noeud(y,g,d)->if x<y
then Noeud(y, insert x g, d)
else Noeud(y, g, insert x d)
;;
Donnez la ligne de code permettant de produire l’arbre représenté par la figure précédente par insertion des valeurs des étiquettes dans l’ordre approprié à l’aide de la fonction insert.
let t = insert 7 (insert 3 (insert 2 (insert 5 Vide)));;
B4 (2 points)
Réalisez une fonction liste2arbre telle que si w est une liste d’entiers, alors liste2arbre w produit un arbre trié contenant tous les éléments de w. L’arbre est produit par insertions successives, à l’aide de la fonction insert, des éléments de w dans un arbre initialement vide.
let rec liste2arbre w =
match w with
|[] -> Vide
|x::q -> insert x (liste2arbre q)
;;
B5 (2 points)
Réalisez une fonction arbre2liste telle que si t est un arbre trié alors arbre2liste t retourne la liste triée des valeurs situées dans t.
Par exemple, arbre2liste (liste2arbre [5; 1; 7; 4; 2; 6]) produit le résultat [1;2;4;5;6;7].
Vous pouvez utiliser l’opérateur @ de concaténation des listes. Par exemple [1;2]@[3;4] a pour résultat [1;2;3;4].
let rec arbre2liste t =
match t with
|Vide -> []
|Noeud(x,g,d) ->
(arbre2liste g) @ x::(arbre2liste d)
;;