2 ms·
Is tail call elimination particularly problematic? With Erlang, recursion is effectively the only looping construct, so it becomes second nature to make everyt
by macintux 6y ago
Is tail call elimination particularly problematic?
With Erlang, recursion is effectively the only looping construct, so it becomes second nature to make everything end with a tail call.
- wyager 6y agoTail call elimination doesn't let you do guarded (co-)recursion. For example, in a strict language you can't have a corecursively defined list like loop a b = a : loop b (a + b) fibs = loop 0 1 Because tail call elimination can't do anything about the first case.
- yawaramin 6y agoThis example actually does not have a tail-recursive call, so if you mean that a non-tail recursive call is not stack safe in a strict language, that is correct, yes.
- dwohnitmok 6y agoI think wyager's point is that you can extract individual Fibonacci numbers from fibs rather than realizing the infinite list immediately.
- wyager 6y agoRight - my point is that tail call elimination doesn’t help you with guarded corecursion, which lazy languages handle just fine. Guarded corecursion represents a huge set of programs it’s useful to be able to evaluate.
- slaymaker1907 6y agoBoth function calls are in tail position. This is what actually matters (along with the ABI return type matching for runtimes where that matters).
- dwohnitmok 6y ago'loop' is not in a tail position. The last operation is the list cons. It can be optimized with TCO modulo cons but that would just make it hang/exhaust heap rather than stack overflow in a strict language.
- yawaramin 6y agoTail call elimination works fine in OCaml, same as in Erlang.
- c-cube 6y agoNot all recursion is tail recursion. If you traverse trees you either deal with your bounded stack somehow (or ignore the problem) ; derecursify by hand, which is a nightmare ; or refactor to continuation passing style. There are options but none is simple and elegant.