CS 251: Programming Languages

Spring 2018

hw3: Lazy lists

Due: Friday, 04/06 at 22:00

This is a pair programming assignment. If you are on a team, this means that you and your partner should be doing the entirety of this assignment side-by-side, on a single computer, where one person is "driving" and the other is "navigating." Set a timer to swap every 15 minutes, say. You can choose your favourite from this online timer page. Make sure your sound volume is audible, but not so loud to disturb the people around you.

1. Goals

To build a data structure to represent a (possibly infinite) sequence of elements.

2. Introduction

Try the following in Python 2

range(3,23)
xrange(3,23)
for n in xrange(3,23):
   print n

and the following in Python 3

range(3,23)
for n in range(3,23):
   print(n)

It would seem that xrange in Python 2 and range in Python 3 yield some kind of (relatively small) objects that represent (possibly large) sequences of numbers. The actual sequence does not need to be generated until needed. Think about difference in storage requirements when the 23 above are replaced with, say, 23000000000000. (If you want to learn more, read about iterators and generators in Python.)

We now try to do this in Scheme. Recall that a nonempty list in Scheme consists of two parts:

• the first element of the list (the car), and
• a list representing the remaining elements (the cdr).

Analogously, a nonempty lazy list in Scheme consists of two parts:

• the first element of the list, and
• a "thunk" representing the remaining elements,

where the thunk is a zero-parameter function that, when called, returns a lazy list.

The key is that the body of a function in Scheme is not evaluated until the function is called, so infinite recursion does not appear to be a problem.

The Scheme function (range a b) generates a list of integers from a up to and including b, like range(a,b+1) in Python 2.

(define range
  (lambda (a b)
    (if (> a b)
        '()
        (cons a
              (range (+ a 1) b)))))

Compare this with (lazy-range a b), which generates a lazy range, like xrange(a,b+1) in Python 2 or range(a,b+1) in Python 3.

(define lazy-range
  (lambda (a b)
    (if (> a b)
        '()
        (cons a
              (lambda () (lazy-range (+ a 1) b))))))

The result of (lazy-range a b) is a cons cell, whose car is is the first integer; and whose cdr is a zero-parameter function that, when called, returns the rest of the sequence represented as a pair of the same (lazy) structure. We still use the empty list () to represent an empty lazy list.

3. Specification

• (lazy-infinite-range first)
  This function takes an integer and returns an integer lazy list containing the infinite sequence of values first, first+1, ...
• (first-n llst n)
  This function takes a lazy list llst and an integer n and returns an ordinary Scheme list containing the first n values in the lazy list. If the lazy list contains fewer than n values, then all the values in the lazy list are returned. You may assume that n is an integer greater than or equal to 1. If the lazy list is empty, return an empty Scheme list.
• (nth llst n)
  This function takes a lazy list llst and an integer n and returns the n-th value in the lazy list (counting from 1). If the lazy list contains fewer than n values, then #f is returned.
• (lazy-add llst1 llst2)
  This function takes two lazy lists llst1 and llst2 and returns the coordinate-wise sum of the two lists as a lazy list. In other words, the n-th entry of the sum of the lists is the sum of the n-th entries of the lists. If llst1 and llst2 have different lengths, imagine that the shorter list is padded with zeros in the end so they have the same lengths. (Also see code notes below.)
• (lazy-filter predicate llst)
  This function takes a function predicate and a lazy list llst and returns a new lazy list that represents (in order) precisely the element elt of llst such that (predicate elt) is true. (Also see code notes below.)

4. Notes

• As usual, if an input to a function is of the wrong type, the behaviour is unspecified.
• Here be some examples of lazy-filter.

  (lazy-filter (lambda (x) (= (modulo x 2) 0)) (lazy-infinite-range 1))
   --> (2 4 6 8 ...)   ;; as a lazy list
  (lazy-filter (lambda (x) (= (modulo x 5) 3)) (lazy-range 9 30))
   --> (13 18 23 28)   ;; as a lazy list
  (lazy-filter (lambda (x) (< x 0)) (lazy-infinite-range 251))
   --> [runs forever]
  

  Your lazy-filter function is permitted to run forever if you give it an infinite lazy list that has no elements that pass the predicate test.

  (In fact, it must! If you were able to guarantee that your function terminated even when the resulting list is empty, you could solve a version of the Halting Problem using lazy-filter. We show in CS 254 that the Halting Problem is undecidable: no algorithm, written in Scheme or otherwise, can solve such a problem.)

• Armed with lazy-add, we can define Fibonacci numbers recursively as follows. Let fib be an infinite lazy list whose first element is 0, second element is 1, and the rest (fib starting at the third element) is the componenent-wise sum of fib itself (!) and fib starting at the second element.

• You must use recursion, and not iteration. You may not use side-effects (e.g. set!).

5. Optional Challenges

• Define the Fibonacci numbers using lazy-add as outlined above.
• (Harder!) You may be wondering why we are not writing a function (lazy-cons first rest) to construct a lazy list whose first item is first and the rest is given by the expression rest, where rest should not be evaluated until later.

  Because Scheme evaluates the arguments before applying a function, this is impossible to achieve without using special forms. Indeed, special forms (define, lambda, quote, etc) are exactly those that need special evaluation rules.

  Here we are using the lambda special form to delay evaluation. One way to circumvent Scheme's evaluation order is to define lazy-cons as our own new special form! This may sound hard (and indeed it is!), but Scheme has a macro system that makes this fairly easy (as compared to other languages). If you wish, look up the documentation and give this a try.

6. Submission

Submit your code in a file called lazy-list.scm. We will be grading this using Moodle's anonymous grading capabilities, so make sure that your names are not included in your file.

Start early, have fun, and discuss questions on Moodle.