CS 251: Programming Languages
Fall 2017
hw3: Lazy lists
Due: Friday, 09/22 at 22:00
This assignment is to be done individually. You can share ideas and thoughts with other people in the class, but you should code your own assignment.
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 non-empty 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, pad the shorter one with zeros until the length of the longer one. (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 elementelt
ofllst
such that(predicate elt)
is true. (Also see code notes below.)
4. Notes
- 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]
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
. 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. 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. 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.