cse341 handout #13

handout #14

CS341—Programming Languages

Programming Assignment #6 (Scheme)

due 11 pm Thursday, 5/14/09

This assignment is meant to bring you up to speed in Scheme and to give you practice with a structure definition. Several of your functions 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))

The main thing to realize about this definition is that it expands into several functions 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 functions relation-domain and relation-pairs to request the different components.

You are allowed to use any Scheme functions defined in the standard top-level environment. This includes macros like if, and, or and functions like member, map, filter. For those who want to go deeper into the functional style, you may also call functions like foldl, foldr, andmap, and ormap even though they are not described 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 functions in the How to Design Programs text by Felleisen linked under “Scheme resources” (you’ll find them in the index).

In implementing your functions, you are allowed to declare helper functions. But you should not, in general, include these helper functions in the top-level environment. As we saw in lecture, a function can have an “internal definition” that defines a function locally by including a “define” inside a “define.” The one case where you would be allowed to define a helper function in the top-level environment is if you find that you are calling it in two different functions. Then we would obviously want to avoid the duplication of making it internal to multiple function definitions.

In the examples we saw in lecture, we used “=” to test for equality for numbers (e.g., the base case of factorial testing if n is equal to 0). This is the right thing to do for numbers and you should do that in your homework. But when you have other kinds of values, you need a more powerful equality operator. For the relation problems, you should use the equal? predicate instead of “=”. For example, below is a function that returns a count of the number of occurrences of a particular value in a list. Notice that it uses equal? rather than “=” to make it more general:

(define (count value lst)

(if (null? lst)

(if (equal? (car lst) value)

(+ 1 (count value (cdr lst)))

(count value (cdr lst)))))

The final problem on this homework involves generating random expressions that can be used to produce art. The expressions will all produce values in the range of -1 to +1. We will build up complex expressions from simpler expressions by applying functions that produce values in the -1 to +1 range given arguments in that range. Below are several examples of such functions:

· sin(pi * <value>)

· cos(pi * <value>)

· (<value> + <value) / 2

· <value> * <value>

The functions that we produce will refer to x and y coordinates. To produce random art, we will generate three such functions, one each for producing red, green, and blue components. Then we scale the -1 to +1 so that it matches the width and height of our picture and we pick a set of red/green/blue colors for each pixel of our picture. The results are quite interesting. Below, for example, is a picture produced with expressions nested 8 levels deep:

Several of the functions you are asked to write have a precondition about the type of value passed to the function. You should document these preconditions. If you want to, you can include code to check for errors and call the function error if a precondition is violated.

Include your answers in a file called hw6.scm.

1. (5 points) Define a function 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 function 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 functions 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 function 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 function 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 function 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. (25 points) Define a function 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. (20 points) Define a function generate that takes an integer n as a parameter and that generates a random expression of depth n. You may assume that n is greater than or equal to 0. For an expression of depth 0, your function should produce either the symbol x or the symbol y (each should be equally probable). For an expression of depth greater than 0 you should produce one of the following five Scheme expressions (each should be equally probable):

· (cos (* pi <expr>))

· (sin (* pi <expr>))

· (/ (+ <expr> <expr>) 2.0)

· (/ (round (* <expr> 10.0)) 10.0)

· (* <expr> <expr>)

Each occurrence of <expr> should be replaced with a random expression of depth (n-1). For the expressions that have two occurrences of <expr>, the two expressions should be generated separately (rather than using the same expression twice). Below is a log of execution showing examples of expressions of varying depths:

> (generate 0)

> (generate 1)

(sin (* pi y))

> (generate 1)

(/ (+ x y) 2.0)

> (generate 1)

(/ (round (* x 10.0)) 10.0)

> (generate 1)

(* y y)

> (generate 1)

(/ (round (* x 10.0)) 10.0)

> (generate 1)

(cos (* pi x))

> (generate 2)

(/ (+ (* y x) (/ (round (* x 10.0)) 10.0)) 2.0)

> (generate 2)

(sin (* pi (* x x)))

> (generate 2)

(/ (+ (sin (* pi y)) (cos (* pi x))) 2.0)

> (generate 2)

(/ (+ (/ (+ y x) 2.0) (sin (* pi y))) 2.0)

> (generate 2)

(cos (* pi (* y y)))

> (generate 2)

(* (/ (round (* x 10.0)) 10.0) (* y x))

> (generate 3)

(cos (* pi (/ (+ (sin (* pi x)) (/ (+ y x) 2.0)) 2.0)))

> (generate 3)

(/ (+ (sin (* pi (sin (* pi y)))) (cos (* pi (/ (+ y x) 2.0)))) 2.0)

> (generate 3)

(/ (+ (/ (+ (sin (* pi y)) (* x y)) 2.0) (* (* x x) (* y y))) 2.0)

> (generate 3)

(sin (* pi (sin (* pi (/ (round (* y 10.0)) 10.0)))))

When you complete your assignment, you can load the file “graphics.scm” and run the function draw passing it a width, height, and expression depth. For example, the previous image was produced by the call:

(draw 300 300 8)

The draw function assumes that you have a correct definition of all-pairs and generate. To generate random numbers you should call the Scheme function called random which takes no arguments and that returns a random real in the range of 0.0 to 1.0.

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.