Don't be too quick to blame your implementation if it can't run this program. The fault may lie with the semantics of the programming language you are trying to use. For example, dynamic scope rules as in APL or old-fashioned dialects of Lisp make it impossible to handle tail-recursion properly. In other cases, the irnplementors may have felt that improper handling of tail-recursion improves the quality of the debugging environment. In any case, an implementation whose worst defect is its handling of tail-recursion may be quite serviceable if you avoid programming styles that exploit tail-recursion.

The test program above could easily be written as a do loop. Indeed, it could easily be written with no looping or recursion at all. Why would anyone want to write programs that use this much tail-recursion? Scheme answers that this is the wrong question. Scheme asks a different question: Why would anyone write a loop using a special kind of looping expression when they could use tail-recursion?

A special syntax for iteration is sometimes easier to read, and it can save programmers from the assembly language programmer's bane of inventing names for loops. That's why Scheme has do expressions for simple loops and named let for more complex recursions. Both do and named let are derived expressions, meaning that they are regarded as mere abbreviations whose semantics are explained formally in terms of procedure calls. As derived expressions, they add little complexity to Scheme, because they can be ignored by programmers who don't wish to use them. The main drawback of a derived expression is that it adds a reserved word, which is the reason that the number of derived expressions was kept small.

There are several reasons why tail-recursion is heavily used in Scheme. Most important is that it works, it's fundamental, it's simple and elegant, and it's just as efficient as anything else, so why not? Tail-recursion is also central to the continuation-passing style of programming, which we will see next time. Another major stylistic use of tail-recursion is to implement state machines, where each procedure corresponds to a state. For example:

    (define (routinel auxi1iary-state)
      (if (p1 auxiliary-state)
          (routine2 (f1 auxiliary-state))
          (routine3 (g1 auxi1iary-state))))
          
    (define (routine2 auxiliary-state)
      (if (p2 auxiliary-state)
          (routine3 (f2 auxiliary-state))
          (routinei (g2 auxiliary-state))))
          
    (define (routine3 auxiliary-state)
      (if (p3 auxiliary-state)
          (routinei (f3 auxiliary-state))
          (routine2 (g3 auxiliary-state))))
  

For such state machines there are few alternatives to tail-recursion. "Prog" loops or tagbodies would probably be used in an implementation that isn't properly tail-recursive, but they have two drawbacks: Arguments cannot be passed between states except through side effects, and the code for the various states must be rearranged if the states are to be compiled separately. Most other techniques for implementing a state machine are awkward because they amount to constructing the dispatch loop of a special purpose interpreter for some representation of the machine.

It is often easy to change a program so it doesn't use tail-recursion, but why should programmers have to bother? Programming languages are supposed to help programmers get things done, not make their lives more challenging. Ultimately, proper handling of tail-recursion is just one small thing that makes it easier to program. Its major benefit in Scheme has been the conceptual simplicity gained by explaining all control constructs in terms of continuations and recursion.

* * *

Thank you, Jonathan Rees, for giving me information on implementations of Scheme. Suggestions and complaints