Tail-Recursive Functions


Probably the single most important optimization performed by the ATS/Geizella 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 = // sum2 is non-recursive
  // [loop] is tail-recursive
  let fun loop (n: int, res: int) = if n > 0 then loop (n-1, res+n) else res in
    loop (n, 0)
  end
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 {
    res = 1;
  }
  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) 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 ;

}

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) ;
    }
    printf ("\n") ;
  }

  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 ()

and loop2 {i,j:nat} (i: int i, j: int j): void =
  if j <= 9 then begin
    if i < j then print ", "; printf ("(%i, %i)", @(i, j)); loop2 (i, j+1)
  end else begin
    print_newline (); loop1 (i+1)
  end
in
  loop1 0
end
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.