Lab 13: Tail Recursion and Streams

Due at 11:59pm on 08/04/2015.

Starter Files

Download lab13.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

To receive credit for this lab, you must complete Questions 2, 3, 5, 6, 7 in lab13.scm and submit through OK.
Questions 8, 9 is extra practice. It can be found in the lab13_extra.scm file. It is recommended that you complete this problem on your own time.

Tail Recursion

Recall from lecture that Scheme supports tail-call optimization. The example we used was factorial (shown in both Python and Scheme):

# Python
def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

# Scheme
(define (fact n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))

Notice that in this version of factorial, the return expressions both use recursive calls, and then use the values for more "work." In other words, the current frame needs to sit around, waiting for the recursive call to return with a value. Then the current frame can use that value to calculate the final answer.

As an example, consider a call to fact(5) (Shown with Scheme below). We make a new frame for the call, and in carrying out the body of the function, we hit the recursive case, where we want to multiply 5 by the return value of the call to fact(4). Then we want to return this product as the answer to fact(5). However, before calculating this product, we must wait for the call to fact(4). The current frame stays while it waits. This is true for every successive recursive call, so by calling fact(5), at one point we will have the frame of fact(5) as well as the frames of fact(4), fact(3), fact(2), and fact(1), all waiting for fact(0).

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

Keeping all these frames around wastes a lot of space, so our goal is to come up with an implementation of factorial that uses a constant amount of space. We notice that in Python we can do this with a while loop:

def fact_while(n):
    total = 1
    while n > 0:
        total = total * n
        n = n - 1
    return total

However, Scheme doesn't have for and while constructs. No problem! Everything that can be written with while and for loops and also be written recursively. Instead of a variable, we introduce a new parameter to keep track of the total.

def fact(n):
    def fact_optimized(n, total):
        if n == 0:
            return total
        return fact_optimized(n - 1, total * n)
    return fact_optimized(n, 1)

(define (fact n)
    (define (fact-optimized n total)
        (if (= n 0)
            total
            (fact-optimized (- n 1) (* total n))))
    (fact-optimized n 1))

Why is this better? Consider calling fact(n) on based on this definition:

(fact 5)
(fact-optimized 5   1)
(fact-optimized 4   5)
(fact-optimized 3  20)
(fact-optimized 2  60)
(fact-optimized 1 120)
(fact-optimized 0 120)
120

Because Scheme supports tail-call optimization (note that Python does not), it knows when it no longer needs to keep around frames because there is no further calculation to do. Looking at the last line in fact_optimized, we notice that it returns the same thing that the recursive call does, no more work required. Scheme realizes that there is no reason to keep around a frame that has no work left to do, so it just has the return of the recursive call return directly to whatever called the current frame.

Therefore the last line in fact_optimized is a tail-call.

Question 1

To sum it up (with vocabulary!), here is the quote from lecture: "A procedure call that has not yet returned is active. Some procedure calls are tail calls. A Scheme interpreter should support an unbounded number of active tail calls."

A tail call is a call expression in a tail context:

The last body sub-expression in a lambda expression
Sub-expressions 2 and 3 in a tail context if expression
All non-predicate sub-expressions in a tail context cond
The last sub-expression in a tail context and or or
The last sub-expression in a tail context begin

Call expressions in "tail contexts" are tail calls, because there is no reason to keep the current frame "active."

For the following procedures, decide whether each is tail-call optimized. Do not run the procedures (they may not work)!

Check the recursive calls in tail positions (there might be multiple). Is it in a tail context? In other words, does the last recursive call need to return to the caller because there is still more work to be done with it?

List what each of the tail-calls are to help decide if they are optimized.

(define (question-a x)
    (if (= x 0)
        0
        (+ x (question-a (- x 1)))))

The tail call is a +. This is not optimized, because a recursive call is an argument to the call to +.

(define (question-b x y)
    (if (= x 0)
        y
        (question-b (- x 1) (+ y x))))

