'Nondeterministic' evaluation wrt exceptions

'Nondeterministic' evaluation wrt exceptions

[Dawid Toton]

Let's look at my OCaml program as a poset of function applications.
Some its elements throw exceptions.
I need to evaluate all applications except of those that 'Follow' 
exception-throwing ones.
This 'Follow' corresponds to the ordering in my poset.
Unfortunately standard tools allow only to do this with 'Follow' 
corresponding to some total order.
Could you give me some advice how to evaluate really all applications 
that precede throwing an exception?

----------
Full story

I have many similar programs that do calculations for me. Some steps are 
very computationally heavy. Every such function do_heavy_thing starts 
another process (on other computer) and throws an exception that means 
"the result will be available later". Everything that relies on this 
result of do_heavy_thing cannot be evaluated. And it won't be because I 
don't catch the exception.

So I run my programs repeatedly. I correct and extend them while 
heavy_thing is done somewhere else (usually for few days).
do_heavy_thing checks for the result. If it's finished at the moment of 
execution, it downloads the data and returns. Then the data undergoes 
some cheap transformations and some next do_heavy_thing function can be 
called.

Every time I execute the program I get some more useful output and 
"Fatal error: exception ..." message. So far this scheme worked very well.

This is basically breaking the calculation at some point with respect to 
a total order (the order of source code). Some calculations should be 
done in parallel, since there are many of them. I solved this problem 
with run_many adapter: firstly collect a list of heavy calculations, 
then execute them as a one node in the total order of evaluation.

Currently I hit the following problem: my new programs (call them 
'Calcs') are too complex to apply the evasion with run_many. So my 
latest calculations are done one-by-one. This is so bad, that I can 
spend several days in order to solve this in a systematical way.

These Calcs are managed by other set of OCaml tools. I have complete 
control over all the code. The tools already do tiny changes to Calcs 
with simple string operations, not real syntax extension. I hope some 
witty preprocessor can help.

I have no idea what code the syntax extension should produce. My first 
guess is to wrap everything in
 type 'a wrapped = Exception | Value 'a
and make all aplications evaluated. But this seems to be a big headache. 
Maybe this is well-known, already solved problem? Any ideas?

Dawid

Re: [Caml-list] 'Nondeterministic' evaluation wrt exceptions

[Gabriel Kerneis]

On Fri, Jul 25, 2008 at 04:29:47PM +0100, Dawid Toton wrote:
> I have no idea what code the syntax extension should produce. My first  
> guess is to wrap everything in
> type 'a wrapped = Exception | Value 'a
> and make all aplications evaluated. But this seems to be a big headache.  
> Maybe this is well-known, already solved problem? Any ideas?

The wrapping you describe looks a lot like a monad, and your problem
definitely looks like having many (cooperative) threads, some of them needing
to be detached (because they are blocking).

You could have a look at http://ocsigen.org/lwt and adapt it to suit your
needs. Pay attention in particular to the detach() function.

Please, note I might be seeing monads and continuation-passing style
everywhere, since this is my current research topic.

Regards,
-- 
Gabriel Kerneis

Re: [Caml-list] 'Nondeterministic' evaluation wrt exceptions

[Xavier Leroy]

> Could you give me some advice how to evaluate really all applications
> that precede throwing an exception?

I'm not sure I fully understand what you're trying to achieve, but I'm
reminded of "futures", a construct for parallel computation that
was popular in the Lisp world in the 80's.  The classic reference
is Halstead's Multilisp system:
   http://www.cs.wisc.edu/~fischer/cs538.s04/multilisp.pdf

In a nutshell, a future is like a lazy value, but the underlying
computation is evaluated speculatively in parallel with the main
program, rather than waiting until its value is needed as in the case
of lazy evaluation.

Hope this might help,

- Xavier Leroy

Re: [Caml-list] 'Nondeterministic' evaluation wrt exceptions

[Dawid Toton]

Thank you all for quick answers!

Let me show an example of what I exactly mean. I start with a code:

1: let a = heavy 1
2: let b = heavy 2
3: let c = report (a + b)
4: let d = heavy 4
5: let e = heavy d

Then I want to translate it automatically so that three applications of
heavy are evaluated (lines 1, 2, 4). The addition a + b won't be
evaluated untill a and b are successfully returned.

It's easier to get only two heavy operations started at once:

