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, 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:
- 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 fulllst
?
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 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
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
andfilter
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 alambda
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.