tail call optimization problem
in [JavaScript]
|
Prev: Math.random() and Math.round(Math.random()) andMath.floor(Math.random()*2)
Next: how to create 5-dimensional array ? [Train-spotting]
From: Balazs Endresz on 2 May 2010 05:25 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?
From: Ry Nohryb on 2 May 2010 05:59 On May 2, 11:25 am, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > 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 -- Jorge.
From: Balazs Endresz on 2 May 2010 06:32 On May 2, 11:59 am, Ry Nohryb <jo...(a)jorgechamorro.com> wrote: > On May 2, 11:25 am, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > > > > > > > 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 > -- > 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
From: Ry Nohryb on 2 May 2010 06:53 On May 2, 12:32 pm, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > On May 2, 11:59 am, Ry Nohryb <jo...(a)jorgechamorro.com> wrote: > > > > > > > On May 2, 11:25 am, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > > > > 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 () {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.
From: Balazs Endresz on 2 May 2010 07:23
On May 2, 12:53 pm, Ry Nohryb <jo...(a)jorgechamorro.com> wrote: > On May 2, 12:32 pm, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > > > > > > > On May 2, 11:59 am, Ry Nohryb <jo...(a)jorgechamorro.com> wrote: > > > > On May 2, 11:25 am, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > > > > > 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 () {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]}); |