Basics of running LISP on openlab: To run LISP on openlab, you must add this line to your .bash_profile

module load acl/9.0

Then source .bash_profile

Then you can run it with the command

alisp

you can then enter expressions. When you want to leave, type control-D, then Y.

You can write your functions in a file, fns.l, then load them in with the command load

(load fns.l)

You can trace functions,

(trace mymemq)

You can quit with exit function

(exit)

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 >. We will start by writing some built-in functions, but we will add my_ to the front of the name. I tried to put these in order of difficulty (IMO). You need only code and test 100 points worth of the functions below.

1 Define a function `my_length` that takes one parameter, a list L, and returns the number of top-level elements in L. Examples:

. (my_length nil) --> 0

. (my_length '(b (a b c)) --> 2

. (my_length '(a (((b))) c)) --> 3

. (my_length '(a b c)) --> 3

2 Define a function `my_memq` that takes two parameters, a symbol A and a list of symbols L, and returns the list starting where the symbol bound to A was found. It returns nil otherwise. Examples:

. (my_memq 'a nil) --> nil

. (my_memq 'b '(a b c)) --> (b c)

. (my_memq 'd '(a b c d e f g)) --> (d e f g)

. (my_memq 'd '(a b c d)) --> (d)

. (my_memq 'd '(a b c)) --> nil

3 Define a function, my_append, that takes two parameters L1, L2 and returns the result of appending the two lists together. You must not call append.

. (my_append (a b c) (d e f)) --> (a b c d e f)

. (my_append ((a) (b) (c)) ((d) (e) (f))) --> ((a) (b) (c) (d) (e) (f))

. (my_append nil (d e f)) --> (d e f)

. (my_append (a b c) nil) --> (a b c)

4 Define the function `my_attach` which takes an object O and a list L and returns the list L with O added to the end. Examples:

. (my_attach 'a nil) --> (a)

. (my_attach 'd '(a b c)) --> (a b c d)

. (my_attach '(a) '(b c)) --> (b c (a))

5 Define the function 'my_assoc' that takes an atom A and a list L and returns the association pair for A. L is of the form ((key1 . value1)(key2 . value2) (keyn . valuen)) Examples:

. (my_assoc a nil) --> nil

. (my_assoc a ((a . b)(c e f)(b))) --> (a . b)

. (my_assoc c ((a . b)(c e f)(b))) --> (c e f)

. (my_assoc b ((a . b)(c e f)(b))) --> (b)

. (my_assoc f ((a . b)(c e f)(b))) --> nil

6 Define the function 'freq' that takes a symbol A and a list L and counts the occurance of symbol A found anywhere in L. Examples:

. (freq 'c '((a c) c e)) --> 2

. (freq 'f '(((s) o ) d)) --> 0

. (freq 'f '(((f) f) f f)) --> 4

7 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

8 Define a function `my_last` that takes two parameters, a symbol A and a list of symbols L, and returns the list starting where the last occurance of symbol A is in L. It returns nil oly if A is not in the list. Examples:

. (my_last 'a '(a b c a b c a b c d e f g)) --> (a b c d e f g)

. (my_last 'b '(a b c a b c a b c d e f g)) --> (b c d e f g)

. (my_last 'c '(a b c a b c a b c d e f g)) --> (c d e f g)

. (my_last 'g '(a b c a b c a b c d e f g)) --> (g)

. (my_last 'h '(a b c a b c a b c d e f g)) --> nil

9 Define the function 'my-reverse' that takes a list L and returns the reverse of L. Examples:

. (my-reverse nil) --> nil

. (my-reverse (a)) --> (a)

. (my-reverse '(1 2 3 4 5)) --> (5 4 3 2 1)

. (my-reverse '((1 2 3) 4 ((5 6)))) --> (((5 6)) 4 (1 2 3))

10 Define the function 'is-pattern?' that takes two SIMPLE lists pat and str and returns the sublist of str which starts with the pat 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

11 Define the function 'first-atom' that takes a list L and returns the first atom of L. Examples:

. (first-atom nil) --> nil

. (first-atom '((2 (1) 4) 6)) --> 2

. (first-atom '((((s)) o ))) --> s

. (first-atom '(1 (((2)) 3 4))) --> 1

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