This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

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: Jean-Christophe Filliatre 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?

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

```