Homework 10
Due by 11:59pm on Thursday, 4/12
Instructions
Download hw10.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:
Q1: Accumulate
Fill in the definition for the procedure accumulate
, which combines the first
n
natural numbers according to the following parameters:
combiner
: a function of two argumentsstart
: a number with which to start combiningn
: the number of natural numbers to combineterm
: a function of one argument that computes the nth term of a sequence
For example, we can find the product of all the numbers from 1 to 5 by using the multiplication operator as the combiner
, and starting our product at 1:
scm> (define (identity x) x)
scm> (accumulate * 1 5 identity) ; 1 * 1 * 2 * 3 * 4 * 5
120
We can also find the sum of the squares of the same numbers by using the addition operator as the combiner
and square
as the term
:
scm> (define (square x) (* x x))
scm> (accumulate + 0 5 square) ; 0 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
55
(define (accumulate combiner start n term)
(if (= n 0)
start
'YOUR-CODE-HERE
)
)
Use Ok to test your code:
python3 ok -q accumulate
Q2: Tail Recursive Accumulate
Update your implementation of accumulate
to be tail recursive. It
should still pass all the tests for "regular" accumulate
!
You may assume that the input combiner
and term
procedures are
properly tail recursive.
If you're running into an recursion depth exceeded error and you're using the staff interpreter, it's very likely your solution is not properly tail recursive.
(define (accumulate-tail combiner start n term)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q accumulate-tail
Q3: List Comprehensions
Recall that list comprehensions in Python had the following form:
[<expression> for <element> in <sequence> if <conditional>]
Use a macro to implement list comprehensions in Scheme. Specifically, we
want a list-of
macro that takes in the following information:
(list-of <expression> for <element> in <sequence> if <conditional>)
As an example, we could use the list comprehension macro in the following way:
scm> (list-of (* x x) for x in '(3 4 5) if (odd? x))
(9 25)
Hint: you may use the built in
map
andfilter
procedures. Check out the Scheme Primitives reference for more information.
Optional (not graded):
Recall also that the if <conditional>
portion of the Python list
comprehension was optional. Modify your macro so that the Scheme list
comprehension does not require a conditional expression.
Refer to the macro form in the Scheme Specification for an explanation of how to do optional macro parameters.
(define-macro (list-of expr for var in seq if filter-fn)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q list-comp