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