# Homework 6: Lazy Evaluation, Tail Recursion, and Macros

*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:

- Scheme Specification
- Scheme Built-ins Reference
- Section 4.2 - Implicit Sequences
- Lazy Evaluation Lecture Slides
- Tail Recursion Lecture Slides
- Section 3.5.4 - Macros

**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:

`combiner`

: a function of two arguments`start`

: a number with which to start combining`n`

: the number of natural numbers to combine`term`

: a function of one argument that computes the*n*th 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.