You will need to find and/or setup a scheme environment on your machine before completing the programs assigned. You may wish to visit http://www.schemers.org/ or http://community.schemewiki.org/?scheme-faq-standards#implementations to find a suitable Scheme environment. MzScheme is recommended, as the MzScheme environment will be used in grading your submission.
After completing this assignment you will know how to:
You are to implement Scheme functions for dealing with sets of planar
coordinate pairs. You will implement two functions,
set-eq? to test for equality and
set-union to union two sets. Both functions are
only required to operate on lists containing elements that are
coordinate pairs as defined below.
You will also need to define a student-name function.
The function should be modeled like this:
(define (student-name) "Joe Student")
So that when you evaluate it behaves like this:
> (student-name) "Joe Student" >
Of course, use you own name.
Coordinates are integer (x y) pairs. To represent a coordinate pair use a list with exactly two elements. The order of these two list elements is important. The first element is the x coordinate and the second element is the y coordinate.
To represent a set of coordinate pairs in scheme use a list of coordinate pairs. For operations on sets, the order of elements is not important. Also, because it's a set, duplicate elements are not relevant.
Here is an example of a set of four coordinate pairs,
((1 1) (1 2) (1 3) (2 2))
Note that the list represents an unordered set of pairs, so this set of coordinate pairs would be equivalent,
((2 2) (1 2) (1 1) (1 3))
Implement the function, set-eq? to accept two
arguments, each of which is a set of coordinate pairs represented by a
list of lists as described above. Your function will return a boolean
#t or #f indicating whether the two lists are equal in the sense of
set equality.
Next, implement the function, set-union to accept
two lists of coordinate pairs and return a new list of coordinate pairs
representing the union of these two sets. Your function,
set-union, must observe the additional
requirement that their are no duplicates in the resulting set,
regardless of whether duplicates are present in the argument lists.
Both of your functions must ensure their arguments are immutable, i.e., your functions should not use destructive operations on the argument lists.
Here is an example mzscheme session showing how you program might run.
$ mzscheme Welcome to MzScheme v370 [3m], Copyright (c) 2004-2007 PLT Scheme Inc. > (load "a1.scm") > (set-eq? '((1 1) (1 2)) '((2 2) (1 2) (1 1))) #f > (set-eq? '((1 1) (1 2) (1 3) (2 2)) '((2 2) (1 2) (1 1) (1 1) (1 3))) #t > (set-eq? '((4 1) (3 2)) '((1 4) (2 3))) #f > (set-eq? '() '()) #t > (set-union '((1 1) (2 2)) '((3 3))) ((1 1) (2 2) (3 3)) > (set-union '((1 1) (2 2)) '((1 1) (3 3))) ((1 1) (2 2) (3 3)) > (set-union '((1 1) (2 2) (2 2)) '((1 1) (3 3))) ((1 1) (2 2) (3 3)) > (set-union '((1 1) (2 2) (2 2)) '()) ((1 1) (2 2))
Here are some observations of this mzscheme session.
Note that the first call compares two sets that differ on one element,
(2 2) in the second argument, thus the function returns #f. The
second call compares two lists containing a different ordering of the
same coordinate. Thus, the two sets are equal, since order is not
important and duplicate list elements are not considered. The third
call compares two different coordinate pairs. Note that the order of
sub-list elements in the x and y position differ, so they are not the
same coordinate pairs. The fourth call handles the boundary case for
empty sets, which are defined to be equal. Note that the
set-union calls may return lists with coordinate
pairs in a different order than shown here. The last call to
set-union demonstrates that performing a
set-union with a null list removes duplicates
from the non-null argument.
You can make some simplifying assumptions about the arguments to your functions.
Your functions, set-eq? and
set-union, are only required to produce results
for lists of coordinate pairs. You need not worry about other inputs
as the grading will only exercise your program with arguments that are
list of coordinate pairs.
Do not use any of Scheme's I/O functions. Neither your program, nor the student-name function should generate output.
Please note that the Scheme interpreter's Read-Eval-Print-Loop (REPL) does print the return result after evaluating your function. Printing under the REPL is normal and expected.
To demonstrate this requirement, consider assign a variable to the result of running your function. When your function call is wrapped inside a define construct, the REPL will not print anything. Instead the return value is assigned to the variable. Specifically, mzscheme should not print anything when evaluating the following,
(define somevalue (set-eq? '((1 1) (1 2)) '((1 1) (2 1))))
Similarly, mzscheme should not print anything when evaluating the following,
(define anothervalue (student-name))
On the other hand, evaluating,
(set-eq? '((1 1) (1 2)) '((1 1) (2 1)))
at the mzscheme prompt should look like this,
> (set-eq? '((1 1) (1 2)) '((1 1) (2 1))) #f >
Just as evaluating,
(student-name)
at the mzscheme prompt should look like this,
> (student-name) "Joe Student" >
Your program did not print anything. It returned a value, and that value was printed by the REPL.
In preparing your submission, you must save the entire program source in a single file, "a1.scm". You can load load this file by entering,
(load "a1.scm")
at the mzscheme prompt.
See the description of the driver program, below.
This file must contain the definition of your scheme functions and a
definition of the student-name function.
You will likely make use of additional helper functions, too.
All of these function definitions should be contained in this single file.
You may find it useful to employ the Scheme functions,
cond, if, and
let in developing your solution.
A driver program similar to this will be used to run your program:
(load "a1.scm") ;; loads your program (load "a1driver.scm") ;; loads the grader program (print (student-name)) ;; prints your name (driver) ;; grades your submission, prints results, and exits
The grader function prints a score value,
for example "10", which is captured by the shell driver. If your program
outputs anything, generates an error message, or fails to run,
spurious output will get captured and your program will fail the
driver test.
This is why your are asked to be sure that your program generates no output, as the
driver program will be run in the context of a Unix shell that invokes
scheme from the command line, e.g.,
mzscheme --load driver.scm
The following can spoil the grading of an otherwise working program, so don't do any of these:
set-eq?
Submit via e-mail using a mime-encoded, zipped attachment. (Note, most e-mail client programs do mime-encoding automatically for you, but to create the zip file attachment, you will need to use zip utility. The zipped attachment must be named, a1.zip, which contains one file, a1.scm in the current directory (i.e., the top-level rooted directory of the zip archive).
To: martin@cs.sjsu.edu Subject: A1