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

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

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