Restarting a piece of code
 Andrej Bauer
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20050827 (14:45) 
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 (sideeffect 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).