Introduction to Programming in ATS:
PrevChapter 3. FunctionsNext

Mutually Defined Tail-Recursion

Suppose that foo and bar are two mutually defined recursive functions. In the body of foo or bar, a tail-call to foo or bar is a mutually recursive tail-call. For instance, the following two functions isevn and isodd are mutually recursive: 

//
fun
isevn (n: int): bool = if n > 0 then isodd (n-1) else true
//
and
isodd (n: int): bool = if n > 0 then isevn (n-1) else false
//

The mutually recursive call to isodd in the body of isevn is a tail-call, and the mutually recursive call to isevn in the body of isodd is also a tail-call. If we want that these two tail-calls be compiled into local jumps, we should replace the keyword fun with the keyword fnx as follows: 

//
fnx
isevn (n: int): bool = if n > 0 then isodd (n-1) else true
//
and
isodd (n: int): bool = if n > 0 then isevn (n-1) else false
//

What the ATS compiler does in this case is to combine these two functions into a single one so that each mutually recursive tail-call in their bodies can be turned into a self tail-call in the body of the combined function, which is then ready to be compiled into a local jump.

When writing code corresponding to embedded loops in an imperative programming language such as C or Java, we often need to make sure that mutually recursive tail-calls are compiled into local jumps. The following function print_multable is implemented to print out a standard multiplication table for nonzero digits: 

fun
print_multable
  ((*void*)) = let
//
#define N 9
//
fnx
loop1
  (i: int): void =
  if i <= N then loop2 (i, 1) else ()
//
and
loop2
  (i: int, j: int): void =
  if j <= i
    then let
      val () = if j >= 2 then print " "
      val () = $extfcall(void, "printf", "%dx%d=%2.2d", j, i, j*i)
    in
      loop2 (i, j+1) 
    end // end of [then]
    else let
      val () = print_newline () in loop1 (i+1)
    end // end of [else]
  // end of [if]
//
in
  loop1 (1)
end // end of [print_multable]

The functions loop1 and loop2 are defined mutually recursively, and the mutually recursive calls in their bodies are all tail-calls. The keyword fnx indicates to the ATS compiler that the functions loop1 and loop2 should be combined so that these tail-calls can be compiled into local jumps. In a case where N is a large number (e.g., 1,000,000), calling loop1 may run the risk of stack overflow if these tail-calls are not compiled into local jumps.

When called, the function print_multable prints out the following multiplication table: 

1x1=01
1x2=02 2x2=04
1x3=03 2x3=06 3x3=09
1x4=04 2x4=08 3x4=12 4x4=16
1x5=05 2x5=10 3x5=15 4x5=20 5x5=25
1x6=06 2x6=12 3x6=18 4x6=24 5x6=30 6x6=36
1x7=07 2x7=14 3x7=21 4x7=28 5x7=35 6x7=42 7x7=49
1x8=08 2x8=16 3x8=24 4x8=32 5x8=40 6x8=48 7x8=56 8x8=64
1x9=09 2x9=18 3x9=27 4x9=36 5x9=45 6x9=54 7x9=63 8x9=72 9x9=81

In summary, the very ability to turn mutually recursive tail-calls into local jumps makes it possible to implement embedded loops as mutually tail-recursive functions. This ability is indispensable for advocating the practice of replacing loops with recursive functions in ATS.

PrevHomeNext
Mutually Recursive FunctionsUpEnvless Functions and Closure-Functions