Homework 7
Due by 11:59pm on Thursday, 4/6
Instructions
Download hw07.zip.
Our course uses a custom version of Scheme (which you will build for Project 4) included in the starter ZIP archive. To start the interpreter, type
python3 scheme
. To run a Scheme program interactively, typepython3 scheme -i <file.scm>
. To exit the Scheme interpreter, type(exit)
.
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:
Hinting
Homework 7 includes a hinting sytem that generates hints
specifically for your submitted code. If you ever find yourself stuck, you can
ask for hints by using adding the --hint
flag to the ok command.
$ python3 ok -q pow --hint
...
Hint: There are extra parentheses on line ...
The system tries to generate hints specific to your program by applying multiple techniques, including:
- simple pattern matching
- program verification
- program synthesis
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: Pow
Implement a procedure pow
for raising the number b
to the power of a nonnegative integer
n
that runs in Θ(log n) time.
Hint: Consider the following observations:
- b2k = (bk)2
- b2k+1 = b(bk)2
You may use the built-in predicates
even?
andodd?
.
(define (square x) (* x x))
(define (pow b n)
'YOUR-CODE-HERE
)
Use OK to unlock and test your code:
python3 ok -q pow -u
python3 ok -q pow
Question 4
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 5
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 6
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 7
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 8
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
Question 9: Survey
Please fill out the midsemester survey. You will receive a passphrase after finishing the survey to submit with the homework.
(define (survey)
'passphrase-here
)
Use OK to unlock and test your code:
python3 ok -q survey -u
python3 ok -q survey