[Caml-list] Lazy recomputing

[Caml-list] Lazy recomputing

[Hans Ole Rafaelsen]

Hi,

I have a hash table which contains values, of which some are dependent on 
other values in the table.  I store the contents as lazy values. The problem 
I'm having is that once a dependent value have been computed, it will not get 
recomputed when the values it depends on changes.

let _ =
  List.iter
    (fun (k,v) -> Hashtbl.add tbl k v)
    [
      ("a", lazy 1);
      ("c", lazy ((Lazy.force (Hashtbl.find tbl "b")) + (Lazy.force 
(Hashtbl.find tbl "a"))));
      ("b", lazy 4);
    ];;

# let _ = Lazy.force (Hashtbl.find tbl "b");;
- : int = 4
# let _ = Lazy.force (Hashtbl.find tbl "c");;
- : int = 5
# let _ = Hashtbl.replace tbl "b" (lazy 6);;
- : unit = ()
# let _ = Lazy.force (Hashtbl.find tbl "b");;
- : int = 6
# let _ = Lazy.force (Hashtbl.find tbl "c");;
- : int = 5
# 

Is there some trick to get it recomputed, other that keep a list of all 
dependent values, and "refresh" the table whenever some value is updated?
From the documentation of Lazy it does not seem that such behavior is 
supported.

-- 
Hans Ole Rafaelsen

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Lazy recomputing

[Thomas Fischbacher]

> Is there some trick to get it recomputed, other that keep a list of all 
> dependent values, and "refresh" the table whenever some value is updated?

This is not what the general concept of laziness is about.

You need something different.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Lazy recomputing

[skaller]

On Tue, 2004-06-01 at 21:43, Thomas Fischbacher wrote:
> > Is there some trick to get it recomputed, other that keep a list of all 
> > dependent values, and "refresh" the table whenever some value is updated?
> 
> This is not what the general concept of laziness is about.
> 
> You need something different.

What he actually needs is a generalisation: a partial evaluator.

In the actual example there is a way to make it work
if you know when you change key X which keys D1, D2, ..
depend on it: you just replace D1, D2 values with
fresh Lazy expressions that aren't yet forced,
next time they're accessed force will cause a recomputation.

I do not know if this is possible in the situation,
nor if the result will be efficient (but it should work :)

I guess Lazy.refresh function might fix this by killing
off the memoised value without having to actually replace
it (and also work in a functional context).

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Lazy recomputing

[Hans Ole Rafaelsen]

On Tuesday 01 June 2004 14:59, skaller wrote:
> On Tue, 2004-06-01 at 21:43, Thomas Fischbacher wrote:
> > > Is there some trick to get it recomputed, other that keep a list of all
> > > dependent values, and "refresh" the table whenever some value is
> > > updated?
> >
> > This is not what the general concept of laziness is about.
> >
> > You need something different.
>
> What he actually needs is a generalisation: a partial evaluator.

Thanks, that got me on the right track.  The values are stored as functions in 
the table.  That way they are not evaluated during initialization, and can be 
forced reevaluated when needed.  Have to make my own access functions.

let _ =
  List.iter
    (fun (k,v) -> Hashtbl.add tbl k v)
    [
      ("a", fun () ->  1);
      ("c", fun () -> ((Hashtbl.find tbl "b") ()) + ((Hashtbl.find tbl "a") 
()));
      ("b", fun () -> 4);
    ]
let find tbl k =
  Hashtbl.find tbl k ()

let replace tbl k v =
  Hashtbl.replace tbl k (fun () -> v)

# let _ = find tbl "c";;
- : int = 5
# let _ = replace tbl "a" 7;;
- : unit = ()
# let _ = find tbl "c";;
- : int = 11
# 

-- 
Hans Ole

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Lazy recomputing

[skaller]

On Wed, 2004-06-02 at 01:22, Hans Ole Rafaelsen wrote:
> let _ =
>   List.iter
>     (fun (k,v) -> Hashtbl.add tbl k v)
>     [
>       ("a", fun () ->  1);
>       ("c", fun () -> ((Hashtbl.find tbl "b") ()) + ((Hashtbl.find tbl "a") 
> ()));
>       ("b", fun () -> 4);
>     ]

Of course, this will recompute the same result needlessly
to make sure it also computes the new result when needed.
Also the functions are bound to a particular hashtble,
which isn't so nice: might be nicer to write:

 fun tbl -> find tbl "b" + find tbl "a"

and 

let eval tbl key = find tbl key tbl;;
let tbl = create 97;;
let eval_tbl key = eval tbl key;;




-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners