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, type python3 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:

  1. combiner: a function of two arguments
  2. start: a number with which to start combining
  3. n: the number of natural numbers to combine
  4. term: 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 and filter 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