# Lab 13: Streams and Tail Recursion

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:

• List creation: `cons-stream`, `stream-car`, `stream-cdr`
• Higher-order: `stream-map`, `stream-filter`
• Empty handling: `the-empty-stream`, `stream-null?`
• Other: `interleave`, `stream-ref`, `stream-enumerate-interval`

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))
______ones
STk> (define twos (cons-stream 2 twos))
______twos
STk> (ss (interleave ones twos)) ; The ss command is very useful!
______(1 2 1 2 1 2 1 2 1 2 ...)
STk> (define (has-even? s)
...    (cond ((stream-null? s) #f)
...          ((even? (stream-car s)) #t)
...          (else (has-even? (stream-cdr s)))))
______has-even?
STk> (has-even? twos)
______#t
STk> (has-even? ones)
______Infinite loop
STk> (define (foo x) (+ x 1))
______foo
STk> (define bar (cons-stream (foo 1) (cons-stream (foo 2) bar)))
______bar
STk> (stream-car bar)
______2
STk> (define (foo x) (+ x 5))
______foo
STk> (stream-car bar)
______2
STk> (stream-cdr bar)
______(7 . #[promise 2479f0 (not forced)])
STk> (define (foo x) (+ x 7))
______foo
STk> (stream-cdr bar)
______(7 . #[promise 2479f0 (not forced)])
STk> (define baz (stream-map foo ones))
______baz
STk> (ss baz)
______(8 8 8 8 8 8 8 8 8 8 ...)
STk> (define (boom x y) (+ x y))
______boom
STk> (ss (stream-map boom baz twos))
______(10 10 10 10 10 10 10 10 10 10 ...)``````

### 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))))
______start-naturals
STk> (ss (start-naturals 0))
______(0 1 2 3 4 5 6 7 8 9 ...)
STk> (ss (stream-filter (lambda (x) (= (remainder x 2) 0)) (start-naturals 0)))
______(0 2 4 6 8 10 12 14 16 18 ...)
STk> (ss (interleave (start-naturals 0) (start-naturals 10)))
______(0 10 1 11 2 12 3 13 4 14 ...)``````

### 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))
______foo
STk> (define (foo-stream x) (cons-stream (foo x) (foo-stream x)))
______foo-stream
STk> (define bar (foo-stream 2))
______bar
STk> (stream-car bar)
______4
STk> (stream-car (stream-cdr bar))
______4
STk> (define (foo x) x)
______foo
STk> (ss bar)
______(4 4 2 2 2 2 2 2 2 2 ...)``````

### 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))
______big-stream
STk> (ss big-stream)
______(1 2 3 4 5 6 7 8 9 10 ...)
STk> (define big-evens (stream-filter even? big-stream))
______big-evens
STk> (stream-cdr big-evens)
______(4 . #[promise xxxxxx (not forced)])
STk> (ss big-evens)
______(2 4 6 8 10 12 14 16 18 20 ...)
STk> (stream-cdr big-evens)
______(4 . #[promise xxxxxx (forced)])``````

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))``

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

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 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:

• 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."

### 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?