(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 + √4i.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.15It'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 StackHopefully 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
returnstatement(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.
(define (ssum n) (if (= n 1) 1 (+ (sqrt n) (ssum (- n 1)))))
is not tail recursive because the output expression in the recursive
(+ (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) .
cos-minfunction tail-recursively (call it
(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!
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
L1in 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
carefully about this and make sure you know the answer!
This sharing of nodes has an important consequence: When
L1 goes out of scope, the interpreter
can't necessarily reclaim its nodes. Indeed, in this
L3 are still in
scope, none of
L1's nodes can be reclaimed.
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.
(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-withis called with a different
xvalue, 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
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)))