Programming Languages Homework 4 Due 10/22

• In writing the following LISP functions, you may use only the primitive functions listed below. You may also write and use auxiliary functions, but you must submit these along with your solution. Some functions require subfunctions. You MUST use recursion instead of looping. DO NOT assume the lists are SIMPLE (i.e., every element is an atom) unless it is explicitly specified in the problem statement. EFFICIENCY NOTE: Do not traverse the whole list more than once. For example, do not flatten the list before processing. Please provide sample runs that adequately test the functionality of each function. Primitive functions: defun, cond, cons, car, cdr, null, eq, listp, atom, symbolp, +, -, <, and >.
• (5 points) Define a function contains that takes two parameters, a symbol A and a list of symbols L, and returns T only if L contains A as one of its elements. Examples:
  • (contains 'a nil) --> nil
  • (contains 'b '(a b c)) --> t
  • (contains 'b '(a (((b))) c)) --> t
  • (contains 'd '(a b c)) --> nil
• (10 points) Define the function insert-q which takes an object O and a list L and returns the list L with O added to the end. Examples:
  • (insert-q 'a nil) --> (a)
  • (insert-q 'd '(a b c)) --> (a b c d)
  • (insert-q '(a) '(b c)) --> (b c (a))
• (15 points) Define the function 'is-pattern?' that takes two SIMPLE lists pat and str and returns the sublist of str if pat is a substring of str. Otherwise it returns nil. Examples:
  • (is-pattern? '(a b s) '(c d b a s)) --> nil
  • (is-pattern? '(c a c) '(b a j a c a c t u s)) --> (c a c t u s)
  • (is-pattern? nil '(a n y l i s t)) --> nil
  • (is-pattern? '(l i s p) nil) --> nil
• (10 points) Define the function 'mapping' that takes 2 arguments - a list L, and an integer value val. Every element of the list L is a list of two atoms - key and object. (e.g. L <-- ((35 kim) (67 clinton) (45 emma))) The function returns a list of objects whose key is less than val. Examples:
  • (mapping '((35 kim) (67 clinton) (45 emma)) 40) --> (kim)
  • (mapping '((24 a) (15 b) (56 c) (19 d)) 26) --> (a b d)
  • (mapping '((90 a) (80 b) (70 c)) 40) --> nil
• (10 points) Define the function 'first-atom' that takes a list L and returns the first atom of L. Examples:
  • (first-atom '((2 (1) 4) 6)) --> 2
  • (first-atom '((((s)) o ))) --> s
  • (first-atom '(1 (((2)) 3 4))) --> 1
• (10 points) Define the function 'rest-list' that takes a list L and returns a list that removes the first atom. Examples:
  • (rest-list '(1 2 3 4 5)) --> (2 3 4 5)
  • (rest-list '((1) 2 3)) --> (2 3)
  • (rest-list '(((a b) c) d e)) --> (((b) c) d e)
• (10 points) Define a function find-all that takes a symbol A and a list L and finds and returns the first symbol following each occurrence of A in L, or nil if A does not occur in L. Note that A may occur nested within L, possibly as the last element of a sublist. You may assume that there is always a symbol occurring afterwards. Examples:
  • (find-all 'a nil) --> nil
  • (find-all 'a '(b a c a e)) --> (c e)
  • (find-all 'a '(b d c e)) --> nil
  • (find-all 'a '(b (a a) c)) --> (a c)
  • (find-all 'a '((b a) ((c a b)))) --> (c b)
• (10 points) Define the function 'occ' that takes a list L and a symbol A and counts the occurance of symbol A in L. Examples:
  • (occ '((a c) c e) 'c) --> 2
  • (occ '(((s) o ) d) 'f) --> 0
• (20 points) Define the function 'total-reverse' that takes a list L and returns the reverse of L including all sublists. Examples:
  • (total-reverse '(1 2 3 4 5)) --> (5 4 3 2 1)
  • (total-reverse '((1 2 3) 4 ((5 6)))) --> (((6 5)) 4 (3 2 1))
  • HINT: To be most efficient, you may internally define a stack and push each atom of L to that stack whenever you pop it from L.
• Submit: a listing of all your solutions to the lisp functions described above plus sample runs on at least the examples provided above. Also submit an electronic version of your solutions so we may run them if necessary.
• Note if you are using Unix for the first time, check out my introduction to Unix at Unix Introduction