- Streams
- What would Scheme output?
- Functions that output streams
- Question 1
- Question 2
- Higher Order Functions on Streams
- Question 3
- Question 4
- Question 5
- Tail Recursion
- Optional Problems

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

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.

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

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

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

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

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!

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!

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

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.

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

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

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

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

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

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