Homework Assignment 2

CS 2360
Winter 1998
Homework Assignment 2
Due no later than 8:00am, Monday, January 26, 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 14 pre-existing
Common LISP functions by using a relatively small subset of Common LISP.
In the process of constructing those 14 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.  Then you'll
get a chance to write six of those functions twice.

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).  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, IF, NULL, ATOM,
LISTP, NUMBERP, FIRST, REST, CONS, ZEROP, 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, some of these were solved
today in class, and all of them have been solved by CS2360 students from 
previous quarters because we've been using variations of this assignment 
for years.  So it's going to be relatively easy to find solutions to all 
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.

Each of the 20 problems specified below is worth 10 points.  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 and 3) my-append

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

Note: write two versions of my-append, one using augmenting recursion
and one using only tail recursion.  Call the tail-recursive version
my-append-tr.


4 and 5) 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)

Note: write two versions of my-remove-duplicates, one using augmenting 
recursion and one using only tail recursion.  Call the tail-recursive 
version my-remove-duplicates-tr.


6) my-reverse

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


7 and 8) 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)

Note: write two versions of my-remove, one using augmenting recursion 
and one using only tail recursion.  Call the tail-recursive 
version my-remove-tr.


9 and 10) 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)

Note: write two versions of my-substitute, one using augmenting recursion 
and one using only tail recursion.  Call the tail-recursive 
version my-substitute-tr.


11 and 12) my-intersection

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

Note: write two versions of my-intersection, one using augmenting recursion 
and one using only tail recursion.  Call the tail-recursive 
version my-intersection-tr.


13) my-union

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


14 and 15) my-make-list

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

Note: write two versions of my-make-list, one using augmenting recursion 
and one using only tail recursion.  Call the tail-recursive 
version my-make-list-tr.


16) 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)


17) my-assoc

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


18) 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


19) 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


20) my-last

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



Copyright 1998 by Kurt Eiselt.  All rights reserved.