# Homework 8

*Due by 11:59pm on Friday, 7/28*

## Instructions

Download hw08.zip.

**Submission:** When you are done, submit with
`python3 ok --submit`

.
You may submit more than once before the deadline; only the final submission
will be scored. Check that you have successfully submitted your code on
okpy.org.
See Lab 0
for more instructions on submitting assignments.

**Using OK:** If you have any questions about using OK, please
refer to this guide.

**Readings:** You might find the following references
useful:

# Homework Questions

## Scheme

### Question 1

Define the procedures `cadr`

and `caddr`

, which return the second
and third elements of a list, respectively:

```
(define (cddr s)
(cdr (cdr s)))
(define (cadr s)
'YOUR-CODE-HERE
nil
)
(define (caddr s)
'YOUR-CODE-HERE
nil
)
```

Use OK to unlock and test your code:

```
python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr
```

### Conditional expressions

The `cond`

special form is a general conditional expression, similar to
a multi-clause conditional statement in Python. The general form of a
conditional expression is:

```
(cond
(<p1> <el1>)
(<p2> <el2>)
...
(<pn> <eln>)
(else <else-expressions>))
```

consisting of the symbol `cond`

followed by sequences of expressions ```
(<p>
<el>)
```

called *clauses*. The first expression in each pair is a
*predicate*: an expression whose value is interpreted as either being true
or false. In Scheme, *all* values except the special boolean value `#f`

are
interpreted as true values (unlike Python). (Our particular version of the
Scheme interpreter allows you to write `True`

and `False`

in place of
`#t`

and `#f`

, and prints boolean values as `True`

and `False`

. This is not
standard.)

Conditional expressions are evaluated as follows. The predicate `<p1>`

is evaluated first. If its value is `#f`

,
then `<p2>`

is evaluated.
If `<p2>`

's value is also `#f`

, then `<p3>`

is evaluated. This
process continues until the first predicate `<pi>`

is found whose value is true, in
which case the interpreter returns the result of evaluating each of the
corresponding list of consequent expressions `<eli>`

and returning the last
value as the value of the
whole conditional expression. The `else`

keyword, if present, is taken to be
true, so that if none of the `<p>`

's is found to be true,
the interpreter evaluates the `else-expressions`

and returns the last value.
If no clause has a true predicate, the result is
an "unspecified value". Unless some of the consequent expressions have
side-effects, there is no point in having more than one in a list `<eli>`

.

This is a somewhat simplified version of the semantics of `cond`

, covering the
cases we usually encounter.

### Question 2

Using `cond`

, define a procedure `sign`

that returns `-1`

for negative
arguments, `0`

for zero, and `1`

for positive arguments:

```
(define (sign x)
'YOUR-CODE-HERE
nil
)
```

Use OK to unlock and test your code:

```
python3 ok -q sign -u
python3 ok -q sign
```

### Question 3

Implement a procedure called `ordered?`

, which takes a list of numbers and
returns `True`

if the numbers are in nondescending order, and `False`

otherwise.

Hint: The built-in`null?`

function returns whether its argument is`nil`

.

```
(define (ordered? s)
'YOUR-CODE-HERE
nil
)
```

Use OK to unlock and test your code:

```
python3 ok -q ordered -u
python3 ok -q ordered
```

### Question 4

Implement the procedure `nodots`

, which takes a nested list of numbers that
may not be well-formed and returns a nested list with the same content and
structure, but which does not have any dots when displayed. Lists are not
well-formed if they do not properly terminate in a null list. In such cases,
the list will print with a dot before the final item to indicate that its
last two items are contained in a single pair. For example,

`(cons 1 (cons 2 3))`

would print as

`(1 2 . 3)`

for which `nodots`

should substitute

`(1 2 3)`

You may find the built-in

`null?`

and`pair?`

predicates useful.

```
(define (nodots s)
'YOUR-CODE-HERE
nil
)
```

Use OK to unlock and test your code:

```
python3 ok -q nodots -u
python3 ok -q nodots
```

### Sets as Ordered Lists

One way to represent a set is by using an ordered list, where the ordering is used to speed up search (although only by a constant factor). The following few questions explore this idea, assuming a "set" is a Scheme list with no repeated elements that is already ordered from least to greatest.

### Question 5

Define `contains?`

, which returns whether a set `s`

contains value `v`

. The
Python implementation of this procedure is provided for your reference.

```
; Sets as sorted lists
(define (empty? s) (null? s))
(define (contains? s v)
(cond ((empty? s) false)
'YOUR-CODE-HERE
(else nil) ; replace this line
))
; Equivalent Python code, for your reference:
;
; def empty(s):
; return s is Link.empty
;
; def contains(s, v):
; if empty(s):
; return False
; elif s.first > v:
; return False
; elif s.first == v:
; return True
; else:
; return contains(s.rest, v)
```

Use OK to unlock and test your code:

```
python3 ok -q contains -u
python3 ok -q contains
```

### Question 6

Define `add`

, which takes a set `s`

and a value `v`

as arguments. It returns a
representation of a set containing the values in `s`

and the value `v`

. There
should be no repeated elements in the return value.

```
(define (add s v)
(cond ((empty? s) (list v))
'YOUR-CODE-HERE
(else nil) ; replace this line
))
```

Use OK to unlock and test your code:

```
python3 ok -q add -u
python3 ok -q add
```

### Question 7

Define `intersect`

, which returns a set containing only values that appear in
both sets `s`

and `t`

. Your implementation should run in linear time in the
length of the input sets. A Python implementation of this procedure is
provided for your reference.

Also, define `union`

, which returns a set containing all values that appear
in either set `s`

or `t`

.

```
(define (intersect s t)
(cond ((or (empty? s) (empty? t)) nil)
'YOUR-CODE-HERE
(else nil) ; replace this line
))
; Equivalent Python code, for your reference:
;
; def intersect(set1, set2):
; if empty(set1) or empty(set2):
; return Link.empty
; else:
; e1, e2 = set1.first, set2.first
; if e1 == e2:
; return Link(e1, intersect(set1.rest, set2.rest))
; elif e1 < e2:
; return intersect(set1.rest, set2)
; elif e2 < e1:
; return intersect(set1, set2.rest)
(define (union s t)
(cond ((empty? s) t)
((empty? t) s)
'YOUR-CODE-HERE
(else nil) ; replace this line
))
```

Use OK to unlock and test your code:

```
python3 ok -q intersect -u
python3 ok -q intersect
python3 ok -q union -u
python3 ok -q union
```

## Tail-Calls in Scheme

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

We want to implement the `exp`

procedure. So, we write the following
recursive procedure:

```
(define (exp-recursive b n)
(if (= n 0)
1
(* b (exp-recursive b (- n 1)))))
```

Try to evaluate

`(exp-recursive 2 (exp-recursive 2 10))`

You will notice that it will case a maximum recursion depth error. To fix this, we need to use tail recursion! Implement the `exp`

procedure using tail recursion:

```
(define (exp b n)
;; Computes b^n.
;; b is any number, n must be a non-negative integer.
)
```

Use OK to unlock and test your code:

```
python3 ok -q test-exp -u
python3 ok -q test-exp
```

### Question 9: Filter

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 filter is tail recursive!**

Hint: Try writing the function iteratively in Python, then convert into a tail recursive Scheme function.You will also find the built-in

`append`

function useful.`append`

concatenates two Scheme lists, much like the`+`

operator in Python.

```
(define (filter pred lst)
'YOUR-CODE-HERE
)
```

Use OK to unlock and test your code:

```
python3 ok -q test-filter -u
python3 ok -q test-filter
```