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 IAA02258; Tue, 17 Dec 2002 08:58:29 +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 IAA02251 for ; Tue, 17 Dec 2002 08:58:28 +0100 (MET) Received: from wetware.wetware.com (wetware.wetware.com [199.108.16.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id gBH7wRH05970 for ; Tue, 17 Dec 2002 08:58:27 +0100 (MET) Received: from wetware.com([208.177.152.19]) (6708 bytes) by wetware.wetware.com via sendmail with P:esmtp/R:bind_hosts/T:inet_zone_bind_smtp (sender: ) id for ; Mon, 16 Dec 2002 23:58:25 -0800 (PST) (Smail-3.2.0.114 2001-Aug-6 #1 built 2002-Sep-2) Date: Mon, 16 Dec 2002 23:58:36 -0800 Subject: Re: [Caml-list] Re: Continuations Content-Type: text/plain; charset=ISO-8859-1; format=flowed Mime-Version: 1.0 (Apple Message framework v548) Cc: The Trade To: Pal-Kristian Engstad From: james woodyatt In-Reply-To: <200212161053.37708.engstad@naughtydog.com> Message-Id: <586843A2-1195-11D7-ABF0-000393BA7EBA@wetware.com> Content-Transfer-Encoding: quoted-printable X-Mailer: Apple Mail (2.548) Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Monday, Dec 16, 2002, at 10:53 US/Pacific, Pal-Kristian Engstad=20 wrote: > On Monday 16 December 2002 05:36 am, Diego Olivier Fernandez Pons=20 > wrote: >> Bonjour, > > I'd _really_ like to know what Diego says in his post to the mailing=20= > list, but > I do not speak French. Please, _please_ write your posts in English.=20= > Can > someone translate it, perhaps? I don't speak French either, but there are automated translation tools=20= on the web. My computer has an application, called Sherlock (it comes=20= with the operating system I use), that has a very easy interface for=20 feeding text into various Systran translators. And Systran does a=20 pretty good job with translations of technical French into English. All in all, I think the mailing list charter should continue to approve=20= of the posting of messages in either French or English. (I tend to=20 view this as an accommodation of the English speakers, rather than of=20 the French speakers.) Here is what Systran says Diego wrote: > The question relates primarily to the simulation of the continuations > by means of exceptions, supplied with an example. > > I am unaware of your level of knowledge on this subject and the book > which you quote approaches of very many problems, unquestionable > simple, others more advanced. > > One thus will start rather simply, with two examples which use the > style rupture/reprise calculation by means of exceptions that your > propose and to see that one can be confronted with a problem of > typing > > i) Calcul of the successor of a node > > Let us suppose that one wants the successor of 3 as a whole [ 1;4;5;6 > ] represented by a binary tree of search. > > You arrive on node 5, then of two things one: - the successor of 3 is > in under left tree of 5 > - the successor of 3 is 5, under left tree of 5 is empty > > The implementation with the means of exceptions is then > immediate > > let rec next X =3D function | Empty -> raise Not_found | Node (L, v, > R) -> match compares 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) Calculation of the kth element > > One seeks the kth element in a binary tree, and one is on a node N, > then of two thing one: - the kth element is in under left tree > - under left tree contains less K elements and the kth one is in under > straight shaft > > One simply will number in a decreasing way the nodes according to the > symmetrical command and one to return the node of number zero. > > 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 > > In both cases one made an interruption of calculation in progress (by > means of an exception) and a later resumption of calculation. Only, to > take again calculation, it was necessary to provide a certain number > of information (a context of stop of execution of calculation in > progress) - Boolean for the function [ next ] - an entirety for the > function [ get ] > > In more complicated examples one is brought to revoyer more > information for example (strategy -> int) in that which you gave. > > The problem is that we are limited in the type of the argument of an > exception, it cannot be polymorphic. =46rom this observation it is not > difficult to build examples for which this approach shows its limits. > > For example a procedure of evaluation and separation (branch and > bound) on polymorphic data in which it is necessary to make go up the > last better solution found (thus polymorphic) > > The second idea is then to use the CPS (continuation passing style or > programming by passage of continuation) > > Informellement, the idea is that in the preceding situations one was > inside a function "fixes" and one transformed data. Now one will make > the opposite: one will leave fixed the data and one will transform a > function (which one thus will pass in argument to each recursive call) > and it is only at the end that one will apply the function built to > the initial data. > > In this approach, one does not encounter any more the problem of > preceding typing (the transmitted function can have a polymorphic type > perfectly) > > Chazarin gives you a multitude of progressive examples > > Here an example (simple) > > let rec min_list F =3D function | [ ] -> failwith "the list is empty" > | [ X ] -> F X | X:: tail -> min_list (fun m -> yew X < m > then F X else F m) tail > > valley min_list: (' -> has; ' b) -> ' list -> has; ' B > > What min_list calculates is a function, very exactly the function > which applies a function given in parameter (' has -> ' b) with the > minimal element of a list (' a) what gives in all logic an element of > the type (' b) > > # min_list (function X -> X =3D 0) [ 1;4;2;0;6;2;2;2 ];; -: bool =3D > true > > Certain languages offer random access to the current continuation to > you (scheme, unlambda) or certain particular implementations (SML/NJ) > of languages which do not comprise any (in the latter case it is due > to the method of compilation used) > > To obtain continuations, you thus can: - to use exceptions in some > limit > - r=C3=A9ecrire your functions in CPS > - to introduce a mechanism of connection to the current continuation > (call/cc) this last point being more or less difficult > > You have in the Caml bump a Unlambda interpreter written in SML with > call/cc then r=C3=A9ecrit in CPS with Caml (Scheme and Java also > available). > > Philip Wadler wrote a certain number of articles on the relationship > between continuations and monades. Lastly, if I have good memory > Benjamin C. Pierce posted in the list Caml some time ago a series of > links in connection with the continuations. I found this to be pretty readable after an automated translation. --=20 j h woodyatt markets are only free to the people who own them. ------------------- 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