From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA10796; Mon, 16 Dec 2002 14:37:52 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA10768 for ; Mon, 16 Dec 2002 14:37:51 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id gBGDbo901862 for ; Mon, 16 Dec 2002 14:37:50 +0100 (MET) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.5/jtpda-5.4) with ESMTP id gBGDbojC086175 for ; Mon, 16 Dec 2002 14:37:50 +0100 (CET) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id OAA68190 for ; Mon, 16 Dec 2002 14:36:28 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id OAA5824514 for ; Mon, 16 Dec 2002 14:36:27 +0100 Date: Mon, 16 Dec 2002 14:36:27 +0100 (NFT) From: Diego Olivier Fernandez Pons To: caml-list@inria.fr Subject: Re: [Caml-list] Re: Continuations Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Antivirus: scanned by sophie at shiva.jussieu.fr Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 =E0 ce sujet et le livre que vous citez aborde de tr=E8s nombreux probl=E8mes, certains simples, d'autres plus avanc=E9s. 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 =EAtre confront=E9 =E0 un probl=E8me 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=E9sent=E9 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=E9mentation au moyens d'exceptions est alors imm=E9diate let rec next x =3D function | Empty -> raise Not_found | Node (l, v, r) -> match compare x v with =09| n when n < 0 -> (try next x l with Not_found -> v) =09| n when n > 0 -> next x r =09| _ -> min_element r (* raises [Not_found] *) ii) Calcul du k-i=E8me =E9l=E9ment On cherche le ki=E8me =E9l=E9ment dans un arbre binaire, et on se trouve su= r un noeud N, alors de deux chose l'une : - le ki=E8me =E9l=E9ment se trouve dans le sous arbre gauche - le sous arbre gauche contient moins de k =E9l=E9ments et le ki=E8me est dans le sous arbre droit On va simplement num=E9roter de fa=E7on d=E9croissante les noeuds suivant l'ordre sym=E9trique et on renvoyer le noeud de num=E9ro z=E9ro. exception Out_of_bounds of int let rec get n =3D function | Empty -> raise (Out_of_bounds n) | Node (_, v, _) when n =3D 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=E9rieure. Seulement, pour reprendre le calcul, il a fallu fournir un certain nombre d'informations (un contexte d'arr=EAt d'ex=E9cution du calcul en cours) - un bool=E9en pour la fonction [next] - un entier pour la fonction [get] Dans des exemples plus compliqu=E9s on est amen=E9 =E0 revoyer plus d'informations par exemple (strategie -> int) dans celui que vous avez donn=E9. Le probl=E8me est que nous sommes limit=E9s dans le type de l'argument d'une exception, il ne peut pas =EAtre 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=E9dure d'=E9valuation et s=E9paration (branch and bound) sur des donn=E9es polymorphes dans laquelle il faut faire remonter la derni=E8re meilleure solution trouv=E9e (donc polymorphe) La seconde id=E9e est alors d'utiliser le CPS (continuation passing style ou programmation par passage de continuation) Informellement, l'id=E9e est que dans les situations pr=E9c=E9dentes on se trouvait =E0 l'int=E9rieur d'une fonction "fixe" et on transformait des donn=E9es. Maintenant on va faire le contraire : on va laisser fixes les donn=E9es et on va transformer une fonction (que l'on va donc passer en argument =E0 chaque appel r=E9cursif) et ce n'est qu'=E0 la fin que l'on va appliquer la fonction construite aux donn=E9es initiales. Dans cette approche, on ne rencontre plus le probl=E8me de typage pr=E9c=E9dent (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 =3D 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=E8s exactement la fonction qui applique une fonction donn=E9e en param=E8tre ('a -> 'b) =E0 l'=E9l=E9m= ent minimal d'une liste ('a) ce qui donne en toute logique un =E9l=E9ment de type ('b) # min_list (function x -> x =3D 0) [1;4;2;0;6;2;2;2];; - : bool =3D true Certains langages vous offrent acc=E8s direct =E0 la continuation courante (scheme, unlambda) ou encore certaines impl=E9mentations particuli=E8res (SML/NJ) de langages qui n'en comportent pas (dans ce dernier cas c'est d=FB =E0 la m=E9thode de compilation utilis=E9e) Pour obtenir des continuations, vous pouvez donc : - utiliser des exceptions dans certaines limites - r=E9ecrire vos fonctions en CPS - introduire un m=E9canisme de liaison =E0 la continuation courante (call/cc) ce dernier point =E9tant plus ou moins difficile Vous avez dans la bosse Caml un interpr=E9teur Unlambda =E9crit en SML avec call/cc puis r=E9ecrit en CPS avec Caml (Scheme et Java =E9galement disponibles). Philip Wadler a =E9crit un certain nombre d'articles sur les rapports entre continuations et monades. Enfin, si j'ai bonne m=E9moire Benjamin C. Pierce a post=E9 dans la liste Caml il y a quelque temps une s=E9rie 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