Plan de la séance¶
Durant cette séance, nous allons étudier la programmation paresseuse: c'est le style de programmation fonctionnelle Haskell par essence.
Nous allons voir deux concepts clés d'Haskell.
L'appel par nécessité: comment éviter des calculs inutiles en ne calculant pas la valeur d'un argument dont on n'a pas besoin
Les flots, ou listes paresseuses: comment ne calculer le contenu d'une liste qu'au moment où on en a réellement besoin.
Bien sûr, nous restons en OCaml, et nous allons devoir "bricoler" un peu, en Haskell ce serait plus direct. Mais vous apprendrez ainsi à programmer en style Haskell dans n'importe quel langage!
Les glaçons: des calcul retardés¶
Un glaçon (en anglais thunk) est une clôture représentant une fonction anonyme sans paramètre .
let glacon0 = fun () -> (1 + 1)
Idée plûtot que de lancer immédiatement l'évaluation d'une expression e, on peut la geler en construisant un glaçon fun () -> e.
Un 'a glacon est donc simplement une fonction sans argument qui calcule une valeur de type 'a.
type 'a glacon = unit -> 'a
On pourra effectuer le calcul plus tard en dégelant le glaçon.
Pour dégeler le glaçon, il me suffit de lui passer l'argument () attendu.
let degeler un_glacon = un_glacon ()
degeler glacon0
degeler glacon0
Question combien de fois a-t-on calculé 1+1?
Autre exemple: un dé à 6 faces
let glacon1 = fun () -> 1 + Random.int 6
degeler glacon1
degeler glacon1
Conclusion lorsqu'on a dégelé deux fois le glaçon, on a refait le calcul qui était gelé! Ne peut-on pas espérer mieux?
Une paresse, c'est justement cela: un glaçon dont ne refait pas le calcul après le premier dégel.
Les paresses¶
Une paresse est donc un glaçon amélioré; le calcul contenu dans une paresse a deux états possibles:
- l'état suspendu : le calcul n'a pas encore été effectué
- l'état terminé : le calcul a été effectué, on se souvient du résultat pour un éventuel nouveau dégel.
Le dégel fait passer de l'état suspendu à l'état terminé: la paresse doit donc être une valeur mutable.
Question comment définir les types 'a calcul et 'a paresse?
type 'a calcul =
| Suspendu of (unit -> 'a) (* un glaçon *)
| Termine of 'a (* une valeur *)
type 'a paresse = 'a calcul ref
Je peux donc définir un entier paresseux comme suit (j'ajoute le type pour plus de clarté).
let entier_paresseux : int paresse =
ref (Suspendu (fun () -> 1 + Random.int 6))
Comment dois-je définir la fonction degeler : 'a paresse -> 'a?
let degeler (p: 'a paresse) = match !p with
| Suspendu(glacon) -> (* CAS 1 : je n'ai encore jamais fait le calcul : *)
let res = glacon () (* 1. je fais le calcul et je mets le résultat dans res *)
in p := Termine res; (* 2. je modifie l'état de ma paresse *)
res (* 3. je renvoie le résultat *)
| Termine(res) -> (* CAS 2 : j'ai déjà fait le calcul : *)
res (* je connais le résultat, je le renvoie *)
degeler entier_paresseux
degeler entier_paresseux
Coup de chance? pas vraiment...
List.init 30 (fun i -> degeler entier_paresseux)
Comment rendre une expression paresseuse?¶
On peut définir une fonction qui transforme un glaçon en paresse
let paresse g = ref (Suspendu g)
Prenons un exemple: l'expression Unix.time() a pour valeur l'heure courante. Considérons maintenant le glaçon
let g = fun () -> Unix.time() (* <==> let g = Unix.time *)
La valeur que j'obtiens en dégelant g est l'heure qu'il est au moment du dégel. Je vais donc pouvoir vérifier si le flottant paresseux paresse g est bien dégelé une seule fois.
let flottant_paresseux = paresse g
degeler flottant_paresseux (* <- l'heure du dégel *)
(je reviens après avoir pris un café...)
degeler flottant_paresseux (* <- l'heure du dégel précédent *)
Ça marche!
Mais il reste un point un peu désagréable: pour créer une paresse pour le calcul de l'expression e, je dois écrire paresse (fun () -> e), et non paresse e.
Question N'y a-t-il pas moyen de programmer paresse autrement pour pouvoir écrire paresse e?
Malheureusement, non. En effet, lorsque OCaml doit évaluer une expression de la forme e1 e2, il procède comme suit:
- évaluer
e1et en déduire une fonctionf = fun x -> e' - évaluer
e2et en déduire une valeurv - évaluer
e'dans lequelxest remplacé parv.
Quoi que fasse la fonction paresse, elle prendra donc son argument sous la forme d'une valeur, et non d'une expression... donc trop tard pour la geler.
Cette stratégie d'évaluation est connue sous le nom d'appel par valeur, c'est la stratégie d'évaluation "classique".
L'appel par nécessité¶
Haskell est le langage qui fait exception. En Haskell, la stratégie d'évaluation est l'appel par nécessité: on n'évalue l'argument que si on en a besoin, au moment où on en a besoin, et seulement la première fois qu'on en a besoin.
Prenons un exemple: la fonction produit sur les entiers
let produit a b = a * b
Je voudrais définir une fonction produit_paresseux qui ne calcule son deuxième argument que si le premier argument est non nul.
En Haskell, j'écrirais quelque chose comme
let produit a b = (* produit qui serait paresseux en Haskell *)
if a = 0 then 0 else a * b
En OCaml, à cause de l'appel par valeur, cela ne suffit pas: le calcul de b a lieu avant le test a=0.
Par exemple, le calcul ci-dessous prend un temps déraisonnable en OCaml.
let rec fibo n = if n < 2 then 1 else fibo (n-1) + fibo (n-2)
let _ = produit 0 (fibo 42) (* <- le calcul de fibo 42 est effectué, mais inutile *)
En Haskell, on n'éffectuerait pas le calcul de fibo 42, et tout irait très vite!
Nous allons voir comment coder l'appel par nécessité dans un langage en appel par valeur comme Ocaml en utilisant une paresse.
Et tant qu'à faire, nous allons utiliser les paresses natives en OCaml.
Le module Lazy : la paresse native en OCaml¶
Ocaml dispose d'une pseudo-fonction lazy.
lazy(e) correspond, sur le principe, à paresse (fun () -> e).
C'est la "fonction" paresse telle que je rêvais de l'écrire mais qui ne peut pas exister en tant que fonction à cause de l'appel par valeur.
let flottant_paresseux2 = lazy(Unix.time())
Pour "dégeler" une paresse, il faut forcer le calcul.
Lazy.force flottant_paresseux2 (* <- calcul de Unix.time() *)
Lazy.force flottant_paresseux2 (* <- pas de second calcul de Unix.time() *)
Note Le type d'une expression paresseuse est 'a lazy_t. Il est recommandé de ne pas l'utiliser pour construire un type de données. À la place, on peut utiliser le type 'a Lazy.t.
type flottant_paresseux = float Lazy.t
Si je demande au toplevel d'afficher une paresse qui n'a pas été forcée, il m'indique une valeur "opaque" <lazy>.
let x = lazy(Float.pi ** 2.)
x
En revanche, si la paresse a été forcée et que le résultat v est connu, le toplevel m'indique lazy v.
Lazy.force x
x
Simuler l'appel par nécessité en OCaml¶
Revenons maintenant sur le problème du produit paresseux. Plutôt que de multiplier des entiers, je vais multiplier des entiers paresseux.
Idée: je ne forcerai mes entiers paresseux qu'au moment où j'ai besoin de connaitre leur valeur.
let produit a b =
if Lazy.force a = 0
then 0
else Lazy.force a * Lazy.force b
produit (lazy 0) (lazy (fibo 42)) (* <- réponse immédiate! *)
Question : Soit le programme suivant:
let carre a = produit a a (* a est un entier paresseux *)
let _ = carre (lazy (fibo 42))
Combien de fois vais-je calculer fibo 42?
Réponse : une seule fois! Détaillons le calcul de carre (lazy (fibo 42)
OCamlévalue l'argumentlazy (fibo 42). Il crée en mémoire une paressepet met le calcul suspendu defibo 42à l'intérieur.OCamlévaluecarreet le remplace parfun a b -> produit a bOCaml"passe les arguments" : l'expression à évaluer devientcarre p p- Nouveau passage d'arguments: il faut évaluer
if Lazy.force p = 0 then 0 else Lazy.force p * Lazy.force p
OCamlévalue la condition, et pour cela forcep. La paresse est modifiée et contient désormais le résultat du calcul defibo 42, 187917426909946969.OCamlévalueLazy.force p * Lazy.force p. Les deux appels àforcerenvoient immédiatement l'entier 187917426909946969.
match lazy(...)¶
OCaml permet insérer lazy dans une définition par cas
(c'est une pseudo-fonction, avec une vraie fonction ce n'est pas autorisé).
L'idée est que match x with lazy(Cons y) -> ...
est un raccourci pour
match Lazy.force x with Cons y -> ...
let produit a b = match a, b with
| lazy(0), _ -> 0
| lazy(a'), lazy(b') -> a' * b'
Les flots, ou listes paresseuses¶
Terminologie
j'emploierai dans ce cours le mot flot comme un synonyme de liste paresseuse. Il s'agit d'un abus de langage, le module
Streamd'OCamlpropose des "flots" qui ne correspondent pas exactement à mes flots, en particulier les'a streamne sont pas persistants, alors que mes flots, qui sont des listes paresseuses, le sont.
Soit à résoudre un problème ayant plusieurs solutions, peut-être une infinité.
Plutôt que de générer la liste de toutes les solutions, on génère un couple (sol, p) formé de la première solution et d'une paresse p qui n'est autre que la promesse de continuer le calcul si besoin.
On retarde ainsi le calcul des autres solutions: si la première est satisfaisante, pas besoin de les calculer.
Un flot est une "promesse": si la promesse est tenue, le flot me donne un couple (sol, flot2) constitué d'une solution et d'un nouveau flot pour les solutions restant à calculer.
J'appelerai le couple (sol, flot) un item.
type 'a item = Item of 'a * 'a flot (* définition mutuellement récursive ! *)
and 'a flot = 'a item Lazy.t
Le flot vide¶
Un flot vide est une promesse qui ne sera pas tenue (on ne calculera pas un item).
exception Flot_vide
let flot_vide : 'a flot = lazy(raise Flot_vide)
Ajouter une solution en début de flot¶
Pour ajouter une solution au début d'un flot, je dois la placer dans un item, et rendre cet item paresseux pour en faire un flot.
let scons x flot = lazy(Item(x, flot))
let flot_42 = scons 42 flot_vide (* un flot qui contient uniquement 42 *)
Construire un flot de solutions¶
Problème soit à trouver les éléments d'une liste l:'a list vérifiant un prédicat p:'a -> bool. La fonction solutions ci-dessous renvoie le flot des solutions, autrement dit la promesse d'une première solution et d'un flot d'autres solutions.
let rec solutions p l = match l with
| [] -> flot_vide
| x::tl when p x ->
lazy(Item(x, solutions p tl)) (* <- bloquage de la récursion*)
| _::tl ->
solutions p tl
let flot0 = solutions Float.is_integer [1.0; 2.17; 2.0; 0.1]
Le flot flot0 promet les deux "solutions" 1.0 et 2.0.
Premier item d'un flot¶
Comment récupérer le premier couple (sol, flot) d'un flot?
Facile:
- Je force le flot pour récupérer un item
- Je déconstruis cet item pour récupérer le couple
let get_item (flot : 'a flot) =
match Lazy.force flot with (* je force le flot et je déconstruit l'item obtenu *)
| Item(solution, flot2) -> (solution, flot2)
(* ou encore *)
let get_item = function lazy(Item(sol, flot)) -> (sol, flot)
Testons ma fonction get_item sur le flot flot0= 1.,2. calculé précédemment
let (sol1, flot1) = get_item flot0 in
let (sol2, flot2) = get_item flot1 in
(sol1, sol2)
let (sol1, flot1) = get_item flot0 in
let (sol2, flot2) = get_item flot1 in
get_item flot2 (* <- flot2 est le flot vide : il n'y a pas d'autres solutions *)
N-ième solution d'un flot¶
Je vais définir un analogue de List.nth pour les flots.
Pour cela, je dois itérer get_item pour calculer le flot restant $n$ fois, puis renvoyer la première solution de ce flot.
let rec n_ieme n flot =
if n<0
then invalid_arg "n_ieme n flot: n >= 0 attendu"
else begin
let (x,flot2) = get_item flot in
if n = 0 then x else n_ieme (n-1) flot2
end
n_ieme 0 flot0
n_ieme 1 flot0
n_ieme 2 flot0
Utiliser un flot pour résoudre un problème¶
Problème Soit à calculer le 42-ième nombre premier d'un gros intervalle, par exemple $\{1,2,3,4,5,6\dots,500\,000\}$.
Méthode naïve Je vais construire la liste des entiers de 1 à 500 000, utiliser List.filter pour ne retenir que les nombres premiers, puis utiliser List.nth pour trouver le 42-ième nombre premier.
let entiers_jusqu'a_500_000 = List.init 500_000 (fun i->i+1)
let premiers_jusqu'a_500_000 =
List.filter est_premier entiers_jusqu'a_500_000
let _42_ieme_premier = List.nth premiers_jusqu'a_500_000 42
Je fais évidemment beaucoup de calculs inutiles!
Seconde approche Je vais utiliser des flots à la place des listes!
Commençons par définir le flot des entiers de a à b.
let rec entiers_entre a b =
if a <= b
then lazy(Item(a, entiers_entre (a+1) b)) (* <- blocage de la récursion *)
else flot_vide
Je vais maintenant construire le flot des nombres premiers compris entre a et b.
Pour cela, je vais filtrer le flot précédent à l'aide d'une fonction
filtre_flot : ('a -> bool) -> 'a flot -> 'a flot
qui fait l'analogue de List.filter mais avec les flots.
let rec filtre_flot condition flot =
lazy begin (* <- blocage de la récursion *)
let (x,flot2) = get_item flot in
if condition x
then Item(x, filtre_flot condition flot2)
else Lazy.force (filtre_flot condition flot2)
end
let premiers_jusqu'a_500_000 =
filtre_flot est_premier (entiers_entre 1 500_000)
Le résultat est immédiat!
Il ne me reste plus qu'à parcourir le flot jusqu'au 42-ième élément.
Pendant le parcours, je vais (enfin) calculer les 42 premiers nombres premiers.
let _42_ieme_nombre_premier = n_ieme 42 premiers_jusqu'a_500_000
Si je demande le 41-ième nombre premier avec n_ieme 41 premiers_jusqu'a_500_000, le résultat sera immédiat: il a déjà été calculé.
Flots infini¶
Un flot n'a aucune raison d'être fini!
Le flot des entiers plus grands que n se définit par récurrence... mais il s'agit d'une récurrence un peu spéciale, sans cas de base.
let rec entiers_depuis n =
lazy(Item(n, entiers_depuis (n+1))) (* <- récurrence bloquée! *)
C'est parce que la récurrence est bloquée que l'on peut appeler sans risque la fonction entiers_depuis.
let entiers = entiers_depuis 0 (* <- termine immédiatement! *)
On peut désormais suivre une troisième approche, plus épurée, pour calculer le 42 ième nombre premier.
let nombres_premiers = filtre_flot est_premier entiers
n_ieme 42 nombres_premiers
Des flots au listes¶
Pour transformer un flot en une liste, il va me falloir fixer une borne k sur la taille de la liste que j'obtiendrai: si le flot est plus long que k, je tronquerai.
let rec list_of_flot k flot =
try begin
match (k, get_item flot) with
| (0, _) -> []
| (k, (a,flot2)) -> a :: list_of_flot (k-1) flot2
end with
| Flot_vide -> []
list_of_flot 10 entiers
list_of_flot 100 (entiers_entre 1 10)
Somme terme à terme de deux flots¶
Soient $\mathbf{a}=(a_0, a_1, \dots)$ et $\mathbf b=(b_0,b_1,\dots)$ deux flots d'entiers de longueurs quelconques.
Problème construire le flot $\mathbf a + \mathbf b = (a_0+b_0,a_1+b_1,\dots)$.
let rec somme_flots flot_a flot_b =
lazy(begin
match get_item flot_a, get_item flot_b with
| (a0, flot_a'), (b0, flot_b') ->
Item( a0 + b0, somme_flots flot_a' flot_b' )
end)
let _2N = somme_flots entiers entiers
let _ = list_of_flot 10 _2N
Les flots définis par une équation de point fixe¶
Considérons le flot constant à 1
let rec un = lazy(Item(1, un))
list_of_flot 10 un
Considérons maintenant le flot suivant
let (++) = somme_flots
let rec flot_e = lazy(Item(0, un ++ flot_e ))
Question : quelle suite d'entiers correspond à flot_e?
Réponse flot_e = entiers!
list_of_flot 10 flot_e
On a donné une définition "implicite" du flot d'entiers. Cette définition est associée à l'équation de point fixe
x = 0 :: (un + x)
Cette équation n'admet qu'une seule solution: x=entiers.
En exploitant de telles équations, vous pourrez calculer le développement en séries entières de l'exponentielle, des fonctions trigonométriques, etc... cf TP?
$$ e^x = \sum_{n\geq 0} \frac{x^n}{n!} $$list_of_flot 5 exponentielle $\to$ [ $1$, $1$, $\frac{1}{2}$, $\frac{1}{6}$, $\frac{1}{24}$ ]
Résumons¶
- un glaçon ( thunk )
fun () -> eest un calcul suspendu de l'expressione - une paresse est un glaçon amélioré: on peut demander le résultats du calcul plusieurs fois sans le recalculer à chaque fois
- un flot est une "liste paresseuse" qui peut être infinie
L'évaluation paresseuse est celle par défaut en Haskell:
- les appels de fonctions se font par nécessité
- les listes sont paresseuses