Version française
Home     About     Download     Resources     Contact us    
Browse thread
Restarting a piece of code
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Andrej Bauer <Andrej.Bauer@a...>
Subject: Restarting a piece of code
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).