[MLton-user] Destructive update

[Matthew Fluet]

> 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.

Correct.

>> 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.

I don't think we've used any particularly MLton enhanced features in the 
hash sets.  It ought to be generally useful in other compilers, to the 
degree that it can be extracted from the rest of the MLton library.

And, I wasn't necessarily advocating that you use that particular data 
structure, but rather that implementing your dictionary in a similar 
manner (with your constraints of ordering function and in order 
traversals) would be feasible and potentially more efficient.

> 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 :-)

That is, of course, a different story.  A mutable data structure has very 
different semantics from a functional data structure; it is a useful 
property that the observable behavior of the data structures are the same 
when used in a single threaded manner.

BTW, it is useful to note that there are really two sub-problems here. 
One is to identify which instances of a data structure are used in a 
single threaded manner.  It is a separate problem to determine how to 
mutate such a single threaded data structure in place.  I know that the 
technology to determine the former is out there (with varying degrees of 
precision due to aliasing, escape analysis, etc.).  The second problem is 
a little less well understood, at least from the literature that I've 
observed.  For example, I don't think we know how to take Okasaki's purely 
functional red-black trees and systematically transform it into CLR's 
imperative red-black trees.  And it isn't clear that that would be a 
performance win.  So, like all optimizations, there is yet a third problem 
out there, which is to determine when it is heuristically profitable to 
apply a transformation.