Closures in recursive calls get shadowed, causing stack overflows

[bengolds]

Quick Summary: When writing a recursive function that has continuations, it appears the values inside the continuation don't get closed over properly. When the continuation is called, values from the inner closures leak out. This can pretty quickly lead to stack overflows.

SSCCE

https://ellie-app.com/7ccRwXWLDsPa1

windDown : Int -> (Int -> Bool) -> Bool
windDown value continuation =
    if value > 0 then
        windDown
            (value - 1)
            continuation -- Works!
           -- (\newValue -> continuation newValue) -- Crashes; max stack size exceeded

    else
        continuation 0

or, another way to see the shadowing issue:

windDown : Int -> (Int -> Bool) -> Bool
windDown value continuation =
    if value > 0 then
        let
            secretValue =
                "This should always be printed."
        in
        windDown
            (value - 1)
            (\newValue ->
                let
                    _ =
                        Debug.log "continuing" secretValue
                in
                continuation newValue
            )

    else
        let
            secretValue =
                "You should never see this printed."
        in
        continuation 0

• Elm: 0.19.1
• Browser: Chrome, but also in the REPL
• Operating System: Mac OS

Additional Details

[harrysarson]

For reference here is the generated javascript:

var $author$project$Main$windDown = F2(
	function (value, continuation) {
		windDown:
		while (true) {
			if (value > 0) {
				var $temp$value = value - 1,
					$temp$continuation = function (newValue) { // (1)
					return continuation(newValue);
				};
				value = $temp$value;
				continuation = $temp$continuation;                 // (2)
				continue windDown;
			} else {
				return continuation(0);                            // (3)
			}
		}
	});

for

windDown : Int -> (Int -> Bool) -> Bool
windDown value continuation =
    if value > 0 then
        windDown
            (value - 1)
            (\newValue -> continuation newValue)

    else
        continuation 0

using elm 0.19.1

[harrysarson]

The issue is that by the time we get to (2), we have already been to (1) and (2) and therefore continuation = function (newValue) { return continuation(newValue); };.

Then calling continuation(0) at (3) gives infinite recursion!

[temochka]

I ran into the same bug recently. I found that you can sometimes work around the issue by adding extraneous let bindings. For example, here’s an Ellie that demonstrates two semantically equivalent CPS-style eval functions (evalBuggy and evalHacky), differing only by additional let bindings, one of which overflows the stack while the other returns:

https://ellie-app.com/dB8FkMNXG4Ta1

Note that there’s an alternative (commented) test "program" in this script. That program fails even with the workaround.

[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 recursion in TCO