typing a value cache

[Christophe DEHLINGER <christophe.dehlinger@ifp.fr>]

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
__________________________