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:
cons-stream
, stream-car
, stream-cdr
stream-map
, stream-filter
the-empty-stream
, stream-null?
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?
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:
lambda
expressionif
expressioncond
and
or or
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)))))
+
. 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))))
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))))
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))))))
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)))))
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)))))
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)))
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?