Tail calls

A tail call is one that occurs as the very last step in a method. A clever compiler can implement tail calls without growing the stack; instead the current call frame is replaced by the frame for the tail call. The Java Virtual Machine does not support tail calls, but they can be simulated. (This is pretty ironic, considering that tail calls were popularised by Guy Steele, one of the three principal designers of Java [SS76].) The simulation is expensive in time: in Pizza, tail calls cost an order of magnitude more than ordinary calls. But since tail calls don't add to the stack, they can be nested arbitrarily deep.

For instance, one can simulate a finite-state machine by defining method for each state, which calls the method for the next state with a tail call. This can be very flexible: you don't need to decide in advance what different states exist, you just define one method for each state as required. To achieve the same effect without tail calls, you need to have each routine return an object that contains the next method to be called, which is how tail calls are implemented in Pizza.

Tail calls are indicated by placing goto in front of the call. Methods that may contain a tail call or be the target of a tail call are indicated by writing continue in the declaration. (Both goto and continue are already reserved words in Java.)

As an example, here is a routine that processes text, counting for each pair of parentheses the number of items (separated by commas) between them, and signalling an error if any item is empty or if parentheses are nested or do not match.

Example 5.1 Tail calls in Pizza.

class Counter {
  final char EOF = (char)0;
  InputStream in;
  Counter (InputStream i) { in = i; }
  char next () {
    int c = in.read();
    if (c == -1) return EOF; else return (char)c;
  }
  continue void normal () {
    switch (next()) {
      case EOF: goto done ();
      case '(': goto startitem (0);
      default: goto normal ();
    }
  }
  continue void startitem (int count) {
    switch (next()) {
      case EOF: goto error ();
      case ')': goto error ();
      case ',': goto error ();
      default: goto insideitem (count);
    }
  }
  continue void insideitem (int count) {
    switch (next()) {
      case EOF: goto error ();
      case ')': System.out.println("count " + count); goto normal ();
      case ',': goto startitem (count+1);
      default: goto insideitem (count);
    }
  }
  continue void done {
    System.out.println("done");  return;
  }
  contine void error {
    System.out.println("error");  return;       
  }
  static public void main (String[] args);
    new Counter(System.in).normal();
  }
}