CSC 8310: Lisp Assignment
Section 001: Tuesday & Thursday 4:30 to 5:45pm in Mendel G30
Section 002: Thursday 6:15 to 8:45 in Mendel G30
Dr. David Matuszek, Mendel 162C, (610) 519-5654
Villanova University, Spring 2000

Write and test the following Lisp functions. Please turn in a listing of your functions, along with a transcript of your testing session. (You can lowercase the names if you prefer.)

Do not do any error checking; it complicates the code too much. Test your functions only with the appropriate types of arguments. Your tests must include the examples given, and must also test every reasonable case. (For all functions except MYLAST, this should include testing with the empty list.) If you fail to test an obvious case, we will assume that your function does not work for that case.

Assume:

• A represents some atom,
• L represents a arbitrary list,
• LAT represents some list containing 0 or more atoms (and only atoms), and
• NEL represents some nonempty list.

(MYLAST NEL)

returns as value the last S-expression which occurs as a member of the nonempty list NEL.

 

(REMBER A LAT)

returns as value the list LAT with all occurrences of the atom A removed; remaining elements are in the same order as those in LAT. Hint: use FIRST and REST to tear the list apart, and CONS to build the new list.

 

(MYAPPEND L1 L2)

forms one list composed of all the elements of L1, in their original order, followed by all the elements of L2, in their original order. For example, (APPEND '(A B C) '(X Y Z)) should give (A B C X Y Z).

 

(MYREVERSE L)

reverses the elements of list L. For example, the list (A B (C D)) becomes the list ((C D) B A). Hint: you probably need APPEND and LIST.

 

(MAKESET LAT)

removes duplicate atoms occurring in LAT. For example, given (A B C A D A B), MAKESET returns (A B C D).

 

(ATOMSOF L)

returns as value the list L with all sublists removed, leaving only the top-level atoms. For example, if L is (P (Q R) ( ) (( )) S), the result should be (P NIL S).

 

(SKELETON L)

removes all the non-nil atoms of list L, but retains all parentheses. If L is (P (Q (R S)) T U (V) ( )), the result is ((( )) ( ) ( )), or in other words, ((NIL) NIL NIL). Note that in this problem NIL must be treated as a list, not as an atom.

 

(REVERSEALL L)

reverses the elements of L at all levels. For example, if L is (A (B C (D)) E), REVERSEALL should return (E ((D) C B) A).

 

(REMBERALL A L)

returns as value the list L with all occurrences of the atom A removed. This differs from REMBER in that L may be an arbitrary list, and the atoms A may occur at any level within L.

 

(COLLAPSE L)

returns the list L with all inner parentheses removed. For example, given (A (B C (D) ( ) E)), COLLAPSE returns (A B C D E). The order of atoms must be preserved.

 

These functions are roughly in order of increasing difficulty (MYREVERSE may be a little more difficult than some that follow it). Once you have written a function, use it in other functions as appropriate--if you don't, some functions will be very difficult!

Notes:

1. The functions LAST, APPEND, and REVERSE are already defined in LispWorks, so you are not allowed to use them (you have to write your own versions).
2. Lisp always prints the empty list as NIL rather than as ( ), and there is no easy way to change this. So in some of the above functions (especially SKELETON) you will have to make the translation mentally.

Due date: Thursday, April 13.
Turn in: (1) A listing of your program and (2) a transcript of your testing. No floppies, please.