Vincent Balat

Programmation fonctionnelle avancée

Documents

Une version préliminaire des notes de cours

TP

TP1 Représentation des ensembles
TP2 Mini-interprète d'un mini langage fonctionnel
TP3 Structures de données
TP4 Threads préemptifs et threads coopératifs
Mini-projet 1 LWP. Script nombre d'occurence : Google et Bing.
TP5 Types abstraits, variants polymorphes et types fantômes
TP6 Monades
TP7 Une brève introduction à Haskell
- http://www.zvon.org/other/haskell/Outputglobal/index.html
- http://www.haskell.org/onlinereport/index98.html
Mini-projet 2 Tri-Mon. Code fourni : tris.ml, po.mli et po.ml (ou tris.hs et po.hs).

Correction partielle de l'exercice sur le lambda-calcul

En appel par valeur de gauche à droite

(fun x y z -> match x y with Left u -> x y | Right v -> z) 
  ((fun y x -> x) (fun x -> (fun y -> x) 1))
  (Left 4)
  ((fun t -> t) (Left 4))

↓ Réduction de gauche à droite. On réduit la fonction : rien à faire, elle est déjà en forme normale faible (i.e. on ne réduit pas sous les fun). Alors on réduit le 1er argument. C'est lui-même une application. On réduit la fonction fun y x -> x : rien à faire c'est un fun. On réduit l'argument : rien à faire non plus. Alors on applique la règle de ß-réduction à ce rédex.

(fun x y z -> match x y with Left u -> x y | Right v -> z) 
  (fun x -> x)
  (Left 4)
  ((fun t -> t) (Left 4))

	(`fun y x -> x` est en fait `fun y -> (fun x -> x)`. Donc la règle de ß-réduction nous dit qu'il faut remplacer tous les `y` libres de `fun x -> x` par l'argument. Il n'y en a aucun, donc ça donne `fun x -> x`.)
↓	Le premier argument de la grosse fonction est un `fun` donc plus rien à faire. Le 2e est déjà réduit aussi. Il faut réduire le 3e.

(fun x y z -> match x y with Left u -> x y | Right v -> z) 
  (fun x -> x)
  (Left 4)
  (Left 4)

↓ La fonction est ses trois arguments sont en forme normale faible. On peut maintenant appliquer la fonction. On commence par passer le premier argument. Cela donne fun y z -> match ... dans lequel x est remplacé par fun x -> x (ou fun t -> t si l'on veut éviter d'utiliser le même nom de variable).

(fun y z -> match (fun x -> x) y with Left u -> (fun x -> x) y | Right v -> z) 
  (Left 4)
  (Left 4)

↓	Passage du 3e argument

match (fun x -> x) (Left 4) with Left u -> (fun x -> x) (Left 4) | Right v -> (Left 4)

↓	encore une ß-réduction

match (Left 4) with Left u -> (fun x -> x) (Left 4) | Right v -> (Left 4)

↓	cette-fois-ci c'est la règle du `match`. On est dans le cas `Left` donc on remplace tous les `u` de `(fun x -> x) (Left 4)` par `4` (Il n'y en a pas).

(fun x -> x) (Left 4)

↓

(Left 4)

Vous pouvez vérifier le résultat avec caml qui, lui, réduit aussi en appel par valeur (et de droite à gauche dans l'implémentation de l'INRIA).

En appel par nom

(fun x y z -> match x y with Left u -> x y | Right v -> z) 
  ((fun y x -> x) (fun x -> (fun y -> x) 1))
  (Left 4)
  ((fun t -> t) (Left 4))

↓	En appel par nom, on ne cherche pas à réduire les arguments avant de faire le passage de paramètre.

(fun y z -> match ((fun y' x -> x) (fun x -> (fun y' -> x) 1)) y with Left u -> ((fun y' x -> x) (fun x -> (fun y' -> x) 1)) y | Right v -> z) 
  (Left 4)
  ((fun t -> t) (Left 4))

	Remarquez la duplication de code.
	Remarquez aussi que j'ai renommé le `y` en `y'` pour éviter de le confondre avec l'autre (problème de capture). J'aurais même pu écrire `(fun y'' -> x) 1`.
↓	2e paramètre
	Je remplace les `y` libres, pas les `y'` (s'il y en avait).

(fun z -> match ((fun y' x -> x) (fun x -> (fun y' -> x) 1)) (Left 4) with Left u -> ((fun y' x -> x) (fun x -> (fun y' -> x) 1)) (Left 4) | Right v -> z) 
  ((fun t -> t) (Left 4))

↓	3e paramètre

match ((fun y' x -> x) (fun x -> (fun y' -> x) 1)) (Left 4) with Left u -> ((fun y' x -> x) (fun x -> (fun y' -> x) 1)) (Left 4) | Right v -> ((fun t -> t) (Left 4))

↓

etc.

match (fun x -> x) (Left 4) with Left u -> ((fun y' x -> x) (fun x -> (fun y' -> x) 1)) (Left 4) | Right v -> ((fun t -> t) (Left 4))

↓

match Left 4 with Left u -> ((fun y' x -> x) (fun x -> (fun y' -> x) 1)) (Left 4) | Right v -> ((fun t -> t) (Left 4))

↓

((fun y' x -> x) (fun x -> (fun y' -> x) 1)) (Left 4)

↓	Remarquez que j'ai déjà fait ce calcul...

(fun x -> x) (Left 4)

↓	Remarquez que j'ai déjà fait ce calcul...

Left 4

En appel par nécessité

Je ne le fais pas (et je ne vous le demanderai pas). Il faudrait remplacer le terme par un graphe. On ne fait plus de substitution mais on fait pointer toutes les variables vers leur contenu. C'est comme l'appel par nom mais

les calculs qui sont faits deux fois en appel par nom ne sont faits qu'une fois (comme en appel par valeur)
comme en appel par nom et contrairement à l'appel par valeur, on ne réduit jamais le sous-terme ((fun t -> t) (Left 4)) (qui ne sert pas).

Dans tous les cas, attention aux problèmes de capture de variable ! Il est conseillé de renommer les variables de chaque fonction pour ne jamais utiliser deux fois le même nom pour éviter de se mélanger les pinceaux entre variables de même nom ! Une bonne idée aurait été de le faire dès le départ !