From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 0B182BC2F for ; Tue, 30 Nov 2004 10:00:17 +0100 (CET) Received: from irsun282.ifp.fr (ns1.ifp.fr [156.118.220.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id iAU90GJ7009452 for ; Tue, 30 Nov 2004 10:00:16 +0100 Received: from smtp.ifp.fr by irsun282.ifp.fr (V35.12) with ESMTP X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4927.1200 Received: from irnts70 ([156.118.220.36]) by irnts70 with Microsoft SMTPSVC(5.0.2195.6713); Tue, 30 Nov 2004 10:01:26 +0100 Received: From irsun165.ifp.fr ([156.118.22.211]) by irnts70 (WebShield SMTP v4.5 MR1a P0803.345); id 1101805283234; Tue, 30 Nov 2004 10:01:23 +0100 Received: from [156.118.21.21] (irlin234 [156.118.21.21]) by irsun165.ifp.fr (8.8.5/8.8.5) with ESMTP id JAA13900 for ; Tue, 30 Nov 2004 09:59:57 +0100 (MET) Message-ID: <41AC368D.8040808@ifp.fr> Date: Tue, 30 Nov 2004 09:59:57 +0100 From: Christophe DEHLINGER User-Agent: Mozilla Thunderbird 0.8 (X11/20040913) X-Accept-Language: en-us, en MIME-Version: 1.0 To: caml-list@yquem.inria.fr Subject: typing a value cache Content-Type: text/plain; charset="ISO-8859-1"; format=flowed Content-Transfer-Encoding: quoted-printable X-OriginalArrivalTime: 30 Nov 2004 09:01:26.0796 (UTC) FILETIME=[2C8E2CC0:01C4D6BB] X-Miltered: at concorde with ID 41AC36A0.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; christophe:01 christophe:01 dependencies:01 bool:01 unit-:01 bool:01 ocaml:01 'a-:01 dependencies:01 parsing:01 cheers:01 eventuelles:01 autorisation:01 confidentiel:98 expresse:98 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.0 X-Spam-Level: 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=20 constant and known at compile time if I have no other choice. These=20 functions may use other functions of the collection in their body. As the exact same function calls will very often be made during=20 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=20 execution (so I actually deal with function references rather than=20 functions). When this happens, the cache entries corresponding to the=20 function calls that used this function during evaluation become=20 obsolete, and thus should be removed from the cache. So - and this is=20 the hard part typing-wise - this means that the cache must somehow=20 record the dependencies between function calls. Simple example, with 3 functions f:int -> bool, g:bool->string, = h:unit->int Initially : . f n =3D n>0 . g b =3D if b then "yo" else (string_of_bool (f 5)) . h () =3D String.length (g false) Then my program then tries to evaluate h () for some purpose. The=20 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. (=3D) 0),=20 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=20 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=20 methods to handle addition of a dependency in a cache. They are=20 inherited respectively by ('a,'b) cache and ('a,'b) cache_key. Each=20 function of type 'a->'b in the collection has its own ('a,'b) cache.=20 Seems to work fine, but notype_cache_key object instances cannot be=20 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=20 be worked around with some info duplication, but all in all although=20 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=E8ces jointes =E9ventuelles) est = confidentiel et =E9tabli =E0 l'intention exclusive de ses destinataires. = Toute utilisation de ce message non conforme =E0 sa destination, toute = diffusion ou toute publication, totale ou partielle, est interdite, sauf = autorisation expresse. L'IFP d=E9cline toute responsabilit=E9 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 __________________________