handout #14
CS341—Programming Languages
Programming
Assignment #6 (Scheme)
due 11 pm Thursday, 5/13/10
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. The pairs may appear in any order, but there
should be no duplicate pairs in the list.
You are
allowed to use any Scheme functions defined in the standard top-level
environment other than mutating functions and those that operate on vectors. 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)
0
(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 '(3 19 7) '(a b c d)) should return ((3 a) (3 b)
(3 c) (3 d) (19 a) (19 b) (19 c) (19 d) (7 a) (7 b) (7 c) (7 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)
x
> (generate 0)
x
> (generate 0)
y
> (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.
There is a variation of the draw function called draw2 that continuously
updates the drawing.
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.