Try Firefox!

SI413 Scheme Lab XX: List Internals, Tail Recursion and letrec


Recursing well: Efficiency and tail-recursion
Consider the following Scheme function for computing the sum of the square roots of the integers from 1 to n.
(define (ssum n) (if (= n 1) 1 (+ (sqrt n) (ssum (- n 1)))))
It works nicely and all, but it really takes some time to compute something like (ssum 1000000). In fact it pretty much bogs the interpreter down. It bogs the whole machine down. Is this necessary? Why is it happening? Well, it turns out that the problem is that this program takes up a lot of memory. But wait a second? Why is that? Looking at the program it isn't clear how it could take more than constant memory since there are no lists. However, this program is recursive, and each recursive call results in a new function record being pushed onto the call stack. This takes up a lot of space when there are 1,000,000 recursive calls, like there are in (ssum 1000000). This is the dark side of functional programming. There's a hidden penalty for all the convenience (yes, I said "convenience") of programming everything recursively, and that's the memory overhead.

However, there are certain recursive functions that don't require this memory overhead. For example, consider the following alternate definition of ssum:

(define (ssum-tr n e) (if (= n 0) e (ssum-tr (- n 1) (+ (sqrt n) e))))
Note: The second paramter e must be zero in the initial call. The idea behind this function is that e carries arround the "extra" stuff you've already computed. Suppose you were computing
	√1 + √2 + √3 + √4 
i.e. (ssum-tr 4 0). In computing this with ssum-tr you'd end up at some point with a recursive call (ssum-tr 2 3.73) which would indicate that the answer is ssum(4) = ssum(2) + 3.73, i.e.
ssum(2) = √1 + √2 + √3 + √4 = 6.15
          \_____/   \_____/
        =  ssum(2) + 3.732  = 2.414 + 3.732 = 6.15
It's a different way of arriving at the same result. However, lets watch the call stack evolve during ssum-tr's computation of (ssum-tr 4 0):
                                        n=0,e=6.15 ---> Answer!
                             n=1,e=5.15 n=1,e=5.15
                  n=2,e=3.73 n=2,e=3.73 n=2,e=3.73
         n=3,e=2  n=3,e=2    n=3,e=2    n=3,e=2   
n=4,e=0  n=4,e=0  n=4,e=0    n=4,e=0    n=4,e=0   
-------  -------  -------    -------    -------   
 Stack    Stack    Stack      Stack      Stack    
Hopefully what you see is that there's no reason to remember anything beyond the top record on the stack. We have the answer without ever having to do a pop, and if we don't need to do any pops, we didn't need to remember the stuff in the first place. A function like this is called tail recursive.
Definition: A function is tail recursive if its output expression in every recursive case is only the recursive call.
In Scheme, this means that the recursive call is outermost. In C/C++/Java, a tail-recursive function can be identified by looking at the return statement(s) for the recursive case(s): if the recursive call itself is the outermost expression in the return, the function is tail-recursive. The fundamental idea is that the result returned by the recursive call is the answer; nothing else needs to be done with it. In that case, there's no reason to pop records off the stack of recursive calls, and if you're never going to pop them off, they needn't be pushed in the first place.

The function (define (ssum n) (if (= n 1) 1 (+ (sqrt n) (ssum (- n 1))))) is not tail recursive because the output expression in the recursive case is (+ (sqrt n) (ssum (- n 1))), which while it contains a recursive call is not just a recursive call. In constrast, the recursive case of ssum-tr has output expression (ssum-tr (- n 1) (+ (sqrt n) e)) which is just a recursive call.

As we noted above, with tail recursive functions we could actually forget about the stack and only ever remember what would ordinarily be the top record of the stack. Thus, tail recursive functions can be optimized to take less memory - and usually to run faster as well. Scheme interpreters are required to make this optimization whenever functions are defined tail-recursively. Our tail recursive ssum-tr has no trouble computing (ssum-tr 1000000 0) .

