Re: [Caml-list] Mututal Recursion and Tail Recursion

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

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