[MLton] flattening, via prefetching

[Stephen Weeks]

> As promised this is a short write up about my algorithm to flatten
> arbitrary nested tuples:

Thanks for sending this.  It made sense.

> The idea behind the algorithm is prefetching. Whenever a tuple is
> introduced, we keep around both representations: a flat and non
> flat.

Another approach to translation would be "lazy" (as opposed to your
"eager" approach).  That is, emit the tuples/selects at the point they
are needed.  I don't know which works better, or if there is some
hybrid that works best.

Another approach, the one I would have tried first, would be to insert
coercions locally, to convert between the original types and the
flattened types, introducing new variables for components and leaving
the types of flattened variables unchanged.  For example, if you have

  fun f (x: a * b) = e

where the annotation says flatten the "a * b", then translate this to

  fun f (x1: a, x2: b) = let val x = (x1, x2) in e end
  
Then the translation of e can assume that all variables (like x) from
the original program have their original types.  The shrinker will get
rid of all the redundant tuples followed by selects.  It feels to me
like your transformation, in keeping the prefetch information, might
be repeating some work that could be done by the shrinker.  Anyways,
the approaches are probably not equivalent, so this is really just a
third translation approach :-).