Right recursion with ocamlyacc

Right recursion with ocamlyacc

[Jon Harrop]

I've just been converting a new Computer Language Shootout submission from 
OCaml to C++ and found that bison falls over very easily with right recursion 
(failing to load a 10^4-element list) but ocamlyacc had no problems (even on 
a 10^5-element list).

Now, I don't know much about yacc internals but I'm curious as to why this 
would be. Does g++ simply consume much bigger stack frames as it recurses 
(>10x the size?) running out much earler, or is there another reason?

Also, assuming this corresponds to non-tail-recursion inside ocamlyacc, could 
a rewrite in CPS eliminate this problem (probably with a performance hit)?

Or am I completely deluded and, in fact, this is a whole-other stack they're 
talking about, and ocamlyacc just happens to allocate a bigger one.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.

Re: [Caml-list] Right recursion with ocamlyacc

[Eric C. Cooper]

On Wed, Feb 16, 2005 at 02:10:45AM +0000, Jon Harrop wrote:
> Now, I don't know much about yacc internals but I'm curious as to why this 
> would be. Does g++ simply consume much bigger stack frames as it recurses 
> (>10x the size?) running out much earler, or is there another reason?

See section 5.9 of the Bison info file:

    By defining the macro `YYMAXDEPTH', you can control how deep the
    parser stack can become before a stack overflow occurs.  Define
    the macro with a value that is an integer.  This value is the
    maximum number of tokens that can be shifted (and not reduced)
    before overflow.  It must be a constant expression whose value is
    known at compile time.
    [...]
    The default value of `YYMAXDEPTH', if you do not define it, is
    10000.

-- 
Eric C. Cooper          e c c @ c m u . e d u

Re: [Caml-list] Right recursion with ocamlyacc

[Markus Mottl]

On Wed, 16 Feb 2005, Jon Harrop wrote:
> I've just been converting a new Computer Language Shootout submission from 
> OCaml to C++ and found that bison falls over very easily with right recursion 
> (failing to load a 10^4-element list) but ocamlyacc had no problems (even on 
> a 10^5-element list).

Why use right recursive productions in the grammar?  Left recursion runs
in constant stack space so this would be the way to go...

Regards,
Markus

-- 
Markus Mottl    markus.mottl@gmail.com    http://www.ocaml.info

Re: [Caml-list] Right recursion with ocamlyacc

[Jon Harrop]

On Wednesday 16 February 2005 03:58, Markus Mottl wrote:
> On Wed, 16 Feb 2005, Jon Harrop wrote:
> > I've just been converting a new Computer Language Shootout submission
> > from OCaml to C++ and found that bison falls over very easily with right
> > recursion (failing to load a 10^4-element list) but ocamlyacc had no
> > problems (even on a 10^5-element list).
>
> Why use right recursive productions in the grammar?

There was no justification for it, right recursion just happened to be most 
natural in this case. I've never worried about it before since it never came 
up.

> Left recursion runs in constant stack space so this would be the way to
> go... 

Yes, left recursion is definitely the way to go in general. But has anyone 
ever had a problem with right-recursion when using ocamlyacc? Is there a 
theoretical reason why this is not a problem with ocamlyacc?

When this came up, it occurred to me that (since switching to OCaml) I've 
neglected the stock advice of avoiding right recursion. And I'm not in the 
habit of parsing small files. :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.

Re: [Caml-list] Right recursion with ocamlyacc

[skaller]

On Wed, 2005-02-16 at 14:58, Markus Mottl wrote:
> On Wed, 16 Feb 2005, Jon Harrop wrote:
> > I've just been converting a new Computer Language Shootout submission from 
> > OCaml to C++ and found that bison falls over very easily with right recursion 
> > (failing to load a 10^4-element list) but ocamlyacc had no problems (even on 
> > a 10^5-element list).
> 
> Why use right recursive productions in the grammar?  Left recursion runs
> in constant stack space so this would be the way to go...

Kind of tricky to represent right associative binary
operator with left recursion .. right recursion is 
much more natural:

rterm: atom rterm { Rterm ($1, $2) }

The thing is, right assoc requires terms to
be stacked up one way or another. Left recursion
defers the problem to client code, and must introduce
intermediate term structure to do that.

Why would I believe my own data structures
would perform more efficiently than the parser stack?

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] Right recursion with ocamlyacc

[Radu Grigore]

On Wed, 16 Feb 2005 04:35:23 +0000, Jon Harrop <jon@jdh30.plus.com> wrote:

> Yes, left recursion is definitely the way to go in general. But has anyone
> ever had a problem with right-recursion when using ocamlyacc? Is there a
> theoretical reason why this is not a problem with ocamlyacc?

In parsing.ml you will find a function approprately named growstacks.
For very big lists you will get an exception from Array.make. In my
experiment this happened after about 3x10^6 elements. OTOH bison/flex
use AFAIK a fixed stack and fails (as you said) on smaller lists.

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Right recursion with ocamlyacc

[Radu Grigore]

On Wed, 16 Feb 2005 11:18:21 +0200, Radu Grigore <radugrigore@gmail.com> wrote:
> In parsing.ml you will find a function approprately named growstacks.

And, BTW the stack size is doubled which is not a very good strategy.
With the simplest memory model (one contiguous segment) one can see
that if the array is allocated first at address 0 and then at the
lowest address that can hold it then the base address will keep
increasing. This assumes that there aren't other big data structures
in memory that get collected.

The same issue prompted a change in the implementation of STL in MSVC
7.0. IIRC the grow factor was reduced from 2 to 1.5. In theory to
allow reuse it is sufficient to use a factor less than the golden
ration.

-- 
regards,
 radu
http://rgrig.idilis.ro/