English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
[Caml-list] file close bug?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-06-28 (01:10)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] file close bug?
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