Homework 6: Scheme
Due by 11:59pm on Monday, November 4
Instructions
Download hw06.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:
Grading: Homework is graded based on effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points. This homework is out of 2 points.
Scheme Editor
How to launch
In your hw06
folder you will find a new editor. To run this editor, run python3 editor
. This should pop up a window in your browser; if it does not, please navigate to localhost:31415 and you should see it.
Make sure to run python3 ok
in a separate tab or window so that the editor keeps running.
Features
The hw06.scm
file should already be open. You can edit this file and then run Run
to run the code and get an interactive terminal or Test
to run the ok
tests.
Environments
will help you diagram your code, and Debug
works with environments so you can see where you are in it. We encourage you to try out all these features.
Reformat
is incredibly useful for determining whether you have parenthesis based bugs in your code. You should be able to see after formatting if your code looks weird where the issue is.
By default, the interpreter uses Lisp-style formatting, where the parens are all put on the end of the last line
(define (f x) (if (> x 0) x (- x)))
However, if you would prefer the close parens to be on their own lines as so
(define (f x) (if (> x 0) x (- x) ) )
you can go to Settings and select the second option.
Warning
The editor will neither back up nor submit on your behalf. You still need to run python ok -u
to unlock cases from the terminal as well as python ok --submit
.
Reporting bugs
This is relatively new software! While we have tested it extensively, it probably has bugs. Please let us know on piazza if there is an issue.
Questions
Q1: Survey
Please fill out the survey at this link
and fill in hw06.py
with the token. The link might not work if you are logged
into some google account other than your Berkeley account, so either log out from all
other accounts or open the link in a private/incognito window and sign in to
your Berkeley account there.
To check that you got the correct token run
Use Ok to test your code:
python3 ok -q survey
Scheme
Q2: Thane of Cadr
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
)
(define (caddr s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr
Q3: Sign
Using a cond
expression, define a procedure sign
that takes in one
parameter x
and returns -1 if x
is negative, 0 if x
is zero, and 1 if x
is positive.
(define (sign x)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q sign -u
python3 ok -q sign
Q4: Pow
Implement a procedure pow
for raising the number b
to the power of a
nonnegative integer n
for which the number of operations grows logarithmically
(as opposed to linearly).
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
Q5: Unique
Implement unique
, which takes in a list s
and returns a new list containing
the same elements as s
with duplicates removed.
scm> (unique '(1 2 1 3 2 3 1))
(1 2 3)
scm> (unique '(a b c a a b b c))
(a b c)
Hint: you may find it useful to use the built-in
filter
procedure. See the built-in procedure reference for more information.
(define (unique s)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q unique