<p>In functional programing languages it is normal to optimize forms like</p>
<pre class="lang-hs prettyprint-override"><code>factorial n = go n 1
   where
       go 0 acc = acc
       go n acc = go (n - 1) (acc * n)
</code></pre>
<p>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:</p>
<ol>
<li><code>go 5 1</code></li>
<li><code>go (5 - 1) (1 * 5)</code></li>
<li><code>go 4 (1 * 5)</code></li>
<li><code>go (4 - 1) (((1 * 5) * 4)</code></li>
<li><code>go 3 (((1 * 5) * 4)</code></li>
<li><code>go (3 - 1) (((1 * 5) * 4) * 3)</code></li>
<li><code>go 2 (((1 * 5) * 4) * 3)</code></li>
<li><code>go (2 - 1) ((((1 * 5) * 4) * 3) * 2)</code></li>
<li><code>go 1 ((((1 * 5) * 4) * 3) * 2)</code></li>
<li><code>go (1 - 1) (((((1 * 5) * 4) * 3) * 2) * 1)</code></li>
<li><code>go 0 (((((1 * 5) * 4) * 3) * 2) * 1)</code></li>
<li><code>(((((1 * 5) * 4) * 3) * 2) * 1)</code></li>
</ol>
<p>This is because resolve the value of <code>n</code> is necessary to select the next call, but the resolution of <code>acc</code> is not yet required with non strict semantics.</p>
<p>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?</p>

<haskell><tail-call-optimization>
Effective Tail Call Optimization in Non strict functional languages
CC BY-SA 4.0
2024-02-15T20:01:24.257Z
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.
Chris Dodd
<p>Haskell <a href="https://stackoverflow.com/a/13052612">has this exact issue (TCO may simply build a chain of thunks)</a>, but there are some ways Haskell makes it less of an issue:</p>
<h2>Strictness analysis</h2>
<p>Haskell has a <a href="https://wiki.haskell.org/Performance/Strictness#Strictness_analysis" rel="nofollow noreferrer">strictness analysis phase</a> which should optimize the specific case of <code>factorial</code> by making the arithmetic eager.</p>
<p>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, &quot;maintains semantics&quot; simply means that eager evaluation doesn't cause non-termination.</p>
<p>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.</p>
<h2>Explicit strictness annotations</h2>
<p>Haskell allows you to force evaluation of terms using <code>!</code> and <code>$!</code> (up to <a href="https://wiki.haskell.org/Weak_head_normal_form" rel="nofollow noreferrer">weak-head-normal form</a>; you can force nested terms using <a href="https://hackage.haskell.org/package/deepseq-1.5.0.0/docs/Control-DeepSeq.html#v:deepseq" rel="nofollow noreferrer"><code>deepseq</code></a>). You avoid the thunk build-up if you force the second argument of the recursive call in <code>factorial</code>, like so:</p>
<pre class="lang-hs prettyprint-override"><code>factorial n = go n 1
   where
       go 0 acc = acc
       go n acc = go (n - 1) $! acc * n
</code></pre>
<h2>Larger or unbounded stack</h2>
<p><a href="https://gitlab.haskell.org/ghc/ghc/-/issues/8189#96702" rel="nofollow noreferrer">By default, Haskell's stack can resize itself up to a large fraction of total memory (one estimate is 80% of the heap)</a>. Even before this, <a href="https://stackoverflow.com/a/20313059">GHCi's default stack used to be 512MB</a>. For reference, <a href="https://stackoverflow.com/a/64085509">C's default stack limit rarely exceeds 8MB</a>, and <a href="https://stackoverflow.com/a/7828803">JavaScript's varies from 10,000 to 65,000 frames in modern browsers</a> (idk how much data each frame takes).</p>
<p>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.</p>

CC BY-SA 4.0
2024-02-16T22:32:03.777Z
2024-02-19T23:14:15.557Z
2024-02-19T23:14:15.557Z
tarzh
CC BY-SA 4.0
2024-02-16T22:38:00.007Z
And Python defaults to 1,000 frames -- they really don't want to encourage recursive algorithms.
Barmar
CC BY-SA 4.0
2024-02-16T23:08:29.053Z
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.
Jörg W Mittag
CC BY-SA 4.0
2024-02-16T23:41:46.470Z
@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.
Jörg W Mittag
CC BY-SA 4.0
2024-02-18T19:46:18.363Z
I find your links lacking of clear information about Guarded Recursion, please give more resources.
Delfin
CC BY-SA 4.0
2024-02-18T23:19:42.863Z
This answer is not correct. GHC implements tail calls. The Stack Overflow answer you link to does not say what you think it says.
Alexis King
CC BY-SA 4.0
2024-02-19T23:16:55.867Z
@AlexisKing I rewrote to match what I now think the SO answer says (TCO may be performed but it doesn't actually optimize), and ended up changing quite a lot (idk whether to edit or delete and post a new answer).
tarzh
CC BY-SA 4.0
2024-02-21T09:14:29.297Z
I consider that claiming that the halting problem applies to the strictness analysis requires a proof. But maybe should I make into his own question?
Delfin
CC BY-SA 4.0
2024-02-21T15:20:39.390Z
Eagerly fully reducing a term without changing semantics requires proving that reduction terminates without an error *or* the program hangs or encounters the same error regardless. The former requires solving the halting problem, the latter can be shown to like in `if halts someProgram then force term else somethingSafe`.
tarzh
CC BY-SA 4.0
2024-02-21T15:30:47.797Z
How much of a sharp corner is for the programmer to have to put an `$!` in their tail call optimizations?
Delfin
CC BY-SA 4.0
2024-02-21T15:31:12.483Z
@JörgWMittag Could you please give a link to the talk.
Delfin
CC BY-SA 4.0
2024-02-21T15:40:15.407Z
Idk quite what you mean by "sharp corner". But if the programmer expects the rhs to terminate without error it's not a danger (function takes too long or hangs = the program has a bug regardless), and it doesn't seem hard for them to figure out where to insert strictness annotations (worst case just force every argument to a tail-call; though the definition of "hard" depends on who you ask).
tarzh
# Effective Tail Call Optimization in Non strict functional languages
Posted by: username_0 on 2024-02-15
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:

go 5 1
go (5 - 1) (1 * 5)
go 4 (1 * 5)
go (4 - 1) (((1 * 5) * 4)
go 3 (((1 * 5) * 4)
go (3 - 1) (((1 * 5) * 4) * 3)
go 2 (((1 * 5) * 4) * 3)
go (2 - 1) ((((1 * 5) * 4) * 3) * 2)
go 1 ((((1 * 5) * 4) * 3) * 2)
go (1 - 1) (((((1 * 5) * 4) * 3) * 2) * 1)
go 0 (((((1 * 5) * 4) * 3) * 2) * 1)
(((((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?
**Tags:** haskell tail-call-optimization
> **Comments:**
> **username_1**: 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.  
---
## 1 answers
### Answer by username_2 on 2024-02-16. Score: 8
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.
> **Comments:**
> **username_3** (2024-02-16): And Python defaults to 1,000 frames -- they really don't want to encourage recursive algorithms.  
> **username_4** (2024-02-16): 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.  
> **username_4** (2024-02-16): @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.  
> **username_0** (2024-02-18): I find your links lacking of clear information about Guarded Recursion, please give more resources.  
> **username_5** (2024-02-18): This answer is not correct. GHC implements tail calls. The Stack Overflow answer you link to does not say what you think it says.  
> **username_2** (2024-02-19): @AlexisKing I rewrote to match what I now think the SO answer says (TCO may be performed but it doesn't actually optimize), and ended up changing quite a lot (idk whether to edit or delete and post a new answer).  
> **username_0** (2024-02-21): I consider that claiming that the halting problem applies to the strictness analysis requires a proof. But maybe should I make into his own question?  
> **username_2** (2024-02-21): Eagerly fully reducing a term without changing semantics requires proving that reduction terminates without an error *or* the program hangs or encounters the same error regardless. The former requires solving the halting problem, the latter can be shown to like in `if halts someProgram then force term else somethingSafe`.  
> **username_0** (2024-02-21): How much of a sharp corner is for the programmer to have to put an `$!` in their tail call optimizations?  
> **username_0** (2024-02-21): @JörgWMittag Could you please give a link to the talk.  
> **username_2** (2024-02-21): Idk quite what you mean by "sharp corner". But if the programmer expects the rhs to terminate without error it's not a danger (function takes too long or hangs = the program has a bug regardless), and it doesn't seem hard for them to figure out where to insert strictness annotations (worst case just force every argument to a tail-call; though the definition of "hard" depends on who you ask).  
---
