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 isnil
.
(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?
andpair?
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