tail call optimization problem

Discussion in 'Javascript' started by Balazs Endresz, May 2, 2010.

  1. 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?
    Balazs Endresz, May 2, 2010
    #1
    1. Advertising

  2. Balazs Endresz

    Ry Nohryb Guest

    On May 2, 11:25 am, Balazs Endresz <> 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.
    Ry Nohryb, May 2, 2010
    #2
    1. Advertising

  3. On May 2, 11:59 am, Ry Nohryb <> wrote:
    > On May 2, 11:25 am, Balazs Endresz <> 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
    Balazs Endresz, May 2, 2010
    #3
  4. Balazs Endresz

    Ry Nohryb Guest

    On May 2, 12:32 pm, Balazs Endresz <> wrote:
    > On May 2, 11:59 am, Ry Nohryb <> wrote:
    >
    >
    >
    >
    >
    > > On May 2, 11:25 am, Balazs Endresz <> 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.
    Ry Nohryb, May 2, 2010
    #4
  5. On May 2, 12:53 pm, Ry Nohryb <> wrote:
    > On May 2, 12:32 pm, Balazs Endresz <> wrote:
    >
    >
    >
    >
    >
    > > On May 2, 11:59 am, Ry Nohryb <> wrote:

    >
    > > > On May 2, 11:25 am, Balazs Endresz <> 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 thenas
    > > > > 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]});
    Balazs Endresz, May 2, 2010
    #5
  6. Balazs Endresz

    Ry Nohryb Guest

    On May 2, 1:23 pm, Balazs Endresz <> wrote:
    > On May 2, 12:53 pm, Ry Nohryb <> wrote:
    >
    >
    >
    >
    >
    > > On May 2, 12:32 pm, Balazs Endresz <> wrote:

    >
    > > > On May 2, 11:59 am, Ry Nohryb <> wrote:

    >
    > > > > On May 2, 11:25 am, Balazs Endresz <> 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 ona
    > > > > > ParseState object, which indicates how much of the text has been
    > > > > > consumed. And it *does* seem to fully consume the input no matterhow
    > > > > > 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.
    Ry Nohryb, May 2, 2010
    #6
  7. Balazs Endresz

    Ry Nohryb Guest

    On May 2, 1:23 pm, Balazs Endresz <> wrote:
    > On May 2, 12:53 pm, Ry Nohryb <> wrote:
    >
    >
    >
    >
    >
    > > On May 2, 12:32 pm, Balazs Endresz <> wrote:

    >
    > > > On May 2, 11:59 am, Ry Nohryb <> wrote:

    >
    > > > > On May 2, 11:25 am, Balazs Endresz <> 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 ona
    > > > > > ParseState object, which indicates how much of the text has been
    > > > > > consumed. And it *does* seem to fully consume the input no matterhow
    > > > > > 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.
    Ry Nohryb, May 2, 2010
    #7
  8. On May 2, 1:38 pm, Ry Nohryb <> wrote:
    > On May 2, 1:23 pm, Balazs Endresz <> wrote:
    >
    >
    >
    >
    >
    > > On May 2, 12:53 pm, Ry Nohryb <> wrote:

    >
    > > > On May 2, 12:32 pm, Balazs Endresz <> wrote:

    >
    > > > > On May 2, 11:59 am, Ry Nohryb <> wrote:

    >
    > > > > > On May 2, 11:25 am, Balazs Endresz <> 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, butI
    > > > > > > 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 until3000
    > > > > > > recursive calls but above that, when the last callback functionshould
    > > > > > > 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!
    Balazs Endresz, May 2, 2010
    #8
  9. On May 2, 1:56 pm, Ry Nohryb <> wrote:
    > On May 2, 1:23 pm, Balazs Endresz <> wrote:
    >
    >
    >
    >
    >
    > > On May 2, 12:53 pm, Ry Nohryb <> wrote:

    >
    > > > On May 2, 12:32 pm, Balazs Endresz <> wrote:

    >
    > > > > On May 2, 11:59 am, Ry Nohryb <> wrote:

    >
    > > > > > On May 2, 11:25 am, Balazs Endresz <> 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, butI
    > > > > > > 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 until3000
    > > > > > > recursive calls but above that, when the last callback functionshould
    > > > > > > 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.
    Balazs Endresz, May 2, 2010
    #9
  10. Balazs Endresz

    Ry Nohryb Guest

    On May 2, 2:03 pm, Balazs Endresz <> wrote:
    > On May 2, 1:38 pm, Ry Nohryb <> wrote:
    >
    >
    >
    >
    >
    > > On May 2, 1:23 pm, Balazs Endresz <> wrote:

    >
    > > > On May 2, 12:53 pm, Ry Nohryb <> wrote:

    >
    > > > > On May 2, 12:32 pm, Balazs Endresz <> wrote:

    >
    > > > > > On May 2, 11:59 am, Ry Nohryb <> wrote:

    >
    > > > > > > On May 2, 11:25 am, Balazs Endresz <>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 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 ?
    > > --
    > > 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.
    Ry Nohryb, May 2, 2010
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Crutcher
    Replies:
    4
    Views:
    291
    Michel Salim
    Mar 3, 2006
  2. Sam Stephenson

    Tail call ``optimization''

    Sam Stephenson, Sep 24, 2004, in forum: Ruby
    Replies:
    1
    Views:
    118
    Robert Klemme
    Sep 25, 2004
  3. Thomas Hurst

    1.9 tail-call optimization status?

    Thomas Hurst, Aug 23, 2008, in forum: Ruby
    Replies:
    0
    Views:
    100
    Thomas Hurst
    Aug 23, 2008
  4. Terry Michaels

    Tail Call Optimization (Tail Recursion)

    Terry Michaels, Apr 18, 2011, in forum: Ruby
    Replies:
    16
    Views:
    309
    Robert Klemme
    Apr 20, 2011
  5. glathoud
    Replies:
    28
    Views:
    400
    glathoud
    Feb 6, 2010
Loading...

Share This Page