Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

RangeError occurs in CP styled functions #2221

Open
magniff opened this issue Aug 17, 2021 · 3 comments
Open

RangeError occurs in CP styled functions #2221

magniff opened this issue Aug 17, 2021 · 3 comments

Comments

@magniff
Copy link

magniff commented Aug 17, 2021

Quick Summary: I've been playing with continuation passing styled functions and stumbled upon the code, that seems to confuse the compiler.

Here is the code:

g : Int -> (Int -> a) -> a
g value cont =
    case value of
        1 -> cont 1
        _ -> g (value-1) (\result -> cont (result * value))

Expected: function g computes value's factorial
Actual (repl):

> g 1 (Debug.log "result")
result: 1
1 : Int
> g 2 (Debug.log "result")
RangeError: Maximum call stack size exceeded
  • Elm: 0.19.1
  • Browser: no browser (repl)
  • Operating System: ubuntu 20
@github-actions
Copy link

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.

@tripack45
Copy link

This is the compiled output:

var $author$project$T$g = F2(
	function (value, cont) {
		g:
		while (true) {
			if (value === 1) {
				return cont(1);
			} else {
				var $temp$value = value - 1,
					$temp$cont = function (result) {
					return cont(result * value);
				};
				value = $temp$value;
				cont = $temp$cont;
				continue g;
			}
		}
	});

It looks like tail-call optimization accidentally broke capturing of arguments, changing the captured values. This problem is evident in perhaps another simpler example:

f x l = if x == 0 then l else f (x - 1) ((\_ -> x) :: l)
> List.map (\g -> g ()) (f 10 [])
[0,0,0,0,0,0,0,0,0,0]
    : List number

The output should be [10, 9, ... , 1]

@miniBill
Copy link

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

changlinli added a commit to Zokka-Dev/zokka-compiler that referenced this issue Dec 22, 2023
This fixes elm/compiler#1813 and
elm/compiler#2221, which both were issues with
overwriting function params in TCO in a way that is observable by
closures. We rewrite function params for tail calls to get around this.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants