# Effective Tail Call Optimization in Non strict functional languages

In functional programing languages it is normal to optimize forms like

factorial n = go n 1
where
go 0 acc = acc
go n acc = go (n - 1) (acc * n)


to loops removing the stack expansion in something called tail call optimization. This is Haskell syntax, but at the same time normally in any non strict call language it would be an easy optimization. Non-strict languages like Haskell have the problem in a naive implementation that the factorial code would behave in the following way:

1. go 5 1
2. go (5 - 1) (1 * 5)
3. go 4 (1 * 5)
4. go (4 - 1) (((1 * 5) * 4)
5. go 3 (((1 * 5) * 4)
6. go (3 - 1) (((1 * 5) * 4) * 3)
7. go 2 (((1 * 5) * 4) * 3)
8. go (2 - 1) ((((1 * 5) * 4) * 3) * 2)
9. go 1 ((((1 * 5) * 4) * 3) * 2)
10. go (1 - 1) (((((1 * 5) * 4) * 3) * 2) * 1)
11. go 0 (((((1 * 5) * 4) * 3) * 2) * 1)
12. (((((1 * 5) * 4) * 3) * 2) * 1)

This is because resolve the value of n is necessary to select the next call, but the resolution of acc is not yet required with non strict semantics.

Which obviously would make the use of tail call optimization pointless in such implementation. Then how does Haskell avoid this problem in his implementation of non-strictness, and how could I add it to my lazy language, so that Tail Call Optimization can coexists with non-strictness without become pointless?

• Bascially, use analysis and heuristics to determine when eager evaluation would (a) not change the semantics and (b) be more efficient. In this specific case, multiply with constant operands should be eagerly evaluated. Feb 15 at 20:01

Haskell has this exact issue (TCO may simply build a chain of thunks), but there are some ways Haskell makes it less of an issue:

## Strictness analysis

Haskell has a strictness analysis phase which should optimize the specific case of factorial by making the arithmetic eager.

As suggested by Chris Dodd, a smart compiler can use heuristics to eagerly reduce terms as long as it maintains semantics and improves performance. In side-effect-free languages like Haskell, "maintains semantics" simply means that eager evaluation doesn't cause non-termination.

The downside is that you will always have functions which could be optimized this way but aren't detected, due to the halting problem. Including functions which build up a chain of thunks in a non-strict language, but evaluate fine in a strict one, if the chain is but can't be proven to be finite or always fully reduced.

## Explicit strictness annotations

Haskell allows you to force evaluation of terms using ! and $! (up to weak-head-normal form; you can force nested terms using deepseq). You avoid the thunk build-up if you force the second argument of the recursive call in factorial, like so: factorial n = go n 1 where go 0 acc = acc go n acc = go (n - 1)$! acc * n


## Larger or unbounded stack

By default, Haskell's stack can resize itself up to a large fraction of total memory (one estimate is 80% of the heap). Even before this, GHCi's default stack used to be 512MB. For reference, C's default stack limit rarely exceeds 8MB, and JavaScript's varies from 10,000 to 65,000 frames in modern browsers (idk how much data each frame takes).

This severely reduces the chance that an improperly-optimized tail-recursive function will cause a stack overflow. Though it doesn't eliminate this possibility (one can imagine a massive computation implemented with tail recursion), and also doesn't address the inefficiency caused by the chain of thunks which get built up and subsequently destroyed.

• And Python defaults to 1,000 frames -- they really don't want to encourage recursive algorithms. Feb 16 at 22:38
• I vaguely remember maybe a discussion on LtU where a GHC dev explained how GHC has Proper Tail Calls as a side-effect of its evaluation without explicitly having TCO as a compiler optimization. But I can't remember where or when I saw that and what the precise mechanism was. Feb 16 at 23:08
• @Barmar: Indeed. Guido van Rossum has even said that implementations are not allowed to perform TCO, and any hypothetical implementation that does is not an implementation of Python. This is basically the opposite of Proper Tail Calls, where the language specification mandates that all implementations must perform TCO. Feb 16 at 23:41