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:

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.