CS 2360 Spring 1996 Homework Assignment 2 Due no later than 8:00am, Monday, April 15, 1996 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 do a little bit more. 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 yet 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, FIRST, REST, CONS, the equality predicates (EQ, EQL, EQUAL, and EQUALP), 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 some solutions to the problems below. In fact, several of these were solved today in class. You'll want to try to solve these problems on your own, though, as your ability to find solutions to these problems will have an impact on how well you'll be able to solve problems on future homework assignments and exams. Each problem 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) 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-intersection (my-intersection '(a b c) '(b c d)) => (b c) ; order is unimportant 8) my-union (my-union '(a b c) '(b c d)) => (a b c d) ; order is unimportant 9) my-make-list (my-make-list 3) => (nil nil nil) 10) 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) 11) my-assoc (my-assoc 'a '((c d)(a b)(e f))) => (a b) (my-assoc 'c '((c d)(a b)(e f))) => (c d) 12) 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) 13) 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 14) my-last (my-last '(a b c d)) => (d) (my-last '(a b (c d))) => ((c d)) (my-last nil) => nil 15) Reconsider your solution to problem 1, in which you defined MY-MEMBER. If you didn't use tail recursion in solving problem 1, provide a new solution in which you do use only tail recursion. If you did use tail recursion in solving problem 1, provide a new solution in which you use recursion, but not tail recursion. 16) Reconsider your solution to problem 2, in which you defined MY-APPEND. If you didn't use tail recursion in solving problem 2, provide a new solution in which you do use only tail recursion. If you did use tail recursion in solving problem 2, provide a new solution in which you use recursion, but not tail recursion. 17) Reconsider your solution to problem 4, in which you defined MY-REVERSE. If you didn't use tail recursion in solving problem 4, provide a new solution in which you do use only tail recursion. If you did use tail recursion in solving problem 4, provide a new solution in which you use recursion, but not tail recursion. 18) Reconsider your solution to problem 5, in which you defined MY-REMOVE. If you didn't use tail recursion in solving problem 5, provide a new solution in which you do use only tail recursion. If you did use tail recursion in solving problem 5, provide a new solution in which you use recursion, but not tail recursion. 19) Reconsider your solution to problem 6, in which you defined MY-SUBSTITUTE. If you didn't use tail recursion in solving problem 6, provide a new solution in which you do use only tail recursion. If you did use tail recursion in solving problem 6, provide a new solution in which you use recursion, but not tail recursion. 20) Reconsider your solution to problem 7, in which you defined MY-INTERSECTION. If you didn't use tail recursion in solving problem 7, provide a new solution in which you do use only tail recursion. If you did use tail recursion in solving problem 7, provide a new solution in which you use recursion, but not tail recursion. Copyright 1996 by Kurt Eiselt. All rights reserved.
Last revised: April 10, 1996