Version française
Home     About     Download     Resources     Contact us    
Browse thread
Mututal Recursion and Tail Recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jonathan Bryant <jtbryant@v...>
Subject: Re: [Caml-list] Mututal Recursion and Tail Recursion
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                    |
*=========================*