To somebody (like me) used to "normal" procedural programming languages with a rich syntax, Lisp is just different. The syntax consists basically of nested sequences of literals enclosed in parentheses. No keywords, no indentation (like in Python), no statements separated by periods or semicolons, no curly braces. However, there is one intriguing advantage to this approach: code and data use the same presentation and can be treated and manipulated with the same means.
The examples follow Geoffrey Gordon's lisp tutorial and some examples from Paul Graham's "Common Lisp" book. Starting clisp leads us to a Lisp shell similar to the Python shell in the first chapter.
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2002
[1]> It works similar to the Python shell in that expression are evaluated and the result is shown in the shell. This means, that our "Hello World" program is again the shortest possible version:
> "Hello World" "Hello World" >
Lisp is just echoing the string value "Hello World". The differences between Lisp and other languages become apparent once we try to start evaluating simple expressions. The only way to evaluate something, is to enclose a function (i.e., the symbol of a function) followed by its arguments in parentheses. For an expression such as "4 + 5", this means that we have to follow the symbol "+" with the arguments "4" and "5".
> (+ 4 5) 9
In other words: Lisp always uses prefix notation (remember Forth, which does the opposite?). For numerical expression this implies that you have to take care of the preference rules yourself using plenty of parentheses.
> (+ (* 2 3) (* 4 5)) 26
There is also an advantage to this notation. In general, you can apply an arithmetic operator (and many other functions) to more then two arguments without repeating the operator, for example:
> (* 2 3 4 5) 120
As we see, Lisp treats the first element of a list a function which is then applied to the remaining elements in the list. The syntax is extremely simple: only parentheses and a few quotation symbols (as we will see below) are treated as special tokens. Otherwise, all kinds of characters can be combined to form symbols, and the symbols are separated with white space. We could call a variable or function *+-x%z5/}$. This can sometimes be surprising, because what looks like an arithmetic expression, e.g., 3*4+5 is just another symbol. Another remark: symbols are case insensitive, that is, the symbols xY and Xy are identical and will be shown in the default mode as XY.
The Lisp expressions we have seen are called forms and the first element is called the form function. Lisp uses this kind of syntax even if the first element is not a real function, but instructs Lisp to perform some special action. Such a form is called a special form and the first element is either a macro or a special built-in operator. In this short introduction we will not distinguish the different forms and always talk about forms and functions. Syntactically, all forms look the same.
As an example, consider a situation where we don't want the default behavior evaluating a form, but are instead interested in the list as such. In this case, we need to quote it. Quoting can't be a normal function since it changes the behavior of the Lisp system. Hence, there is a special quote form which turns the form evaluation off, and, since lists are such prominent data structures in Lisp, you can alternatively just put a single quote in front of the list.
> (quote (1 2 3)) (1 2 3) > (list 1 2) (1 2) > '(1 2 3) (1 2 3)
Not surprisingly, Lisp comes with a large library of functions manipulating lists. The most fundamental ones give you the head (first element) or the tail (the rest) of a list, or, as the opposite, create a new list from a given head and tail.
> (first '(1 2 3)) 1 > (rest '(1 2 3)) (2 3) > (cons 1 '(2 3)) (1 2 3) > (list 1 2 3) (1 2 3) > (length '(1 2 3)) 3
In older programs you will still find the original names car and cdr instead of first and rest. The old names date back to the first implementation of Lisp. There are many ways to access parts or elements of a list besides head and tail. Here are the most often used functions:
> (first '(1 2 3 4)) 1 > (second '(1 2 3 4)) 2 > (third '1 2 3 4)) 3 > (nth 3 '(1 2 3 4)) 4 > (nth 0 '(1 2 3 4)) 1 > (elt '(1 2 3 4) 3) 4 > (nthcdr 2 '(1 2 3 4 5)) (3 4 5) > (last '(1 2 3 4)) (4) > (last '(1 2 3 4 5) 2) (4 5)
Note the two functions nth and elt used to access individual elements in a list. The new function elt works for all kinds of sequences whereas the old nth works for lists only. Annoyingly, the two functions use a different argument order. Besides the core functions cons and list, there are also many functions creating new lists. Note, however, that these functions are different from the list manipulation functions we have seen in the more procedural oriented languages. The functions here always create new lists and leave the original ones unaltered.
> (append '(1 2 3) '(4 5 6) '(7 8 9)) (1 2 3 4 5 6 7 8 9) > (remove 2 '(1 2 3 4)) (1 3 4)
There is a corresponding set of "destructive" list functions, but they are rarely used. First, moving away from the functional programming style makes it harder to follow the programs logic. Second, the non-destructive list functions are implemented very efficiently. The main overhead is the additional memory used.
Before we can define more interesting examples, we have to learn how to use variables. Variables are set using the setf function (which is actually a macro). If the variable does not exist yet, it is created automatically.
> (setf x "blah") "blah" > x "blah" > (setf x 1234) 1234 > x 1234 > (setf x '(1 2 3)) (1 2 3)
More general, you can use setf to assign a new value to any "settable" place (the alternative setq is restricted to setting variables). As an example, Lisp allows you to change a value in a list using setf combined with the list accessor function.
> (setf x '(1 2 3 4)) (1 2 3 4) > (setf (elt x 2) 55) 55 > x (1 2 55 4)
This is a first example of a destructive list function. Other useful examples are the stack functions push and pop.
> (setf x nil) NIL > (push 4 x) (4) > (push 5 x) (5 4) > (pop x) 5 > x (4)
The variables defined with setf are global and therefore should be avoided. Local variables are defined using the let statement.
> (let ((x 5) (y 6))
(+ x y))
11This is a first example of a typical nested Lisp statement. Everything is expressed with nested lists. The let function takes two arguments: a list of local variable definitions and an expression. The local variable definitions are name-value pair. In this example we are defining two variables, x and y, set to 5 and 6, respectively. The scope of these variables is the expression given as the second argument to the let function. You may be able to guess now how control statements are written in Lisp.
> (if (> 1 2) 5 6)
6
> (setf x 50)
50
> (cond ((< x 10) "small")
((< x 100) "medium")
(t "big"))
"medium"
> (case x
(10 "ten")
(20 "twenty")
(otherwise "some other number"))
"some other number"The if function, for example, has three arguments: the condition, the expression returned if the condition evaluates to true, and the expression returned if the condition is false. And since we are dealing with common Lisp, there is not just one conditional expression, but a whole set, the most useful ones besides if being cond and case.
[34]> (do ((i 0 (+ i 1)))
((> i 5))
(format t "i=~A~%" i))
i=0
i=1
i=2
i=3
i=4
i=5The do loop is similar to the for loop in C. Like the if function it has three arguments. The first argument is a list of loop variable definitions, the second argument contains the stop condition and optionally expression to be evaluated afterwards, and the third argument is the loop's body. A loop variable definition consists of three expressions: the name of the loop variable, its initial value, and the update expression to be evaluated at the end of the loop. In Java, the same loop would look like:
for (int i=0; i<=5; ++i) {
System.out.println("i=" + i);
}Next to lists, functions are the most prominent elements in Lisp (it's a functional language after all). A function is defined using another function called defun.
> (defun times2 (x) (* 2 x)) TIMES2 > (times2 55) 110 > (defun fac (n) (if (< n 2) 1 (* n (fac (- n 1))))) FAC > (fac 5) 120
The definition of the faculty function not only shows that you can define functions in a compact manner (including recursion), but also that the parentheses add up quickly. When writing Lisp programs, an editor showing matching parentheses helps a lot as does proper indentation:
> (defun fac (n)
(if (< n 2)
1
(* n (fac (- n 1)))))
FACOptional and keyword arguments are possible (possibly with default) and so are variable argument lists. The optional arguments of a function are introduced by the keyword &optional followed by pairs containing the name of the argument and the default value.
> (defun times2 (x &optional (y 1)) (* x y 2)) TIMES2 > (times2 10) 20 > (times2 10 2) 40>
Similarly, keyword arguments follow &key. Each keyword argument is either just the name of the argument or a pair of name and default value like in the case of optional argument.
> (defun linfunc (x &key a (b 0)) (+ (* a x) b)) LINFUNC > (linfunc 10 :a 2) 20 > (linfunc 10 :a 2 :b 5) 25
When calling a function with a keyword argument, the name of the argument is preceded with a colon. Finally, variable argument lists can be passed as lists to a function using the &rest parameter definition.
> (defun vararg (x &rest r) (print x) (print r)) VARARG > (vararg 5) 5 NIL NIL > (vararg 1 2 3 4 5) 5 (2 3 4 5) (2 3 4 5)
As seen above for the car and cdr functions, the result of a function can be used to set the corresponding value. To define such a function ourselves, defun is used together with setf.
> (defun primo (l) (car l)) PRIMO > (defun (setf primo) (x l) (setf (car l) x)) (SETF PRIMO) > (setf y '(1 2 3)) (1 2 3) > (primo y) 1 > (setf (primo y) 55) 55 > y (55 2 3)
So what is a function? Using funcall, we can apply a function explicitly, but when we try to apply our times2 function, we receive an error message.
> (funcall times2 2)
EVAL: Die Variable TIMES2 hat keinen Wert. This means that the symbol times2 does not have a value as a variable (but as a function). Functions and variables live in different worlds. More precisely, Common Lisp is a two cell Lisp dialect. What does this mean? Internally, a symbol is represented as a structure. In Common Lisp, this structure has two slots (or cells), one for the value of the symbol treated as a variable, one for the symbol treated as a function. Having seen languages such as Python and Smalltalk this strikes us as odd. Why not treat functions as any other value (or object)? It looks like this is one of the things Common Lisp has carried over from its beginnings. The light-weigth Lisp dialect Scheme uses the one cell approach. To put Common Lisp in perspective, don't forget that some modern languages (e.g., Java) do not treat functions as values at all.
Coming back to our example, we can apply our function using its symbol 'times2.
> (funcall 'times2 4) 8
funcall knows how to get the function for a given symbol (from the symbol's function cell). This help us with funcall, but we still can't assign functions to other symbols or pass them as arguments. That is we can't treat functions as values (or objects) yet. To get the function object (called closure in the functional world), there is a special function called function, and, since it is used quite often, the prefix #' as a shortcut.
> (funcall (function times2) 4) 8 > (funcall #'times2 4) 8 > (print #'times2) #<CLOSURE TIMES2 (X) ...>
Hence, funcall takes either a closure or a symbol. When given a symbol, funcall retrieves the function from the function cell of the symbol.
We have seen anonymous functions in the form of Python's lambda expressions. In Lisp, a lambda expression looks like a function definition with the defun replaced by lambda. A lambda expression returns a function object or closure directly.
> (lambda (x) (+ x 2)) #<CLOSURE :LAMBDA (X) (+ X 2)> > (funcall (lambda (x) (+ x 2) 3)) 5 > (setf x (lambda (x) (+ x 2))) #<CLOSURE :LAMBDA (X) (+ X 2)> > (funcall x 3) 5
Now we can go from functions to closure and define closures directly, but we can't turn these closures into new functions. In the example above, x is not a function.
> (x 3) *** - EVAL: the function X is undefined
The missing link is symbol-function which can be used in combination with setf to set a function, that is, the function cell of a symbol.
> (setf (symbol-function 'add2) (lambda (x) (+ x 2))) #<CLOSURE :LAMBDA (X) (+ X 2)> > (add2 3) 5
Defining a function with defun is equivalent to setting the symbol-function of a symbol to a closure.
There are two ways to get the function object from a symbol, either by applying function to the function or by applying symbol-function to the symbol
> (function +) #<SYSTEM-FUNCTION +> > (function add2) #<CLOSURE ADD2 (X) ... > > (symbol-function '+) #<SYSTEM-FUNCTION +> > (symbol-function 'add2) #<CLOSURE ADD2 (X) ... >
Now that we know lists and functions we can tackle more complicated list processing. Let's start with the familiar map and reduce functions.
> (mapcar #'(lambda (x) (* 2 x)) '(1 2 3)) (2 4 6) > (map 'list #'(lambda (x) (* 2 x)) '(1 2 3)) (2 4 6) > (reduce #'+ '(1 2 3 4)) 10 > (reduce #'+ '(1 2 3) :initial-value 10) 16
As you can imagine, the cryptic name mapcar denotes the original function. The map function belongs to a set of relatively new functions in Common Lisp which generalize the original versions to arbitrary sequences. The first argument is always the type of the result. The filter function is called remove-if, but otherwise works as expected.
> (remove-if #'oddp '(1 2 3 4 5)) (2 4)
The dolist function iterates through a list (just like Smalltalk's do:).
> (dolist (i '(1 2 3 4)) (print i)) 1 2 3 4 NIL
Besides these straight-forward functions there is an almost overwhelming amount of functions which look for elements, check properties of the list (e.g., do all elements satisfy a certain condition), and so forth. In most cases, you do not need to iterate through the list yourself, but can apply one of these functions.
>
For now it looks like Lisp really is a pure list processing language. While this was true in the beginning, Common Lisp now supports a whole range of collection classes. Starting with hash tables, the Lisp syntax requires some getting used to, but we can do all the things we know other high level languages.
> (setf x (make-hash-table :test 'equal)) #S(HASH-TABLE EQUAL) > (setf (gethash "blah" x) 55) 55 > (gethash "blah" x) 55 ; T > (setf (gethash "blub" x) 66) 66 > (maphash #'(lambda (key value) (format t "~&~A=~A" key value)) x) blub=66 blah=55 NIL
The first expression creates a hash table which uses the equal operator for the equality test when looking for a key. The gethash function looks for a value for a given key. It is a settable function so that we can also use it in combination with setf to insert a key-value pair into the table.
Common Lisp also offers multidimensional arrays of fixed size. An array is constructed using the make-array function whose first argument is the list of sizes, one for each dimension (or just a single size in case of a one-dimensional array).
> (setf x (make-array '(2 3) :initial-element 0.0)) #2A((0.0 0.0 0.0) (0.0 0.0 0.0)) > (setf (aref x 1 2) 55) 55 > x #2A((0.0 0.0 0.0) (0.0 0.0 55))
Elements can be get and set using the aref function which is the equivalent of elt for arrays. One-dimensional arrays are vectors and can alternatively be contructed with the vector function which works like the list function, but constructs a vector instead of a list.
> (setf x (vector 1 2 3)) #(1 2 3) > (svref x 1) 2
An instead of aref, one can use the more efficient "simple vector reference" function svref.
Lisp's equivalent of a C structure is defined with defstruct. This special form creates the type and associated constructor, copy, and accessor functions.
> (defstruct point x y) POINT > (setf p (make-point :x 5 :y 6)) #S(POINT :X 5 :Y 6) > (format t "p=~A" p) p=#S(POINT :X 5 :Y 6) > (setf q (copy-point p)) #S(POINT :X 5 :Y 6) > (setf (point-y p) 10) 10 > p #S(POINT :X 10 :Y 6) > q #S(POINT :X 5 :Y 6)>
Note that the constructor and copy function end with the structure's name, whereas the accessor functions use it as a prefix.
In many programming languages reading complex data structures is a serious task. As an example, most applications use some kind of configuration file which is interpreted when starting the application. One could even argue that technologies such as XML (used for the representation of hierarchical data structures, not for markup of text) with its corresponding parsers and interfaces were invented to remedy the deficiencies of these programming languages. In Lisp, reading an arbitrarily complex Lisp expression is a single call to read.
> (setf x (read))
(1 2 ("blah" "blub"))
(1 2 ("blah" "blub"))
> x
(1 2 ("blah" "blub"))Read reads exactly one Lisp expression from the input stream. Without arguments, read reads from standard input. The second line shows my input, the nested list (1 2 ("blah" "blub")). The second line is the return value of the setf function. Once we have read the Lisp expression, we can process it like any other Lisp expression. As an example, we can read a lambda expression and execute it.
> (setf x (read)) (lambda (x) (* 2 x) (LAMBDA (X) (* 2 X) > (funcall (eval x) 5) 10
A configuration file could just contain a Lisp expression.
Lisp has mainly two modes when printing objects: the output is either meant for a human being or for a program. As an example, a string is surrounded by double quotes when printed for a computer. This way, a reading program can reconstruct the type. The human reader just gets the string itself. I havn't found an explanation for the extremely mnemonic function names: princ is the people oriented print function, prin1 the one for programs, and print is like prin1, but starts with an additional newline.
> (princ "bla") bla "bla" > (prin1 "bla") "bla" "bla" > (print "bla") "bla" "bla"
Playing with standard input and output is one thing, but in the real world, we would like to read from and write to files. Like many I/O systems, Lisp I/O is stream oriented. The standard input and output we have used so far are examples of streams. The proper starting point to accessing files in Lisp is to create a pathname.
> (setf path (make-pathname :name "test.dat")) #P"test.dat"
Common Lisp's pathname library offers an abstraction of file names on the different operating systems. Once we have a path, we can open the file, write to it, and close it again.
> (setf out (open path :direction :output)) #<OUTPUT BUFFERED FILE-STREAM CHARACTER #P"test.dat" @1> > (princ "Hello World" out) "Hello World" > (close out) T
The problem with this code is that we have to make sure that the close function under any circumstances unless we want to risk a file descriptor leak. A better way to achieve the same thing is to use with-open-file.
> (with-open-file (out path :direction :output) (format out "~A~%" "Hello World") (format out "~A~%" "Hello Again")) "Hello World"
The with-open-file function ensures that the specified stream is available for the block of expressions and that it is properly closed afterwards even in case of an error. You can view it as a predecessor of the using statement in C#. The same can be used to read the file.
> (with-open-file (in path :direction :input) (format t "line: ~A" (read-line in))) line: Hello World NIL
Here are some more interesting functions reading from a file.
> (defun process-lines (in task)
(do ((line (read-line in nil 'eof) (read-line in nil 'eof)))
((eql line 'eof))
(funcall task line)))
PROCESS-LINES
> (with-open-file (in path :direction :input)
(process-lines in #'print)))
"Hello World"
"Hello Again"
NILThe function process-lines reads a stream line by line applying a function to each line. We then apply this new function to the implicitly opened input stream in and simple print each line.