2.9 Laziness and Infinite Data

Programming Language Design (Fall 2009)

2

2.1	Musical Notation
2.2	Survey
2.3	Basic Scheme
2.4	Lists and Trees
2.5	Higher-order Functions
2.6	Rudimentary Interpreter
2.7	Substitution
2.8	Extended Interpreter
2.9	Laziness and Infinite Data
2.10	Laziness
2.11	Raw Web Programming
2.12	Language Design
2.13	Continuations
2.14	PLT Web Programming
2.15	Garbage Collectors
2.16	Garbage Collection
2.17	Type Checking
2.18	Type Checker
2.19	Type Inferrer
2.20	Type Inference
2.21	Prolog
2.22	Final

2.9

Laziness and Infinite Data

On this page:

2.9.1 A note on testing

2.9.2 Utility Functions

build-infinite-list

2.9.3 Primes

2.9.4 Longest Common Subsequence

← prev up next →

2.9 Laziness and Infinite Data

Complete this assignment with Team One.

You must submit this in an archive named "lazy.zip".

You must submit this in a file named "lazy.ss".

Develop the following functions and data structures in the Lazy Scheme language.

2.9.1 A note on testing

There is no testing facility built in to the Lazy Scheme language. So, you should use the following pattern for tests:

(printf "~S should be ~S~n" testing-expr expected-result-expr)

For example,

(printf "~S should be ~S~n"

(take-while odd? (list 1 3 4))

(list 1 3))

2.9.2 Utility Functions

(take-while p l) → (listof any/c)

p : (any/c . -> . boolean?)

l : (listof any/c)

Returns the prefix of l such that for all elements p returns true. This is not filter.

For example, (take-while (lambda (n) (< n 5)) (list 1 2 3 4 5 1 2)) returns (list 1 2 3 4).

(build-infinite-list f) → (listof any/c)

f : (exact-nonnegative-integer? . -> . any/c)

Lazily constructs the infinite list such that (list-ref (build-infinite-list f) i) returns (f i).

2.9.3 Primes

(prime? n) → boolean?

n : exact-positive-integer?

Returns true if n is prime.

primes : (listof exact-positive-integer?)

The list of all primes.

You may find filter, prime?, and build-infinite-list useful.

(prime?/fast n) → boolean

n : exact-positive-integer?

Returns true if n is prime, but tests only prime factors from primes/fast.

primes/fast : (listof exact-positive-integer?)

The list of all primes constructed with prime?/fast.

2.9.4 Longest Common Subsequence

(build-table rows cols f) → (vectorof (vectorof any/c))

rows : exact-positive-integer?

cols : exact-positive-integer?

f : (exact-nonnegative-integer? exact-nonnegative-integer? . -> . any/c)

Lazily constructs a vector such that (vector-ref (vector-ref (build-table rows cols f) i) j) equals (f i j), when (< i rows) (< j cols).

You will find the following function helpful:

(define (build-vector num f)
(apply vector (build-list num f)))

(lcs-length s1 s2) → exact-nonnegative-integer?

s1 : string?

s2 : string?

Computes the length of the longest common subsequence of two strings s1 and s2.

You must use build-table to construct a table of the longest common subsequence of prefixes of s1 and s2 are synthesize the result from these intermediate points. You will not get credit if you do a computation twice.

You may find string-ref, char=?, apply, and max useful.

Warning: Many people errorneously implement the longest common substring. The longest common substring of Artist and Artsy is Art. The longest common subsequence of Artist and Artsy is Arts. You are implementing longest common subsequence.

← prev up next →