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
\]

"Réponse"

image-2022020421295974

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
\]

"Réponse"

image-20220204213632076

A2 (2 points)

Pour chacune des paires de termes suivantes, indiquez si les termes sont équivalents. Répondez par oui ou non.

  1. \(a\lambda b. ab\) et \(a\lambda c. ac\)
  2. \(a\lambda b. ab\) et \(b\lambda b. bc\)
  3. \(\lambda x.\lambda f. f (fx)\) et \(\lambda x.\lambda f. f f x\)
  4. \(\lambda x.\lambda f. f (fx)\) et \(\lambda f.\lambda x. x (x f)\)
  5. \(a \lambda x.x\) et \(a \lambda y. y\)
  6. \(\lambda x .xy \lambda x . x\) et \(\lambda x .yx \lambda y . y\)
"Réponse"

  1. oui
  2. non
  3. non
  4. oui
  5. oui
  6. non

A2 (5 points)

Évaluez chacun des termes suivants. Encadrez le redex utilisé à chaque étape.

\[(\lambda w. ww) a a
\]

"Réponse"

  1. \((aa)a\) équivalent à \(aaa\)

\[(\lambda w.waw)\lambda x.x
\]

"Réponse"

  1. \((\lambda x .x) a (\lambda x . x)\)
  2. \(a(\lambda x . x)\) équivalent à \(a \lambda x.x\)

\[u(\lambda w.waw)(\lambda x.x)bb
\]

"Réponse"

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
\]

"Réponse"

  1. Un renommage est nécessaire : \((\lambda w . \lambda t. aw)\lambda x.yb\)
  2. \(\lambda t. a(\lambda x.yb)\)

\[(\lambda g.\lambda y.gy)(\lambda f.\lambda x.fx)
\]

"Réponse"

  1. \(\lambda y.(\lambda f.\lambda x.fx)y\)
  2. \(\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;;
"Réponse"

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 :

3

"Réponse"

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 g sont toutes strictement inférieures à x,

  • les valeurs des étiquettes de d sont toute supérieures ou égale à x,

  • d et g sont triés.

4

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.

"Réponse"

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.

"Réponse"

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].

"Réponse"

let rec arbre2liste t =
  match t with
  |Vide -> []
  |Noeud(x,g,d) -> 
      (arbre2liste g) @ x::(arbre2liste d)
;;