Before we get to the lab assignment, here are some notes about list manipulation in lisp:
For historical reasons, the lisp terms for the basic list manipulation functions are car (head), cdr (rest), and cons (prepend); the function null will test to see if a list is empty or not.
In lisp, lists can contain other lists - for example, we could have the list '(1 (2.1 2.2) 3 4). The second element of this list is itself a list, so if we let l be that list, then (car l) is 1, and (car (cdr l)) is the list '(2.1 2.2). Note also that mapcar applies a function to each element of the "top-level" list; it would apply the function 4 times if called on the list list (for example:
(mapcar #'listp l))
produces the result (NIL T NIL NIL); listp is a function that returns t (true) if its argument is a list (such as '(2.1 2.2)) and nil (ie (), or false) if its argument is not a lis (such as 1)).
To apply a function to an argument with apply, we need a function and a list of arguments for that function (even if its a unary function). So if we want to apply the function times2 to 5, we would do this:
(defun times2 (x)
(* 2 x))
(apply 'times2 '(5))
If you try to do (apply 'times2 5) , you get an error message. If you want to apply times2 to a variable, you can use the "list" function to produce a list containing the value of the variable, like this:
(let ((y 5))
(apply 'times2 (list y)))
This is a hard way to do (times2 5). Note that you shouldn't try just make a list by quoting it (as we did with 5 above), like this:
(let ((y 5))
(apply 'times2 '(y))) ; WRONG
Since that applies times2 to y, not 5.
Write the functions for Question 1-4 in a file lab8.lisp in your simple-funcs project, and draw your answer to question 5 on paper and hand it in.
1) Write a recursive function "length-of-list" to find the length of a list. Do not use the lisp "length" function. Your function should return 4 when applied to the list l above.
2) We can represent a tree with a list of lists - the list l in the notes above represents a tree with 4 branches from the root, the second of which branches again. Write a function "mapleaf" that applies a function to every "leaf" in such a list, and produces a list of the same structure containing the results. That is, (mapleaf #'times2 l) should produce (2 (4.2 4.4) 6 8).
3) Write a function "compose" that returns the composition of two unary functions (the composition of f and g is a function that gives (f (g x)) for any x. For example, we would get the list (12 (14.2 14.4) 16 18) if we did this with mapleaf and compose: (mapleaf (compose #'times2 #'(lambda (x) (+ x 5))) l)
4) Write a function "specialize" that takes a binary function f and a value val, and produces a unary function that produces the same result as (f val x) for any argument x. For example, the result of (specialize #'- 0) negates numbers, and (specialize #'/ 1) gives inverses: (mapcar (specialize #'- 0) '(2 3 4)) should give the result (-2 -3 -4).
5) During the execution of (mapcar (specialize #'- 0) '(2 3 4)), the function - is called exactly once with the arguments 0 and 3, to produce -3. Draw a diagram showing what the stack and heap look like at the start of this call to -.