Re: [Caml-list] Re: Continuations

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

    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