[MLton] HOL's Moscow ML implementation, and pushing MLton to emulate it

[Stephen Weeks]

> My memory is a bit sketchy, but as I recall Shao's approach assuems
> a native unboxed/host representation.

Sort of.  But he imposes a *severe* restriction on what host
representations are allowed, that in particular rules out many
representations that MLton uses.

> For example here's how the paritally unboxed approach differs from
> the fully boxed approach.

Right, and your example shows one instance of the problem: the
approach restricts lists to use a single-word representation for list
elements so that any list can be coerced in constant time to boxed
form.

> In the partially boxed approach each boxing or unboxing operation is
> constant time, because we only box the toplevel structure.

Right, but this is only achieved because of the restriction.

Don't get me wrong, we may need to change the host types to make this
all work, and if we do, partial boxing may be the way to go (although
I'd just go for full boxing to start).  But in the spirit of MLton's
aggressive compilation strategy, I'd like to first exhaust all
possibilities that use MLton's native representations.