# Lab 13: Tail Recursion and Streams

*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
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 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
(add-streams (stream-cdr fibs) fibs))))
```

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