From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 300CEBCAE for ; Fri, 15 Jul 2005 14:14:42 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6FCEfnR013917 for ; Fri, 15 Jul 2005 14:14:41 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA17916 for ; Fri, 15 Jul 2005 14:14:41 +0200 (MET DST) Received: from xmail.valdosta.edu (xmail.valdosta.edu [168.18.130.220]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6FCEetw013911 for ; Fri, 15 Jul 2005 14:14:41 +0200 Received: from starlight.valdosta.edu (starlight.valdosta.edu [168.18.148.146]) by xmail.valdosta.edu (8.13.4/8.13.4) with ESMTP id j6FCEb4Q017196 for ; Fri, 15 Jul 2005 08:14:37 -0400 (EDT) (envelope-from jtbryant@valdosta.edu) Subject: Re: [Caml-list] Mututal Recursion and Tail Recursion From: Jonathan Bryant Reply-To: jtbryant@valdosta.edu To: caml-list@inria.fr In-Reply-To: <17111.23105.448745.536629@gargle.gargle.HOWL> References: <1121281425.30107.36.camel@starlight.valdosta.edu> <17111.23105.448745.536629@gargle.gargle.HOWL> Content-Type: text/plain Organization: Valdosta State University Information Technology (System Operations) Date: Fri, 15 Jul 2005 08:15:33 -0400 Message-Id: <1121429733.25450.5.camel@starlight.valdosta.edu> Mime-Version: 1.0 X-Mailer: Evolution 2.0.2 (2.0.2-16) Content-Transfer-Encoding: 7bit X-PMX-Version: 5.0.2.153301, Antispam-Engine: 2.0.3.2, Antispam-Data: 2005.7.15.8 X-PerlMx-Spam: Gauge=IIIIIII, Probability=7%, Report='__CT 0, __CTE 0, __CT_TEXT_PLAIN 0, __HAS_MSGID 0, __HAS_X_MAILER 0, __MIME_TEXT_ONLY 0, __MIME_VERSION 0, __SANE_MSGID 0' X-Miltered: at concorde with ID 42D7A8B1.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42D7A8B0.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 recursion:01 recursion:01 recursive:01 recursive:01 filliatre:01 flatten:01 stack:01 ocamlopt:01 wrote:01 wrote:01 writes:01 tail:01 tail:01 functions:01 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: Ok, I don't know enough about assembly to know exactly what that means, although I think that you mean they are tail recursive. The whole reason I wrote this tiny module was to do that tail recursive since the List module isn't. How does one submit code updates to INRIA for things like this? On Fri, 2005-07-15 at 08:40 +0200, Jean-Christophe Filliatre wrote: > Jonathan Bryant writes: > > Is is possible to have mutually recursive functions that are also tail > > recursive? > > Yes. > > > For example, attached is some code I wrote to flatten a list > > of lists using mutually recursive functions. I've tried this with large > > lists (5,000,000+) and have not encountered a stack overflow, but that > > does not necessarily mean that tail recursion is happening. > > Looking at the assembly code (obtained with "ocamlopt -S") clearly > gives the answer: all three recursive calls in flat_in and flat_out > are realized by jumps (and not calls). > > I copy below the assembly code for the functions flat_in and flat_out. > > Hope this helps, -- *=========================* |Jonathan Bryant | |Valdosta State University| |Information Technology | |System Operations | |-------------------------| |jtbryant@valdosta.edu | |x6358 | *=========================*