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

Michael Norrish Michael Norrish <Michael.Norrish@nicta.com.au>
Fri, 7 Jul 2006 09:38:53 +1000


Matthew Fluet writes:

> [fibonacci example]
 
> 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.

Thanks for the responses everyone.  I certainly won't do any more
manual conversion to a tail-recursive style for these functions given
that MLton will resize the stack if necessary.  None of these
functions are likely to have constant-space versions because they are
tree traversals.  This means that the conversion to tail-recursive
forms requires building a list on the heap to emulate the stack
anyway.

Michael.