Restarting a piece of code

Restarting a piece of code

[Andrej Bauer]

I have a problem which I do not know how to program in The Right Way.
I would be grateful to hear ideas on how to do it.

Suppose I have a bunch of functions (the actual example is exact real
number arithmetic) which optimistically compute results (e.g. we compute
numbers up to some precision and hope it will be good enough) that may
turn out not to be good enough later during the computation. When this
happens, the entire computation needs to be restarted (e.g. we need to
recompute the numbers again with higher precision).

I will describe a specific made up example which demonstrates my point.
Suppose we want to add numbers, but if we ever exceed max_value during
addition, an exception is thrown:

let max_value := ref 10

exception Overflow

let add x y =
  let z = x + y in
    if z < !max_value then z else raise Overflow

If in a computation Overflow is thrown, we want to catch it, increase
max_value by some amount (say, double it), and try again. One way to do
this is by wrapping the code with a "compute" function that does this:

let rec compute code =
  try
    code ()
  with
    Overflow ->
      (max_value := 2 * !max_value;
       compute code)

To compute the sum 1 + 2 + 3 + .. + 100 we evaluate

compute (fun () ->
  let s = ref 0 in
  for i = 1 to 100 do
    s := add !s i
  done ;
  s)

While this idea works, there are two problems (side-effect are also an
issue but I do not care about that):

1) The programer who has to enclose pieces of code that use "add"
   inside the "compute" wrapper that catches Overflow and restarts
   the computation.

2) max_value is a global variable. Sometimes we want nested "computes",
   each with its own max_value.

What to do? I want the programmer to have a minimal overhead
(syntactically and also in terms of having to think about what is going
on). Which programming concept am I failing to use here?

Thanks for your help,

Andrej

P.S. One idea is to remember enough info so that we can recompute better
values on demand. This turns out to be bad in my case (real number
arithmetic) because you end up using space linear in the number of
arithmetic operations, which is too expensive (think a hundred billion
arithmetic operations).

Re: [Caml-list] Restarting a piece of code

[Alex Baretta]

Andrej Bauer wrote:
> I have a problem which I do not know how to program in The Right Way.
> I would be grateful to hear ideas on how to do it.
> 
> Suppose I have a bunch of functions (the actual example is exact real
> number arithmetic) which optimistically compute results (e.g. we compute
> numbers up to some precision and hope it will be good enough) that may
> turn out not to be good enough later during the computation. When this
> happens, the entire computation needs to be restarted (e.g. we need to
> recompute the numbers again with higher precision).

This is a very interesting idea. Something similar comes up in my
AS/Xcaml application server when an HTTP resource which has already
computed a portion of the HTTP response realizes that it cannot continue
and must delegate the response to a different HTTP resource. An
exception is raised which is caught by the AS/Xcaml runtime system,
which aborts the current computation and restarts the computation of the
request by activating the HTTP resource whose URL is provided in the
exception body.

***

Back to your question, I suggest not to represent computations as thunks
but to use continuation passing style. This programming paradigm
provides enough flexibility to allow for different overflow thresholds
in different parts of the computation, without need for globals and side
effects (yes, you should worry about them, they are the bad guys).

exception Overflow

let grow_threshold old_value = ...

let compute threshold threshold_transformation computation =
  try
    computation (threshold_transformation threshold)
  with Overflow ->
    let new_threshold = grow_threshold threshold in
      computation (threshold_transformation new_threshold)

Recursive computations occur through the compute driver, which also
receives a threshold_transformation function determining the value of
the threshold for the next computation. If you want your code to be
parametric with respect to the threshold growing policy, you might want
to modify the code as follows (-rectypes required!)

let rec compute grow_threshold = fun
  threshold
  threshold_transformation
  computation
->
  try
    computation
      (compute grow_threshold)
      (threshold_transformation threshold)
  with Overflow ->
    let new_threshold = grow_threshold threshold in
      computation
        (compute grow_threshold)
        (threshold_transformation new_threshold)


In this case the driver for recursive computations is no longer the
global compute function but the first parameter of the computation function.

Alex

-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Restarting a piece of code

[Alex Baretta]

Andrej Bauer wrote:

> 
> Can we avoid having to pass treshold around directly? You can imagine
> that users won't be too thrilled about this sort of thing.

I think you can. See arithmetic functions as building blocks for
computations---rather than computations themselves---which are
parametric with respect to the threshold value.

let unit_expression _ = assert false
let imaginary_unit_expression _ = assert false
let addition_expression _ = assert false
let negative_expression _ = assert false
let multiplication_expression _ = assert false
let inverse_expression _ = assert false
let exponential_expression _ = assert false
let logarithm_expression _ = assert false

exception Overflow

let rec compute grow_threshold threshold_transformation = fun
  computation
  threshold
->
  try
    computation
      (compute grow_threshold)
      (threshold_transformation threshold)
  with Overflow ->
    let new_threshold = grow_threshold threshold in
      computation
        (compute grow_threshold)
        (threshold_transformation new_threshold)

(* Here we define the primitive operations of the algebraic structure *)
(* We don't mind if the primitive operations are a little heavy, so   *)
(* long as it is easy to compose them to form complex computations.   *)

let one = fun compute threshold -> unit_expression threshold
let i = fun compute threshold -> imaginary_unit_expression threshold

let add x y = fun compute threshold ->
  let x' = compute x threshold in
  let y' = compute y threshold in
    addition_expression x y threshold

let neg x = fun compute threshold ->
  let x' = compute x threshold in
    negative_expression x threshold

let mul x y = fun compute threshold ->
  let x' = compute x threshold in
  let y' = compute y threshold in
    multiplication_expression x y threshold

let inv x = fun compute threshold ->
  let x' = compute x threshold in
    inverse_expression x threshold

let exp x = fun compute threshold ->
  let x' = compute x threshold in
    exponential_expression x threshold

let log x = fun compute threshold ->
  let x' = compute x threshold in
    logarithm_expression x threshold

(* Let's say these are all the basic computations we need. Now we can *)
(* start building more computations on top of these.                  *)

let sub x y = add x (neg y)
let div x y = mul x (inv y)
let pow x y = exp (mul (log x) y)
let root x y = exp (mul (log x) (inv y))
let two = add one one
let twoi = add i i
let cos x = div (add (exp (mul i x)) (exp (neg (mul i x)))) two
let sin x = div (sub (exp (mul i x)) (exp (neg (mul i x)))) twoi

> I sense monads. Or am I looking for dynamic binding?

You are looking for partial evaluation/multistage programming, but you
don't necessarily have to delve into MetaOcaml to solve your problem. As
you can see you can generate a homomorphism from the calculus of
imaginary numbers to the calculus of computations of imaginary numbers
which can be directly represented in Ocaml.

> Best regards,
> 
> Andrej
> 


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>