How can Lisp produce an iterative process from a recursive procedure?

Question

I am starting to learn Lisp, using the SICP book. The authors mention that a procedure (i.e. function) can be recursive or iterative. Additionally, the process those procedures will generate will also be recursive or iterative, and that, surprisingly, a recursive procedure can sometimes generate an iterative process.

The example given is the factorial procedure, which is a recursive procedure, but which generates an iterative process:

(define factorial n)
    (iter 1 1 n))

(define (iter product counter max-count)
    (if (> counter max-count)
        product
        (iter (* counter product)
              (+ counter 1)
              max-count)))

And here's a quotation from the book:

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. The implementation of Scheme we shall consider does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure.

Question: I understood the principles involved (i.e. the what) but I still don't understand how the Lisp interpreter/compiler will generate an iterative process from a recursive function, being able to calculate it using constant space, and why most other languages are not able to do it.

Look up *tail recursion*. Basically this is possible only if every iteration performs the same operation on the same set of variables, with no branching, variation, or post-operation cleanup. That allows you to reuse all variables instead of allocating a new stack frame for each step. — Kilian Foth, Feb 03 '14 at 11:17
It's not that most other languages couldn't do that. They just don't care much about it, so they don't require it in the language standard and common implementations don't bother with it either. — , Feb 03 '14 at 11:19
@delna Why the SICP author (Jay Sussman) then says that not being able to do that is a "defect" of other languages? — Daniel Scocco, Feb 03 '14 at 11:23
@KilianFoth That makes sense. Why wouldn't other languages do that though? Wouldn't it save memory and make the process slightly faster? — Daniel Scocco, Feb 03 '14 at 11:26
At least in the part you quote, I don't see any claim that they are *unable* to do so, just that they don't *do* so. The "defect" is the lack of TCO, not anything in the language design making TCO impossible. — , Feb 03 '14 at 11:29
@daniels It's a mixture of low demand (many programmer don't care about recursion), additional implementation effort (you have to detect the preconditions for tail recursion, or introduce a new keyword to declare them), and other factors (e.g. the JVM doesn't optimize tail calls, so none of the shiny new languages running on top of it can support tail recursion). — Kilian Foth, Feb 03 '14 at 11:37
@KilianFoth: That's not true in general. Some of these shiny new languages perform their own TCO and just generate iterative bytecode. F.ex., Scala even has a `@tailrec` annotation, which guarantees you tail recursiveness if the compile runs error-free. — Frank, Feb 03 '14 at 13:51
@KilianFoth General tail call optimization (TCO) requires a general GOTO (JUMP) operation in the "machine language". The Java Virtual Machine specifically does not provide such an operation, making general TCO impossible in language implementations targeting the JVM. Tail recursion optimization requires a local jump, which the JVM does provide. HAVING SAID THAT, I know of no reason why a NATIVE CODE Java implementation, as opposed to a JVM implementation, could not do general TCO, and in this, the end days of 2020, there is no excuse for NOT doing it if you can. — John R. Strohm, Nov 08 '20 at 11:03
@KilianFoth Read the various "Lambda: The Ultimate ..." papers from the MIT-AI Lab. They go into this in some details. One of them in particular shows that tail recursion optimization is actually a straightforward code generation optimization: if the "recursion" turns out not to need to return to a previous level, and a stack frame turns out not to be needed, then there is no need to generate a new stack frame or push a return address when the "recursive call" is done. This effectively turns the CALL (or JSR, or PUSHJ) instruction into a simple JMP (or BRA) instruction. — John R. Strohm, May 31 '21 at 20:47

daniel gratzer · Accepted Answer · 2014-02-03T14:19:28.777

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.

@DocBrown In the case of Scheme the standard specifies that all conforming languages are TCO'd. Of course this is not the case of all languages and TCO is usually just that, a compiler optimization. — daniel gratzer, Feb 03 '14 at 14:21

How can Lisp produce an iterative process from a recursive procedure?

1 Answers1

Note, Tail Call Optimization /= Tail Recursion