►Programming Language Design (Fall 2011)
▼3 Assignments
►3.9 Laziness and Infinite Data
On this page:
3.9.1 A note on testing
3.9.2 Utility Functions
take-while
build-infinite-list
3.9.3 Primes
prime?
primes
prime?/ fast
primes/ fast
3.9.4 Longest Common Subsequence
build-table
lcs-length
  ← prev  up  next → 

3.9 Laziness and Infinite Data

Complete this assignment with Team One.

You must submit this in an archive named "lazy.zip". This archive must contain a folder named "lazy". This folder must contain all the files specified below. You must attach "lazy.zip" to an email whose subject is "BYU - Fall 2011 - CS 330 - lazy" and whose message body contains the name of everyone on your team (each on a separate line.) You must send this email to jay@cs.byu.edu before 5pm (Provo time) on 10/11. Ensure that what you are satisfied with what you submit, because only your chronologically first submission will be graded. Ensure that you follow these instructions exactly, since submissions that do not meet these requirements (i.e. do not have the correct format) will receive no credit, despite the time and energy you put into the assignment. Please see Turn In Policy for more information.

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

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

3.9.1 A note on testing

There is no testing facility built in to the Lazy Racket language. So, you should add one for your file:
(define print-only-errors #t)
(define (test l r)
  (if (equal? l r)
      (if print-only-errors
          ()
          (printf "Test Passed~n"))
      (printf "Test Failed.~nActual:   ~S ~nExpected: ~S~n" l r)))
For example,
(test (take-while odd? (list 1 3 4))
      (list 1 3))

3.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).

3.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.

3.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 answer for sub-problem made from prefixes of s1 and s2 then 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 →