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: Ry Nohryb on 2 May 2010 07:38 On May 2, 1:23 pm, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > 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]}); Yeah, that works, even in FF. Does your code fail too in the other browsers @ their respective call stack limits ? -- Jorge.
From: Ry Nohryb on 2 May 2010 07:56 On May 2, 1:23 pm, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > 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]}); Trampoline2 in your code isn't looping, instead it's calling itself recursively. -- Jorge.
From: Balazs Endresz on 2 May 2010 08:03 On May 2, 1:38 pm, Ry Nohryb <jo...(a)jorgechamorro.com> wrote: > On May 2, 1:23 pm, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > > > > > > > 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]}); > > Yeah, that works, even in FF. Does your code fail too in the other > browsers @ their respective call stack limits ? > -- > Jorge. 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!
From: Balazs Endresz on 2 May 2010 08:15 On May 2, 1:56 pm, Ry Nohryb <jo...(a)jorgechamorro.com> wrote: > On May 2, 1:23 pm, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > > > > > > > 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]}); > > Trampoline2 in your code isn't looping, instead it's calling itself > recursively. > -- > Jorge. 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.
From: Ry Nohryb on 2 May 2010 08:36
On May 2, 2:03 pm, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > On May 2, 1:38 pm, Ry Nohryb <jo...(a)jorgechamorro.com> wrote: > > > > > > > On May 2, 1:23 pm, Balazs Endresz <balazs.endr...(a)gmail.com> wrote: > > > > 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]}); > > > Yeah, that works, even in FF. Does your code fail too in the other > > browsers @ their respective call stack limits ? > > -- > > Jorge. > > 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. -- Jorge. |