[MLton-user] Destructive update

Joe Hurd joe.hurd@comlab.ox.ac.uk
Wed, 8 Feb 2006 15:33:50 +0000


Hi Matthew,

thanks for your reply. I'm pleased that I had the correct syntax for
overriding the ram-slop parameter, and I assume that setting
fixed-heap at runtime will also override the compiled-in ram-slop.

> That's a fairly common programming style, using purely functional data
> structures.  It does happen to play into the live ratio discussed above:
> using such data structures tends to produce a lot of garbage, because only
> the latest instance of the dictionary is live.  (On the other hand, this
> is exactly the scenario that supports the generational hypothesis.)

Yes, I do tend to generate a lot of garbage, as was already remarked
upon in my model-elimination contribution to the benchmark suite.

> The imperative features of ML can be put to good use to destructively
> update a data structure.  One of the most commonly used data structures in
> the MLton compiler is a mutable HashSet:
>
> http://mlton.org/cgi-bin/viewsvn.cgi/mlton/trunk/lib/mlton/basic/hash-set.sig?rev=4014

Thanks for pointing me to this: it has very nearly the signature I
need, plus I'm sure the operations are well optimized for MLton.
However, it has three drawbacks for me:

1. I've been defining ('a * 'a -> order) comparison functions for all
my data structures, and it would be a little painful to go back and
define ('a -> int) hash functions for all of them. However, you've put
the idea into my head that it might be a LOT more efficient to do so,
and that's the kind of thought that keeps nagging me until I do it.
(Particularly when summer approaches and I really don't need my
computer to heat up my study for 10 hours a day.)

2. One advantage of using comparison functions instead of hash
functions is that the

foldl : ('a * 'b * 'c -> 'c) -> 'c -> ('a,'b) dict -> 'c

can traverse the elements in order, which is a behaviour that I
sometimes rely on.

3. This is the really big one: I'm a very lazy programmer, and don't
want to have to think about which of my uses of dictionaries are safe
to be replaced with destructive update versions. Especially when a
Sufficiently Clever Compiler (that mythical beast) could figure it out
for itself :-)

Thanks again for your reply,

Joe