Tail Call Optimization produces bad closures

[micahhahn]

The code generation for the tail call optimization does not appear to create proper closures to variables. In the following example I would expect goodOutput and badOutput to be the same, but instead all the closures generated in tcoMakeLazy reference the same variable which contains its final value of 3.

SSCCE

makeLazy : List a -> List (() -> a) -> List (() -> a)
makeLazy list accum =
    case list of
        item :: items ->
            makeLazy items <| ((\_ -> item) :: accum)

        _ ->
            accum

tcoMakeLazy : List a -> List (() -> a) -> List (() -> a)
tcoMakeLazy list accum =
    case list of
        item :: items ->
            tcoMakeLazy items ((\_ -> item) :: accum)

        _ ->
            accum

-- [1, 2, 3]
goodOutput =
    makeLazy [ 1, 2, 3 ] [] |> List.map (\f -> f ())

-- [3, 3, 3]
badOutput =
    tcoMakeLazy [ 1, 2, 3 ] [] |> List.map (\f -> f ())

• Elm: 0.19
• Browser: Any
• Operating System: Any

[github-actions[bot]]

Thanks for reporting this! To set expectations:

• Issues are reviewed in batches, so it can take some time to get a response.
• Ask questions in a community forum. You will get an answer quicker that way!
• If you experience something similar, open a new issue. We like duplicates.

Finally, please be patient with the core team. They are trying their best with limited resources.

[jfmengels]

I have noticed the same problem before (but forgot about making an issue :man_facepalming:).

While this example here might not seem all that problematic, the CPS (Continuation Passing Style) pattern relies on code like this, meaning that it is not a pattern that we can use in Elm. The pattern IIRC helps with getting stack safety, even when doing operations on the result of a recursive call.

[jvoigtlaender]

See also: https://github.com/elm/compiler/issues/1287

[micahhahn]

@jfmengels CPS is the same context where I encountered this! Thankfully this doesn't directly block me on anything, it was just a very confusing couple hours of debugging.

[miniBill]

For people being bitten by this in the future, using https://github.com/micahhahn/elm-safe-recursion is both going to fix this and allow mutual recusion in TCO

[micahhahn]

@miniBill While elm-safe-recursion can be used to work around the bug, the problem still remains that this is easy to unwittingly trigger and extremely difficult to track down.

[andrewMacmurray]

Here's another example for reference where TCO produces bad closures:

type Trampoline a
    = More (() -> Trampoline a)
    | Done a


wrapMany : Int -> Trampoline a -> Trampoline a
wrapMany n trampoline =
    if n > 0 then
        wrapMany (n - 1) (More (\_ -> trampoline))

    else
        trampoline


run : Trampoline a -> a
run trampoline =
    case trampoline of
        More next ->
            run (next ())

        Done a ->
            a

The Trampoline returns More infinitely and eventually crashes.

However, if you substitute the inline More (\_ -> trampoline) with a named function:

wrapMany : Int -> Trampoline a -> Trampoline a
wrapMany n trampoline =
    if n > 0 then
        wrapMany (n - 1) (more trampoline)

    else
        trampoline


more : Trampoline a -> Trampoline a
more a =
    More (\_ -> a)

It's still TCOd but the closures work correctly.