From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 4C995BC8E for ; Wed, 16 Feb 2005 03:09:12 +0100 (CET) Received: from ptb-relay01.plus.net (ptb-relay01.plus.net [212.159.14.212]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j1G29B2L007644 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 16 Feb 2005 03:09:12 +0100 Received: from [80.229.56.224] (helo=chetara) by ptb-relay01.plus.net with esmtp (Exim) id 1D1Ecp-000Nmb-74 for caml-list@yquem.inria.fr; Wed, 16 Feb 2005 02:09:11 +0000 From: Jon Harrop Organization: University of Cambridge To: caml-list@yquem.inria.fr Subject: Right recursion with ocamlyacc Date: Wed, 16 Feb 2005 02:10:45 +0000 User-Agent: KMail/1.7.1 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200502160210.46048.jon@jdh30.plus.com> X-Miltered: at concorde with ID 4212AB47.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; recursion:01 ocamlyacc:01 ocaml:01 recursion:01 ocamlyacc:01 internals:01 stack:01 corresponds:01 deluded:01 stack:01 frog:98 rewrite:01 cps:01 shootout:02 failing:02 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: 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.