Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Right recursion with ocamlyacc
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-02-16 (02:09)
From: Jon Harrop <jon@j...>
Subject: Right recursion with ocamlyacc

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.