[MLton] MLton's adherence to the Definition of SML

[Stephen Weeks]

Here's a few thoughts on our philosophy regarding MLton's adherence to
the Definition of SML.

We can consider three ways that one might deviate from the Definition.

1. restrictions, in which one could disallowing something that is
   allowed by the definition.  An example is SML/NJ's "dependency
   cycle in instantiate" error, which disallows some signatures.
2. differences, in which a construct that is specified by the
   definition is interpreted differently.  An example is SML/NJ's
   handling of withtype.
3. extensions, in which a construct not described in or disallowed by
   the definition is accepted.  An example is SML/NJ's vector
   literals.

Differences are the worst of the three, since code may silently behave
differently when moving from compiler to compiler.  There is also the
fact that the Definition will provide an inaccurate description of the
behavior.  Other than bugs, the last time that MLton had a difference
was when we didn't raise the Overflow exception on integer operations.
And, we still have this difference available via the -detect-overflow
flag.  Another example is the -safe flag.

Restrictions are pretty bad, especially when the boundaries aren't
clearly documented (as with SML/NJ's "dependency cycle in
instantiate").  It makes porting code from other SML compilers more
difficult.  We do have one restriction in MLton that I can think of:
-sequence-unit true, which disallows certain programs that are allowed
by the definition.  I guess this means that we think that a
restriction governed by a flag is OK, at least if it has a simple
explanation.

Extensions are the least bad of the three.  Examples of extensions in
MLton are _export, _import, and the MLton structure.

Looking back at the above, it's clear that we do allow differences,
restrictions, and extensions into MLton.  So, the question is then
what principles do we use to decide when to do so.  For differences,
we have been driven by pragmatism, adding a difference only when
performance compels us to.  Fortunately, all our differences are now
off by default, and always governed by a flag.  I could imagine
introducing differences in the future for similar reasons, again
always governed by a flag with the default being no difference.

Our one restriction is driven by the pragmatism of helping users find
bugs.  Again, it is governed by a flag, with the default being off.
And again, I could imagine introducing restrictions in the future,
with similar reasons, controls, and defaults.

The main issue seems to be with extensions (both language and
library), so that's what I'm going to talk about for the rest of this
note.  Here are some potential benefits of adding an extension to
MLton.

* easier to port code that uses SML/NJ extensions to MLton
* ability to do something that is impossible without the extension
* cleaner code and more effective programming
* lock-in users to MLton

And here are some potential drawbacks.

* uses MLton-developer time
* increased compiler complexity
* lack of clear documentation and semantics
* difficult to port MLton programs to other compilers
* balkanizes the already small SML community
* the language MLton compiles changes over time
* perception/reality that MLton is not a stable platform for development

There is a range in complexity of the various extensions one might
add.

* low (e.g. vector literals)
* medium (e.g. or patterns)
* high (e.g. higher-order functors)

As the complexity of an extension increases, the drawbacks of
developer time, compiler complexity, and unclear semantics increase.
Increased MLton-developer time can be mitigated (but not eliminated)
if the extension is a patch from elsewhere, but that doesn't address
the other issues.

One potential problem with extensions is if a user unwittingly uses
them, and hence unknowingly sacrifices future portability.  Making it
obvious when an extension is an extension, either with a flag, or an
underscore, or something else, sufficiently addresses this problem.
We have certainly done this to mitigate this drawback of our
extensions.

Looking at the extensions we have accepted so far, they certainly
suffer from all of the drawbacks that I mentioned, and they certainly
have been on the high end of the complexity scale.  So why do we
accept them?  What I see in common is that all of them let us do
something that is *impossible* to do in the language without the
extension.  The Definition of SML has no FFI, so if one wants on in
MLton, the language must be extended.  Similarly, the Definition of
SML and the Basis Library do not have threads, so if one wants threads
in MLton, the library must be extended.

So, that is at least one extension benefit that we allow to override
all the other drawbacks.  I guess it could be argued that the mlb
extension doesn't quite meet this benefit.  But it's pretty close --
since without mlbs (or somesuch) it is impossible to deliver packaged
libraries and have a hope of users using them without name clashes.
At the least mlbs rank very highly on the more effective programming
and cleaner code benefit.  Also, we've done a good job of addressing
the lack of semantics drawback, something that hasn't been done
sufficiently to my eyes for or patterns, higher-order functors, and a
number of other SML/NJ extensions.

Getting the semantics right is one reason why we've been more willing
to make library extensions than language extensions.  Because there is
already the Definition of SML, a language extension has a very high
standard to live up to in order not to lower the value of the entire
definition.  On the other hand, since the basis library is informally
specified, adding another informally specified library doesn't hurt so
much.  Another difference between library extensions and language
extensions is that library extensions are mostly implemented outside
the compiler, and are hence presumably more accessible to non MLton
experts.

As to the the extensions specifically targeted at improving
portability from SML/NJ to MLton, that is typically their main benefit
-- that is, they don't make something new possible, and they don't
make a significant (to my eyes) improvement to programmer
productivity.  And, as I mentioned earlier, they often don't address
the semantics issue well enough.  Finally, I'm not convinced that the
potential gain in terms of an increased SML code base is really all
that great.  To point to three ports of code from SML/NJ to MLton, we
have: the SML/NJ library, HOL (over 100K lines), and SML.NET (over 80K
lines), of which the latter two are quite recent.  So, it doesn't seem
that the lack of extensions in MLton is all that serious stumbling
block.  I'm not saying it's not a hurdle, just that it is one of many
issues in portability, and there are lots of benefits to using MLton,
so it's not a deal-breaker.  So, should we spend time and effort on
getting those last few bits of SML/NJ code out there, or should we
spend it on ...

This brings me to my last point of this mail, and also a start to my
thoughts on Matthew's question of what MLton strives to be.  I would
like to grow MLton's user community, and so I like to make
improvements that I think will accomplish that.  There is a lot more
room for growth by grabbing a very small fraction of the non-SML world
than by grabbing even all of the SML/NJ world.  I realize that one can
work on both, but in addition to the ever-present developer-time
tradeoff, I feel that the last two drawbacks I mentioned about
presenting a stable development environment are an important component
of convincing non-SML people to even try MLton.  There is an important
distinction to consider between doing things that help current users
(which adding extensions no doubt would do) and doing things to
attract new users.  I believe that making extensions doesn't offer a
lot of bang for the buck in this, unless they let one do what was
impossible.

In summary, we do allow deviations to the language/library in MLton.
But it has been quite uncommon, and we are very conservative in
over-estimating the drawbacks and under-estimating the benefits.  So,
so far, it only happens when the benefits are clearly huge (_import,
MLton.Thread) or the drawbacks are clearly small (-sequence-unit).
Unfortunately, not such a clear principle :-), but there are a lot of
factors in play.  Hopefully the discussion on what MLton strives to be
will shed more light on things.  More on that tomorrow.