[MLton] Fixed points in SML

[Vesa Karvonen]

[Continuing an old discussion:
   http://mlton.org/pipermail/mlton/2006-August/029041.html]

Stephen Weeks:
> Wesley W. Terpstra:
> > I am no Haskell programmer, but
> >    val Y : ((unit -> 'a) -> 'a) -> 'a = fn g => (fn x => x (T x)) (fn  
> > (T x) => fn () => g (x (T x))) ()
> > seems to do much the same thing that a lazy language would.
> 
> That's my favorite version.  One could do it with ref cells too.
> 
>    val Y: ((unit -> 'a) -> 'a) -> 'a =
>       fn g =>
>       let
>          val r = ref (fn () => raise Fail "Y")
>          val a = g (fn () => !r ())
>          val () = r := (fn () => a)
>       in
>          a
>       end
> 
>   val fact = Y (fn fact => fn n => if n=0 then 1 else n * fact () (n-1))
>   val 120 = fact 5

I'm trying to better understand the relative weaknesses and strengths of
this Y combinator and the fixpoint framework described on the page
  http://mlton.org/Fixpoints .

Consider the following code pattern:

   val x = Y (fn x => (... (x ()) ...))

For the above to make sense, the expression (x ()) must be in a position
that isn't evaluated when the surrounding expression (... (x ()) ...) is
evaluated.

For example, suppose you have defined a type of lazy streams.  You might
naively think that you can create an infinite stream of ones as

   val ones = Y (fn ones => Stream.cons (1, (ones ())))

where

   val cons : 'a * 'a Stream.t -> 'a Stream.t

but this doesn't work, because (ones ()) is evaluated too early.  To make
it work you could use a constructor function with the spec

   val lazy : (unit -> 'a Stream.t) -> 'a Stream.t

and then you could write

   val ones = Y (fn ones => Stream.cons (1, Stream.lazy ones))

and you'd get what you wanted.

Indeed, it seems that the above Y combinator only works for types t for
which a constructor function with the spec

  val lazy : (unit -> t) -> t

can be provided.  One question is whether such a lazy constructor function
can always be provided and at what cost (performance and otherwise).

For lazy constructions (like the lazy stream above) that already use a
combination of thunking and refs there seems to be little or no extra cost
(extra stuff is eliminated as the thunk is evaluated the first time and the
ref cell is updated (inside the stream/promise implementation) to point
directly to the resulting value).

For something like the Compare function implementation (or any function)
described in

   http://mlton.org/pipermail/mlton-user/2006-August/000907.html

it would mean extra thunk/apply for each recursion step while processing
values of recursive types.

Other than the performance costs, using this Y combinator one loses the
ability to pattern match.  This becomes significant when one wants to
compute fixpoints of products.  For example, a translation of the isEven &
isOdd example from the http://mlton.org/Fixpoints page to use the Y
combinator + lazy constructor approach could look something like this

val (isEven, isOdd) =
    Y (fn th =>
          (fn 0w0 => true
            | 0w1 => false
            | n => #2 (th ()) (n-0w1),
           fn 0w0 => false
            | 0w1 => true
            | n => #1 (th ()) (n-0w1)))

The above suggest an extra record selection per iteration (in addition to
the extra thunk/apply) when computing fixpoints of products.  (This probably
doesn't create extra space leaks.)

For something like the Dummy value implementation described in the same
post as the Compare function the cost would be extra thunking throughout
and loss of sharing.  Indeed, one could argue that it is impossible to
provide a lazy constructor for Dummy (without changing the semantics of
Dummy).  In the case of Dummy this isn't very serious.  Can you think of
cases where it would be?

Does MLton eliminate the (potential) performance costs?
Thoughts?

--Vesa Karvonen