The goal of this lab is to give you some practice working with Common Lisp functions and expressions. In particular, the exercises focus on the idea of higher-order functions, which is one of the benefits of using Lisp and its relatives.
Common Lisp is an interactive, functional programming language that uses fully-parenthesized prefix notation. As such, it may be quite different from any other language you have used. If so, you will want to do plenty of exercises to become familiar with its syntax and style.
Part of learning any language is learning its vocabulary, the primitive expressions built into the language. The flip side to Common Lisp's simple and uniform syntax is that the language provides over 700 built-in functions. So, as you read the first chapters in Graham's text, pay special attention to the predefined functions they discuss. They will serve as the foundation for the programs we read and write later on.
Included in Common Lisp's set of pre-defined operations are a number of special forms. A special form is like a function except that it has its own evaluation rule. Consider setf:
(setf x 10)
This expression assigns the symbol x the value of 10. But setf cannot be a function: if it were, then it would operate on the value of x, not x itself. Instead, it is a special form, with its own evaluation rule: take the first argument literally, evaluate the second argument, and bind the first argument to the value of the second.
We will encounter a number of special forms in the next few labs:
setf sets a variable or a field to a new value.
defun defines a function.
defparameter defines a special variable.
let binds local variables.
if provides two-way selection of control.
cond chooses one of several alternatives.
function or #' refers to a function by name.
quote or ' refers to data literal.
One feature that sets Common Lisp apart from most languages that you know is its facility with higher-order functions. A higher-order function takes another function as an argument.
We use this idea in lots of different scenarios in real life. Suppose that I asked you to sort a pile of graded papers. You might ask me whether I want them sorted by name or by score. You then might ask whether I want them sorted in ascending or descending order. Sorting is a function that can be parameterized with functions that specify the comparison to use (less than or greater than) and the field to compare (compare names or compare scores).
Common Lisp makes it easy to write functions like sort by treating functions like any other data. The functions that "define" the sort can be passed as arguments to it.
Among the higher-order functions that you will want to become familiar with soon are Common Lisp's many list-manipulation functions. Graham discusses several in Chapter 3. For example, mapcar applies its first argument, a function, to every item in its second argument, a list. Its value is a list of the answers.
Lisp also provides two ways to invoke a function without using the standard notation:
At first, these two functions will seem a bit strange. But you will later see just how much power they give to the programmer: the ability to select a function and its arguments dynamically. The result is code that can respond to changes in its environment at run-time -- and even apply functions that the programmer did not create!
Building a Common Lisp program consists of creating a set of functions that, when applied to an input in an appropriate order, computes the desired output. Given this emphasis on computation as function evaluation, writing large Lisp programs requires a particular sort of programming discipline. (I think that you'll find the same discipline will help you to manage in the face of so many parentheses.)
Two essential components of this discipline are not new to you, but they now become even more imnportant:
Disciplined use of abstractions is an essential part of how humans tame complexity!
Prior to doing the in-lab activity, be sure that you have done the following:
Please seek clarifications on the topics you see in the first three chapters from me or from one of the Lisp books on reserve at the library. The benefits of early clarification dwarf the cost of obtaining them.
;;
;; AUTHOR: Peter Norvig
;;
(defun power (x n)
"power raises x to the nth power. n must be an integer >= 0.
This executes in log n time, because of the check for even n."
(cond ((= n 0) 1)
((evenp n) (expt (power x (/ n 2)) 2))
(t (* x (power x (- n 1))))
))
>(first-name '(Mark McGwire))
MARK
>(first-name '(Sir Laurence Olivier))
LAURENCE
>(last-name '(Mark McGwire))
MCGWIRE
>(last-name '(Marcus Welby MD))
WELBY
You may assume that the honorifics and suffixes are defined as top-level lists named *name-honorifics* and *name-suffixes*
>(assoc 'a '((a 1) (b 2)))
(A 1)
>(assoc 'b '((a 1) (b 2)))
(B 2)
Define a version of assoc named retrieve. Your function should return the first list that has any element that matches the target. For example:
>(retrieve 1 '((a 1) (b 2)))
(A 1)
>(retrieve 2 '((a 1) (b 2)))
(B 2)
>(retrieve 'a '((a 1) (b 2)))
(A 1)
>(retrieve 'b '((a 1) (b 2)))
(B 2)
>(make-assoc-list '(a b c d e) '(1 2 3 4 5))
((A 1) (B 2) (C 3) (D 4) (E 5))
"gcl-loadable" means that I should be able to do the following:
I should not have to edit the file saved from mail. This means that...
If you have comments or questions that you would like to send accompanying your submission, please send a separate message.
Both your message and your print-out should reach me by Wednesday, September 12, at 2:00 PM.
We are still in the phase of learning Common Lisp. As promised, we are moving briskly, leaving you to do a little side reading in an introductory textbook or in a reference manual. I suggest that you do so anyway.
Spend another hour or so playing with Common Lisp after you have completed the in-lab exercises. You would probably be better off to go away for a while and come back for another work session. Try out code that you see in your reading, and experiment with functions to see if you can begin to understand how they work. Try out some of Graham's exercises. The solutions are given in the back of the book, so you can check your understanding immediately.
As a part of your exploration, explain the following Common Lisp transcript:
>(apply 'cdr '((a b c)))
(B C)
>(funcall 'cdr '((a b c)))
NIL
After your second session in the lab, send to me via e-mail your explanation and at least three questions that you have about Common Lisp. Think hard about your questions. Using your time well now to understand Common Lisp will make all the difference in the world in the coming weeks as I ask you to write more, and more complex, Lisp programs.
Your message should reach me by 2:00 PM on Wednesday, September 12.
You have now encountered another way in which Common Lisp is different from many of the languages that know: the same identifier can be used as the name of a function and the name of a data value. For example:
>(setf x 10)
10
>(defun x (y) (+ y y))
X
>(x x)
20
You know how to get the data value associated with x -- just evaluate it:
>x
10
... and you know how to pass its function binding as a value, using the function special form or #'.
>(mapcar #'x (list x))
(20)
How can you find out what the function value associated with a symbol is? Use the function symbol-function:
>(symbol-function 'x)
(LAMBDA-BLOCK X (Y) (+ Y Y))
What you see is something close to the lambda expression that Graham introduces on page 26. (What do you get when you pass a built-in function name to symbol-function?) lambda is the basic internal mechanism with which functions are implemented in Lisp. When you use defun, it builds a lambda expression and associates the expression with the name given.
The Lisp interpreter uses the context in which a symbol appears to determine whether to retrieve the associated data value or function value. In the example above, when x appears in the first position of (x x), the evaluator knows to grab the function value; when it appears in the second position, it knows to grab the data value. That is why we have to use the special form #' whenever we wish to pass a function as an argument: to instruct the evaluator to retrieve the function value associated with the symbol and not the data value.