Mututal Recursion and Tail Recursion

Mututal Recursion and Tail Recursion

[Jonathan Bryant]

[-- Attachment #1: Type: text/plain, Size: 948 bytes --]

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.

Also, I know that there are ZAM opcodes that indicate a tail recursive
function (TAILCALL, if I am not mistaken) and one or two of the
undocumented compiler options will dump the opcodes.  Could someone
briefly explain what each of those options do so I wouldn't have to take
up everybody's time asking if this is tail recursive?

--Jonathan

-- 
*=========================*
|Jonathan Bryant          |
|Valdosta State University|
|Information Technology   |
|System Operations        |
|-------------------------|
|jtbryant@valdosta.edu    |
|x6358                    |
*=========================*

[-- Attachment #2: list_aux.ml --]
[-- Type: text/plain, Size: 2643 bytes --]

let print l = 
    let rec aux l1 = match l1 with
          []    -> Printf.printf "[]";
        | h::[] -> Printf.printf "%d]" h
        | h::t  -> Printf.printf "%d; " h; aux t in
    Printf.printf "[";
    aux l;;

let print_ll ll =
    let rec aux l1 = match l1 with
          [] -> Printf.printf "[]";
        | h::[] -> print h; Printf.printf "]"
        | h::t -> print h; Printf.printf "; "; aux t in
    Printf.printf "[";
    aux ll;;

let flatten ll =
    let rec flat_out ol oa = match ol with
          []   -> oa
        | h::t -> flat_in h t oa
    and flat_in il ot ia = match il with
          []   -> flat_out ot ia
        | h::t -> flat_in t ot (h::ia) in
    List.rev (flat_out ll []);;

let interpolate l1 l2 =
    let rec inter x y a = match x,y with
          [],[]         -> a
        | [],h::t       -> inter t x (h::a)
        | h::t,[]       -> inter t y (h::a)
        | h1::t1,h2::t2 -> inter y t1 (h1::a) in
    List.rev (inter l1 l2 []);;

let range x m s =
    let rec aux c a = if c > m then a else aux (c + s) (c :: a) in
    List.rev (aux x []);;

let range_ll min max step division =
    let l = range min max step in
    let rec aux1 l1 a1 = match l1 with
          []   -> (List.rev a1)
        | h::t -> aux2 l1 0 [] a1
    and aux2 l2 len a2 a1 =
        if len < division
        then match l2 with
              []   -> aux2 [] division a2 a1
            | h::t -> aux2 t (len + 1) (h::a2) a1
        else aux1 l2 ((List.rev a2)::a1)
    in aux1 l [];;

let _ =
    let min = 1 and max = 5000000 in
    Printf.printf "Generating lists"; flush stdout;
    Printf.printf "."; flush stdout;
    let my_list = range min max 2 in
    Printf.printf "."; flush stdout;
    let my_other_list = range (min + 1) max 2 in
    Printf.printf "."; flush stdout;
    let my_list_list = range_ll min max 1 1 in
    Printf.printf "\n"; flush stdout;
    Printf.printf "\nMy List: "; flush stdout;
    (* print my_list; *)
    Printf.printf "\nMy Other List: "; flush stdout;
    (* print my_other_list; *)
    Printf.printf "\nMy List and My Other List Interpolated: "; flush stdout;
    (* print (interpolate my_list my_other_list); *)
    Printf.printf "\nMy List List: "; flush stdout;
    (* print_ll my_list_list; *)
    Printf.printf "\nMy List List Flattened: "; flush stdout;
    (* print (flatten my_list_list); *)
    Printf.printf "\n\n"; flush stdout;
    if (interpolate my_list my_other_list) = (flatten my_list_list)
    then (
        Printf.printf "The interpolated and flattened lists are equal!\n";
        flush stdout
    ) else (
        Printf.printf "Hmmm...\n";
        flush stdout
    );;

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

[Jean-Christophe Filliatre]

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

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

[Jonathan Bryant]

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

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

[Jacques Garrigue]

From: Jonathan Bryant <jtbryant@valdosta.edu>

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

There are already lots of tail-recursive replacements for the List
module, most notably the one included in Extlib. So if you need to
handle very long lists you can already use them.

The common problem for all these replacements is that they are slower
than the original (non tail-recursive) functions, particularly for
short lists, which are the most frequent ones.

So there is no need to submit this code :-)

(But I wonder whether it would not be a good idea to include a
Safelist module in the standard library...)

Cheers,

Jacques Garrigue