Il y a longtemps, avant même que je sache se qu'est un blog, Seb, le même que déjà cité, m'avait fait part d'un petit défit auquel il avait été confronté lors de l'écriture d'un compilateur.
Comment créer un arbre dont les noeuds connaissent leur parent sans utiliser de dangereux effets de bord ? Un autre pote autour de la table (oui c'était dans un restau, on décroche jamais) m'a suggéré que la solution tournait sûrement autours de la fainéantise (Lazyness).
Précisément qu'est-ce que la fainéantise ? C'est le fait de ne pas effectuer une opération avant que son résultat ne soit nécessaire.
exemple :
let f arg1 arg2 = arg1 + 3
let r = f <expression1> <expression2>
Un langage courageux (
eager) comme C ou Objective Caml va évaluer expression1 et expression2 (dans un ordre indéterminé) puis lancer l'appel de f sur ces 2 arguments. Et découvrir que le calcul d'
expression2 était inutile (dans le cas d'un exemple aussi simple, le compilateur peut optimiser s'il a la preuve que
expression2 ne contient pas d'effet de bord).
Un langage fainéant (
lazy) va directement passer à la fonction les expressions non évaluées, elle se débrouillera pour évaluer ce qu'elle veut si elle a besoin d'un résultat. Ainsi,
expression2 ne sera pas évaluée dans cet exemple.
Bien, c'est super, mais c'est pas super utile jusqu'ici, on peut faire mieux. Tout n'est calculé qu'à la demande, par exemple les éléments d'une liste chainée ne sont calculés qu'à la demande donc pour les grandes listes dont seul le début nous intéresse, c'est super, rien de trop ne sera calculé ni même instancié.
exemple :
let liste n =
let rec liste' m = if m >= 0 then n - m :: liste' (m-1) else []
in liste' n
let l = liste 10000000
let result =
let rec calc x::xs n =
if n > 0 then x + calc xs (n-1) else 0
in calc l 10
La notation
tete::queue est la notation des listes.
Avec cet exemple, dans un langage avide, le calcul de
l est obligatoire, quelquesoit sont utilisation réelle. Sauf que dans cet exemple, un "stack overflow" a toutes les chances de survenir avant que le résultat n'arrive (le calcul n'est volontairement pas récursif terminal). Dans un langage fainéant, pas de problème ! on calcule la somme des 10 premiers entiers.
Et puisque qu'on sait écrire des choses tecniquement incalculables, allons-y à fond, il est même possible décrire des choses théoriquement infinies.
exemple :
let rec suivants n = n::suivants (n + 1)
qui représente la liste des entiers suivants
n. Tant que vous n'essayez pas d'en calculer des trop grands, tout va bien dans un langage fainéant.
Revenons à notre problème d'arbres.
Prenons simplement un parent et un enfant (liste chainée de 2 éléments), si on construit le père d'abord et qu'on le passe au fils, le père ne connaitra pas son fils, car on a pas le droit "d'affecter" le père pour y enregistrer le fils, trivialement, dans l'ordre inverse, ça ne marche pas non plus.
Il faut donc construire simultanément les 2. Ce qui consiste à retarder la construction de l'un jusqu'à la création de l'autre, et réciproquement, d'où une belle boucle infinie. Hors la fainéantise permet de manipuler l'infinité, tant qu'on cherche pas à calculer sa valeur (qui reviendrait à tourner en rond indéfiniment entre le père et le fils dans ce cas).
petit exemple :
en langage Haskell qui est purement fonctionnel
data noeud = Element noeud
let rec parent = Element enfant
and enfant = Element parent
ce qui en Objective Caml donne plus ou moins :
type noeud = Element noeud Lazy.t
let rec parent' rien = Element lazy (enfant ())
and enfant' rien = Element lazy (parent ())
parent = Lazy.force parent'
enfant = Lazy.force enfant'
Dans le cas d'Objective Caml, on ne peut faire du récursif qu'avec des fonctions, on utilise donc des fonctions qui prement un argument inutile et on leur donne
() (l'unité) comme paramètre. Le mot-clef lazy transforme l'expression qui suit en valeur non-évaluée, le mot-clef Lazy.force, calcule l'expression non évaluée passée en paramètre.
Bien, on peut donc maintenant généraliser :
(* arbre de départ, qui va être converti *)
type 'a ltree = LLeaf of 'a | LNode of 'a ltree * 'a ltree
(* arbre d'arrivée, qui possède des référence enfants->parent *)
(* solution à parent lazy *)
type 'a rtree = RRoot of 'a rtree | RNode of 'a rtree * 'a rtree * 'a rtree Lazy.t | RLeaf of 'a * 'a rtree Lazy.t
let convert t =
let rec root = lazy(RRoot(tree t))
and tree t' = go root t'
and go pn = function
| LLeaf(v) -> RLeaf(v, pn)
| LNode(f, s) ->
let rec top = lazy (RNode(lson f, rson s, pn)) (* l'image du noeud *)
and lson f' = go top f' (* l'image de son fils gauche *)
and rson s' = go top s' (* l'image de son fils droit *)
in Lazy.force top
in Lazy.force root
et voiloù, la solution complète
ici, avec un exemple et une fonction d'affichage faite par Seb pour vérifier.
À noter que ce post est un large recyclage d'un
post que j'avais fait sur
HFR.