Assignment Five: Functional Programming in Scheme

Assigned: Friday, April 3, 1998
Due: 11am, Wednesday, April 15, 1998

All of your coding for this assignment should be done in Scheme.

A. Testing Sorting Functions

As you may have noted from the previous assignment, it is essential to develop good and comprehensive testing routines for your attempted implementations of algorithms. In the case of sorting routines, it is particularly important to develop reasonably comprehensive testing routines. Here is a reasonable test routine, written in a generic imperative language

for each list size from 0 to some reasonable size (e.g., 8)
  for each kind of list of that size
    generate a sample list of that kind and size
    for each permutation of that list
      make sure the sorting mechanism works

What "kinds" of lists do we want? At least four kinds: one kind of list has no duplicates. Since we're building every permutation, it seems reasonable to simply generate a sequence of numbers (possibly starting with a negative number and ending with a positive one so that we also test positive/negative problems). A second kind of list has all the same value to ensure that numbers aren't lost. A third kind of list is used to ensure that numeric sorting is used and includes things like (1,2,12). If these were sorted textually, they would appear as (1,12,2). A final kind of list is of a mixed form: some duplicates, some differences.

Your goal will be to translate these ideas into a comprehensive sort testing predicate, (sorts? function) that takes a sorting function as a parameter and returns true (#t) if the parameter seems to be a correct sorting routine (or at least passes a relatively comprehensive suite of tests and false (#f) if it fails some test.

A.1. Generating Sequences

Write a Scheme function (nints n start) that generates a list of n successive integers starting with start. For example, (nints 4 -2) would produce the list (-2 -1 0 1).

A.2. Generating Copies

Write a Scheme function (ncopies n val) that generates a list of n copies of val. For example, (ncopies 4 3) would produce (3 3 3 3).

A.3. Generating Stranger Sequences

Write a Scheme function that generates lists that will be sorted differently if textual and numeric comparison routines are used. (For example, a textual comparison routine will generally place 12 before 2; a numeric comparison routine will place 2 before 12.)

A.4. Generating Compound Sequences

Write a Scheme function that generates lists which have some of the criteria given above. That is, they should include both different numbers and copies of some number (as long as the list has at least three elements).

A.5. Generating Permutations

Write a recursive Scheme function, (permutations lst), that generates a list of all the permutations of lst. For example, (permutations '(1 2 3)) should produce something like

( (1 2 3)
  (2 1 3)
  (2 3 1)
  (1 3 2)
  (3 1 2)
  (3 2 1) )

Chat with me if you need some ideas on how to do this recursively.

A.6. Developing a Testing Predicate

Using the pieces developed above, develop a predicate, (sorts? fun) that returns true if fun appears to sort lists and false otherwise.

A.7. Developing a Quicksort Function

Write a function, (quicksort lst), that computes a sorted version of lst using the quicksort algorithm. Feel free to reuse code from class (provided you cite it appropriately). Run your testing predicate on your sorting routine and report the results.

A.8. Developing a Mergesort Function

Write a function, (mergesortlst), that computes a sorted version of lst using the mergesort algorithm. Feel free to reuse code from class (provided you cite it appropriately). Run your testing predicate on your sorting routine and report the results.

A.8. Developing an Insertion Sort Function

Write a function, (itsort lst), that computes a sorted version of lst using the insertion sort algorithm. Feel free to reuse code from class (provided you cite it appropriately). Run your testing predicate on your sorting routine and report the results.

B. Continuations

B.1: Continuation-passing Mathematical Operations

Write Scheme functions (cadd a b cont failcont), cmult, csub, cdiv and csqrt. Each of these functions takes some values and two continuations as parameters. The functions are expected to compute the appropriate function of the initial values (e.g., addition for cadd, square root for csqrtcont to the result of the function if successful. If the operation fails, they should apply failcont to 0.

B.2: Using continuations

Convert each of the following to continuation-passing style, using your functions from B.1 above. You should use the current continuation as cont and use a function that prints an error message as failcont.

• (+ A B)
• (/ A B)
• (+ A (/ A B))
• (+ (/ A B) A)
• (sqrt A)
• (sqrt (/ A B))
• (/ A (sqrt B))

B.3: Computing continuations

This problem is optional. It serves as extra credit for the assignment.

Write a function, (cps expression), that converts an expression in Scheme prefix format to continuation-passing style. In effect, your function will provide answers for the previous question.

C. Delayed Evaluation and Infinite Lists

As we've seen, Scheme generally performs a form of eager evaluation: before calling a function on arguments, it evaluates the arguments. Some time ago, a number of computer science researchers suggested that one use lazy evaluation, in which one delays evaluation of an expression as long as possible.

Scheme provides a few built-in functions to support this type of evaluation. However, it is also possible to support delayed evaluation using lambda expressions. Consider the lambda expression

(lambda () (+ a (* b c)))

> (define a 2)
> (define b 3)
> (define c 4)
> (define fun (lambda () (+ a (* b c))))
> fun
#
> (fun)
14
> (define a 100)
> (fun)
112
> (define (foo a) (+ a (fun)))
> (foo 1)
113

Let's consider how we might use this in building lists. Suppose we wanted to build a list of four items and only used the forth. It would obviously be a waste of computation power to compute all four items in advance. Hence, we might encapsulate each in a lambda expression and then only extract them when necessary. In fact, if we were to take this idea to extremes, we might not even want to build anything but the first cons cell (leaving the construction of the remaining ones to "on demand").

Why might this be useful? Well, it provides a different form of program modularity. Consider the functions (listn n) which lists the first n integers and (nprimes n) which lists the first n primes. Good program design suggests that we should extract out any common features of these two functions. What is common? Getting the first n elements in a sequence. We could define then define (firstn n lis) as

(define (firstn n lis)
  (if (= n 0) nil
      (cons (car lis) (firstn (- n 1) (cdr lis)))))

C.1. Unencapsulation

Write a function, (demand encapsulated), that extracts an encapsulated value from a lambda abstraction. For example,

(demand (lambda () (+ 2 3)))

C.2. List Unencapsulation

Write functions demandcar and demandcdr, that extract the actual car and cdr of an encapulsated list. For example,

> (define ls
    (cons (lambda () (display 'a) (newline) (+ 2 3))
          (lambda () (cons (lambda () (display 'b) (newline)
                                      (* 3 4))
                           (lambda () nil)))))
> (demandcdr (demandcdr ls))
()
> (demandcar ls)
a
5
> (demandcar (demandcdr ls))
b
12

C.3. Infinite Lists

Write a function, (intsfrom n), that creates an encapsulated list of all the integers from n to infinity. Using an appropriate variant of the firstn function above, test your function. For example,

> (firstn 3 (intsfrom 5))
(5 6 7)

C.4. Other Applications

Come up with some other interesting infinite list and demonstrate its use with firstn.