Problems
  1. Implement the cos-min function tail-recursively (call it cos-min-tr), where (cos-min i j) whould return the integer in the range [i,j] with the smallest cosine. Here's a regular (non-tail) recursive solution:
    (define (cos-min i j) 
      (if (= i j) 
          j 
          (let ((k (cos-min (+ i 1) j))) (if (< (cos i) (cos k)) i k))))
    	    
    Try it on the range 1 to 10,000,000. Takes a while, eh? Now do it with tail-recursion!
  2. The inverse tangent of x, if -1 < x < 1, is x - x^3/3 + x^5/5 - x^7/7 + x^9/9 - x^11/11 + ... Write a function (inv-tan x i) that approximates the inverse tangent of x using i terms of the above sequence. Write it normally first (inv-tan), then make it tail-recursive (inv-tan-tr)!
    With 1000 terms, the answer should be about 0.7851481634599485

Under the hood with lists in Scheme
We talked about the internals of list representation in scheme - what "cons" does, for example. This immediately led to discussions of garbage collection and how in Scheme, everything's a pointer.

In a nutshell, consider the following:

(define L1 '(1 2 3))
(define L2 (cons 'a L1))
(define L3 (append '(8 9) L2))
The second line creates a new list (a 1 2 3) and gives it the name L2. It hasn't modified L1 in any way, so it's not like pushing a new element on top of the stack which, of course, modifies the stack. Since we have two distinct lists (1 2 3) and (a 1 2 3), it would seem that the interpreter would've created 7 list nodes. However, recall that we have referential transparency, i.e. nothing is ever modified. Therefore, there's no harm done if the linked lists that store L2 and L1 share nodes. Same goes for L3. In fact, internally, these three lists with a total of 13 data values are represented internally by 6 nodes:

This means that (cdr L) and (cons x L) are constant time operations (make sure you see why), i.e. they take the same amount of time regardless of the size of L. How about (append L1 L2)? How does its running time depend on the length of L1 and the length of L2? Think carefully about this and make sure you know the answer!

This sharing of nodes has an important consequence: When the name L1 goes out of scope, the interpreter can't necessarily reclaim its nodes. Indeed, in this example, if L2 or L3 are still in scope, none of L1's nodes can be reclaimed. What if L3 goes out of scope? Then the first two nodes can be reclaimed, but not the rest. In general, when this sharing of nodes occurs it becomes very difficult to determine which nodes can be reclaimed. It's completely impractical to expect the programmer to do it, and really undesireable too, since Scheme programmers are supposed to think of lists abstractly, and not bother with the details of how the interpreter implements them. Thus, Scheme really requires automatic garbage collection, meaning that the interpreter has to figure out which nodes can be reclaimed.

More functions creating functions: letrec
The function (pair-with x L) is an interesting one.
(define (pair-with x L) (map (lambda (i) (list x i)) L))
	
Why? Because pair-with includes a lambda expression that defines a different function each time pair-with is called: Each time pair-with is called with a different x value, the function created by that lambda-expression is different. So here's an example of a function that creates new functions dynamically.

To really be able to create any function on-the-fly with a lambda expression, we need some way to define recursive functions in lambda expressions. With what we've seen so far that's not possible, because we have no name to use for the function in the recursive call. Scheme's solution to this is a special variant of let called letrec. In a normal let you can't use a name from the name-value list inside the name value list. In letrec, you can use a name from any point after its first appearance. The following expression evaluates to a factorial function:

(letrec 
  ( (f (lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))) ) 
  f)
This is a nice way of creating tail-recursive function definitions without lots of named helper-functions. For example, this definition of (power x k) is nice and efficiently implemented with tail-recursion:
(define (power x k)
  (letrec ((pow (lambda (exp c) (if (= exp 0) c (pow (- exp 1) (* x c))))))
    (pow k 1)))


Christopher W Brown
Last modified: Mon Sep 14 09:47:34 EDT 2009