Re: [Caml-list] typing a value cache

[Virgile Prevosto <virgile.prevosto@m4x.org>]

Le 30.11.2004, à 09:59:57, Christophe DEHLINGER a écrit:
> Now things get tricky: the body of any function may change during 
> execution (so I actually deal with function references rather than 
> functions). When this happens, the cache entries corresponding to the 
> function calls that used this function during evaluation become 
> obsolete, and thus should be removed from the cache. So - and this is 
> the hard part typing-wise - this means that the cache must somehow 
> record the dependencies between function calls.
> 
> I have found (I think) two ways to do that:
> - defining  notype_cache and no_type_cache_key, two class types with 
> methods to handle addition of a dependency in a cache. They are 
> inherited respectively by ('a,'b) cache and ('a,'b) cache_key. Each 
> function of type 'a->'b in the collection has its own ('a,'b) cache. 
> Seems to work fine, but notype_cache_key object instances cannot be 

Hello,
I'm not sure I really understand your solution, but I'd say that a
way to handle this problem would be to store together with a
given cached value the actions needed to remove the other cached values
that depend on it (for instance under the form of unit -> unit
functions). Then, each time you're about to erase a value, you perform
the corresponding actions. If they are correctly coded, you should then
be able to recursively remove the obsolete cached values, and only them.

I include at the bottom of this message a small module which seems to do
the trick (at least on your 3-functions example), but is of course
absolutely not tested on a large set of functions.

Hope this might help.
-- 
E tutto per oggi, a la prossima volta
Virgile
------------------------------------------------------------------------
module Cache:
sig
  type ('a, 'b) t
  val create: ('a -> 'b) -> ('a, 'b) t
  val app: ('a, 'b) t -> 'a -> 'b
  val modify: ('a, 'b) t -> ('a -> 'b) -> unit
end = 
struct
  type ('a, 'b) t = { 
    mutable f: 'a -> 'b; (* the function's body. *)
    cache: ('a, 'b * (unit -> unit) list) Hashtbl.t
      (* cached result, with the list of erasures to perform if the
         value becomes inaccurate. *)
  }

  let create f = { f = f; cache = Hashtbl.create 13}

  let cont = ref None (* how to remove the cached result that performs
                         the current call (None = call from a
                         non-monitored function).*)

  let remove cache x = (* remove all dependencies wrt a given value. *)
    try 
      let (_,l) = Hashtbl.find cache x in
        List.iter (fun x -> x ()) l;
        Hashtbl.remove cache x
    with Not_found -> () 

  let app f x =
    try 
      (let (res, dep) = Hashtbl.find f.cache x in
         print_endline "cached";
         match !cont with
             None -> res
           | Some cont -> 
               Hashtbl.replace f.cache x (res, cont::dep);
               res)
    with Not_found ->
      let prec_cont = !cont in
        cont := Some (fun () -> remove f.cache x);
        let res = f.f x in
        let dep = match prec_cont with
            None -> []
          | Some n -> [n]
        in 
          Hashtbl.add f.cache x (res,dep);
          cont := prec_cont;
          res

  let modify f new_f = 
    f.f <- new_f;
    Hashtbl.iter (fun _ -> fun (_,l) -> List.iter (fun x -> x()) l)
                  f.cache;
    Hashtbl.clear f.cache
end                  

let f = Cache.create (fun n -> n > 0);;

let g = Cache.create 
          (fun b -> if b then "yo" else 
                    string_of_bool (Cache.app f 5));;

let h = Cache.create (fun () -> String.length (Cache.app g false));;

Cache.app h ();;

Cache.app g false;;

Cache.app f 5;;

Cache.app g true;;

Cache.modify f (fun n -> n = 0);;

Cache.app f 5;; (* recomputed. *)

Cache.app g true;; (* still cached. *)

Cache.app h ();;
-----------------------------------------------------------------------