Tail-call to question-b. It is in sub-expression 3 in a tail context if expression.

(define (question-c x y)
    (if (= x y)
        #t
        (if (< x y)
            #f
            (or (question-c (- x 1) (- y 2)) #f))))

Does not have a tail-call. (question-c would need to be called outside of the or statement or in the last sub-expression)

(define (question-d x y)
    (cond ((= x y) #t)
            ((< x y) #f)
            (else (or #f (question-d (- x 1) (- y 2))))))

There is a tail-call to question-d because it is the last sub-expression in a tail context or statement.

(define (question-e x y)
    (if (> x y)
        (question-e (- y 1) x)
        (question-e (+ x 10) y)))

Both recursive calls are tail-calls. But infinite loop! So please don't do this.

(define (question-f n)
    (if (question-f n)
        (question-f (- n 1))
        (question-f (+ n 10))))

The 2 recursive calls in the non-predicate sub-expressions are tail-calls.

Question 2: Last

Write a function last, which takes in a Scheme list of length 1 or more and returns the last element of the list. Make sure it is tail recursive!

(define (last s)
  'YOUR-CODE-HERE
  (if (null? (cdr s))
      (car s)
      (last (cdr s)))
)

Use OK to unlock and test your code:

python3 ok -q last -u
python3 ok -q last

Question 3: Reverse

Write a tail-recursive function reverse that takes in a Scheme list a returns a reversed copy. Hint: use a helper function!

(define (reverse lst)
  'YOUR-CODE-HERE
  (define (reverse-tail sofar rest)
    (if (null? rest)
          sofar
          (reverse-tail (cons (car rest) sofar) (cdr rest))))
  (reverse-tail nil lst)
)

Use OK to unlock and test your code:

python3 ok -q reverse -u
python3 ok -q reverse

Streams

A stream is another example of a lazy sequence. A stream is a lazily evaluated linked list. In other words, the stream's elements (except for the first element) are only evaluated when the values are needed. In addition, streams are memoized: the elements that have already been computed are saved!

We have many built-in procedures that can manipulate streams:

Stream creation: cons-stream
First of the Stream: car
Rest of the Stream: stream-cdr
Empty Stream: nil
Empty handling: null?

Now we are ready to look at a simple example. This stream is an infinite stream where each element is 1.

scm> (define ones (cons-stream 1 ones))
ones
scm> (car ones)
1
scm> (stream-cdr ones)
(1 . #[promise (forced)])

We start out with a stream whose first element is 1, and whose rest is an unevaluated expression that will lead to another stream. Thus, we can recurse on the name ones that we are trying to define in the first place.

Next, here's one way to build a stream of the natural numbers starting at the nth number.

scm> (define (naturals (n))
       (cons-stream n
         (naturals (+ n 1))))
naturals
scm> (define nat (naturals 0))
nat
scm> (car nat)
0
scm> (car (stream-cdr nat))
1
scm> (car (stream-cdr (stream-cdr nat)))
2

So when we do compute the rest, we get another stream whose first element is one greater than the previous element, and whose rest creates another stream. Hence, we effectively get an infinite stream of integers, computed one at a time. This is almost like an infinite recursion, but one which can be viewed one step at a time, and so does not crash.

Question 4: What would Scheme print?

Use OK to unlock the following questions:

python3 ok -q wwsp -u

The following function has been defined for you.

scm> (define (has-even? s)
       (cond ((null? s) False)
             ((even? (car s)) True)
             (else (has-even? (stream-cdr s)))))
has-even?

scm> (define ones (cons-stream 1 ones))
______
ones
scm> (define twos (cons-stream 2 twos))
______
twos
scm> (has-even? twos)
______
True
scm> (has-even? ones)
______
Infinite loop
scm> (define (foo x) (+ x 1))
______
foo
scm> (define bar (cons-stream (foo 1) (cons-stream (foo 2) bar)))
______
bar
scm> (car bar)
______
2
scm> (define (foo x) (+ x 5))
______
foo
scm> (car bar)
______
2
scm> (stream-cdr bar)
______
(7 . #[promise (not forced)])
scm> (define (foo x) (+ x 7))
______
foo
scm> (stream-cdr bar)
______
(7 . #[promise (not forced)])

Question 5: Interleave

We implemented the stream-to-list function that takes in a stream s and an int num-elements. It returns a list that contains the first num-elements items from the stream s. This is just to visualize streams; you shouldn't be using this function to solve the following problems.

(define (stream-to-list s num-elements)
  (if (or (null? s) (= num-elements 0))
    nil
    (cons (car s)
          (stream-to-list (stream-cdr s)
                          (- num-elements 1)))))

Write the interleave function which takes in two streams:

a1, a2, a3, ...
b1, b2, b3, ...

and returns the new stream

a1, b1, a2, b2, a3, b3, ...

If either of the inputs is finite, the output stream should be finite as well, terminating just at the point where it would be impossible to go on. If both of the inputs are infinite, the output stream should be infinite as well.

(define (interleave-map s1 s2)
  'YOUR-CODE-HERE
  (if (null? s1)
      nil 
      (cons-stream (car s1)
           (interleave-map s2 (stream-cdr s1))))
)

Use OK to unlock and test your code:

python3 ok -q interleave-map -u
python3 ok -q interleave-map

Note: Due to a typo, the function is called interleave-map, even though it doesn't do any mapping. Oops!

Question 6: Filter

Define stream-filter, which takes in a stream s and a predicate pred. stream-filter returns a new stream that filters s based on pred.

(define (stream-filter s pred)
    'YOUR-CODE-HERE
    (cond ((null? s) s)
        ((pred (car s))
            (cons-stream (car s) 
                (stream-filter (stream-cdr s) pred)))
        (else (stream-filter (stream-cdr s) pred)))
)

Use OK to unlock and test your code:

python3 ok -q stream-filter -u
python3 ok -q stream-filter

Question 7: Fibonacci

Let's create an infinite stream of Fibonacci numbers called fibs. To do so, implement the make-fib-stream helper function (try to figure out what a and b are). Remember that the first two Fibonacci numbers are 0 and 1.

(define fibs (make-fib-stream 0 1))
(define (make-fib-stream a b)
  'YOUR-CODE-HERE
  (cons-stream a
       (make-fib-stream b (+ a b)))
)

If the add-streams function has been defined (add-streams is a function that adds the ith elements of two streams together), we can write fibs this way instead:

(define fibs
  (cons-stream 0
    (cons-stream 1
      (add-streams (stream-cdr fibs) fibs))))

Use OK to unlock and test your code:

python3 ok -q fibs -u
python3 ok -q fibs

Extra Questions

The following questions are for extra practice — it can be found in the the lab13_extra.py file. It is recommended that you complete this problem on your own time.

Question 8: Insert

Write a tail-recursive function that inserts number n into a sorted list of numbers, s. s is of at least length 1. Hint: Use the built-in Scheme function append.

(define (insert n s)
  'YOUR-CODE-HERE
  (define (insert-help s so-far)
      (cond ((null? s) (append so-far (cons n s)))
               ((< n (car s)) (append so-far (cons n s)))
               (else (insert-help (cdr s) (append so-far (list (car s)))))))
  (insert-help s nil)
)

Use OK to unlock and test your code:

python3 ok -q insert -u
python3 ok -q insert

Question 9: Cycle

Define a function cycle which takes in as input an ordinary Scheme list and returns a stream which just repeats that list over and over. For example, cycle('(a b c) )) is the stream containing elements (a b c a b c ...). If the input list is empty, output the empty stream; otherwise, the output stream should be infinite.

(define (cycle lst)
  'YOUR-CODE-HERE
  (if (null? lst)
      nil 
      (cons-stream (car lst)
         (cycle (append (cdr lst) (list (car lst))))))
)

Use OK to unlock and test your code:

python3 ok -q cycle -u
python3 ok -q cycle