Homework 7: Scheme
Due by 11:59pm on Thursday, November 4
Instructions
Download hw07.zip. Inside the archive, you will find a file called
hw07.scm, along with a copy of the ok
autograder.
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 correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.
Scheme is a famous functional programming language from the 1970s. It is a dialect of Lisp (which stands for LISt Processing). The first observation most people make is the unique syntax, which uses a prefix notation and (often many) nested parentheses (see http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.
You may find it useful to try code.cs61a.org/scheme when working through problems, as it can draw environment and box-and-pointer diagrams and it lets you walk your code step-by-step (similar to Python Tutor). Don't forget to submit your code through Ok though!
Scheme Editor
As you're writing your code, you can debug using the Scheme Editor. In your scheme
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.
If you find that your code works in the online editor but not in your own interpreter, it's possible you have a bug in code from an earlier part that you'll have to track down. Every once in a while there's a bug that our tests don't catch, and if you find one you should let us know!
Required Questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
Q1: Thane of Cadr
Define the procedures cadr
and caddr
, which return the second
and third elements of a list, respectively. If you would like a quick refresher on scheme syntax consider looking at Lab 10 Scheme Refresher.
(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
Q2: Ordered
Implement a procedure called ordered?
, which takes a list of numbers and
returns True
if the numbers are in nondescending order, and False
otherwise. Numbers are considered nondescending if each subsequent number is
either larger or equal to the previous, that is:
1 2 3 3 4
Is nondescending, but:
1 2 3 3 2
Is not.
Hint: The built-in
null?
function returns whether its argument isnil
.
(define (ordered? s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q ordered -u
python3 ok -q ordered
Q3: Pow
Implement a procedure pow
for raising the number base
to the power of a
nonnegative integer exp
for which the number of operations grows logarithmically, rather than linearly (the number of recursive calls should be much smaller than the input exp
). For example, for (pow 2 32)
should take 5 recursive calls rather than 32 recursive calls. Similarly, (pow 2 64)
should take 6 recursive calls.
Hint: Consider the following observations:
- x2y = (xy)2
- x2y+1 = x(xy)2
For example we see that 232 is (216)2, 216 is (28)2, etc. You may use the built-in predicates
even?
andodd?
. Scheme doesn't support iteration in the same manner as Python, so consider another way to solve this problem.
(define (square x) (* x x))
(define (pow base exp)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q pow -u
python3 ok -q pow