[
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: | 2004-11-30 (09:00) |
From: | Christophe DEHLINGER <christophe.dehlinger@i...> |
Subject: | typing a value cache |
Hi all, I'm trying to find an elegant way to build a data structure. My program must deal with a large collection (1000+) of unary functions. The collection should be dynamically expandable, but I may have it be constant and known at compile time if I have no other choice. These functions may use other functions of the collection in their body. As the exact same function calls will very often be made during execution, I wanted to build a cache structure in which frequently asked values would be stored. 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. Simple example, with 3 functions f:int -> bool, g:bool->string, h:unit->int Initially : . f n = n>0 . g b = if b then "yo" else (string_of_bool (f 5)) . h () = String.length (g false) Then my program then tries to evaluate h () for some purpose. The following entries are then added to the cache: 1) f : 5 -> true 2) g : false -> "true" 3) h : () -> 4 It then evaluates g true. The following entry is then added to the cache: 4) g : true -> "yo" Then, if the body of f is changed to something else (e.g. (=) 0), entries 1, 2 and 3 should be removed from the cache, but not 4. My question is : how do I build this cache thing in ocaml ? Is there a way to avoid coding type information ? 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 compared (by value) in general, so dependencies cannot be removed (as it involves parsing a list of dependencies (of type no_type_cache_key list) and trying to find a particular notype_cache_key value in it). This can be worked around with some info duplication, but all in all although this approach seems to work, it is definitely unwieldy and has shortcomings - too ugly to tell. Suffice to say it involves camlp4. So, have I missed the simple-and-obvious solution to this problem ? Cheers, Christophe __________________________ Ce message (et toutes ses pièces jointes éventuelles) est confidentiel et établi à l'intention exclusive de ses destinataires. Toute utilisation de ce message non conforme à sa destination, toute diffusion ou toute publication, totale ou partielle, est interdite, sauf autorisation expresse. L'IFP décline toute responsabilité au titre de ce message. This message and any attachments (the message) are confidential and intended solely for the addressees. Any unauthorised use or dissemination is prohibited. IFP should not be liable for this message. Visitez notre site Web / Visit our web site : http://www.ifp.fr __________________________