# Homework 10 hw10.zip

Due by 11:59pm on Thursday, 4/12

## Instructions

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``