Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: [Caml-list] Re: Continuations
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@c...>
Subject: Re: [Caml-list] Re: Continuations
    Bonjour,

> [continuations] Are not they possible ? If I remember well (I did
> not check it back), the following sample do what is called
> `Programming with rupture and continuation' (I learned it from J.
> Chazarin "Programmer avec Scheme").

La question porte essentiellement sur la simulation des continuations
au moyen d'exceptions, assortie d'un exemple.

J'ignore votre niveau de connaissances à ce sujet et le livre que vous
citez aborde de très nombreux problèmes, certains simples, d'autres
plus avancés.

On va donc commencer assez simplement, avec deux exemples qui
utilisent le style rupture/reprise de calcul au moyen d'exceptions que
vos proposez et voir que l'on peut être confronté à un problème de
typage

i) Calcul du successeur d'un noeud

Supposons que l'on veuille le successeur de 3 dans l'ensemble
[1;4;5;6] représenté par un arbre de recherche binaire.

Vous arrivez sur le noeud 5, alors de deux choses l'une :
  - le successeur de 3 est dans le sous arbre gauche de 5
  - le successeur de 3 est 5, le sous arbre gauche de 5 est vide

L'implémentation au moyens d'exceptions est alors immédiate

let rec next x = function
  | Empty -> raise Not_found
  | Node (l, v, r) ->
      match compare x v with
	| n when n < 0 -> (try next x l with Not_found -> v)
	| n when n > 0 -> next x r
	| _ -> min_element r (* raises [Not_found] *)

ii) Calcul du k-ième élément

On cherche le kième élément dans un arbre binaire, et on se trouve sur
un noeud N, alors de deux chose l'une :
- le kième élément se trouve dans le sous arbre gauche
- le sous arbre gauche contient moins de k éléments et le kième est
dans le sous arbre droit

On va simplement numéroter de façon décroissante les noeuds suivant
l'ordre symétrique et on renvoyer le noeud de numéro zéro.

exception Out_of_bounds of int

let rec get n = function
  | Empty -> raise (Out_of_bounds n)
  | Node (_, v, _) when n = 0 -> v
  | Node (l, v, r) ->
      try get n l
      with Out_of_bounds k -> get (k - 1) r

Dans les deux cas on a fait une interruption du calcul en cours (au
moyen d'une exception) et une reprise de calcul ultérieure. Seulement,
pour reprendre le calcul, il a fallu fournir un certain nombre
d'informations (un contexte d'arrêt d'exécution du calcul en cours)
  - un booléen pour la fonction [next]
  - un entier pour la fonction [get]

Dans des exemples plus compliqués on est amené à revoyer plus
d'informations par exemple (strategie -> int) dans celui que vous avez
donné.

Le problème est que nous sommes limités dans le type de l'argument
d'une exception, il ne peut pas être polymorphe. A partir de cette
constatation il n'est pas difficile de construire des exemples pour
lesquels cette approche montre ses limites.

Par exemple une procédure d'évaluation et séparation (branch and
bound) sur des données polymorphes dans laquelle il faut faire
remonter la dernière meilleure solution trouvée (donc polymorphe)

La seconde idée est alors d'utiliser le CPS (continuation passing
style ou programmation par passage de continuation)

Informellement, l'idée est que dans les situations précédentes on se
trouvait à l'intérieur d'une fonction "fixe" et on transformait des
données. Maintenant on va faire le contraire :  on va laisser fixes
les données et on va transformer une fonction (que l'on va donc passer
en argument à chaque appel récursif) et ce n'est qu'à la fin que l'on
va appliquer la fonction construite aux données initiales.

Dans cette approche, on ne rencontre plus le problème de typage
précédent (la fonction transmise peut parfaitement avoir un type
polymorphe)

Chazarin vous donne une multitude d'exemples progressifs

Voici un exemple (simple)

let rec min_list f = function
  | [] -> failwith "the list is empty"
  | [x] -> f x
  | x :: tail -> min_list (fun m -> if x < m then f x else f m) tail

val min_list : ('a -> 'b) -> 'a list -> 'b

Ce que min_list calcule est une fonction, très exactement la fonction
qui applique une fonction donnée en paramètre ('a -> 'b) à l'élément
minimal d'une liste ('a) ce qui donne en toute logique un élément de
type ('b)

# min_list (function x -> x = 0) [1;4;2;0;6;2;2;2];;
- : bool = true

Certains langages vous offrent accès direct à la continuation courante
(scheme, unlambda) ou encore certaines implémentations particulières
(SML/NJ) de langages qui n'en comportent pas (dans ce dernier cas
c'est dû à la méthode de compilation utilisée)

Pour obtenir des continuations, vous pouvez donc :
 - utiliser des exceptions dans certaines limites
 - réecrire vos fonctions en CPS
 - introduire un mécanisme de liaison à la continuation courante
(call/cc) ce dernier point étant plus ou moins difficile

Vous avez dans la bosse Caml un interpréteur Unlambda écrit en SML
avec call/cc puis réecrit en CPS avec Caml (Scheme et Java également
disponibles).

Philip Wadler a écrit un certain nombre d'articles sur les rapports
entre continuations et monades. Enfin, si j'ai bonne mémoire Benjamin
C.  Pierce a posté dans la liste Caml il y a quelque temps une série
de liens en rapport avec les continuations.


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners