tail call optimization problem

[Balazs Endresz]

Recently I made a parser combinator lib, based on Parsec:
http://code.google.com/p/jsparsec/
and I started to rewrite it in trampolined style to avoid "too much
recursion". But above about 3000 "recursive" calls (in Firefox) it
doesn't work as expected. I might have messed something up, but I
can't seem to figure out what's happening. The parser operates on a
ParseState object, which indicates how much of the text has been
consumed. And it *does* seem to fully consume the input no matter how
deep the recursion is, but when it approaches to the last function
call, then it fails with "Internal error: too much recursion". I even
inserted timeouts between every few hundred calls but it fails then as
well, but with a slightly different error: "too much recursion (802
out of range 13)" - this is a bit strange but I don't think it's
related. If I stop it before the last computation and evaluate the
remaining thunks manually, one by one, then again: "Internal error:
too much recursion".

Here's the code I used to test it:
http://code.google.com/p/jsparsec/source/browse/branches/tailopt-test/test.js

So, what seems to be happening, is that it works properly until 3000
recursive calls but above that, when the last callback function should
receive the final result, it fails. But I can see that the input in
the ParseState object has been fully consumed. How could such thing
happen?

 

[Ry Nohryb]

Recently I made a parser combinator lib, based on Parsec:http://code.google.com/p/jsparsec/
and I started to rewrite it in trampolined style to avoid "too much
recursion". But above about 3000 "recursive" calls (in Firefox) it
doesn't work as expected. I might have messed something up, but I
can't seem to figure out what's happening. The parser operates on a
ParseState object, which indicates how much of the text has been
consumed. And it *does* seem to fully consume the input no matter how
deep the recursion is, but when it approaches to the last function
call, then it fails with "Internal error: too much recursion". I even
inserted timeouts between every few hundred calls but it fails then as
well, but with a slightly different error: "too much recursion (802
out of range 13)" - this is a bit strange but I don't think it's
related. If I stop it before the last computation and evaluate the
remaining thunks manually, one by one, then again: "Internal error:
too much recursion".

Here's the code I used to test it:http://code.google.com/p/jsparsec/source/browse/branches/tailopt-test...

So, what seems to be happening, is that it works properly until 3000
recursive calls but above that, when the last callback function should
receive the final result, it fails. But I can see that the input in
the ParseState object has been fully consumed. How could such thing
happen?

That's the limit of its call stack:

javascript:var n=0;(function f () {try {f(n++)} catch (e) {alert(n)}})
(0);

Safari:40328
Opera:16384
Chrome:6921
FF:3000

 

[Balazs Endresz]

That's the limit of its call stack:

javascript:var n=0;(function f () {try {f(n++)} catch (e) {alert(n)}})
(0);

Safari:40328
Opera:16384
Chrome:6921
FF:3000

I understand that this shouldn't work above those limits but writing
it in trampolined style *should* solve this issue. See the second
answer here:
http://stackoverflow.com/questions/189725/what-is-a-trampoline-function

 

[Ry Nohryb]

I understand that this shouldn't work above those limits but writing
it in trampolined style *should* solve this issue. See the second
answer here:http://stackoverflow.com/questions/189725/what-is-a-trampoline-function

Can you post a short "trampolinized" snippet that fails ?

 

[Balazs Endresz]

Can you post a short "trampolinized" snippet that fails ?

Other than the one I already posted, if I could make a really simple
one, my problem would be solved
But here's one that works:

function trampoline(x) {
while (x && x.func) {
x = x.func.apply(null, x.args);
}
}

var n = 0;
function f(callback){
return n++ >50000 ? callback(n) : {func:f, args:[callback]};
}

trampoline({func:f, args:[alert]});

 

[Ry Nohryb]

Can you post a short "trampolinized" snippet that fails ?

Other than the one I already posted, if I could make a really simple
one, my problem would be solved
But here's one that works:

function trampoline(x) {
  while (x && x.func) {
    x = x.func.apply(null, x.args);
  }

}

var n = 0;
function f(callback){
  return n++ >50000 ? callback(n) : {func:f, args:[callback]};

}

trampoline({func:f, args:[alert]});

Yeah, that works, even in FF. Does your code fail too in the other
browsers @ their respective call stack limits ?

 

[Ry Nohryb]

Can you post a short "trampolinized" snippet that fails ?

Other than the one I already posted, if I could make a really simple
one, my problem would be solved
But here's one that works:

function trampoline(x) {
  while (x && x.func) {
    x = x.func.apply(null, x.args);
  }

}

var n = 0;
function f(callback){
  return n++ >50000 ? callback(n) : {func:f, args:[callback]};

}

trampoline({func:f, args:[alert]});

Trampoline2 in your code isn't looping, instead it's calling itself
recursively.

 

[Balazs Endresz]

Other than the one I already posted, if I could make a really simple
one, my problem would be solved
But here's one that works:

function trampoline(x) {
  while (x && x.func) {
    x = x.func.apply(null, x.args);
  }

}

var n = 0;
function f(callback){
  return n++ >50000 ? callback(n) : {func:f, args:[callback]};

}

trampoline({func:f, args:[alert]});

Yeah, that works, even in FF. Does your code fail too in the other
browsers @ their respective call stack limits ?

I forgot to mention that I tried it in Chrome too, and the same thing
happened but without any error messages. But now I tried it in IE, and
unlike other browsers, it pointed to the exact location where the
problem occurred. So, problem solved: I called a function directly at
the end of the parse, which caused this issue.

Thanks very much for the suggestions!

 

[Balazs Endresz]

Other than the one I already posted, if I could make a really simple
one, my problem would be solved
But here's one that works:

function trampoline(x) {
  while (x && x.func) {
    x = x.func.apply(null, x.args);
  }

}

var n = 0;
function f(callback){
  return n++ >50000 ? callback(n) : {func:f, args:[callback]};

}

trampoline({func:f, args:[alert]});

Trampoline2 in your code isn't looping, instead it's calling itself
recursively.

Since there's a setTimeout in every 200 iteration, that's not issue.
It's only for not blocking the browser for too long. Btw, I updated
the code so now the link points to the correct version.

 

[Ry Nohryb]

Recently I made a parser combinator lib, based on Parsec:http://code.google.com/p/jsparsec/
and I started to rewrite it in trampolined style to avoid "too much
recursion". But above about 3000 "recursive" calls (in Firefox) it
doesn't work as expected. I might have messed something up, but I
can't seem to figure out what's happening. The parser operates on a
ParseState object, which indicates how much of the text has been
consumed. And it *does* seem to fully consume the input no matter how
deep the recursion is, but when it approaches to the last function
call, then it fails with "Internal error: too much recursion".. I even
inserted timeouts between every few hundred calls but it fails then as
well, but with a slightly different error: "too much recursion (802
out of range 13)" - this is a bit strange but I don't think it's
related. If I stop it before the last computation and evaluate the
remaining thunks manually, one by one, then again: "Internal error:
too much recursion".
Here's the code I used to test it:http://code.google.com/p/jsparsec/source/browse/branches/tailopt-test...
So, what seems to be happening, is that it works properly until 3000
recursive calls but above that, when the last callback function should
receive the final result, it fails. But I can see that the input in
the ParseState object has been fully consumed. How could suchthing
happen?
That's the limit of its call stack:
javascript:var n=0;(function f () {if (n>5e4) return; try {setTimeout(function(){f(n++),0}} catch (e) {alert(n)}})
(0);
Safari:40328
Opera:16384
Chrome:6921
FF:3000
--
Jorge.
I understand that this shouldn't work above those limits but writing
it in trampolined style *should* solve this issue. See the second
answer here:http://stackoverflow.com/questions/189725/what-is-a-trampoline-function
Can you post a short "trampolinized" snippet that fails ?
--
Jorge.
Other than the one I already posted, if I could make a really simple
one, my problem would be solved
But here's one that works:
function trampoline(x) {
  while (x && x.func) {
    x = x.func.apply(null, x.args);
  }
}
var n = 0;
function f(callback){
  return n++ >50000 ? callback(n) : {func:f, args:[callback]};
}
trampoline({func:f, args:[alert]});

Yeah, that works, even in FF. Does your code fail too in the other
browsers @ their respective call stack limits ?

I forgot to mention that I tried it in Chrome too, and the same thing
happened but without any error messages. But now I tried it in IE, and
unlike other browsers, it pointed to the exact location where the
problem occurred.

Glad to know that IE does a thing right

So, problem solved: I called a function directly at
the end of the parse, which caused this issue.

Thanks very much for the suggestions!

You're welcome.