Homework Assignment 2

CS 2360
Fall 1998
Homework Assignment 2
Due no later than 8:00am, Monday, October 12, 1998

One of the amazing things about LISP is that so much of the language can be
defined in terms of just a very few pre-existing functions.  In this
assignment, you will be constructing your own versions of 17 pre-existing
Common LISP functions and one function that doesn't exist in LISP already 
(we'll let you figure out which one that is) by using a relatively small 
subset of Common LISP.  In the process of constructing those 18 functions, 
you'll not only get to practice your LISP programming skills, but you'll 
also gain familiarity with a lot of very useful LISP functions such as 
APPEND and ASSOC.  

The functions that you'll be constructing will, in some cases, be
simplifications of the pre-existing functions in that your versions will not
have to deal with optional arguments (which we haven't talked about much
anyway), and they don't have to accommodate arguments containing dotted
pairs (dotted pairs are mentioned in the posted class notes).  In all other 
regards, however, the behavior of your functions should mimic the behavior 
of the pre-existing functions.  You can check out the behavior of the 
pre-existing functions by playing around with them while you're working 
in the LISP interpreter, and, if you're especially interested, you can 
find exact specifications for those functions in "Common LISP: The
Language" by Guy Steele or "ANSI Common Lisp" by Paul Graham.

The functions that you are to define are listed below, along with examples of
how we expect them to work.  For all the functions, you can obtain the name of
their pre-existing counterparts by just removing the prefix "my-".

To construct these functions, you may use DEFUN, COND, NULL, ATOM, SYMBOLP,
LISTP, NUMBERP, FIRST, REST, CONS, the equality predicates (EQ, EQL, 
EQUAL, EQUALP, and =), QUOTE (or '), the arithmetic functions (+, -, 
*, and /), and the Boolean functions (AND, OR, and NOT; we haven't 
mentioned these in class yet, but if you look them up you'll see what 
they're all about pretty quickly).  You may not need all these functions, 
but they are available to you.  You may also use (or reuse) any function 
which you have defined.  Don't use assignment, and don't use any control 
structure other than recursion.

If you were to look through various LISP books, you might find many
solutions to the problems below.  In fact, one of these was solved
today in class, others will be solved on Thursday, and almost all of 
them have been solved by CS2360 students from previous quarters because 
we've been using variations of this assignment for years, and I used 
this exact same assignment in Fall 1997.  So it's going to be relatively 
easy to find solutions to most of these problems if you want to.  But 
knowing where to find these answers isn't going to help you in the weeks 
to come; if you can't solve most of these problems on your own now, you're 
going to encounter great difficulty with future homework assignments.  So 
please, do yourself a very big favor and solve as many as you can on your 
own and don't go looking up the answers in textbooks or elsewhere.

Don't forget to worry about modularity, abstraction, meaningful function 
and parameter names, reasonable comments, appropriate indentation, and
all that.

Here are the functions we want you to construct:

1) my-member

(my-member 'c '(a b c d e)) => (c d e)

2) my-append

(my-append '(a b) '(c d)) => (a b c d)

3) my-remove-duplicates

(my-remove-duplicates '(a b a c a d)) => (b c a d)
(my-remove-duplicates '(a b (a c) a d)) => (b (a c) a d)

4) my-reverse

(my-reverse '(a b c)) => (c b a)
(my-reverse '(a (b c) d) => (d (b c) a)

5) my-remove

(my-remove 'a '(a b a c a d)) => (b c d)
(my-remove 'a '(a b (a c) a d)) => (b (a c) d)

6) my-substitute

(my-substitute 'x 'a '(a b a c a d)) => (x b x c x d)
(my-substitute 'x 'a '(a b (a c) a d)) => (x b (a c) x d)

7) my-subst

(my-subst 'x 'a '(a b a c a d)) => (x b x c x d)
(my-subst 'x 'a '(a b (a c) a d)) => (x b (x c) x d)

8) my-intersection

(my-intersection '(a b c) '(b c d)) => (b c)  ; order is unimportant

9) my-union

(my-union '(a b c) '(b c d)) => (a b c d)     ; order is unimportant

10) my-set-difference

(my-set-difference '(a b c) '(b c d)) => (a)
(my-set-difference '(b c d) '(a b c)) => (d)
(my-set-difference '(a b) '(c d)) => (b a)    ; order is unimportant

11) my-subsetp

(my-subsetp '(c d) '(a b c d)) => T
(my-subsetp '(c d) '(d c b a)) => T
(my-subsetp '(a b c) '(b c d)) => nil

12) my-make-list

(my-make-list 3) => (nil nil nil)

13) my-subseq

(my-subseq '(a b c d) 0 3) => (a b c)
(my-subseq '(a b c d) 1 3) => (b c)
(my-subseq '(a b c d) 2 3) => (c)
(my-subseq '(a b c d) 3 3) => nil
(my-subseq '(a b c d) 1 4) => (b c d)

14) my-assoc

(my-assoc 'a '((c d)(a b)(e f))) => (a b)
(my-assoc 'c '((c d)(a b)(e f))) => (c d)

15) my-insert

(my-insert 'a '(b c d e) 0) => (a b c d e)
(my-insert 'a '(b c d e) 2) => (b c a d e)
(my-insert 'a '(b c d e) 4) => (b c d e a)

16) my-nthcdr

(my-nthcdr 0 '(a b c)) => (a b c)
(my-nthcdr 2 '(a b c)) => (c)
(my-nthcdr 4 '(a b c)) => nil

17) my-last

(my-last '(a b c d)) => (d)
(my-last '(a b (c d))) => ((c d))
(my-last nil) => nil

18) my-set-exclusive-or

(my-set-exclusive-or '(a b) '(c d)) => (d c b a)  ; order is unimportant
(my-set-exclusive-or '(a b) '(b c)) => (c a)


Copyright 1998 by Kurt Eiselt.  All rights reserved.