décembre
2008
Un article de SpiceGuid
Ce billet vient compléter à la fois la partie 5 (la programmation impérative) et la partie 8 (les types algébriques) de mon tutoriel Objective-Caml, il emprunte à ces deux parties pour généraliser le traitement des types arborescents au traitement des types DAG (graphes dirigés acycliques ou Directed Acyclic Graphs).
On y réalise cette généralisation à l’aide de la technique des pointeurs ‘intelligents’, complétée par un vilain hack, pas beau mais pas encore trop méchant.
1. Motivation
Les types sommes ne couvrent que les structures arborescentes, or on aimerait bien disposer des mêmes facilités sur les structures contenant des cellules partagées. En particulier on aimerait pouvoir mémoizer les calculs sur les noeuds partagés plutôt que les dupliquer autant de fois que le noeud est référencé.
2. L’interface
Le module Shared contiendra toutes les fonctionalités necéssaire au partage du calcul, il nous faudra en particulier :
- un type Shared.t qui servira à construire un type partagé
- un tick d’horloge
- un constructeur Shared.shared pour les cellules éventuellement partagées
- un constructeur Shared.owned pour les cellules dont on sait qu’elles ne seront jamais partagées
- un accesseur Shared.contents (on dit aussi déconstructeur)
- un constructeur Shared.memo pour créer un calcul partagé
- un foncteur de partage memo_map
Autant d’exigences que l’on peut exprimer à l’aide de cette interface :
module Shared :
sig
type 'a t (* le constructeur de types partagés *)
val tick : unit (* l'horloge *)
val owned : 'a -> 'a t (* le constructeurs pour les valeurs non-partagées *)
val shared : 'a -> 'a t (* le constructeurs pour les valeurs partagées *)
val contents : 'a t -> 'a (* l'accesseur/déconstructeur *)
val memo : ('a -> 'b) -> ('a t -> 'b) (* le constructeur de calcul partagé *)
val memo_map : ('a -> 'b) -> ('a t -> 'b t) (* le foncteur de partage *)
end
L’utilité du tick d’horloge est en tous points semblable à la description faite à la partie 5 (la programmation impérative).
Les noeuds partagés du DAG sont marqués avec la date du dernier passage.
Un noeud partagé qui est à l’heure par rapport à l’horloge est un noeud à jour.
Un noeud partagé qui est en retard par rapport à l’horloge est un noeud à mettre à jour.
Il suffit de ticker l’horloge avant un parcours sur le DAG afin d’ôter le marquage sur les noeuds partagés.
Grâce à cette astuce il n’est pas nécessaire de traverser le graphe uniquement pour ôter le marquage comme on devrait le faire si l’on marquait simplement avec un bool.
3. L’utilisation
Pour transformer un type quelconque en un type partagé il suffira de lui adjoindre Shared.t en position postfixe.
Par exemple ce type arbres binaires sans partage :
type 'a bintree =
| BLeaf
| BNode of ('a bintree) * 'a * ('a bintree)
Se convertira facilement en un type arbres binaires avec partage:
type 'a sbintree =
| SLeaf
| SNode of ('a sbintree Shared.t) * 'a * ('a sbintree Shared.t)
De même, le pliage d’un type arbre binaire sans partage :
let bfold f init t =
let rec loop t =
match t with
| BLeaf -> init
| BNode(l,a,r) -> f (loop l) a (loop r)
in loop t
Se réécrira aisément en un pliage pour arbre binaire avec partage, pour cela il suffira de ticker l’horloge et de partager les calculs à l’aide de Shared.memo :
let sfold f init t =
let rec loop t =
let memo_loop = Shared.memo loop in
match t with
| SLeaf -> init
| SNode(l,a,r) -> f (memo_loop l) a (memo_loop r)
in Shared.tick; loop t
Les fonctions usuelles sont alors disponibles exactement sous la même forme que leurs équivalents non-partagées :
let size t = sfold (fun l a r -> l + r + 1) 0 t let depth t = sfold (fun l a r -> max l r + 1) 0 t let strahler t = sfold (fun l a r -> if l=r then l+1 else max l r) 1 t let iter f t = sfold (fun l a r -> f a) () t let flatten t = sfold (fun l a r -> l @ a::r) [] t let for_all f t = sfold (fun l a r -> l && r && f a) true t let exists f t = sfold (fun l a r -> l or r or f a) false t let mem x t = sfold (fun l a r -> l or r or x=a) false t let rev t = sfold (fun l a r -> BNode(r,a,l)) BLeaf t let map f t = sfold (fun l a r -> BNode(l,f a,r))) BLeaf t let split t = sfold (fun (m,q) (a,b) (p,r) -> BNode(m,a,p),BNode(q,b,r)) (BLeaf,BLeaf) t
Les trois dernières fonctions suggèrent une extension supplémentaire.
Car elles renvoient bien des arbres binaires mais ceux-ci sont non-partagés.
Notre pliage a tout simplement oublié le partage dans la structure initiale.
Comment faire si nous voulons préserver le partage dans le résultat ?
Pour obtenir la mémoire du partage il va bous falloir un nouveau pliage, moins général, plus spécialisé dans la création d’arbres binaires partagés, mais qui a le mérite de préserver le partage de notre structure initiale.
On implémente ce pliage à l’aide du foncteur de partage Shared.memo_map :
let sfold_map f t =
let rec loop t =
let memo_loop = Shared.memo_map loop in
match t with
| SLeaf -> SLeaf
| SNode(l,a,r) -> f (memo_loop l) a (memo_loop r)
in Shared.tick; loop t
On utilisera ce pliage conservateur exactement de la même façon que la version oublieuse :
let srev t = sfold_map (fun l a r -> SNode(r,a,l)) t let smap f t = sfold_map (fun l a r -> SNode(l,f a,r)) t
4. L’implémentation
Le module Shared ne fait qu’implémenter un pointeur ‘intelligent’ avec une horloge interne et un champ pour mémoizer le résultat du calcul effectué lors du premier passage.
Par conséquent le code de ce module n’est pas très chargé en logique.
module Shared =
struct
let clock = ref 0
let tick = incr clock
type 'a t =
| Owned of 'a
| Shared of 'a * int ref * unit ref
let owned x = Owned x
let shared x = Shared(x,ref 0,ref ())
let contents = function
| Owned x -> x
| Shared(x,_,_) -> x
let memo f = function
| Owned x -> f x
| Shared(x,date,result) ->
if !date < !clock then begin
result := Obj.magic (f x); date := !clock;
end;
Obj.magic !result
let memo_map f = function
| Owned x -> owned (f x)
| Shared(x,date,result) ->
if !date < !clock then begin
result := Obj.magic (shared (f x)); date := !clock;
end;
Obj.magic !result
end
La seule chose un peu discutable c’est l’utilisation de Obj.magic pour casser le typage du champ de mémoization. Cependant la seule alternative irréprochable qui me vienne à l’esprit consiste à parcourir l’ensemble du graphe d’objets pour calculer sa taille dans le but de créer un tableau dynamique avec la taille et le type adéquats. Dans ce cas les noeuds ne stockeraient plus le résultat du calcul mais l’indice où trouver le résultat dans le tableau.
5. Les limitations
Notre approche ne fournit pas exactement la généralité souhaitée.
En particulier le partage du calcul n’est pas réentrant, c’est-à-dire qu’il ne peut y avoir, à un moment donné, qu’un seul calcul partagé qui court à travers un même graphe d’objets.
Stocker les résultats dans un tableau réservé à un parcours ne nous avancerait à rien quant au contournement de cette limitation, en effet :
- un même noeud ne sera pas forcément situé au même indice pour tous les parcours qui le traversent
- un noeud ne contient qu’un seul marqueur, or il faudrait un marquage distinct pour chacun des parcours
6. Conclusion
On a bien vu avec cet exemple que, malgré la présence d’un ramasse-miettes, le partage n’est pas encore complètement géré par les langages de haut niveau et par conséquent on ne peut pas se permettre de bouder les techniques de pointeurs ‘intelligents’.
On a implémenté un pointeur sur objets partagés qui entraîne un minimum d’inconfort pour l’utilisateur.
On a donné un exemple d’utilisation dans le cadre du parcours d’un DAG, cependant notre module n’est pas limité aux structures acycliques, quand cela fait sens on pourra très bien propager un calcul sur un TAD contenant éventuellement des cycles.
Les cycles restent complètement transparents, ils ne sont pas traités différemment du partage sans cycles.