From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 72E07BCAE for ; Fri, 15 Jul 2005 08:40:03 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6F6e23j028608 for ; Fri, 15 Jul 2005 08:40:03 +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 IAA13367 for ; Fri, 15 Jul 2005 08:40:02 +0200 (MET DST) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6F6e20K012521 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Fri, 15 Jul 2005 08:40:02 +0200 Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id 1D5F219E6DC; Fri, 15 Jul 2005 08:40:02 +0200 (CEST) Received: from ext.lri.fr ([127.0.0.1]) by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 00968-02; Fri, 15 Jul 2005 08:40:02 +0200 (CEST) Received: from smtp.lri.fr (serveur3-5 [129.175.3.5]) by ext.lri.fr (Postfix) with ESMTP id 0B13219E61D; Fri, 15 Jul 2005 08:40:02 +0200 (CEST) Received: from pc9-152 (pc9-152 [129.175.9.152]) by smtp.lri.fr (Postfix) with ESMTP id 692E1CED98; Fri, 15 Jul 2005 08:40:01 +0200 (CEST) Received: from filliatr by pc9-152 with local (Exim 3.36 #1 (Debian)) id 1DtJrd-0001Oe-00; Fri, 15 Jul 2005 08:40:01 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <17111.23105.448745.536629@gargle.gargle.HOWL> Date: Fri, 15 Jul 2005 08:40:01 +0200 To: jtbryant@valdosta.edu Cc: caml-list@inria.fr Subject: Re: [Caml-list] Mututal Recursion and Tail Recursion In-Reply-To: <1121281425.30107.36.camel@starlight.valdosta.edu> References: <1121281425.30107.36.camel@starlight.valdosta.edu> X-Mailer: VM 7.19 under Emacs 21.4.1 From: Jean-Christophe Filliatre X-Virus-Scanned: by amavisd-new at lri.fr X-Miltered: at nez-perce with ID 42D75A42.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42D75A42.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 recursion:01 recursion:01 filliatre:01 filliatre:01 lri:01 recursive:01 recursive:01 flatten:01 stack:01 ocamlopt:01 lri:01 filliatr:01 globl:01 globl: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: 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, -- Jean-Christophe Filliātre (http://www.lri.fr/~filliatr) ====================================================================== .data .globl camlTest__data_begin camlTest__data_begin: .text .globl camlTest__code_begin camlTest__code_begin: .data .long 2048 .globl camlTest camlTest: .space 8 .data .long 7415 camlTest__1: .long caml_curry2 .long 5 .long camlTest__flat_out_57 .long 4345 .long caml_curry3 .long 7 .long camlTest__flat_in_58 .text .align 16 .globl camlTest__flat_in_58 .type camlTest__flat_in_58,@function camlTest__flat_in_58: .L101: movl %eax, %edx cmpl $1, %edx je .L100 .L102: movl caml_young_ptr, %eax subl $12, %eax movl %eax, caml_young_ptr cmpl caml_young_limit, %eax jb .L103 leal 4(%eax), %esi movl $2048, -4(%esi) movl (%edx), %eax movl %eax, (%esi) movl %ecx, 4(%esi) movl 4(%edx), %eax movl %esi, %ecx jmp .L101 .align 16 .L100: movl %ebx, %eax movl %ecx, %ebx jmp camlTest__flat_out_57 .L103: call caml_call_gc .L104: jmp .L102 .text .align 16 .globl camlTest__flat_out_57 .type camlTest__flat_out_57,@function camlTest__flat_out_57: .L106: movl %ebx, %ecx cmpl $1, %eax je .L105 movl 4(%eax), %ebx movl (%eax), %eax jmp camlTest__flat_in_58 .align 16 .L105: movl %ecx, %eax ret .text .align 16 .globl camlTest__entry .type camlTest__entry,@function camlTest__entry: .L107: movl $camlTest__1, %eax movl %eax, %ebx addl $16, %eax movl %ebx, camlTest movl %eax, camlTest + 4 movl $1, %eax ret .text .globl camlTest__code_end camlTest__code_end: .data .globl camlTest__data_end camlTest__data_end: .long 0 .globl camlTest__frametable camlTest__frametable: .long 1 .long .L104 .word 4 .word 3 .word 5 .word 3 .word 7 .align 4 ======================================================================