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?
Asked
Active
Viewed 300 times
2
-
1One thing to keep in mind is the issue of mutual recursion. – rwong Apr 05 '15 at 21:24
-
Only in-so-far as functional languages actually provide/guarantee TCO. – Telastyn Apr 05 '15 at 21:30
1 Answers
7
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.
