Re: Ant: Re: Ant: Re: Ant: Re: Ant: Re: [Caml-list] Avoiding shared data

[skaller <skaller@users.sourceforge.net>]

On Tue, 2005-10-04 at 20:09 +0200, Martin Chabr wrote:

> > Mutable shared data is very useful: caching is
> > an obvious example where this is precisely what you
> > want.

> This sounds very interesting. Can you say a little
> more about it please?

Well others know more about techniques like HashConsing 
and memoisation than I do .. but basically it is sometimes
useful for a pure function which is expensive to evaluate,
to have a cache of results already computed.

For example, in Felix I have to do 'lookup' to bind
string names of functions to entries in the symbol table.

The lookup is very expensive for functions, because Felix
supports overloading, which means the argument type has
to be calculated, and unification against bound signatures
of candidates is used to select the most specialised matching
function.

the problem is that to bind the types required to do this
*also* requires lookup (and it can even be recursive).

So in the process of doing all this lookup, it would be nice
to cache the results so that the 'expensive' lookup is only
done once, and after that the cached value is used.

In fact I tried that using a Hashtbl .. but because the keys 
were complex, it turned out that polymorphic compare and hash
functions were actually *slower* than my nasty purely functional
lookup code.

However, I do cache the environments, and this save some
time: environments are created by a call like

	build_env (parent)

which follows the chain of parents to ground, gathering
all the symbols defined in each one (resulting in a list
of hashtables). This process isn't all that slow .. the
problem is that in a purely functional system with
random symbol lookups, it has to be done once for EVERY
lookup .. not just once when you do a lookup, since as
noted above doing a lookup can spawn a hundreds of other
lookups. So caching the 'environment' in which to do the
lookups was a good way to speed up the process, without
changing the functional style of the code.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net