Tail-calls in recursive functions are not optimized if used with pipeline operators #1770

ymtszw · 2018-08-29T16:59:09Z

From slack discussion: https://elmlang.slack.com/archives/C13L7S5GR/p1535488054000100

In Elm 0.19. Reproducible in Ellie.

SSCCE:

module Main exposing (main)

import Browser
import Html

main : Program () () ()
main =
    Browser.sandbox
        { init = ()
        , update = \_ m -> m
        , view = \_ -> Html.text (tailCallWithPipeline 12345 "something")
        }

-- TCO Bug SSCCE

tailCallWithPipeline : Int -> String -> String
tailCallWithPipeline count acc =
    if count <= 0 then
        acc

    else
        acc
            |> tailCallWithPipeline (count - 1)


tailCallWithoutPipeline : Int -> String -> String
tailCallWithoutPipeline count acc =
    if count <= 0 then
        acc

    else
        tailCallWithoutPipeline (count - 1) acc

<html>
<head></head>
<body>
  <main></main>
  <script>
    var app = Elm.Main.init({ node: document.querySelector('main') })
  </script>
</body>
</html>

Here, tailCallWithPipeline and tailCallWithoutPipeline are semantically identical recursive functions, the only difference is a use of pipeline operator |>.
However, executing tailCallWithPipeline ends up in runtime error: RangeError: Maximum call stack size exceeded, whereas tailCallWithoutPipeline does not (correctly optimized and run fine).

Both worked fine in 0.18.

The text was updated successfully, but these errors were encountered:

atdixon · 2019-01-09T21:55:30Z

Here is another (smaller/repl-based) example:

> sum_ n i = if n == 0 then i else sum_ (n - 1) (n + i)
> sum_ 1000000 0
500000500000 : Int

HOWEVER, not if slightly modified using pipe operator:

> sum_ n i = if n == 0 then i else sum_ (n - 1) <| n + i
> sum_ 1000000 0
RangeError: Maximum call stack size exceeded

tail call optimization fails when pipes are used elm/compiler#1770.

evancz · 2019-07-19T19:39:59Z

In changing how code was generated in 0.19.0 to make sure the generated assets were really small, we moved some AST shuffling later into the optimization process. The old version tried to flatten out <| and |> uses earlier in the pipeline.

The resulting behavior is that tail-call elimination is only performed when the recursive call is in "tail call position" (i.e. called directly at the conclusion of some some branch of logic)

This particular optimization enters into the realm of feature because it can change program behavior, so it's definitely important to keep this stable. It looks like this behavior is going to remain the same from 0.19.0 to 0.19.1, and I think the best path is to just require the "tail call position" without any special exceptions for now.

atdixon · 2019-07-19T23:48:24Z

Is the change in behavior anything other than a "RangeError: Maximum call stack size exceeded"? I think it would be safe to say no client would be relying on this behavior and furthermore the behavior is likely widely variant across systems.

From the operator documentation, we have

-- (arg |> func) is the same as (func arg)

But what seems to be suggested in your note is that this is not an equivalency. I may be missing something, but this is rather surprising behavior. A common refactoring relies on the expectation of this equivalency; that (arg |> func) and (func arg) are referentially transparent. But perform such refactoring in tail position and you're in for trouble?

avh4 mentioned this issue Sep 1, 2018

Infinite recursion shrinking with fuzz2 elm-explorations/test#18

Closed

This was referenced Jan 9, 2019

Some functions do not leverage elm TCO the-sett/lazy-list#5

Closed

fix non-tco optimized cases the-sett/lazy-list#8

Merged

RavenDream added a commit to reserve-protocol/elm-html-string that referenced this issue Feb 3, 2019

fix: work around tail call optimization failure bug in compiler

8d2c235

tail call optimization fails when pipes are used elm/compiler#1770.

RavenDream mentioned this issue Feb 3, 2019

fix: work around tail call optimization failure bug in compiler zwilias/elm-html-string#6

Merged

RavenDream added a commit to reserve-protocol/elm-html-string that referenced this issue Feb 3, 2019

fix: work around tail call optimization failure bug in compiler

9e1259d

tail call optimization fails when pipes are used elm/compiler#1770.

pablohirafuji mentioned this issue Mar 24, 2019

Remove pipelines pablohirafuji/elm-qrcode#8

Merged

evancz closed this as completed Jul 19, 2019

simonh1000 added a commit to simonh1000/AdventCode2019 that referenced this issue Dec 22, 2019

change code to work around elm/compiler#1770

68e9582

jfmengels mentioned this issue Mar 14, 2021

Report functions that are not tail-call-optimized jfmengels/elm-review#74

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Tail-calls in recursive functions are not optimized if used with pipeline operators #1770

Tail-calls in recursive functions are not optimized if used with pipeline operators #1770

ymtszw commented Aug 29, 2018 •

edited

atdixon commented Jan 9, 2019

evancz commented Jul 19, 2019 •

edited

atdixon commented Jul 19, 2019

Tail-calls in recursive functions are not optimized if used with pipeline operators #1770

Tail-calls in recursive functions are not optimized if used with pipeline operators #1770

Comments

ymtszw commented Aug 29, 2018 • edited

atdixon commented Jan 9, 2019

evancz commented Jul 19, 2019 • edited

atdixon commented Jul 19, 2019

ymtszw commented Aug 29, 2018 •

edited

evancz commented Jul 19, 2019 •

edited