4
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chris Dodd
    Feb 15 at 20:01

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
11
  • 4
    $\begingroup$ And Python defaults to 1,000 frames -- they really don't want to encourage recursive algorithms. $\endgroup$
    – Barmar
    Feb 16 at 22:38
  • $\begingroup$ 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. $\endgroup$ Feb 16 at 23:08
  • 2
    $\begingroup$ @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. $\endgroup$ Feb 16 at 23:41
  • $\begingroup$ I find your links lacking of clear information about Guarded Recursion, please give more resources. $\endgroup$
    – Delfin
    Feb 18 at 19:46
  • 3
    $\begingroup$ This answer is not correct. GHC implements tail calls. The Stack Overflow answer you link to does not say what you think it says. $\endgroup$
    – Alexis King
    Feb 18 at 23:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .