English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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: 2005-07-15 (06:40)
From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@l...>
Subject: Re: [Caml-list] Mututal Recursion and Tail Recursion

Jonathan Bryant writes:
 > Is is possible to have mutually recursive functions that are also tail
 > recursive?  


 > 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)

	.globl	camlTest__data_begin
	.globl	camlTest__code_begin
	.long	2048
	.globl	camlTest
	.space	8
	.long	7415
	.long	caml_curry2
	.long	5
	.long	camlTest__flat_out_57
	.long	4345
	.long	caml_curry3
	.long	7
	.long	camlTest__flat_in_58
	.align	16
	.globl	camlTest__flat_in_58
	.type	camlTest__flat_in_58,@function
	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
	movl	%ebx, %eax
	movl	%ecx, %ebx
	jmp	camlTest__flat_out_57
.L103:	call	caml_call_gc
.L104:	jmp	.L102
	.align	16
	.globl	camlTest__flat_out_57
	.type	camlTest__flat_out_57,@function
	movl	%ebx, %ecx
	cmpl	$1, %eax
	je	.L105
	movl	4(%eax), %ebx
	movl	(%eax), %eax
	jmp	camlTest__flat_in_58
	.align	16
	movl	%ecx, %eax
	.align	16
	.globl	camlTest__entry
	.type	camlTest__entry,@function
	movl	$camlTest__1, %eax
	movl	%eax, %ebx
	addl	$16, %eax
	movl	%ebx, camlTest
	movl	%eax, camlTest + 4
	movl	$1, %eax
	.globl	camlTest__code_end
	.globl	camlTest__data_end
	.long	0
	.globl	camlTest__frametable
	.long	1
	.long	.L104
	.word	4
	.word	3
	.word	5
	.word	3
	.word	7
	.align	4