[MLton] it is necessary to manually make things tail-recursive?

Matthew Fluet fluet@cs.cornell.edu
Thu, 6 Jul 2006 14:57:07 -0400 (EDT)


> The tradeoff between tail style and nontail style is between
> heap-allocated closure records and stack-allocated stack frames.  Up
> to a small constant factor, the same amount of stuff will be allocated
> and live with both styles.  As Matthew said, MLton allocates the stack
> on the heap and doubles it as necessary, so the only way to blow out
> the stack is to run out of memory (unlike the ML Kit and Moscow ML).

I agree that the tradeoff between CPS-style and non-CPS-style 
implementations is between heap-allocated closure records and 
stack-allocated stack frames, but I wouldn't say that is the tradeoff 
between tail and non-tail functions in general.

For example:

fun fib_nt n =
   if n = 0 orelse n = 1
      then 1
      else fib_nt (n - 1) + fib_nt (n - 2)

fun fib_t' (n, a, b) =
   if n = 0
      then a
      else fib_t' (n - 1, b, a + b)
fun fib_t n = fib_t' (n, 1, 1)

Whether or not you CPS convert fib_nt, it will require more memory than 
fib_t.  And, fib_t will run _much_ faster than fib_nt.  So, in Michael's 
case, while MLton will handle deep recursion without problems, there maybe 
significant performance wins in finding constant-space functions. 
Benchmarking and profiling are the way to go.