handout #14

CS341—Programming Languages

Programming Assignment #6 (Scheme)

due 11 pm Wednesday, 2/21/07

This assignment is meant to bring you up to speed in Scheme and to give you practice with a structure definition. Several of your procedures will act on something known as a relation. This concept is important in many branches of computer science, particularly in databases. Any given relation will be over a particular set of values that we refer to as the domain of the relation. The relation itself is simply a set of ordered pairs of values from the domain. For example, the domain might be the set of integers {1, 2, 3}. An example of a relation would be the following set of ordered pairs that correspond to the relation we call “less than”:

{(1, 2), (1, 3), (2, 3)}

The order of the pairs doesn’t matter. Below is a list of pairs that would correspond to the relation “less than or equal” over the same domain:

{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}

We will use a structure definition as a way to describe a relation:

(define-struct relation (domain pairs))

This is described as define-structure in the textbook. The main thing to realize about this definition is that it expands into several procedures that you can use to access a relation:

· (make-relation d p) returns a relation with domain d and pairs p (d should be a list of values, p should be a list of pairs of values from d, neither list should have any duplicates, each pair is represented as a list of two values)

· (relation? x) returns #t if x is a relation, #f otherwise

· (relation-domain r) returns the domain of relation r

· (relation-pairs r) returns the pairs of relation r

For example, we could define the relations described above by saying:

(define less-than (make-relation '(1 2 3) '((1 2) (1 3) (2 3)))

(define less-than-or-equal

(make-relation '(1 2 3) '((1 1) (1 2) (1 3) (2 2) (2 3) (3 3))))

Once the relations are constructed, we can use the procedures relation-domain and relation-pairs to request the different components.

You are allowed to use any Scheme procedures defined in the standard top-level environment. This includes macros like if, and, or and procedures like member, map, filter. For those who want to go deeper into the functional style, you may also call procedures like foldl, foldr, andmap, and ormap even though they are not described in the textbook or in the Scheme standard. These correspond to the ML functions List.foldl, List.foldr, List.all and List.exists. There is a short description of these procedures in the How to Design Programs text by Felleisen linked under “Scheme resources” (you’ll find them in the index).

There is one constraint, however, that you must abide by. For this assignment, any helper procedures must be declared as named local procedures. You will generally use a letrec expression to define such procedures. The requirement that they be local means that you can’t define helper procedures in the top-level environment. They have to be defined inside the procedure that uses them. The requirement that they be named means that you can’t use a lambda without naming it. Scheme programmers tend not to name a lambda if it is short and we’ll allow you to do that in the next assignment, but the intent is to make you practice using letrec to define local procedures.

You should use equal? for all of your comparisons on items in a relation because we want the code to work for relations on any type of data, not just relations on simple integers, although you should use = if you know that what you are comparing are simple numbers. Several of the procedures you are asked to write have a precondition about the type of value passed to the procedure. You should document these preconditions. If you want to, you can include code to check for errors and call the procedure error (described in the textbook) if a precondition is violated.

1. (5 points) Define a procedure collapse that takes a list of numbers and that collapses successive pairs of numbers by replacing the pair with the sum of the numbers. If the list has an odd length, then the last value is not collapsed. For example:

(collapse '(3.4 2 8 14.7 3 12)) should return (5.4 22.7 15)

(collapse '(13 4 27 9 48)) should return (17 36 48)

2. (10 points) Define a procedure stretch that takes a list of integers and that doubles its length by replacing each integer with two numbers that add up to the integer. The two numbers should each be half of the original, but if the original number is odd, then the first number in the new pair should be one higher in absolute value than the second. You might want to call the procedures quotient and modulo. For example:

(stretch '(38 4 19 7 -5)) should return (19 19 2 2 10 9 4 3 -3 -2)

3. (10 points) Define a procedure all-pairs that takes two lists as arguments and that returns a list of all of the ordered pairs that can be formed with one value from the first list and one value from the second list. The list should be ordered first by the order of values from the first list and within those groups, ordered by the order of values from the second list. You can assume that the lists contain no duplicates. For example:

(all-pairs '(1 2 3) '(a b c d)) should return ((1 a) (1 b) (1 c) (1 d) (2 a) (2 b) (2 c) (2 d) (3 a) (3 b) (3 c) (3 d))

4. (15 points) Define a procedure reflexive? that takes a relation as an argument and that returns #t if it is reflexive and that returns #f otherwise. A relation is considered reflexive if for every value x in the doman, the pair (x x) is included in the relation. For the two sample relations, less-than is not reflexive but less-than-or-equal is reflexive.

5. (15 points) Define a procedure symmetric? that takes a relation as an argument and that returns #t if it is symmetric and that returns #f otherwise. A relation is considered symmetric if for every pair (x y) in the relation, the pair (y x) is also in the relation. Neither of the sample relations is symmetric.

6. (20 points) Define a procedure transitive? that takes a relation as an argument and that returns #t if it is transitive and that returns #f otherwise. A relation is considered transitive if for every combination of pairs (x y) and (y z) that are in the relation, the pair (x z) is also in the relation. Both of the sample relations are transitive.

7. (25 points) Define a procedure reflexive-closure that takes a relation as an argument and that returns the smallest relation containing the original relation that is reflexive. In other words, the reflexive closure should include any missing pairs that are needed to make the relation reflexive (but no extra pairs other than the ones that are needed to make it reflexive).

Note: Several of these problem statements talk about returning #t, but in Scheme it is considered acceptable to return any value other than #f to indicate true. You are allowed to use this interpretation for these problem statements.