Re: [Caml-list] Re: Continuations

Re: [Caml-list] Re: Continuations

[Diego Olivier Fernandez Pons]

    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

Re: [Caml-list] Re: Continuations

[Pal-Kristian Engstad]

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?

PKE.

-------------------
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

Re: [Caml-list] Re: Continuations

[james woodyatt]

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

Re: [Caml-list] Re: Continuations

[james woodyatt]

On Monday, Dec 16, 2002, at 05:36 US/Pacific, Diego Olivier Fernandez 
Pons wrote:
> "Michaël Grünewald" <michael-grunewald@wanadoo.fr> wrote:
>>
>> [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").
>
> [...] 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.

Another paper that I found exceedingly helpful in this regard is this 
one:

	<http://www.math.chalmers.se/~augustss/AFP/monads.html>

Of course, all the code in that paper is written in some Haskell 
variant that I can't identify with complete accuracy.  But scroll down 
to the section about the continuation monad, and then watch how it can 
be used as the basis of more complicated monads.

I've found that equivalent code in Ocaml is not terribly difficult to 
write.  It does tend to make you wish for something to let you define 
overloaded operators, but you can get by fine without.


-- 
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

Re: [Caml-list] Re: Continuations

[Diego Olivier Fernandez Pons]

    Hi,

Continuation simulation with an exception mechanism is a well known
subject and what I said in my last french post and will explain again
in english here is nothing new. Then you should find all this (and
more) in english textbooks on the subject.

Roughly, the idea of continuations is the ability to interrupt a
computation, do other computations, and then get back to the
first computation in the same point it was left.

To achieve this goal one needs to save some kind of 'context' of the
ongoing computation. This can be obtained in several ways, among which
saving the stack (confer to Raffalli's recent posts on the
subject), etc.

Let us take a simple example :

Consider a branch and bound distributed algorithm. There are many ways
to parallelize a graph exploration (shared priority queue, graph
partition, ...) we will use the graph partition for simplicity (that
is every processor is given a subgraph to explore)

Then, every time a given processor founds a solution which is better
than the current best known solution, it has to send it to the other
machines in order to be able to cut more branches of the graph.

that is :
  - search
  - if a good solution is found then send it to the other machines
  - continue the search at the same point it was left

The problem is that when you raise an exception (or return a value by
usual function returning mechanism), you escape of the current
function and loose all intermediate computations, so you cannot get
back to the same point you left.

In many cases, this is not really a problem since you do not need to
get back to 'exactly' the same point you left. All you need is to
memorize enought information to go back to a state similar to the
state you left.

In my french post I gave two examples of reduced information handling
in a interruption/recovery style

- successor function (a boolean)
- get function (an integer)

One problem you may face is that the argument of an exception has a
restricted type (it cannot be polymorphic). Then how could you do when
you have to return a polymorphic value (as it would be the case if the
branch and bound was polymorphic ?)

In most of the cases, you can still manage

In the branch and bound example, you can save the path of the current
node

type direction = Left | Right
exception Found of direction list

type 'a tree = Empty | Node of 'a tree * 'a * 'a tree

let rec search x = function
  | Empty -> raise Not_found
  | Node (_, v, _) when v = x -> raise (Found [])
  | Node (l, _, r) ->
     try search x l with
       | Not_found ->
	  (try search x r with
		Found path -> raise (Found (Right :: path)))
       | Found path -> raise (Found (Left :: path))

This function just searches x in a binary tree and raises
  - Not_found if x is not in the tree
  - Found path if x is in the tree

You can then compose it with a function that locates a node from a
given path, or finds a given node

val locate : direction list -> 'a tree -> 'a tree
val find : direction list -> 'a tree -> 'a


In my french post I also spoke of continuation passing style. Just
notice that with CPS you are not subjected to type limitations

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

Min_list computes a function that applies a given function to the min
element of a list

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


        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

[Caml-list] Re: Continuations

[Michaël Grünewald]

Ceri Storey <cez@mrtall.compsoc.man.ac.uk> writes:

> I was just wondering if there any possibility of there being support
> for continuations in a future version of ocaml?

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").

Help me: just after the "resoud_probleme" definition, you can spot ";;", the
i can not achieve to remove (i got a syntax error, then).

---- BEGIN CODE ----
type strategie = Abandonne | Ignore | Remplace of int

exception Rupture of (strategie -> int)

let resoud_probleme l =

    let rec continue ax togo strategy =
	match strategy with
	    | Abandonne -> 	ax
	    | Ignore -> 	resoud ax (List.tl togo)
	    | Remplace x -> 	resoud ax (x::(List.tl togo))

    and resoud ax l = 
	match l with 
	    | [] ->	ax
	    | 0::tl -> 	raise (Rupture (continue ax l))
	    | hd::tl -> resoud (ax + hd) tl

    in resoud 0 l
;;

let process_problem l s =
    try  resoud_probleme l
    with Rupture closure -> closure s
    	
in
let strategie_to_string s = 
    match s with
	| Abandonne -> "Abandonne"
	| Ignore -> "Ignore"
	| Remplace x -> Printf.sprintf "Remplace par %d" x

in
let monitor_problem l s =
    Printf.printf "Solution: %d (%s)\n" (process_problem l s) 
    (strategie_to_string s)

in

let main () = 
    let pblm = [10; 23; 33; 0; 12] in
	List.iter (monitor_problem pblm) [Abandonne; Ignore; 
					  Remplace 1; Remplace 12];
	exit 0

in main()
---- END CODE ----

This code is in the awful French/English mix i write when programming, there
is a little lexicon by the end of this message.

Maybe this is not what you call Rupture/Cotninuation (you did not speak of
rupture), but after my memories, this is.

Code explanation: `resoud_problem' must process an horrific and very looong
calculous (the sum of 5 or 6 integers from a list), but take the occurence
of '0' as a critical situation where the calculous cannot be resumed in a
consistent way, it asks the users which Strategy to apply (give up, ignore
critical value, correct the value).

Lexicon :
Abandonne : give up
Ignore : ignore (it could have been 'remove')
Remplace : replace

-- 
Michaël Grünewald <michael-grunewald@wanadoo.fr>  - RSA PGP Key ID: 0x20D90C12
-------------------
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