From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id DAA23121; Mon, 28 Jun 2004 03:10:18 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id DAA23151 for ; Mon, 28 Jun 2004 03:10:17 +0200 (MET DST) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i5S1AESH022663 for ; Mon, 28 Jun 2004 03:10:16 +0200 Received: from [192.168.1.200] (ppp217-185.lns1.syd3.internode.on.net [203.122.217.185]) by smtp1.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i5S1AA4Y022616; Mon, 28 Jun 2004 10:40:11 +0930 (CST) Subject: Re: [Caml-list] file close bug? From: skaller Reply-To: skaller@users.sourceforge.net To: Jon Harrop Cc: caml-list In-Reply-To: <200406272115.39422.postmaster@jdh30.plus.com> References: <1088353277.32642.28.camel@pelican.wigram> <20040627190417.GA22473@force.stwing.upenn.edu> <1088365375.18587.15.camel@pelican.wigram> <200406272115.39422.postmaster@jdh30.plus.com> Content-Type: text/plain Message-Id: <1088385009.18587.47.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 28 Jun 2004 11:10:09 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 40DF6FF6.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 bug:01 sourceforge:01 2004:99 2004:99 bignums:01 marshalling:01 hashtable:01 nums:01 nums:01 hashed:01 bignum:01 marshalling:01 hashtable:01 annotated:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, 2004-06-28 at 06:15, Jon Harrop wrote: > On Sunday 27 June 2004 20:42, skaller wrote: > > ... > > I wrapped the bignums in a class just to get a comparable id. > > Now I can't marshal it :( > > Unless you're marshalling a hashtable of big nums, can you not just wrap the > big nums in a class temporarily while they're being hashed? No. The bignum represent integers in expressions. I'm marshalling the whole input parse tree in a single line as shown in the code I gave. The hashtable was mapping expressions to bound expressions (ones for which lookup is done annotated with a bound type) because that can be done multiple times .. and the algorithm is purely functional and doesn't record any partial results for subsequent evalulations. This complexity arises in Felix because it supports several advanced features: there's an open directive like Ocaml's except that there is no hiding or ordering, functions are overloaded, there is a typeof(e) term, everything is mutually recursive, and function returns and values have their types deduced. Polymorphism is also supported (everything is done in the presence of type variables some of which can be bound in a call by unification). Altogether that means the type of an expression may depend on almost arbitrary other pieces of code than itself, and so to bind and type it may require binding and typing those other pieces of code too .. but the result of those extra evaluation is simply lost at that time, and recalculated again when needed. Even binding recursively may not work where the current algorithm does, since for example to find the return type of a function only requires binding its signature and some of the return values (and not the other code in the function). Caching partial results is itself problematic since some types are recursive: Felix doesn't use fixpoint binder terms, only fixpoints of kind Fix n where n is the number of 'levels' up in the term structure the binder would be.. so some sub-terms are incomplete during construction and mustn't be cached. Lookup/binding accounts for 80% of all the compiler time, which is why I'm trying to optimise it. My guess is that the algorithm is exponential time: if everything was done only once it would clearly be linear. Almost all the time seems to be taken doing Hashtbl.find on integer keys, which I use to represent entities (binding just maps their names to integers or to Fix term for recursive types). Caching type terms seems to make a tiny difference, caching expressions actually stopped the compiler working altogether in one case (only) for an unknown reason. -- 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