1

I've heard some people in my university discuss the tail call optimisation in ML as if it were a special version tail call optimisation. Does the ML (SML/F#) implementations of tco in these languages differ substantially from the implementation in other languages, such as C++ and Haskell?

  • 1
    One thing to keep in mind is the issue of mutual recursion. – rwong Apr 5 '15 at 21:24
  • Only in-so-far as functional languages actually provide/guarantee TCO. – Telastyn Apr 5 '15 at 21:30
6

Does the ML (SML/F#) implementations of tco in these languages differ substantially from the implementation in other languages, such as C++ and Haskell?

Not as far as I know, no. The optimization of discarding the existing stack rather than saving off its current state (and possibly adjusting the execution pointer directly) on the last function call in the current stack is common across languages. There may be details, like since Haskell works lazily it might need additional steps, but the implementations do not differ substantially since the underlying assembly does not differ at all.

The difference is the level of guarantee provided by the language specification and/or the language implementation. For functional languages, there is very often a stronger guarantee (will always provide TCO, will provide TCO in cases of mutual recursion), since having an ever growing stack for certain common structures would make that language/implementation effectively useless. Non-functional languages often make no guarantee, or some weak guarantee (may supply TCO if we feel like it) since there are common alternatives that do not grow the stack.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.