Browse thread
Right recursion with ocamlyacc
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ 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.