Common Lisp
Contents
LISP in.
[from 'LISt Processing language', but mythically from 'Lots of Irritating Superfluous Parentheses'] AI's mother tongue, a language based on the ideas of (a) variable-length lists and trees as fundamental data types, and (b) the interpretation of code as data and vice-versa. Invented by John McCarthy at MIT in the late 1950s, it is actually older than any other high-level language still in use except FORTRAN. Accordingly, it has undergone considerable adaptive radiation over the years; modern variants are quite different in detail from the original LISP 1.5. The dominant high-level language among hackers until the early 1980s.
0.1: Introduction
Quote Wikipedia: Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 (R2004), (formerly X3.226-1994 (R1999)).[1] From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived[2] for use with web browsers.
Common Lisp was developed to standardize the divergent variants of Lisp (though mainly the MacLisp variants) which predated it, thus it is not an implementation but rather a language specification. Several implementations of the Common Lisp standard are available, including free and open source software and proprietary products.
Common Lisp is a general-purpose, multi-paradigm programming language. It supports a combination of procedural, functional, and object-oriented programming paradigms. As a dynamic programming language, it facilitates evolutionary and incremental software development, with iterative compilation into efficient run-time programs.
Common Lisp includes CLOS, an object system that supports multimethods and method combinations. It is extensible through standard features such as Lisp macros (compile-time code rearrangement accomplished by the program itself) and reader macros (extension of syntax to give special meaning to characters reserved for users for this purpose).
This series of articles intends to demonstrate all of the above, as well as giving the reader a general introduction to Lisp programming, with a leaning to Common Lisp specifics.
This part of the series has been aimed at those who might not have any prior programming experience in any language, but it is just as valid for readers who are coming from a C-related language or Java background.
In this part, we aim to cover the basic Lisp data types, symbols, dealing with values and functions, and the evaluation of Lisp code in a Lisp environment.
Each major section will begin with a series of definitions taken either from the Jargon File or from the Common Lisp HyperSpec. They are present to provide the actual definitions used by the ANSI Common Lisp standard, and as a brief overview of what that particular section aims to demonstrate. Do not concern yourself with fully understanding the definitions, that will happen once you have understood the principles involved in each section.
0.2: Notation
Lisp uses a form of notation known as prefix notation (also known as Polish notation).
This means that, rather than writing 5 + 5, we write + 5 5.
If you are not used to prefix notation, or you're too used to infix notation (as used in C, C++, Java, Cblunt et al) then the switch might lead to confusion at the beginning, but do not worry. The more you use Lisp, the easier it will become to read, just like any other language takes time to learn to read.
0.3: How to read the Lisp example code
Lisp documentation usually has a specific format when it comes to example Lisp code. This format represents Lisp statements and any results that are a product of evaluation.
There are two forms of examples that I will be using in this article. The first being a simple example of Lisp syntax, and it will look like:
(a-syntax-example ()
(representing how a Lisp statement would look)
(it is not meant to be typed in to a Lisp prompt, but)
(just highlights how a given Lisp statement would look))
The second form of example is designed to show you code that has been typed in at a Lisp prompt. It shows both the code, prefixed by CL-USER> to represent the prompt that Lisp presents, any side effects, and any results of evaluation.
CL-LISP> ... code that you type in at a Lisp prompt will go here ...
... and might well span several lines ...
... it will be indented in a way to distinguish it from output ...
... the first line will be prefixed with 'CL-LISP' to illustrate ...
... the prompt that a Lisp system will present to you when it is ...
... accepting input ...
Any byproducts or side effects will be listed here, not delimited by anything.
=> The result of a Lisp evaluation will go here, delimited by an arrow.
OR=> If the evaluation can return different results, then OR=> represents this.
AND=> If the evaluation returns multiple results, then AND=> represents this.
NOT=> If the function works differently from what one would expect, NOT=> represents this
There are also some typographical conventions used throughout the article:
- Any Lisp expression encountered in the text will be ITALIC AND UPPER CASE.
- Any concept or Lisp terminology will be italic
- When any Lisp operator is defined, it will be in the form of the Common Lisp HyperLink documentation. See below.
The Common Lisp HyperSpec is one of the main sources of Common Lisp documentation and is the source for most of the documentation that is quoted when we look at a specific Lisp symbol. Although I do not expect you to be able to read and understand the CLHS documentation on the first pass, I would sincerely hope you spend some time in getting used to the phraseology used. Most of the time I will paraphrase the important parts of the CLHS documentation beneath its quotation.
0.4: Obtaining and installing a Common Lisp system
There are many many different Common Lisp implementations out there today. Some commercial, some open source. Each one has their own pros and cons, and I will leave you to discover which one you prefer. However, for the purpose of these articles, and also given the fact that I know this particular Common Lisp system supports the four main architectures in use today, I will recommend you obtain LispWorks Personal Edition.
You can download LispWorks Personal Edition from the LispWorks download page. It is available for Windows, MacOS X, Linux, and FreeBSD, and ships with good quality documentation, UI support, and an integrated editor, freeing you from the extra workload of setting up GNU Emacs or XEmacs on your system.
0.5: Entering code into Common Lisp
Once you have installed and launched LispWorks, you will be presented with a window quite similar to this one:
The window with the 'CL-USER 1 >' text in it is called the 'Lisp Listener', and is where you will be entering most of your Lisp code.
LispWorks has other facilities that we will explore later on in this series. If you desire, you can read the LispWorks user guide here.
0.6: Dealing with errors in Common Lisp
It is perfectly OK to make mistakes, we all do it. But mistakes made in an alien environment can lead to confusion and panic. Although I am not going to turn you into a Lisp debugger expert in one or two paragraphs, I will show you how to deal with most errors you may receive while using LispWorks.
This is what an error would look like:
CL-USER 1 > (HACK THE-GIBSON)
Error: Undefined operator HACK in form (HACK THE-GIBSON).
1 (continue) Try invoking HACK again.
2 Return some values from the form (HACK THE-GIBSON).
3 Try invoking something other than HACK with the same arguments.
4 Set the symbol-function of HACK to another function.
5 Set the macro-function of HACK to another function.
6 (abort) Return to level 0.
7 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
CL-USER 2 : 1 >
In this case, the error message is telling us that HACK is undefined, and that Lisp is unsure what to do.
The numbered options listed below the error are things called restarts. They allow us to inform Lisp how we intend to correct this error. For the most part, the simplest restart while learning Lisp is simply 'get me the hell out of here' -- otherwise known as 'Return to level 0.', or simply 'abort'.
There are two ways of doing this in LispWorks. The first is by typing :C followed by the number of the restart, e.g.:
CL-USER 1 > (HACK THE-GIBSON)
Error: Undefined operator HACK in form (HACK THE-GIBSON).
1 (continue) Try invoking HACK again.
2 Return some values from the form (HACK THE-GIBSON).
3 Try invoking something other than HACK with the same arguments.
4 Set the symbol-function of HACK to another function.
5 Set the macro-function of HACK to another function.
6 (abort) Return to level 0.
7 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
CL-USER 2 : 1 > :C 6
CL-USER 3 >
This will call the 'abort' restart and place you back at the top-level prompt.
The second is by using a button on the GUI:
The button with the arrow trying to escape from between parenthesis is the one you want.
1.0: The Very Beginning -- Atoms, Symbols, and Lists
atom n.
any object that is not a cons. "A vector is an atom."
cons n.v.
1. n. a compound data object having two components called the car and the cdr.
2. v. to create such an object.
3. v. Idiom. to create any object, or to allocate storage.
list n.
1. a chain of conses in which the car of each cons is an element of the list, and the cdr of each cons is either the next link in the chain or a terminating atom.
2. the type that is the union of null and cons.
symbol n.
an object of type symbol.
1.1: Atoms
The most basic form of primitive in Common Lisp is the atom. It is the most basic data type available in Lisp, and anything that is not a list is an atom.
Here are some examples of atoms:
3.141
foo
"oh my god think of the children"
thing
oh-wow-look-at-the-stars
42
convert/string->number
*
-
Lisp is a strongly-typed language but atoms themselves are not typed, rather the value that the atom contains is. As an example, let us consider the atom 42. It is an atom with a numerical value, a number. Thus, the type of 42 is number.
An atom named "hello there" is an atom with a string value, thus the type of "hello there" is string.
When one types an atom in to a Lisp prompt, the atom will self-evaluate -- that is, it will return its own value. This is the most basic of Lisp expression.
CL-USER> 42
=> 42
CL-USER> "Hello"
=> "Hello"
1.2: Symbols
What if an atom is neither a string or a number, what happens then? That is when an atom gets typed as a symbol.
The symbol is a data type that is unique to Lisp, and the symbol itself is quite flexible with what can be done with it.
Remember though, only an atom's value is typed, so a symbol is just an atom with a value of the symbol data type.
A symbol can contain both a value and a function, and when it does contain a value or function is said to be bound.
The act of giving a symbol a value or function is known as binding.
There are two special symbols that you will want to know about here and now. These are: T and NIL.
If you are used to C, you could equate T as true, and NIL as both false and null. That is pretty much their exact meaning in Lisp. NIL is a null value that equates to both an empty list and a false value, with T being the boolean truth value.
1.3: Lists
Lists are one of the basic data types in Lisp. A list is basically any atom surrounded by parentheses.
Here are some example lists:
(all work and no play makes Jack a dull boy)
(1 2 (3 4 (5 6) 7) 8 9)
(42 is the meaning of life the universe and everything)
("what" exclaimed Harry)
(this weeks lottery numbers are 42 12 8 19 27 5 1)
(defun hello () (format t "hello there!"))
Lists have an internal structure that you will want to be aware of. Each list is made up of cons cells, and each cons is made up of what is called a car and cdr.
We use three functions to both create and access the contents of cons cells: CONS, CAR and CDR
Surprisingly, cons, car, and cdr actually mean something: construct, Contents of the Address part of Register, and Contents of the Decrement part of Register. These actually go back to the old days of Lisp in the 1950s.
These days you don't have to care beyond knowing that CONS creates a cons cell, CAR references the 'head' of the cons cell, and CDR references the 'tail' of the cons cell.
This is a cons cell:
[ * | * ]--> cdr
|
v
car
If you are used to C, then you might recognise cons cells for what they really are, linked list nodes.
In the following example of CONS, CAR and CDR, we have a symbol named MY-CONS, which has a cons cell value with a car of 42 and a cdr of 76:
CL-USER> MY-CONS
=> (42 . 76)
CL-USER> (CAR MY-CONS)
=> 42
CL-USER> (CDR MY-CONS)
=> 76
We can represent this as:
[ * | * ]--> 76
|
v
42
At this point it is worth noting that the creators of Common Lisp understood the fact that CAR, CDR et al might be considered antiquated, and added in some functions with names that are easier to understand. So, instead of using CAR, you could use FIRST; and instead of using CDR, you could use REST.
Lists are groups of cons cells, with the last element being NIL, such as:
[ * | * ]-->[ * | * ]-->[ * | * ]--> NIL
| | |
v v v
2 4 6
This represents the list (2 4 6).
Now, there are two ways to actually create a list. The first is by using CONS:
CL-USER> (CONS 1 (CONS 2 (CONS 3 (CONS 4 (CONS 5 NIL)))))
=> (1 2 3 4 5)
The second way, and the way that's actually used, is using LIST:
CL-USER> (LIST 1 2 3 4 5)
=> (1 2 3 4 5)
You can see that we cons a lot in that above example. We cons 5 times. That is consing. Each time you create a cons cell, or a list, or modify a list in a way that results in a copy of that list is returned, you are consing.
The same constructs can be used to assemble lists with sublists. Consider the following list (1 2 (9 8 7) 3 4). The cons cell layout would look like:
[ * | * ]-->[ * | * ]-->[ * | * ]-->[ * | * ]-->[ * | * ]--> NIL
| | | | |
v v | v v
1 2 | 3 4
v
[ * | * ]-->[ * | * ]-->[ * | * ]--> NIL
| | |
v v v
9 8 7
A list with sublists can be constructed using CONS and LIST in the same way as 'flat' lists:
CL-USER> (CONS 1 (CONS 2 (CONS (CONS 9 (CONS 8 (CONS 7 NIL))) (CONS 3 (CONS 4 NIL)))))
=> (1 2 (9 8 7) 3 4)
CL-USER> (LIST 1 2 (LIST 9 8 7) 3 4)
=> (1 2 (9 8 7) 3 4)
As a list is a series of conses, CAR and CDR work just as they would work on cons cells. In the following example, we have a symbol named my-list which has a value of (1 2 3 4 5):
CL-USER> MY-LIST
=> (1 2 3 4 5)
CL-USER> (CAR MY-LIST)
=> 1
CL-USER> (CDR MY-LIST)
=> (2 3 4 5)
CL-USER> (CAR (CDR MY-LIST))
=> 2
CL-USER> (CADR MY-LIST)
=> 2
If you've spotted CADR, then you've just noticed one of the many car/cdr-related symbols that are used as shortcuts. Instead of typing (CAR (CDR ...)), you can just type (CADR ...).
You may remember that I mentioned FIRST and REST above, all car/cdr-related symbols also have corresponding symbols with names that might be more clear.
- The car: CAR, FIRST
- The car of the cdr: CADR, SECOND
- The car of the cdr of the cdr: CADDR, THIRD
- The car of the cdr of the cdr of the cdr: CADDDR, FOURTH
2: Binding -- Assigning values
binding n.
an association between a name and that which the name denotes. "A lexical binding is a lexical association between a name and its value." When the term binding is qualified by the name of a namespace, such as "variable" or "function," it restricts the binding to the indicated namespace, as in: "let establishes variable bindings." or "let establishes bindings of variables."
evaluate v.t.
(a form or an implicit progn) to execute the code represented by the form (or the series of forms making up the implicit progn) by applying the rules of evaluation, returning zero or more values.
evaluation n.
a model whereby forms are executed, returning zero or more values. Such execution might be implemented directly in one step by an interpreter or in two steps by first compiling the form and then executing the compiled code; this choice is dependent both on context and the nature of the implementation, but in any case is not in general detectable by any program. The evaluation model is designed in such a way that a conforming implementation might legitimately have only a compiler and no interpreter, or vice versa.
form n.
1. any object meant to be evaluated.
2. a symbol, a compound form, or a self-evaluating object.
3. (for an operator, as in "<<operator>> form") a compound form having that operator as its first element. "A quote form is a constant form."
scope n.
the structural or textual region of code in which references to an object, a binding, an exit point, a tag, or an environment (usually by name) can occur.
lexical closure n.
a function that, when invoked on arguments, executes the body of a lambda expression in the lexical environment that was captured at the time of the creation of the lexical closure, augmented by bindings of the function's parameters to the corresponding arguments.
2.1: How binding works
Binding is the act of associating a symbol with a function or a value. It an important concept to master, as the idea of assignment within Lisp is somewhat different than it would be in most other languages.
For example, in C one assigns a value to a variable using the assignment operator (=) thusly:
int value = 42;
The immediate act of that assignment is to store the number 42 in an area of memory called the stack, the compiler then keeps track of the location of the number inside the stack.
Lisp does things differently. When one binds a value to a symbol, that value is stored inside memory with the symbol keeping track of where it is via the symbol's value slot.
The same takes place when one binds a function to a symbol, except the symbol's function slot is used.
There are various Lisp operations that bind symbols to value and functions and change symbol bindings, and we shall be looking at a few in the following subsections. But first, a word about evaluation.
2.1.1: Evaluation
Although we will be looking at evaluation in depth in section 3, it has come to the point where I have to tell you what evaluation means, otherwise the following sections will not make any sense. So, in this subsection we will look at forms and evaluation briefly.
A form is an expression or group of expressions that are evaluated by the Lisp interpreter. It is essentially a list where the car is a symbol with a bound function.
The act of evaluation is the process whereby the Lisp interpreter will parse the form, evaluate each argument in turn, and then 'call' the function with the arguments, and finally returning any results that might have been generated.
In the following example we have a Lisp form that the interpreter can evaluate:
CL-USER> (* (+ 4 4) (+ 7.62 (1+ 4.56)))
=> 105.44
As we can see, the interpreter has evaluated (* (+ 4 4) (+ 7.62 (1+ 4.56))), and given us the result of 105.44 (as represented by the '=>' indicator.)
2.1.2: LET
Here is the CLHS (Common Lisp HyperSpec) documentation for LET:
Quote LET: Special Operator LET, LET*
Syntax:
let ({var | (var [init-form])}*) declaration* form* => result*
let* ({var | (var [init-form])}*) declaration* form* => result*
Arguments and Values:
var---a symbol.
init-form---a form.
declaration---a declare expression; not evaluated.
form---a form.
results---the values returned by the forms.
Description:
let and let* create new variable bindings and execute a series of forms that use these bindings. let performs the bindings in parallel and let* does them sequentially.
The form
(let ((var1 init-form-1)
(var2 init-form-2)
...
(varm init-form-m))
declaration1
declaration2
...
declarationp
form1
form2
...
formn)
first evaluates the expressions init-form-1, init-form-2, and so on, in that order, saving the resulting values. Then all of the variables varj are bound to the corresponding values; each binding is lexical unless there is a special declaration to the contrary. The expressions formk are then evaluated in order; the values of all but the last are discarded (that is, the body of a let is an implicit progn).
let* is similar to let, but the bindings of variables are performed sequentially rather than in parallel. The expression for the init-form of a var can refer to vars previously bound in the let*.
The form
(let* ((var1 init-form-1)
(var2 init-form-2)
...
(varm init-form-m))
declaration1
declaration2
...
declarationp
form1
form2
...
formn)
first evaluates the expression init-form-1, then binds the variable var1 to that value; then it evaluates init-form-2 and binds var2, and so on. The expressions formj are then evaluated in order; the values of all but the last are discarded (that is, the body of let* is an implicit progn).
For both let and let*, if there is not an init-form associated with a var, var is initialized to nil.
The special form let has the property that the scope of the name binding does not include any initial value form. For let*, a variable's scope also includes the remaining initial value forms for subsequent variable bindings.
Wow, doesn't that one look complicated! Well, first off, we can ignore LET* for now, we're not interested in what it does yet. Let's concentrate on LET.
There are two forms of arguments it can understand.
The first form of argument is one single symbol, which is not bound to a value:
CL-USER> (LET (FOO)
... )
The second form of argument is a list containing the symbol and an initial value to bind it to:
CL-USER> (LET ((FOO 42)
(BAR 96))
... )
When LET is used, it creates a block of code (and a lexical scope, as we will discuss in the next section). It is in that block of code that all operations on the defined symbols must take place.
CL-USER> (LET ((FOO 20)
(BAR 10))
(* (* FOO BAR)
(+ (/ BAR FOO)
(* BAR BAR)
(- FOO FOO))))
=> 20100
You should note that 'block' means the (* (* FOO BAR) ... ) chunk inside the let.
It is said that any symbol bound to a value by LET is only available inside the block of code defined by LET. This means that FOO and BAR are only bound to 20 and 10 inside the LET, and is called environment. Environment and scope are two highly related idioms, as we will discover in the next section.
2.1.3: SET
Here is the CLHS documentation for SET:
Quote SET: Function SET
Syntax:
set symbol value => value
Arguments and Values:
symbol---a symbol.
value---an object.
Description:
set changes the contents of the value cell of symbol to the given value.
(set symbol value) == (setf (symbol-value symbol) value)
SET takes two arguments, a symbol and a value. This is setting at its most basic, and works thus:
CL-USER> (SET 'FOO 42)
=> 42
CL-USER> FOO
=> 42
Notice I have to use a ' in front of the symbol name. This is a special Lisp notation and it is a shortcut for the QUOTE function. QUOTE simply returns the name of the symbol without evaluating it:
CL-USER> (LISP-IMPLEMENTATION-TYPE)
=> "Symbolics Common Lisp"
CL-USER> (QUOTE LISP-IMPLEMENTATION-TYPE)
=> LISP-IMPLEMENTATION-TYPE
The reason why we have to use QUOTE is that symbols do usually self-evaluate, thus when it is evaluated before SET is called, the evaluation process will flag an error.
2.1.4: SETQ
Now, so we don't have to remember to quote everything properly, some bright spark created SETQ -- SET Quoted.
Quote SETQ: Special Form SETQ
Syntax:
setq {pair}* => result
pair::= var form
Pronunciation:
['set,kyoo]
Arguments and Values:
var---a symbol naming a variable other than a constant variable.
form---a form.
result---the primary value of the last form, or nil if no pairs were supplied.
Description:
Assigns values to variables.
(setq var1 form1 var2 form2 ...) is the simple variable assignment statement of Lisp. First form1 is evaluated and the result is stored in the variable var1, then form2 is evaluated and the result stored in var2, and so forth. setq may be used for assignment of both lexical and dynamic variables.
If any var refers to a binding made by symbol-macrolet, then that var is treated as if setf (not setq) had been used.
SETQ takes a variable number of arguments, with each argument being in the form of a pair, evaluates the form of each pair and places the result in the corresponding variable of each pair.
CL-USER> (SETQ MY-VARIABLE 42)
=> 42
CL-USER> (SETQ ANOTHER-VARIABLE 12
USEFUL-THING 98
MY-NAME "Paul")
=> "Paul"
CL-USER> (SETQ EVAL-THIS (* 4 4)
AND-THIS (* (+ 4 9) 10))
=> 130
As we can see, SETQ works similar to SET, but we no longer need to quote the symbol name.
2.1.5: SETF
Another form used for setting values is SETF -- SET Form. SETF is used in a similar way to SETQ, but with one big difference. The variable (known as a `place' with SETF) is evaluated via a setf expander as well, as we will find out.
Quote SETF: Macro SETF, PSETF
Syntax:
setf {pair}* => result*
psetf {pair}* => nil
pair::= place newvalue
Arguments and Values:
place---a place.
newvalue---a form.
results---the multiple values[2] returned by the storing form for the last place, or nil if there are no pairs.
Description:
setf changes the value of place to be newvalue.
(setf place newvalue) expands into an update form that stores the result of evaluating newvalue into the location referred to by place. Some place forms involve uses of accessors that take optional arguments. Whether those optional arguments are permitted by setf, or what their use is, is up to the setf expander function and is not under the control of setf. The documentation for any function that accepts &optional, &rest, or ..... key arguments and that claims to be usable with setf must specify how those arguments are treated.
If more than one pair is supplied, the pairs are processed sequentially; that is,
(setf place-1 newvalue-1
place-2 newvalue-2
...
place-N newvalue-N)
is precisely equivalent to
(progn (setf place-1 newvalue-1)
(setf place-2 newvalue-2)
...
(setf place-N newvalue-N))
For psetf, if more than one pair is supplied then the assignments of new values to places are done in parallel. More precisely, all subforms (in both the place and newvalue forms) that are to be evaluated are evaluated from left to right; after all evaluations have been performed, all of the assignments are performed in an unpredictable order.
For detailed treatment of the expansion of setf and psetf, see Section 5.1.2 (Kinds of Places).
If we ignore the references to PROGN and PSETF (because we're not interested in those symbols just yet) we can see that SETF has a similar syntax to SETQ, and looks like:
CL-USER> (SETF QUOTIENT 1/2)
=> 1/2
CL-USER> (SETF THE-MACHINE-THAT-GOES-BING "bing"
SOME-COMPLEX-LIST '(4 (5 6) (7 (8 (9 10) 11) 12) 13 14))
=> "bing"
=> (4 (5 6) (7 (8 (9 10) 11) 12) 13 14)
It is important here to know the difference between SET, SETQ, and SETF.
Do you remember that I mentioned something about a setf expander? This is why SETF is nearly always used in high-end Lisp code. It can expand the variable via evaluation to obtain the exact place to store the new value, e.g.:
CL-USER> (SET 'SOME-LIST '(1 2 3 4))
=> (1 2 3 4)
CL-USER> (SETQ (CAR SOME-LIST) 4)
=> ERROR: CANNOT SETQ (CAR SOME-LIST) -- NOT A SYMBOL.
CL-USER> (SETF (CAR SOME-LIST) 4)
=> 4
CL-USER> SOME-LIST
=> (4 2 3 4)
SETF saw that I wanted to set the CAR of the list to 4 and worked with (CAR SOME-LIST) to actually set the car of the list to 4, whereas SETQ couldn't.
That is the difference between SETF and SETQ. SET is rarely used in high-end Lisp code mostly because it is very basic and requires correct quoting.
2.1.6: DEFUN
I'll be honest with you. I feel that touching upon DEFUN here might cause a lot of confusion due to the CLHS documentation. If it does, please be honest and post a comment saying so. Hopefully, if you take the documentation with a large portion of salt and just concentrate on the syntax, things will make sense, and you will be able to pass through this subsection without too much mental fighting.
Quote defun: Macro DEFUN
Syntax:
defun function-name lambda-list [[declaration* | documentation]] form*
=> function-name
Arguments and Values:
function-name---a function name.
lambda-list---an ordinary lambda list.
declaration---a declare expression; not evaluated.
documentation---a string; not evaluated.
forms---an implicit progn.
block-name---the function block name of the function-name.
Description:
Defines a new function named function-name in the global environment. The body of the function defined by defun consists of forms; they are executed as an implicit progn when the function is called. defun can be used to define a new function, to install a corrected version of an incorrect definition, to redefine an already-defined function, or to redefine a macro as a function.
defun implicitly puts a block named block-name around the body forms (but not the forms in the lambda-list) of the function defined.
Documentation is attached as a documentation string to name (as kind function) and to the function object.
Evaluating defun causes function-name to be a global name for the function specified by the lambda expression
(lambda lambda-list
[[declaration* | documentation]]
(block block-name form*))
processed in the lexical environment in which defun was executed.
(None of the arguments are evaluated at macro expansion time.)
defun is not required to perform any compile-time side effects. In particular, defun does not make the function definition available at compile time. An implementation may choose to store information about the function for the purposes of compile-time error-checking (such as checking the number of arguments on calls), or to enable the function to be expanded inline.
DEFUN is one of the functions used to create and bind a symbol to a function, and it takes takes several arguments.
For now, we are only interested in a few of those:
- function-name: The name of the function we wish to define.
- documentation: An optional string that contains any documentation for the function.
- lambda-list: For now, imagine this as a list of arguments for the function. We shall discuss lambda later.
- form: The code that comprises the function.
So, we can see that DEFUN will compose a function with the given function-name, lambda-list of arguments, and the form body (the contents of the function), let's see it in action:
CL-USER> (DEFUN SQUARE (X)
"The square of x is x multiplied by x."
(* X X))
=> SQUARE
In the above example, I have defined a function named SQUARE with one argument, X. The function returns the value of X multiplied by X.
We can read the function declaration as: define the function of square x to be the value of x multiplied by x.
A more complex example would be:
CL-USER> (DEFUN COMPOUND-INTEREST (AMOUNT INTEREST TERM)
(* AMOUNT (EXPT (1+ INTEREST) TERM)))
=> COMPOUND-INTEREST
Which would be: a function named COMPOUND-INTEREST with three arguments, AMOUNT, INTEREST, and TERM. The function returns the value of AMOUNT multiplied by the exponential of 1 plus INTEREST by the power of TERM. You might know this as a simple compound interest formula.
2.1.7: Lambda
In the world of mathematics, lambda is defined as function expressions in the lambda calculus. And lambda calculus is a formal system for function definition, function application and recursion.
Lisp was created as a vehicle for set theory and lambda calculus. This has huge consequences for the language in general.
It brings about the notation of lambda expression.
A lambda expression is a function with no name -- an anonymous function. It can be used ad-hoc, it can be stored in a symbols value, and it can also be stored in a symbols function. This brings an incredible level of power to Lisp.
The Lisp function for creating lambda expressions is simply LAMBDA.
Let's see how LAMBDA would work:
CL-USER> (FUNCALL (LAMBDA (X) (* X X)) 10)
=> 100
FUNCALL applies the given function to its argument -- in effect I am manually doing what Lisp automatically does, because I know that LAMBDA just evaluates to an anonymous function, it does not then evaluate that function.
Now that we know what FUNCALL does, we can see that when the lambda function is applied to 10, the result is 100 -- the result of 10 * 10.
We didn't store it, we didn't name it, we just used it as a one-shot throw-away function.
This where things can get complex. I've opened a can of worms here. Take a deep breath and prepare yourself for what is about to come.
All bound functions in Lisp are lambda expressions.
Take our use of DEFUN for example. It is not as straight-forward as one is lead to believe. It actually has a function of:
(LAMBDA (X)
(* X X))
which is equivalent to:
CL-USER> (SETF (SYMBOL-FUNCTION 'FOO) (FUNCTION (LAMBDA (X) (* X X))))
=> #<anonymous interpreted function 200D61E2>
CL-USER> (FOO 10)
=> 100
Where SYMBOL-FUNCTION returns the function slot of the symbol (remember, SETF expands so we end up setting the function slot) and FUNCTION creates something known as a lexical closure, which we will look at in the next part of this article.
Lambda, as an idiom, is quite a powerful tool within Common Lisp, as it allows functions to be created for just one specific instance, and then thrown away. We shall discover just how useful these are in a future article..
2.2: Scope
Scope is the 'locality' of a symbol. It is the environment that a symbol lives in, the neighbourhood of atoms that are aware of each other.
There are many different environments with Common Lisp. The main one is the top-level environment, the Lisp environment available right from the get-go, where everything is available. It is then compartmentalized down from there.
Take this following code for example. FOO is a named symbol with a value in the top-level environment. SOME-COMPLEX-FOO is a named symbol with a function in the top-level environment. But FOO is also a symbol bound to a value inside the function SOME-COMPLEX-FOO. What value does FOO hold inside SOME-COMPLEX-FOO?
CL-USER> (DEFVAR FOO 42)
=> FOO
CL-USER> (DEFUN SOME-COMPLEX-FOO (FOO BAR FROB QUUX)
(LET ((FOO (* FOO 3))
(BAR (+ BAR 9)))
(* FOO
(+ BAR
(* QUUX 2)
(* FROB 9)))))
=> SOME-COMPLEX-FOO
- FOO is bound to the value of 42 in the top-level environment, and...
- SOME-COMPLEX-FOO has a LET expression that binds FOO to the value of (* FOO 3), but...
- That symbol named FOO exists within the lexical scope of the LET block, thus...
- FOO inside that lexical scope will contain the value of whatever (* FOO 3) evaluates to, but..
- FOO outside that lexical scope will still contain 42.
If you are unsure of what scope a symbol is in, you can scan the source code and find the right-most block -- in this case that block is LET.
Let's try it:
CL-USER> (SOME-COMPLEX-FOO 1 2 3 4)
=> 138
CL-USER> FOO
=> 42
2.3: Closures
A lexical closure is an environment which is closed off from any other environment except its own. What I mean by that is that any symbol bound within that closure can only be affected by a function bound within that very same closure.
Think of closures as a private lexical environment and you won't be far wrong.
As an example, consider the following function. It is not making use of any lexical closure:
CL-USER> (SETF FOO 42)
=> 42
CL-USER> (DEFUN SOME-COMPLEX-BAR (FROB QUUX)
(LET ((FROB (* FOO QUUX)))
(* (FOO QUUX)
(+ (/ QUUX FROB)
(* FROB FOO)))))
=> SOME-COMPLEX-BAR
If SOME-COMPLEX-BAR were to be evaluated, what would the FOO inside that function contain?
- FOO is bound to the value of 42 inside the top-level environment, and...
- SOME-COMPLEX-BAR makes use of FOO in its expressions, but...
- FOO is not bound in a lexical scope by LET, therefore...
- FOO contains 42.
If FOO were to be changed in the top-level environment, the result of the evaluation of SOME-COMPLEX-BAR's body form would change.
If a function were to make use of a lexical closure, it would have the following properties:
- It has to be defined within a lexical scope.
- If it makes use of any symbol bound within that local scope, and that symbol shares its name with a symbol in any higher scope, then that function will always use the symbol from its own scope
- If the function changes the value of any bound symbol within its lexical scope, any symbol with the same name from any higher scope will not reflect those changes.
In layman's terms. a lexical closure locks a function in to a given lexical scope, as the following examples will demonstrate:
CL-USER> (LET ((BAR 12))
(DEFUN GET-BAR ()
BAR))
=> GET-BAR
CL-USER> (SETF BAR 42)
=> 42
What value would GET-BAR return?
- A LET expression binds a symbol named BAR in its lexical scope to a value of 12, and...
- The function GET-BAR is defined within the same lexical scope, which...
- Returns the value of the symbol named BAR.
- A symbol named BAR within the top-level scope is bound to a value of 42
But does GET-BAR return 42?
CL-USER> (GET-BAR)
=> 12
CL-USER> BAR
=> 49
Why? Because GET-BAR is trapped in what is known as a lexical closure, in which the environment has BAR defined as 12, and in which BAR can be changed only by a function which has that same environment -- e.g. is in the same lexical closure.
CL-USER> (LET ((BAR 12))
(DEFUN GET-BAR ()
BAR)
(DEFUN SET-BAR (X)
(SETF BAR X)))
=> SET-BAR
CL-USER> BAR
=> 49
CL-USER> (SET-BAR 9219)
=> 9219
CL-USER> BAR
=> 49
CL-USER> (GET-BAR)
=> 9219
From this example we can see that BAR, GET-BAR, and SET-BAR are within the same lexical scope and lexical closure, therefore any call to GET-BAR and SET-BAR will not use or affect the symbol named BAR in the top-level scope.
3: Evaluation -- Form and function
Evaluation is the process by which Lisp arrives at the results by interpreting a given form. But what exactly does that mean?
In this section, we will find out. There is a caveat emptor, though... Lisp is a complex beast, and the rules for evaluation are also complex. What is presented here is a simplified view in order to help you understand how Lisp arrives at its results when evaluating a form.
Let's abstract down evaluation into some generalised rules:
- One: Atoms evaluate to themselves.
- Two: Most symbols will evaluate to their bound value.
- Three: Lists will evaluate to the function of the first symbol in the list, unless it is quoted.
- Four: Arguments are evaluated from left to right.
- Five: Functions are applied to their arguments.
- Six: Special forms and macros will often do special things when it comes to evaluation.
This is about as complicated as I want things to get right now, let's look deeper into evaluation.
3.1: Atoms
As stated in the rules above, atoms self-evaluate to their own value. When you type 5 into your Lisp console, it prints 5 in return -- the numbers own value. The same would happen if you were to type "hello".
An atom that is a number, string, or keyword will self-evaluate. An atom that is a symbol will generally behave in a way that we will look at in the next subsection.
3.2: Symbols
When you type a symbol into your Lisp console, then Lisp will attempt to evaluate the value of the symbol. If you had a symbol called five which was bound to a value of 5, then typing five would result in Lisp printing 5 in reply.
Remember, Lisp will type anything that it can't quite get the type for as a symbol, and a symbol will not evaluate until bound to a value or function.
3.3: Lists
When you type a list into your Lisp console something special happens. Lisp will look at the first thing in the lisp and, if it is a symbol, attempt to evaluate the symbols function. If you had a symbol called HALT-AND-CATCH-FIRE which was bound to a function, then typing (HALT-AND-CATCH-FIRE) would result in Lisp evaluating the function and displaying the results.
However, if the list is quoted, then the list will not be evaluated. Instead, the QUOTE function would be evaluated, resulting in the contents of the list being displayed. For example:
CL-LISP (QUOTE (LIST 1 2 3 4 5))
=> (LIST 1 2 3 4 5)
CL-LISP '(LIST 1 2 3 4 5)
=> (LIST 1 2 3 4 5)
You use the QUOTE (or it's ' shortcut) when you would like to treat a list as data, i.e. you don't want it to be evaluated.
Remember, evaluating a list will mean that the first atom in the list will be evaluated. Thus, the atom will need to be a symbol that is bound to a function.
3.4: Arguments are evaluated from left to right
When Lisp evaluates a form with arguments, it will evaluate the arguments starting with the left-most argument and working its way towards the right-most.
I will demonstrate this with an form that does some simple mathematics:
(* (+ 4 4) (+ 7.62 (1+ 4.56))) + The function (*, in this case) and it's list of arguments
(+ 4 4) |---> The first argument
4 | |---> 4 self-evaluates to 4
4 | |---> 4 self-evaluates to 4
8 | `---> apply + to 4 and 4, result is 8
(+ 7.62 (1+ 4.56)) |---> The second argument
7.62 | |---> 7.62 self-evaluates to 7.62
(1+ 4.56) | | `---> The second argument
4.56 | | |---> 4.56 self-evaluates to 4.56
5.56 | | `---> apply 1+ to 4.56, result is 5.56
13.18 | `---> apply + to 7.62 and 5.56, result is 13.18
105.44 `---> apply * to 8 and 13.18, result is 105.44
=> 105.44
3.5: Functions are applied to their arguments
This one is quite simple. Any arguments to a function will be evaluated in the order defined above, with the function applied to the results.
When an atom or list is presented for evaluation, it is known as a form. As stated above, if the form is an atom, then Lisp attempts to evaluate it, and when the form is a list, Lisp attempts to evaluate the first atom in that list.
Congratulations! You have made it to the end of this part of my series on Common Lisp. Hopefully you are now ready to move on to the next part.
Revision history
2010-03-22 Initial version.
2010-03-23 Improved layout, added typographical and example style information, removed forward and circular references.
2010-03-24 Corrected a typo. |
Copyright Open Source Institute, 2006 