# Homework 6: Lazy Evaluation, Tail Recursion, and Macros hw06.zip

Due by 11:59pm on Tuesday, 7/31

## Instructions

Download hw06.zip. Starter code for the problems can be found in `hw06.scm`.

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:

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.

# Questions

## Scheme streams

### Q1: Find

Define a function `find` which takes in as input a finite stream `s` and a `predicate` function, which is a one argument function that returns either `#t` or `#f`. `find` returns the first element in `s` satisfying the predicate. If `s` does not contain an element that satisfies the predicate, return `#f`.

``````(define (find s predicate)
'YOUR-CODE-HERE
)``````

Use Ok to test your code:

``python3 ok -q find``

### Q2: Scale Stream

Implement the function `scale-stream`, which takes a stream `s` and a number `k`, and returns a stream where each element is the corresponding element of `s` multiplied by `k`. For example, if `k` is 2, then all the elements in the stream are doubled. Your solution should work even if `s` has an infinite number of items.

``````(define (scale-stream s k)
'YOUR-CODE-HERE
)``````

Use Ok to test your code:

``python3 ok -q scale-stream``

### Q3: Cycles

In Scheme, it's possible to have a stream with cycles. That is, a stream may contain itself as part of the stream definition.

``````scm> (define s (cons-stream 1 (cons-stream 2 s)))
scm> (car s)
1
scm> (car (cdr-stream (cdr-stream s)))
1
scm> (eq? (cdr-stream (cdr-stream s)) s)
#t``````

Implement `has-cycle?`, which returns whether a stream contains a cycle. You may assume that the input is either a stream of some unknown finite length, or is one that contains a cycle. You should implement and use the `contains?` procedure in your solution. We have provided a skeleton for `has-cycle?`; your solution must fit on the lines provided.

Hint: A stream has a cycle if you see the same pair object more than once. The built-in procedure `eq?` may be used to check if two expressions evaluate to the same object in memory.

``````  scm> (define lst1 '(1 2 3))
lst1
scm> (define lst2 lst1)
lst2
scm> (define lst3 '(1 2 3))
lst3
scm> (eq? lst1 lst2)
#t
scm> (eq? lst1 lst3)
#f``````
``````(define (has-cycle? s)
(define (pair-tracker seen-so-far curr)
(cond (_________________ ____________)
(_________________ ____________)
(else _________________________))
)
______________________________
)

(define (contains? lst s)
'YOUR-CODE-HERE
)``````

Use Ok to test your code:

``python3 ok -q has-cycle``

Extra question: This question is not worth extra credit and is entirely optional.

Implement `has-cycle-constant` with only constant space. The solution is short (fewer than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

We don't directly test if your solution uses constant space, but it will likely timeout if you do not use constant space.

``````(define (has-cycle-constant s)
'YOUR-CODE-HERE
)
``````

Use Ok to test your code:

``python3 ok -q has-cycle-constant``

## Python iterators

### Q4: Generate Permutations

Given a sequence of unique elements, a permutation of the sequence is a list containing the elements of the sequence in some arbitrary order. For example, `[2, 1, 3]`, `[1, 3, 2]`, and `[3, 2, 1]` are some of the permutations of the sequence `[1, 2, 3]`.

Implement `permutations`, a generator function that takes in a sequence `seq` and returns a generator that yields all permutations of `seq`.

Permutations may be yielded in any order. Note that the doctests test whether you are yielding all possible permutations, but not in any particular order. The built-in `sorted` function takes in an iterable object and returns a list containing the elements of the iterable in non-decreasing order.

Your solution must fit on the lines provided in the skeleton code.

Hint: If you had the permutations of all the elements in `lst` not including the first element, how could you use that to generate the permutations of the full `lst`?

``````def permutations(seq):
"""Generates all permutations of the given sequence. Each permutation is a
list of the elements in SEQ in a different order. The permutations may be
yielded in any order.

>>> perms = permutations([100])
>>> type(perms)
<class 'generator'>
>>> next(perms)
[100]
>>> try:
...     next(perms)
... except StopIteration:
...     print('No more permutations!')
No more permutations!
>>> sorted(permutations([1, 2, 3])) # Returns a sorted list containing elements of the generator
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> sorted(permutations((10, 20, 30)))
[[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
>>> sorted(permutations("ab"))
[['a', 'b'], ['b', 'a']]
"""
if ____________________:
yield ____________________
else:
for perm in _____________________:
for _____ in ________________:
_________________________
``````

Use Ok to test your code:

``python3 ok -q permutations``

## Tail recursion

### Q5: 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
scm> (accumulate + 5 5 square)  ; 5 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
60``````

You may assume that the `combiner` will always be commutative: i.e. the order of arguments do not matter. Your solution must be properly tail recursive and run in a constant number of frames. You may assume that the given `combiner` and `term` procedures are properly tail recursive.

``````(define (accumulate combiner start n term)
'YOUR-CODE-HERE
)``````

Use Ok to test your code:

``python3 ok -q accumulate``

## Macros

### Q6: List Comprehensions

Recall that list comprehensions in Python allow us to create lists out of iterables:

``[<expression> for <name> in <iterable> if <conditional-expression>]``

Use a macro to implement list comprehensions in Scheme that can create lists out of lists. Specifically, we want a `list-of` macro that can be called as follows:

``(list-of <expression> for <name> in <list> if <conditional-expression>)``

Calling `list-of` will return a new list constructed by doing the following for each element in `<list>`:

• Bind `<name>` to the element.
• If `<conditional-expression>` evaluates to a truth-y value, evaluate `<expression>` and add it to the result list.

Here are some examples:

``````scm> (list-of (* x x) for x in '(3 4 5) if (odd? x))
(9 25)
scm> (list-of 'hi for x in '(1 2 3 4 5 6) if (= (modulo x 3) 0))
(hi hi)
scm> (list-of (car e) for e in '((10) 11 (12) 13 (14 15)) if (list? e))
(10 12 14)``````

Hint: You may use the built-in `map` and `filter` procedures. Check out the Scheme Built-ins reference for more information.

You may find it helpful to refer to the `for` loop macro introduced in lecture. The filter expression should be transformed using a `lambda` in a similar way to the map expression in the example.

``````(define-macro (list-of expr for var in lst if filter-expr)
'YOUR-CODE-HERE
)``````

Use Ok to test your code:

``python3 ok -q list-comp``

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.