Re: [Caml-list] Re: Continuations

[james woodyatt <jhw@wetware.com>]

On Monday, Dec 16, 2002, at 10:53 US/Pacific, Pal-Kristian Engstad 
wrote:
> On Monday 16 December 2002 05:36 am, Diego Olivier Fernandez Pons 
> wrote:
>>     Bonjour,
>
> I'd _really_ like to know what Diego says in his post to the mailing 
> list, but
> I do not speak French. Please, _please_ write your posts in English. 
> Can
> someone translate it, perhaps?

I don't speak French either, but there are automated translation tools 
on the web.  My computer has an application, called Sherlock (it comes 
with the operating system I use), that has a very easy interface for 
feeding text into various Systran translators.  And Systran does a 
pretty good job with translations of technical French into English.

All in all, I think the mailing list charter should continue to approve 
of the posting of messages in either French or English.  (I tend to 
view this as an accommodation of the English speakers, rather than of 
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 = 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 = 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
>
> 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. From 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 = 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: (' -&gt has; ' b) -> ' list -&gt 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 = 0) [ 1;4;2;0;6;2;2;2 ];; -: bool =
> 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éecrire 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éecrit 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.


-- 
j h woodyatt <jhw@wetware.com>
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