Lab 13: Streams and Tail Recursion

Table of Contents

Deadline

By the end of this lab, you should have submitted the lab13 assignment using the command submit lab13.

This lab is due by 11:59pm on 8/7/2014.

We have provided the following starter file: lab13.scm

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:

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

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

Notice what is happening here. 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.

 (define naturals
   (cons-stream 0
     (stream-map (lambda (x) (+ x 1))
                 naturals)))

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.

What would Scheme output?

These questions are meant to help you gain confidence in writing streams code in Scheme. Please type the following into the interpreter. Guess what outputs, and see if the results are the same or different.

STk> (define ones (cons-stream 1 ones))
______
STk> (define twos (cons-stream 2 twos))
______
STk> (ss (interleave ones twos)) ; The ss command is very useful!
______
STk> (define (has-even? s)
...    (cond ((stream-null? s) #f)
...          ((even? (stream-car s)) #t)
...          (else (has-even? (stream-cdr s)))))
______
STk> (has-even? twos)
______
STk> (has-even? ones)
______
STk> (define (foo x) (+ x 1))
______
STk> (define bar (cons-stream (foo 1) (cons-stream (foo 2) bar)))
______
STk> (stream-car bar)
______
STk> (define (foo x) (+ x 5))
______
STk> (stream-car bar)
______
STk> (stream-cdr bar)
______
STk> (define (foo x) (+ x 7))
______
STk> (stream-cdr bar)
______
STk> (define baz (stream-map foo ones))
______
STk> (ss baz)
______
STk> (define (boom x y) (+ x y))
______
STk> (ss (stream-map boom baz twos))
______

Functions that output streams

We do not need to limit ourselves to predefined streams or the built-in stream functions for the rest part of cons-streams. We can actually define our own functions that output streams. It's important to consider domain and range here, as well as the myriad ways to combine streams now that we can write our own stream-outputting functions. Try out this example:

STk> (define (start-naturals x) (cons-stream x (start-naturals (+ 1 x))))
______
STk> (ss (start-naturals 0))
______
STk> (ss (stream-filter (lambda (x) (= (remainder x 2) 0)) (start-naturals 0)))
______
STk> (ss (interleave (start-naturals 0) (start-naturals 10)))
______

Question 1

Define implicitly an infinite stream multiples-of-three that contains the multiples of 3. Do not use any helper functions.

(define multiples-of-three
  'YOUR-CODE-HERE)

;; Doctests for multiples-stream
(assert-equal 1 "multiples-stream"
	      (ss multiples-of-three)
	      '(3 6 9 12 15 18 21 24 27 30 ...))
(define multiples-of-three
  (cons-stream 3
    (stream-map (lambda (x) (+ x 3)) multiples-of-three)))

Question 2

Guess what the following code does before typing it into the interpreter.
STk> (define (foo x) (* x x))
______
STk> (define (foo-stream x) (cons-stream (foo x) (foo-stream x)))
______
STk> (define bar (foo-stream 2))
______
STk> (stream-car bar)
______
STk> (stream-car (stream-cdr bar))
______
STk> (define (foo x) x)
______
STk> (ss bar)
______

Higher Order Functions on Streams

Naturally, as the theme has always been in this class, we can abstract our stream procedures to be higher order.

STk> (define big-stream (stream-enumerate-interval 1 100000))
______
STk> (ss big-stream)
______
STk> (define big-evens (stream-filter even? big-stream))
______
STk> (stream-cdr big-evens)
______
STk> (ss big-evens)
______
STk> (stream-cdr big-evens)
______

Notice how the stream we create has as its rest a promise to filter out the rest of the stream when asked. So at any one point, the entire stream has not been filtered. Instead, only the part of the stream that has been referenced has been filtered, but the rest will be filtered when asked. We can model other higher order Stream procedures after this one, and we can combine our higher order Stream procedures to do incredible things!

Question 3

Define a function find which takes in as input a stream and a predicate, and returns the first element in the stream satisfying the predicate.

Note: Consider the case where there is no element in the stream satisfying the predicate. Could we add to the specification that this function must return okay in that case? Explain the difficulty implementing such a specification, and the conditions under which one can and cannot meet it.

(define (find stream predicate)
  'YOUR-CODE-HERE)

; Doctests for find
(define m (cons-stream 1 (cons-stream 2 the-empty-stream)))
(assert-equal 1 "find" (find m even?) 2)
(assert-equal 2 "find" (find m (lambda (x) (= x 3))) 'okay)
(assert-equal 3 "find" (find m (lambda (x) (= x 1))) 1)
(define (find stream predicate) 
  (if (stream-null? stream)
      'okay
      (if (predicate (stream-car stream))
	  (stream-car stream)
	  (find (stream-cdr stream) predicate))))

Note: The exception can only be reached on finite streams Find will simply run forever on infinite streams which lack a suitable element!

Question 4

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)

; Doctests for cycle
(define n '(1 2 3))
(assert-equal 1 "cycle" (ss (cycle n)) '(1 2 3 1 2 3 1 2 3 1 ...))
(define o nil)
(assert-equal 2 "cycle" (cycle o) the-empty-stream)
(define (cycle lst)
  (if (null? lst)
      the-empty-stream
      (cons-stream (car lst) 
		   (cycle (append (cdr lst) (list (car lst)))))))

Question 5

Recall that a stream remembers elements it has previously computed and does not recompute them. This can play in unexpected ways with computations whose values may change over time (so-called "impure" computations).

Suppose one wants to define a random infinite stream of numbers via the recursive definition "A random infinite stream consists of a first random number, followed by a remaining random infinite stream". Consider an attempt to implement this via the code:

(define random-stream (cons-stream (random 100) random-stream))

What it is unsatisfactory about this?

The provided code will generate a single random number, and then produce an infinite stream which simply repeats that one number over and over.

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 its recursive call returns:. (fact 5) returns whatever (fact-optimized 5 1) returns; (fact-optimized 5 1) returns whatever fact-optimized 4 5) returns; etc. Thus the Scheme interpreter kills the intermediate frames since we no longer need them to produce the solution. We say that the last line in fact_optimized is a tail-call.

One way to identify tail calls is by identifying tail contexts:

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

Question 6

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 of 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.

Question 7

Write a function last, which takes in a Scheme list and returns the last element of the list. Make sure it is tail recursive! The tests don't check, but our autograder will!

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

Question 8

Write a function filter, which takes in a predicate and a Scheme list and returns a Scheme list whose elements are the elements from the inputted Scheme list that satisfy the predicate. Make sure it is tail recursive! The tests don't check, but our autograder will!

(define (filter pred lst)
  'YOUR-CODE-HERE)
(define (filter pred lst)
  (define (helper lst so-far)
    (if (null? lst)
	so-far
	(if (pred (car lst))
	    (helper (cdr lst) (append so-far (list (car lst))))
	    (helper (cdr lst) so-far))))
  (helper lst '()))

Optional Problems

Question 9

We want to implement starts-with from homework 3 in Scheme. Recall that starts-with is supposed to return #t if sublst is a prefix of lst (that is, if lst starts with sublst), and #f otherwise. Note that unlike homework 3, we assume that sublst will never be longer than lst.

Here are three implementations. For each implementation:

a) Does it work?

b) Is it tail recursive?

(define (starts-with-a lst sublst)
  (or (null? sublst)
      (and (equal? (car lst) (car sublst))
	   (starts-with-a (cdr lst) (cdr sublst)))))
a) Yes, it is a valid implementation. (try it out in the interpeter!)

b) Yes, it is tail recursive, because there is a tail call to starts-with in the last sub-expression in a tail context and statement.

(define (starts-with-b lst sublst)
  (or (null? sublst)
      (and (starts-with-b (cdr lst) (cdr sublst))
	   (equal? (car lst) (car sublst)))))
a) Yes, it is a valid implementation.

b) No, it is not tail recursive, because, like question-c, the recursive call to starts-with is not a tail call.

(define (starts-with lst sublst)
  (or (and (equal? (car lst) (car sublst))
	   (starts-with (cdr lst) (cdr sublst)))
      (null? sublst)))
a) No, this is not a valid implementation. It will break on the case that sublst is a null list.

b) No, it is not tail recursive.

Question 10

Remember in calculus that we can make pretty good approximations like e, cos, and sin using power series. For instance, we have e^x = 1 + x + x^2/2! + x^3/3! + ...

First, define a stream whose elements are closer and closer approximations to e^x. This means the first element is 1, the second is x, the third is x^2/2! and so forth.

Hint: Speaking of calculus, here is a quote from Rene Descartes:

"Divide each of the difficulties under examination into as many parts 
as possible, and as might be necessary for its adequate solution."

You should also use your naturals stream, which starts from 1.

; Note: Helper code will help!
(define (e-to-the x)
  'YOUR-CODE-HERE)

; Doctests for e-to-the
(assert-equal 1 "e-to-the"
	      (< (abs (- (stream-ref (e-to-the 2) 10) 7.3890561)) 0.0001)
	      #t)
(define (factorial n)
  (if (<= n 1)
      1
      (* n (factorial (- n 1)))))
(define (compute-term x count)
  (* (/ 1 (factorial count)) (expt x count)))

(define (term-stream x) (stream-map (lambda (count) (compute-term x count)) naturals))
(define (e-to-the x) 
  (cons-stream (stream-car (term-stream x))
	       (add-streams (stream-cdr (term-stream x)) (e-to-the x))))

Question 11

Note that to get the cosine stream, all one has to do is just change the way each term is computed. Let's write a general function power-series that does the same thing as e-to-the, but takes in a function to compute the term this time.
(define (power-series x compute-term)
  'YOUR-CODE-HERE)

;; Doctests for power-series
(define (sine-term x count)
  (* (/ (expt -1 count) (factorial (+ (* 2 count) 1)))
     (expt x (+ (* 2 count) 1))))
;; Do not change this test
(define sin-series (power-series 3 sine-term))
(define error (< (abs (- (stream-ref sin-series 10) (sin 3))) 0.00001))
(assert-equal 1 "power-series" error #t)
(define (power-series x compute-term)
  (define (term-stream x) (stream-map (lambda (count) (compute-term x count)) naturals))
  (cons-stream (stream-car (term-stream x))
	       (add-streams (stream-cdr (term-stream x)) (power-series x compute-term))))

Now, all it takes to calculate derivatives and integrals of these functions is to properly implement a deriv or integrate function and then map them on the stream you created, right?