Programmation Fonctionnelle, TD1

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD1 : Variables et Fonctions.

Guyslain Naves

Exercice 1 : portée des variables

Dans la suite d'expressions suivantes, indiquer pour chaque occurence de variable si elle est libre ou liée, dans le second cas, indiquer à quelle définition elle est liée. Il est conseillé de mettre chaque expression sous forme d'arbre syntaxique.

  1. let a a = a * let a = 3 in a in a (let a = 4 in a);;

  3. let a = let a = let a = 1 in a+1 in let a = 2 in a*2 in a+3;;

  5. let a =
  6. let b = 2 in
  7. let c = 3 in
  8. a + b + (let d = 5 in b * c * d);;

  10. let a =
  11. let f = fun a -> a + 1 in
  12. let g = fun a -> a * 2 in
  13. let a = 2 * a in
  14. f (g ((fun a -> a+3) 5));;

Exercice 2 : renommage de variables

Dans les expressions suivantes, renommer la variable $x$ indiquée par un commentaire en $y$, sans changer la sémantique de l'expression.

  1. let x =
  2. let x (* celui-ci *) = 42 in
  3. let f x = x+3 in
  4. x + ((fun x -> 2 * x) (3 * x))

  6. let x =
  7. let x = 21 in
  8. let x (* celui-ci *) = 32 in
  9. let g x = (fun x -> x+3) x in
  10. g (x+x)

  12. let x (* celui-ci *) =
  13. (fun x -> x + (fun x -> x + 2) (x+3)) ((fun x -> x*2) (let x = 12 in x + 5 * x))

Exercice 3 : Évaluation d'applications par $\beta$-réduction

Évaluer chacune des expressions suivantes, d'abord avec une stratégie d'évaluation stricte, puis une stratégie d'évaluation paresseuse.


  2. (fun x -> x + x) ((fun y -> y + y) 2);;

  4. (fun f g x -> let y = g x in f y) (fun x -> x+2) (fun x -> x * 3) ((fun x -> x-1) 5);;

  6. (fun x -> x * x + 2 * x + 1) ((fun x -> x * 3) ((fun x -> x * 5) 2));;