[MLton] Optional Arguments and FRU

[Vesa Karvonen]

Quoting Stephen Weeks <sweeks@sweeks.com>:
[...]
> >    val z = f' 1 [set#a 1.0, set#c 2, set#b 1.0]

> [...] Unfortunately, there is no way MLton is going to simplify that
> away because it doesn't optimize much insider recursive data structures.
[...]
> we can use composition of updates to avoid the list construction.
> 
>   val z = f' 1 (set#a 1.0 o set#c 2 o set#b 1.0)
> 
> I'm more confident that MLton will do the right thing here, although
> not as confident as with the CPS approach. [...]

Interesting. I actually first used composition, just like you do, but I
found the list syntax more "appealing" (for lack of a better word). I'm not
intimately familiar with the optimizations that MLton does, so it is good
to know that CPS and/or composition may be preferable performance wise.

> Also, I'm not super happy with the name "set" or "o".  To me, it would be
> more readable to use, say, "opt" and "&"
[...]
>   val z = f' 1 (opt#a 1.0 & opt#c 2 & opt#b 1.0)

Yes, I agree. That is nicer. But I probably wouldn't define an infix &
operator just for this purpose, because the Basis Library already provides
the infix o. Well, I would consider it twice if/when the use of default
arguments would be an enabling technique for an important library (which
is not unimaginable as Matthew points out in his original email on OA:
  http://mlton.org/pipermail/mlton/2002-March/021574.html ).

> Actually, our tick (`) notation wasn't so bad either, except that one
> must put a space between the tick and the hash to keep it from being
> treated as one symbol
> 
>   val z = f' 1 (` #a 1.0 & ` #c 2 & ` #b 1.0)
> 
> Seeing the similarity of this and what's currently on the OA page
> makes it clear that the main simplification of your proposal comes not
> so much from the use of FRU techniques, but rather from the
> elimination of the variable number of arguments, which requires the
> CPS and $ at the end.

Actually, the main reduction in implementation complexity does come from
the use of FRU. If you look at the OA page, you can see that it uses
O(n*n) code to implement the FRU operations (look at the body of the functor
MakeF). The use of the FRU technique reduces the complexity to O(n) with
a lower constant factor.

However, you are right in that replacing CPS with composition/list+fold
does also somewhat simplify the technique. The need for a terminator
($) vanishes, which is a minor technical advantage. The difference in
implementation complexity is not big, because the CPS machinery can be
factored into a reusable module (as is done on the OA page).

I guess what I'm really after here is to find a way to minimize the cost
of providing functions with optional arguments with reasonably concise
syntax. In other words, to make optional arguments attractive to library
authors. It seems that the use of records to pass named arguments allows
one to build support for optional arguments outside of a library and it
is probably advisable when a function needs many arguments. This reminds
me that the Basis Library uses options in at least one place:

  http://www.standardml.org/Basis/string.html#SIG:STRING.extract:VAL .

> I wonder if in practice, since set/opt is specific to f' anyways, it
> might be reasonable to name each of the optional argument updaters, so
> that one could write
> 
>   val z = f' 10 (a 1.0 & c 2 & b 1.0)

Although it is notationally nice, I think that the extra code needed to
implement it may not always be worth it. It might also suffer from the
fact that the update functions (a, b and c) are specific to a particular
argument record. I think that it is likely to be the case that many
functions (in a library) would have optional arguments by the same name,
but not always the same set of optional arguments.

-Vesa Karvonen