Lisp Values – ‘Values’ vs ‘List’ for Returning Multiple Values from Lisp Form

A Lisp list is not really terminated with an empty list -- it's terminated with a special value, traditionally called nil. As it happens, that also traditionally evaluates as false -- which makes it about as close to C's null pointer as you can get (in C, a null pointer constant is an integer constant equal to zero, which also evaluates to false).

An empty list is basically just a rather short-hand way of expressing NIL -- since you don't even have a single cons cell, all you're left with is the NIL that terminates the list. In other words, it's not that a list is terminated with an empty list -- it's that an empty list consists of only a terminator.

Using dot notation, it's possible to link cons cells together in other ways, but the result isn't a "list" as the term is normally used.

Essentially with tail recursion, the problem with recursion in general is that you each function call gets it's own stack frame. In this stack frame you store all your local variables and whatnot.

So if you run a function like

  int fact(int n){
      if(n == 0)
           return 1;
      return n * fact(n-1);
  }

fact is called n times, allocating n stackframes. If n is big, that's a lot of memory.

There is hope however, when our function is structured in the form

 int f(int x){
     ...
     return g(foo); // Function call is in the final position
 }

Then we can throw away f's stack frame before entering g, this means that we won't allocate too many frames as long as we're using simple tail calls. It will actually compile to each function having it's own label and jmping to the tail called function, very fast.

All Schemes is tail recursive, as are most functional languages' implementations like those of SML, OCaml, Haskell, Scala, and (kind of) Clojure. This means that whenever you have a function call as the absolute last thing in your function, it won't allocate a new stack frame. Using this, we can write a do-while loop as follows in Scheme

  (define (do-while pred body)
     (body)                   ;; Execute the body
     (if (pred)               ;; Check the predicate
         (do-while pred body) ;; Tail call
         '()))                ;; Exit

And this runs in exactly the same amount of space as the equivalent imperative code would :) Pretty nifty.

Note, Tail Call Optimization /= Tail Recursion

A common misconception is that TCO is strictly confined to the case where a function tail calls itself. This is a specific subset of TCO and what most JVM languages provide. Languages like Scheme which aren't restricted by the JVM's limitations are properly TCO'd making it possible to say write a DFA which will run in constant memory by tail calling between states.