0: type 'a future_t = 'a Lazy.t
1: let a = future heavy 1
2: let b = future heavy 2
3: let c = report ((force a) + (force b))
4: let d = future heavy 4
5: let e = future heavy (force d)

Computation of c hangs or throws an exception. Hence lines 4 an 5 are
not executed. So I think I need some more invasive transformarion:

0: type 'a future_t = 'a Lazy.t
1: let a = future heavy 1
2: let b = future heavy 2
3: let c = lazy (report (force a) + (force b))
4: let d = future heavy 4
5: let e = future heavy (force d)
6: let _ = force c

In this case we have a problem: line 5 throws an exception, so report in
line 3 is not executed even if first two heavy operations are finished.
The function report could even contain some other heavy operations that
need to be started as soon as possible.

So I can conctruct a tree of deferred computations, but probably I can't
force it to do as much as possible. Forcing is governed by total order.
Let's consider:

7: let f = foo (force c) (force e)

If one of arguments fails first, the other is not forced. This is bad.

So I go to the original idea: thread the exception across everything.
Wrap with variant instead of Lazy.t.

0: type 'a lifted_t = Exception | Value 'a
1: let a = start heavy 1
2: let b = start heavy 2
3: let c = bind2 (fun a b -> return (report (a+b))) a b
4: let d = start heavy 4
5: let e = bind1 (fun d -> start heavy d) d
7: let f = bind2 (fun c e -> return (foo c e)) c e

Function 'start' starts calculation and returns Exception or returns
Value result if it's available.
bindX functions evaluate the function passed as a parameter if all
arguments are Values.

Is is easy to lift every heavy call to 'start heavy arg arg arg ...' -
since in any case I have to distinguish heavy functions manually.
I need to decide about granularity of bindX incrustation. I can have
some modules marked as 'nondeterministic' and leave the other ones
untouched.
I could wrap into lifted_t all single values in 'nondeterministic'
modules. This would mean placing bindX for every integer addition, every
string concatenation...

I need rules: where should I place bindX and return in the original
code. At the moment I don't know.

I have looked at the Lwt library - as far as I understand in my case the
idea boils down to threading something across all expressions.

Dawid

Re: [Caml-list] 'Nondeterministic' evaluation wrt exceptions

[Christophe TROESTLER]

On Fri, 25 Jul 2008 20:29:12 +0100, Dawid Toton wrote:
> 
> Let me show an example of what I exactly mean. I start with a code:
> 
> 1: let a = heavy 1
> 2: let b = heavy 2
> 3: let c = report (a + b)
> 4: let d = heavy 4
> 5: let e = heavy d
> 
> Then I want to translate it automatically so that three applications of
> heavy are evaluated (lines 1, 2, 4). The addition a + b won't be
> evaluated untill a and b are successfully returned. (...)

You may want to have a look to
http://enfranchisedmind.com/blog/2007/08/06/a-monad-tutorial-for-ocaml/
especially the "Russian Nesting Doll Monads" section for ideas.

Regards,
ChriS

Re: 'Nondeterministic' evaluation wrt exceptions

[Zheng Li]

Hi,

Dawid Toton wrote:
> Thank you all for quick answers!
> 
> Let me show an example of what I exactly mean. I start with a code:
> 
> 1: let a = heavy 1
> 2: let b = heavy 2
> 3: let c = report (a + b)
> 4: let d = heavy 4
> 5: let e = heavy d
> 
> Then I want to translate it automatically so that three applications of
> heavy are evaluated (lines 1, 2, 4). The addition a + b won't be
> evaluated untill a and b are successfully returned.

I'm not clear about what you want. It seems that you're doing 
asynchronous parallel programming.

I have a Async library, which is not yet released (needs polish). It 
allows you express the logic like

<code>
let c = Future
   { let! a = heavy 1 in
     let! b = heavy 2 in
     return (a + b) }

let e = Future
   { let! d = heavy 4 in
     heavy d }
</code>

or

<code>
let c = Future
   { let! a = spawn heavy 1 in
     let! b = spawn heavy 2 in
     return (a + b) }

let e = Future
   { let! d = spawn heavy 4 in
     spawn heavy d }
</code>

if you intend to assign specific computing unit for some heavy computation.

I hope to release it in the summer, but don't hold your breath. If 
you're in a hurry, you should turn to other libraries instead. (There 
exist a few of them doing the similar thing, but I can't remember the 
accurate information.)

HTH.

--
Zheng Li
http://www.pps.jussieu.fr/~li