COS 371: Programming Languages
Spring 2022
hw3: Lazy lists
Due: Wednesday, 02/16 at 22:00
This is a solo/pair programming assignment. You may either work alone or with one other student of your choice. If you are pair programming, 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." (Or a remote equivalent of this experience.) Set a timer to swap every 15 minutes, say. You can choose your favourite from this online timer page. You are not allowed to divide-and-conquer the assignment by each working separately on half of it. If your schedule does not allow you to find enough time to meet together to complete the entire assignment side-by-side, you should opt to do the assignment solo instead.
1. Goals
To build a data structure to represent a (possibly infinite) sequence of elements.2. Introduction
Try the following in Python 2range(3,23) xrange(3,23) for n in xrange(3,23): print nand 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
).
- the first element of the list, and
- a "thunk" representing the remaining elements,
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 valuesfirst
,first
+1, ...- (first-n llst n)
This function takes a lazy listllst
and an integern
and returns an ordinary Scheme list containing the firstn
values in the lazy list. If the lazy list contains fewer thann
values, then all the values in the lazy list are returned. You may assume thatn
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 listllst
and an integern
and returns then
-th value in the lazy list (counting from 1). If the lazy list contains fewer thann
values, then #f is returned. (lazy-add llst1 llst2)
This function takes two lazy listsllst1
andllst2
and returns the coordinate-wise sum of the two lists as a lazy list. In other words, then
-th entry of the sum of the lists is the sum of then
-th entries of the lists. Ifllst1
andllst2
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 functionpredicate
and a lazy listllst
and returns a new lazy list that represents (in order) precisely the elementselt
ofllst
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 371)) --> [runs forever]
Yourlazy-filter
function is permitted to run forever if you give it an infinite lazy list that has no elements that pass thepredicate
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
. But the Halting Problem is undecidable: no algorithm, written in Scheme or otherwise, can solve such a problem.)(Note: undecidability, which is beyond the scope of this course, is at the core of my research; if you want to know more, I am delighted to talk about it in office hours.)
- Armed with
lazy-add
, we can define Fibonacci numbers recursively as follows. Letfib
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 offib
itself (!) andfib
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 isfirst
and the rest is given by the expressionrest
, whererest
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 definelazy-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.
Start early, have fun, and discuss questions on Moodle.