Tail-Recursive Functions

Probably the single most important optimization performed by the ATS/Anairiats compiler is the translation of tail-recursive function calls into direct (local) jumps.

Tail-Recursion

When applied to an integer n, the following defined function sum1 sums up integers from 1 to n.

// [sum1] is recursive but not tail-recursive
fun sum1 (n: int): int = if n > 0 then n + sum1 (n-1) else 0

This function is recursive but not tail-recursive. The stack space it consumes is proportional to the value of its argument. Essentially, the ATS compiler translates the definition of sum1 into the following C code:

int sum1 (int n) {
  if (n > 1) return n + sum1 (n-1) ; else return 1 ;
}

When applied to an integer n, the following defined function sum2 also sums up integers from 1 to n.

fn sum2 (n: int): int = let // sum2 is non-recursive
  // [loop] is tail-recursive
  fun loop (n: int, res: int): int =
    if n > 0 then loop (n-1, res+n) else res
  // end of [loop]
in
  loop (n, 0)
end // end of [sum2]

The inner function loop in the definition of sum2 is tail-recursive. The stack space consumed by loop is a constant independent of th value of the argument of sum2. Essentially, the ATS compiler translates the definition of sum2 into the following C code:

int sum2_loop (int n, int res) {
  loop:
  if (n > 1) {
    res = res + n ; n = n - 1; goto loop; 
  } else {
    // do nothing
  }
  return res ;
}

int sum2 (int n) { return sum2_loop (n, 0) ; }

Mutual Tail-Recursion

Sometimes, mutually tail-recursive functions are encountered. For instance, in the following example, the functions even and odd are mutually tail-recursive.

// [fn*] indicates the need to combine two or more functions
// so as to translate tail-recursive calls into direct jumps
fn* even (n: int): bool = if n > 0 then odd (n-1) else true
and odd (n: int): bool = if n > 0 then even (n-1) else false

The keyword fn* is used to indicate to the ATS compiler that the functions even and odd need to be combined together so as to turn (mutually) tail-recursive function calls into direct jumps. Essentially, the ATS compiler emits the following C code after compiling this example:

bool even_odd (int tag, int n) {

bool res ;

switch (tag) {
  0: goto even ;
  1: goto odd ;
  default : exit (1) ;
}

even: if (n > 0) { n = n - 1; goto odd; } else { res = true; goto done; }

odd: if (n > 0) { n = n - 1; goto even; } else { res = false; goto done; }

done: return res ;

} /* end of [even_odd] */

bool even (int n) { return even_odd (0, n) ; }
bool odd (int n) { return even_odd (1, n) ; }

Note that mutually recursive functions can be combined in such a manner only if they all have the same return type. In the above case, both even and odd have the same return type bool.

When translating C code involving embedded loops, we often encounter mutual tail-recursion. For instance, the following C code prints out ordered pairs of digits:

int main (int argc, char *argv[]) {
  int i, j ;

  for (i = 0; i <= 9; i += 1) {
    for (j = i; j <= 9; j += 1) {
      if (i < j) printf (", ") ; printf ("(%i, %i)", i, j) ;
    } /* for */
    printf ("\n") ;
  } /* for */

  return 0 ;
}

A straightforward translation of the C code into ATS (in functional style) is given as follows:

implement main (argc, argv) = let
  fn* loop1 {i:nat} (i: int i): void =
    if i <= 9 then loop2 (i, i) else ()
  // end of [loop1]

  and loop2 {i,j:nat} (i: int i, j: int j): void =
    if j <= 9 then begin
      if i < j then begin
        print ", "; printf ("(%i, %i)", @(i, j)); loop2 (i, j+1)
      end // end of [if]
    end else begin
      print_newline (); loop1 (i+1)
    end // end of [if]
  // end of [loop2]
in
  loop1 0
end // end of [main]

where the mutually tail-recursive funtions loop1 and loop2 correspond to the outer and inner loops in the C code, respectively.

The code used for illustration is available here.