Assignment 1ex (extra, optional)
Assignment 1ex (extra, optional)
------------------------------------------------------------------
Assignment 1ex: GETTING USED TO LISP ON YOUR COURSE ACCOUNT
------------------------------------------------------------------
You won't be doing any programming this week, but it's a good idea to
get used to the LISP environment, and you can do that even if you
don't know how to program in LISP yet. This first part of this week's
assignment will walk you through a step by step tutorial introducing
you to some LISP basics. (Credit where due: I've adapted some of
Prof. Dorr's CMSC421 course materials!) This is far from an exhaustive
introduction, but it's a decent way you can get started entirely on
your own, to get a feeling for what LISP is like. We'll be covering
all this and more in detail through the semester.
Once you've gotten logged in to your course account (on the
AITS computing cluster), do the following.
1. Type "lisp" (without the double quotes) at the shell prompt
and hit return:
---
% lisp
CMU Common Lisp 17f, running on holmes.umd.edu
Send bug reports and questions to your local CMU CL maintainer, or to
cmucl-bugs@cs.cmu.edu.
Loaded subsystems:
Python 1.0, target Alpha
CLOS based on PCL version: September 16 92 PCL (f)
CLX X Library MIT R5.02
Hemlock 3.5
*
---
2. The star (*) is the prompt for working within LISP on this system.
When you're in LISP, the interpreter waits for you to give
it an expression of some kind, evaluates that expression,
and then returns the value it got. For example, try typing
the number 7 and return:
---
* 7
7
---
Try typing an expression like (+ 2 3) and see what gets returned:
---
* (+ 2 3)
5
---
Note that any time you want to quit out of lisp, type (quit)
at the star prompt.
---
* (quit)
%
---
Notice that it has to be (quit) in parentheses!
3. Try typing something that LISP actually doesn't know the value of;
for example, if you type the symbol x, the LISP interpreter
will try to figure out what the value of x is, but fail, because
you haven't bound the symbol x to any value, and unlike numbers
it doesn't have any intrinsic value. LISP will tell you about
the problem as follows:
---
* x
Error in KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER: the
variable X is unbound.
Restarts:
0: [ABORT] Return to Top-Level.
Debug (type H for help)
(EVAL X)
0]
---
The message is telling you where LISP is reporting the error from,
namely a part of the interpreter called
KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER. You don't really
care about that, but you do care about the error message:
"the variable X is unbound". Notice that it is reporting
something about uppercase X, even though what you typed was
lowercase -- LISP is not case sensitive, and traditionally
everything is just treated as if it were uppercase.
You can now muck around in the debugger (if you'd care to try,
take a look at
http://that.cs.umd.edu:8080/local-cgi-bin/info2www?(cmu-user.info)The%20Debugger
for documentation), but
what you'll want to do much of the time is just get out of the
debugger and back to the star prompt. To do this you can
just type a 0 (to choose option 0, return to the top level),
or you can type quit, which will pop you up to the top level.
Be careful not to type (quit) in parentheses, though, or
you'll quit out of the LISP interpreter altogether! In parentheses,
it's a function call to the LISP interpreter; out of parentheses,
it's a command to the debugger saying to go back to the top level.
Yup, computers are a pain sometimes.
---
* x
Error in KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER:
the variable X is unbound.
Restarts:
0: [ABORT] Return to Top-Level.
Debug (type H for help)
(EVAL X)
0] quit
*
---
4. Here are some basics of how expressions get evaluated:
- Number -> number itself (e.g., 7 -> 7)
- String -> string itself (e.g., "hi" -> "hi")
- Symbol -> value of symbol (e.g., X -> 5,
if X has the value 5). Symbols are like variables in
most languages, in that they have a value associated
with them. Some special symbols include T and NIL.
These represent true and false, and can't be set to
any values other than themselves.
- List -> normally function evaluation
In usual mathematical notation, you write a function f
with arguments a and b as f(a,b). In LISP, the notation
is to write it as a list, with the first element being
the function and the rest of the list being the arguments,
e.g. (f a b). That's why to add 2 plus 3, the expression
is (+ 2 3) -- you're applying the function + to arguments
2 and 3.
- If you want to tell LISP to treat something as the
thing itself, for example to treat a list as the list
itself, you put a single quote in front it. For example,
---
* (+ 2 3)
5
* '(+ 2 3)
(+ 2 3)
---
When you gave the first expression to the LISP interpreter,
it evaluated it by calling function + on arguments 2 and 3,
hence returning the result 5. Since the second expression
was quoted, it was evaluated and the result was the list
containing the symbols +, 2, and 3.
Here are some more examples to try. If you get errors,
see Step 3 above for how to get out of an
error and back to the top level of the interpreter.
(+ 1 1)
(* 23 13)
(+ 1 (* 23 13))
(+ (* 2 2) (- 10 9))
(* 2 2 2 2)
(sqrt (* 2 2 2 2))
(/ 25 5)
The following example shows that strings, like numbers,
evaluate to themselves:
"Hello, world!"
Here's another quotation example. Quoting the symbol
means that you want to get the symbol itself, not the
value the symbol is bound to. (Compare this to what we
did in Step 3 above.)
'x
Here's how you assign (or "bind") values to variables.
(setf x 5)
This binds the variable x to the value 5, and returns the value
that x got bound to as a side effect. Notice that now if you
type just x without the quotes
x
it'll give you back the value x is bound to instead of an unbound
symbol error. Similarly, consider:
(setf x (* 2 3))
By the way, don't worry about warnings that the interpreter
is "declaring X special".
Here are some more things to try:
(setf y (reverse '(+ a b)))
The "reverse" function takes a list and reverses it. When this
whole expression was evaluated, first the reverse function was
called on the quoted list containing the symbols +, a, and b
(you needed the quote, or it would have tried to call the plus
function on variables a and b!), giving you a list containing
b, a, and +. Then y was bound to that value. As mentioned above,
the setf function then returned the value that the variable got
bound to.
More to do: set the value l to be a list containing 5 symbols.
(That's lowercase L, not the number 1!)
(setf l '(a b c d e))
Here are some operations on lists: the length function returns the
length of a list:
(length l)
The append function merges two lists together, returning the merged
list as the value. Notice here that l is not quoted but the list
'(f) is quoted -- if you're not entirely sure why, go back and re-read
the description above where the "reverse" function was first used.
(append l '(f))
Now try:
(length l)
Notice that the length of l hasn't changed! That's because
when you called the append function, it computed a NEW merged
list, first copying l and then merging it with '(f) -- what
got returned was the copy. This kind of operation is called
"non-destructive", since it creates a new value without messing
with the values of its arguments. This kind of copying can
be wasteful, in terms of computational efficiency, but it's
often useful and very characteristic of the LISP language.
Now try:
(list '(John Q Public) 'Sandy)
The list function creates a new list whose elements are the
arguments to the function -- in this case a list whose first
element is itself a list, and whose second element is the
symbol Sandy. Symbols like 'Sandy are called "atoms" because
they have no internal structure.
Note how list puts the arguments into a list; it
doesn't merge them like append does. Can you figure
out what the result of the following is going to be before
you try it?
(length (append '(pat Kim) (list '(John Q Public) 'Sandy)))
Notice the order of evaluation is critical here: the
innermost things get evaluated first. That is, first
(list '(John Q Public) 'Sandy)
to give you the list
((JOHN Q PUBLIC) SANDY)
(Remember that uppercase/lowercase doesn't matter!)
Then, continuing, it's as if you've made the function call
(length (append '(pat Kim) '((JOHN Q PUBLIC) SANDY))
(Can you figure out why the second argument to append is quoted?
Try it without the quote!) Next, the append is evaluated,
with its two list arguments, to get
(PAT KIM (JOHN Q PUBLIC) SANDY))
So in the next step it's just like you're evaluating
(length '(PAT KIM (JOHN Q PUBLIC) SANDY))
Can you see why the value is 4? What is the first element
of the list? The third element?
In case you haven't already figured it out, by the way,
you must always be careful that your parentheses match.
You get bizarre errors otherwise.
Have you forgotten what the value of the symbol l is?
Type it to find out:
l
Here are some more things you can do with lists:
(first l)
(rest l)
That last one, rest, gives you a list that is "the rest"
of l after the first element. You can also do
(second l)
(third l)
and so forth. I'm not sure how high these go, but in general
you can use the "nth" function to get the nth element of
a list, e.g. get the fourth element by calling
(nth 3 l)
(Notice numbering of list elements starts from zero.)
And as usual, you can nest these calls. So, for example,
(first (rest l))
gives you the first element of the rest of l, which is equivalent
to the second element on the list.
What will
(rest '(a))
give you? Yes, it should give you the empty list,
since after that first element the list is empty.
But in LISP the empty list is written NIL -- it is
the same value that is used for "false".
A few more things to do with lists, and we'll be done for now.
An "association list", or a-list, is a special kind of list
whose elements are pairs of elements; intuitively, this is a
way to represent a mapping from one set to another (i.e.,
a mathematical relation). For example
(setf departments '((smith physics) (jones math) (perez english)))
This list has three elements, each of which is an ordered pair;
for this example, it gives a fictitious name and the department
that person is in. The assoc function can be used to search
such a list, e.g.
(assoc 'jones departments)
finds the pair where jones is the "key", and
(second (assoc 'jones departments))
gives you the second element in the pair, which is the
way you can find out what value jones is associated with.
If what you're looking for isn't found, the value NIL
is returned
(assoc 'jackson departments)
and by definition any element of the empty list, NIL,
is itself NIL:
(second (assoc 'jackson departments))
5. Try the following as a review exercise.
Set variable list1 to be a list containing symbols q1 q2 q3 q4.
Set variable list2 to be a 3-element list whose elements are
themselves the following lists:
(a b)
(c d e)
(e f)
Optionally turn in: what do you get when you do the following? Do
these in order and show the result at each step:
(setf combined (append list1 list2))
(length combined)
(setf newlist (rest (rest (rest (rest combined)))))
(third (assoc 'c newlist))
combined
(pop combined)
(pop combined)
(pop combined)
(first combined)
(push 'q5 combined)
combined
Return to the course home page.