Learning Lisp Fast - Part 3

(Source and copyright: Sean Luke - George Mason University, cs.gmu.edu/~sean/lisp/LispTutorial3.html)

Yet more Lisp!


As before, the table cell below shows what you type, and the output, for this tutorial. Text shown in blue you are responsible for typing, with a Return at the end of the line. Text shown in black indicate stuff that is printed back to you. Text shown in red are remarks -- do not type them.

If the cell is divided by a line, as is shown at right, then this indicates two different examples.

This text is being printed out.
You would type this text         [This is a remark]

Here is another example.

List Functions

Lisp's primary data type is the list.

A list is a linked list elements. The linking structures are called cons cells. A cons cell is a structure with two fields: car and cdr. The car field points to the element the cons cell is holding. The cdr field points to the next cons cell, or to nil if the cons cell is at the end of the list.

When you are storing a list, you are really storing a pointer to the first cons cell in the list. Thus car (first) returns the thing that cons cell is pointing to, and cdr (rest) returns the next cons cell (what the cdr is pointing to). Similarly, the cons function allocates a new cons cell, sets its cdr to the cons cell representing the original list, and sets its car to the element you're tacking onto the list. Thus the original list isn't modified at all! You've just made a new cons cell which reuses the list to "extend" it by one.

last returns (as a list) the last n elements in the list. Really it just marches down the list and finds the appropriate cons and returns that to you. last's argument is optional -- if it's not there, it returns (as a list) the last element in the list.

butlast returns (as a list) a copy of everything but the last n elements in the list.

list takes some n arguments and makes a list out of them. It differs from just quoting a list because the arguments are evaluated first (it's a function).

[1]> (last '(a b c d e))
[2]> (last '(a b c d e) 3)  

(C D E)
[3]> (butlast '(a b c d e))  
(A B C D)
[4]> (butlast '(a b c d e) 3)  
(A B)
[5]> (list 1 2 (+ 3 2) "hello")  
(1 2 5 "hello")
[6]> '(1 2 (+ 3 2) "hello")  
(1 2 (+ 3 2) "hello")

nth works on lists just like elt. You can use it in setf. For lists, it's a tiny bit faster than (the more general function) elt. Note that nth's arguments are not the same order as those for elt. This is historical.

listp is a predicate which returns true if its argument is a list.

atom is a predicate which returns true if its argument is an atom. Note that nil is both a list and an atom. It's the only thing which is both.

consp is a predicate which is true if its argument is a list but is not nil.

null is a predicate which returns true if its argument is nil.

If you think about it, the logical not function is identical to the null function.

There are a great many more list functions. See "conses" in the text.

[1]> (listp '(4 3 8)) 
[2]> (listp nil)  

[3]> (consp '(4 3 8))
[4]> (consp nil)
[5]> (atom 'a)
[6]> (atom nil)
[7]> (null nil)

[8]> (not nil)
[9]> (nth 4 '(a b c d e))

There are a great many permuations of cdr and car.

caar is the same as (car (car ... ))

cdar is the same as (cdr (car ... ))

caadr is the same as (car (car (cdr ... )))

cddddr is the same as (cdr (cdr (cdr (cdr ... ))))

second through tenth return the second through the tenth elements of a list.

[1]> (caar '((a b c) ((d)) e f g h))

[2]> (cdar '((a b c) ((d)) e f g h))  
(B C)
[3]> (caadr '((a b c) ((d)) e f g h))
[4]> (cddddr '((a b c) ((d)) e f g h))
(G H)
[5]> (fourth '((a b c) ((d)) e f g h))

The cdr field of a cons cell doesn't have to point to a list (or to nil). Technically, it can point to anything you like. For example, a single cons cell can point to 45 car and "hello" in its cdr. Such a cons cell is called a dotted pair, because its printed form is (45 . "hello"). Note the period.

You can construct long lists where the last item doesn't point to nil but instead is a dotted pair.

If you think about it, the dotted pair can only be at the end of a list.

Dotted pairs qualify as lists as far as listp is concerned.

[1]> (cons 45 "hello")

(45 . "hello")
[2]> (cons 'a (cons 'b (cons 45 "hello")))
(A B 45 . "hello")
[3]> (listp '(45 . "hello"))

Lists are constructed like beads of pearls. So far we've been careful not to damage them.

setf can be used to do evil things to a list.

You can use setf to modify a list. Since we construct lists which point to original lists, if we modify a list then it might modify other lists which pointed to it.

One particular danger is to use setf to modify cons cells to have circular references. For example, you could use setf to set the cdr of a cell point to the same cell.

Most Lisp systems are smart enough to detect circular references while printing a list to the screen. Some (like CLISP) are not! They'll go into an infinite loop trying to print such beasts. Try it out on osf1 for some fun as well.

[1]> (setf *x* '(a b c d e))

(A B C D E)
[2]> (setf *y* (rest *x*))
(B C D E)
[3]> (setf (rest *y*) '(1 2 3))
(1 2 3)
[4]> *y*
(B 1 2 3)
[5]> *x*
(A B 1 2 3)     [ hey, wait a minute! ]

[6]> (setf *x* '(a))
[7]> (setf (cdr *x*) *x*)
(A A A A A A A A A A A A A A A A A A A A A A A A 
 A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A 
 A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A 
 ...  [ ad naseum ] 

There are a number of destructive versions of list functions. Just as in applying the destructive sequence functions to list, the same warning applies: destructive functions are faster and use much less memory, but because lists are strung together like beads of pearls, make sure you know what you're doing if you choose to use them! Here are two common ones:

nconc is the destructive version of append.

nbutlast is the destructive version of butlast.

[1]> (setf *x* '(a b c d e))

(A B C D E)
[2]> (setf *y* '(1 2 3 4 5))
(1 2 3 4 5)
[3]> (nconc *x* *y*)
(A B C D E 1 2 3 4 5)
[4]> *x*
(A B C D E 1 2 3 4 5)   [ what the ... ]
[5]> (nbutlast 4 *x*)

(A B C D E 1)
[6]> *x*
(A B C D E 1)  [ it keeps modifying *x*! ] 

Predicates and Types

Lisp has a number of predicates to compare equality. Here are some type-specific ones.

(= num1 num2) compares two numbers to see if they are equal. 2.0 and 2 are considered =. Also, -0 and 0 are =.

(char= char1 char2) compares two characters. (can you guess what char>, char<=, etc. do?)

(char-equal char1 char2) compares two characters in a case-insensitive way.

(string= str1 str2) compares two strings.

(string-equal str1 str2) compares two strings in a case-insensitive way.

There are also general equality predicates. These predicates vary in strength. Here are some loose descriptions.

(eq obj1 obj2) is true if obj1 and obj2 are the exact same thing in memory. Symbols and same-type numbers are the same thing: (eq 'a 'a) is true for example. But complex objects made separately aren't the same thing: (eq '(1 2 3) '(1 2 3)) is false. Neither are integers and floats eq with one another: (eq 0 0.0) is false. eq is fast (it's a pointer comparison).

(eql obj1 obj2) is is like eq but also allows integers and floats to be the same (as in (eq 0 0.0) is true). eql is the default comparator for most stuff.

(equal obj1 obj2) says two objects are equal if they are eql or if they "look equal" and are lists, strings and pathnames, or bit-vectors.

(equalp obj1 obj2) says two objects are equal if they look equal. equalp compares nearly every kind of Lisp thing, including all sorts of numbers, symbols, characters, arrays, strings, lists, hash tables, structures, files, you name it. equalp is the slowest comparator predicate, but you will generally find it to be the most useful.

Some numbers should be = but may not be due to numeric precision.

[1]> (eql '(a b) '(a b))
[2]> (equalp '(a b) '(a b))  
[3]> (= 0.25 1/4)  
[4]> (eq (setf *q* '(a b)) *q*)  [ remember the function rule ]

[5]> (string-equal "hello" "HelLo")  
[6]> (= 1/5 .2)  
NIL        [ what the ... ? ] 

Lisp also has predicates to determine the type of objects. You've already seen some such predicates: atom, null, listp.

(numberp obj) is true if obj is a number. There are a number of useful numerical predicates as well: oddp is true if the number is odd (see also evenp). zerop is true if the number is zero. plusp is true if the number is > 0. Etc.

characterp is true if obj is a character. There are a number of subpredicates, such as alphanumericp which is true if the character is a letter or a number.

symbolp is true if it's a symbol. stringp is true if it's a string. arrayp is true if it's an array. vectorp and simple-vector-p are...well you get the idea. There's a lot of this stuff.

[1]> (numberp 'a)
[2]> (stringp "hello")  

Lisp has a general type-determination predicate called typep. It looks like this:

(typep expression type)

A type is (usually but not always) a symbol representing the type (you have to quote it -- it's evaluated). Example types include number, list, simple-vector, string, etc.

Types are organized into a hierarchy: thus types can have subtypes (simple-vector is a subtype of vector, which is a subtype of array, for example). The root type is t. The typep function returns true if the expression has the type that as its base type or as a supertype.

Numeric types in particular have quite a lot of subtypes, such as fixnum (small integers), bignum (massive integers), float, double-float, rational, real, complex, etc.

[1]> (typep 'a 'symbol)
[2]> (typep "hello" 'string)  
[3]> (typep 23409812342341234134123434234 'bignum)  
[4]> (typep 23409812342341234134123434234 'rational)  

[5]> (typep 1/9 'rational)  
[6]> (typep 1/9 'list)  
[7]> (typep 1/9 'foo)  

*** - TYPEP: invalid type specification FOO

You can get the type of any expression with (type-of expr)

[1]> (type-of 'float)

[2]> (type-of 1/3)  
[3]> (type-of -2)  
[4]> (type-of "hello")  
(SIMPLE-BASE-STRING 5) [ types can be lists starting with a symbol ] 
[5]> (type-of (make-array '(3 3)))  

[6]> (type-of nil)  

Many objects may be coerced into another type, using the coerce function:

(coerce expression type)

Vectors and lists may be coerced into one another.

Strings may be coerced into other sequences, and lists or vectors of characters can be coerced into strings.

Integers may be coerced into floats. To convert a float or other rational into an integer, use one of the functions floor, round, truncate (round towards zero), or ceiling.

[1]> (coerce 4 'float)
[2]> (coerce "hello world" 'list)  
(#\h #\e #\l #\l #\o #\Space #\w #\o #\r #\l #\d)
[3]> (coerce '(#\h #\e #\l #\l #\o #\Space #\w #\o #\r #\l #\d)
"hello world"
[4]> (floor -4.3)  

[5]> (coerce '(a b c) 'simple-vector)  
#(A B C)
[6]> (coerce '(a b c) 'string)  

*** - SYSTEM::STORE: A does not fit into "", bad type

While we're on the subject of the four rounding functions (floor, round, truncate, ceiling), these are how you do integer division. Each function takes an optional argument, and divides the first argument by the second, then returns the appropriate rounding as an integer.

If you're used to C++ or Java's integer division, probably the most obvious choice is truncate.

Lisp functions can actually return more than one item. For example, integer division functions return both the divided value and the remainder. Both are printed to the screen. The primary return value (in this case, the divided value) is returned as normal. To access the "alternate" return value (in this case, the remainder), you need to use a macro such as multiple-value-bind or multiple-value-list (among others).

[1]> (floor 9 4)

2;    [ the primary return value ]
1     [ the alternative return value ]
[2]> (floor -9 4)  
-3 ;
[3]> (truncate -9 4)  
-2 ;
[4]> (* 4 (truncate -9 4))  

-8    [ 4 mulplied against the primary return value ]
[5]> (multiple-value-list (truncate -9 4))  
(-2 -1)
[6]> (multiple-value-bind (x y) (truncate -9 4)
          (* x y))

Hash Tables

Hash tables are created with make-hash-table. You can hash with anything as a key. Hash tables by default use eql as a comparison predicate. This is almost always the wrong predicate to use: you usually would want to use equal or equalp. To do this for example, you type:

(make-hash-table :test #'equalp)

Elements are accessed with gethash. If the element doesn't exist, nil is returned. An alternative return value indicates whether or not the element exists (returning T or NIL). If you stored nil as the value, then we have a problem! Instead of having to look up the alternate return value, you can supply an optional return value (instead of nil) to return if the slot really is empty.

(gethash key hashtable &optional return-if-empty)

Use setf to set hashed values.

(setf (gethash key hashtable) value)

Remove elements with remhash.

(remhash key hashtable)

Although it's not very efficient, you can map over a hashtable with maphash.

(maphash function hashtable)

function must take two arguments (the key and the value).

[1]> (setf *hash* (make-hash-table :test #'equalp))
[2]> (setf (gethash "hello" *hash*) '(a b c))  
(A B C)
[3]> (setf (gethash 2 *hash*) 1/2)  

[4]> (setf (gethash 2.0 *hash*) 9.2)  [ 2.0 is equalp to 2 ]
[5]> (gethash 2 *hash*)  
9.2   [ because we're using equalp as a test ]
T     [ T because the slot exists in the hashtable ]
[6]> (setf (gethash #\a *hash*) nil)    [ store NIL as the value ]   

[7]> (gethash #\b *hash*) 
NIL;    [ No such key #\b in *hash* ]  
[8]> (gethash #\a *hash*) 
NIL;   [ uh... wait a minute... -- NIL is returned! ]  
[9]> (gethash #\b *hash* 'my-empty-symbol) 

[10]> (gethash #\a *hash* 'my-empty-symbol) 
NIL;    [ that's better! ] 
[11]> (maphash #'(lambda (key val) (print key)) *hash*) 


Printing and Reading

(tepri) prints a linefeed.

(print obj) of course prints a linefeed followed by obj (in a computer readable fashion). Unlike Java's System.println("foo") or C's printf("foo\n"), in Lisp it's traditional to print the newline first.

(prin1 obj) prints obj (in a computer readable fashion) -- no prior linefeed.

(princ obj) prints obj in a human readable fashion -- no prior linefeed. Strings are printed without "quotes", for example. Such printed elements aren't guaranteed to be readable back into the intepreter.

[1]> (progn (terpri) (terpri) (terpri) (print 'hello))

[2]> (progn (prin1 2) (prin1 '(a b c)) (prin1 "hello"))  
2(A B C)"hello"
[3]> (progn (princ 2) (princ '(a b c)) (princ "hello"))  

2(A B C)hello

(prin1-to-string obj) is like prin1, but the output is into a string.

(princ-to-string obj) is like princ, but the output is into a string.

[1]> (prin1-to-string 4.324)
[2]> (prin1-to-string "hello world")
"\"hello world\""
[3]> (princ-to-string "hello world")
"hello world"
[4]> (prin1-to-string '(a b "hello" c))

"(A B \"hello\" C)"
[5]> (princ-to-string '(a b "hello" c))
"(A B hello C)"

(read) reads in an expression from the command line.

read is a complete Lisp parser: it will read any expression.

(read-from-string string) reads in an expression from a string, and returns the expression plus an integer indicating at what point reading was completed.

(y-or-no-p) waits for the user to type in a yes or a no somehow, then returns it. The way the question is presented the user (graphical interface, printed on screen, etc.) is up to the Lisp system. y-or-no-p is a predicate.

[1]> (read)    [ Lisp waits for you to type an expression ]
'(a b c d)

(A B C D)
[2]> (read-from-string "'(a b c d)")
'(A B C D) ;   [ Or equivalently (QUOTE (A B C D)) ]
10     [ Reading the expression finished before the tenth character ]
[3]> (y-or-n-p)   [ clisp waits for you to type y or n ]
TRUE      [ I tried to type in TRUE ]

Please answer with y or n : y   [ oh, okay! ]

format is a much more sophisticated printing facility. It is somewhat similar to C's printf command plus formating string. But format's formatting string is much more capable. Generally, format looks like:

(format print-to-where format-string obj1 obj2 ...)

print-to-where can be t (print to the screen) or nil (print to a string).

Formatting sequences begin with a tilde (~). The simplest sequences include: ~a (princ an element); ~% (print a linefeed); ~s (prin1 an element). Much more complex formatting includes very complex numerical printing, adding spaces and buffers, printing through lists, even printing in roman numerals! format has its own little programming language. It's astounding what format can do.

[1]> (format t "~%My name is ~a and my ID is ~a" "Sean" 1231)

My name is Sean and my ID is 1231
[2]> (format nil "~%~%~%~a~a~s    ~a" '(a b c) 
         #(1 2 3) "yo" 'whatever)

(A B C)#(1 2 3)\"yo\"    WHATEVER"
[3]> (format t "~% ~a ~R ~:R ~@R ~:@R ~$ ~E" 4 4 4 4 4 4 4)

 4 four fourth IV IIII 4.00 4.0E+0    [ hee hee hee! ]


More Control Structures

(when test expr1 expr2 ...) evaluates the expressions (and returns the last) only if test is true, else it returns nil.

(unless test expr1 expr2 ...) evaluates the expressions (and returns the last) only if test is nil, else it returns nil.

(case test-object case1 case2 ... ) goes through the cases one by one and returns the one which "matches" the test-object. A case looks like this:

(obj expr1 expr2 ... )

If obj (not evaluated, so you shouldn't quote it) is an object which is eql to test-object, or is a list in which test-object appears, then the case "matches" test-object. In this case, the expressions are evaluated left-to-right, and the last one is returned. obj can also be t, which matches anything. This is the "default" case.

If no case matches, then case returns nil.

case is a lot like the Java/C++ switch statement. There are other versions: ecase, ccase.

[1]> (unless (y-or-n-p) (print "you picked no!") 
                 (print "good for you!"))

"you picked no!" 
"good for you!" 
"good for you!"
[2]> (defun type-discriminator (obj)
   "Prints out a guess at the type"
   (let ((typ (type-of obj)))
      (when (consp typ) (setf typ (first typ)))
      (case typ
         ((fixnum rational ratio complex real bignum) 
            (print "a number perhaps?"))
         ((simple-vector vector string list) 
            (print "some kind of sequence?"))
         (hash-table (print "hey, a hash table..."))
         (nil (print "it's nil!"))
         (t (print "beats me what this thing is.  It says:")
            (print (type-of obj))))))
[3]> (type-discriminator 42)  

"a number perhaps?" 
"a number perhaps?"
[4]> (type-discriminator "hello")  

"beats me what this thing is.  It says:" 

cond is a powerful generalization of case. It takes the form:

(cond (test1 expr expr ... )
      (test2 expr expr ... )
      (test3 expr expr ... )
      ... )

cond works like this. First, test1 is evaluated. If this is true, the following expressions are evaluated and the last one is returned. If not, then test2 is evaluated. If this is true, its following expressions are evaluated and the last one is true. And so on. If no test evaluates to true, then nil is returned.

[ Previously, type-discriminator didn't work for string.
  let's get it working right. ]

[2]> (defun type-discriminator (obj)
   "Prints out a guess at the type"
      ((find-if #'(lambda (x) (typep obj x)) 
           '(fixnum rational ratio complex real bignum))
         (print "a number perhaps?"))
      ((find-if #'(lambda (x) (typep obj x)) 
           '(simple-vector vector string list))
         (print "some kind of sequence?"))
      ((typep obj 'hash-table) (print "hey, a hash table..."))
      ((typep obj null) (print "it's nil!"))
      (t (print "beats me what this thing is.  It says:")
         (print (type-of obj)))))
[3]> (type-discriminator "hello")  

"some kind of sequence?" 
"some kind of sequence?"

do is a general iterator. It takes the form:

(do (initial-variable-declarations)
      (test res-expr1 res-expr2 ... )
      ... )

do works like this. First, local variables are declared in a way somwhat similarly to let (we'll get to that). Then test is evaluated. If it is true, then the res-expr's are evaluated and the last one is returned (if there are none, then nil is returned).

If test returned false, then expr's in the body are evaluated. Then do iterates again, starting with trying test again. And so on.

A variable declaration is either a variable name (a symbol), just as in let, or it is a list of the form (var optional-init optional-update) The optional-init expression initializes the variable (else it's nil). The optional-update expression specifies the new value of var each iteration. optional-update is evaluated in the context of the variables of the previous iteration.

[ generate some random numbers ]
[2]> (defun generate (num)
       (do ((y 0 (1+ y))
            (x 234567 (mod (* x 16807) 2147483647)))
           ((>= y num) "the end!")
           (print x)))
[3]> (generate 20)  

"the end!"

loop is a very powerful, complex iteration macro which can do nearly anything. Literally. It has its own language built into it. loop is one of the few things in Lisp more complex than format.

loop has an idiosyncratic syntax that is very un-lisp-like. It is also so complex that few people understand it, and it is not recommended for use. We will not discuss loop except to mention that its very simplest form: (loop expressions ... ) makes a very nice infinite loop.

[2]> (loop (print 'hello) (print 'yo))
 [ ... ad nauseum until you press Control-C ]

A block is a sequence of expressions. Blocks appear in lots of control structures, such as let, all iterators (do, dotimes, dolist, loop, etc.), many conditional statements (cond, case, when, etc.), progn, etc.

Blocks have labels (names). In control structures, the implicit blocks are all named nil.

Functions created with defun have an implicit block whose label is the same name as the function. Functions created with lambda have an implicit block whose label is nil.

(return-from label optional-value) will exit prematurely from a block whose label is label (not evaluated -- don't quote it). This is somewhat like Java/C++'s break statement. The return value of the block is optional-value (or nil if no value provided).

Because so many blocks are named nil, the simpler (return optional-value) is the same thing as (return-from nil optional-value)

Use return and return-from sparingly. They should be rare.

[1]> (dotimes (x 100) 
         (print x) 
         (if (> x 10) (return 'hello)))

[2]> (defun differents (list &key (test #'eql))
        "Returns the first different pair in list"
         (dolist (x list)
           (dolist (y list)
             (unless (funcall test x y)
               (return-from differents (list x y))))))
[3]> (differents '(a a a b c d))

(A B)
[4]> (differents '(a a a a a a))

Another way to escape is with catch and throw. catch looks like this:

(catch catch-symbol expressions ... )

throw looks like:

(throw catch-symbol return-value)

Normally, catch works just like progn. But if there is a throw statement inside the catch whose catch-symbol matches the catch's, then we prematurely drop out of the catch and the catch returns the return value of the throw.

This works even if the throw appears in a subfunction called inside the catch.

In C++ such a thing is done with longjump. In Java such a thing is done with an exception.

[ another way to do the differents function ]
[2]> (defun differents (list &key (test #'eql))
        "Returns the first different pair in list"
         (catch 'my-return-value 
           (dolist (x list)
             (dolist (y list)
               (unless (funcall test x y)
                 (throw 'my-return-value (list x y)))))))

[3]> (differents '(a a a b c d))
(A B)
[4]> (differents '(a a a a a a))

Writing Lisp in Lisp

Lisp has a built-in interpreter. It is called eval, and looks like this:

(eval data)

eval takes data and submits it to the Lisp interpreter to be executed.

The data submitted to the interpeter is not evaluated in the context of any current local variables.

eval is powerful. You can assemble lists and then have them executed as code. Thus eval allows you to make lisp programs which generate lisp code on-the-fly. C++ and Java can only do this in truly evil ways (like writing machine code to an array, then casting it into a function, yikes!).

[1]> (list '+ 4 7 9)
(+ 4 7 9)
[2]> (eval (list '+ 4 7 9))


Lisp has an interpeter eval, a full-featured printer print, and a full-featured parser read. Using these tools, we can create our own Lisp command line!

[1]> (loop (format t "~%my-lisp --> ")
           (print (eval (read))))

my-lisp --> (dotimes (x 10) (print 'hi))

my-lisp -->

More Debugging

(break) signals an error, just as if the user pressed Control-C.

You can continue from a break.

[1]> (defun foo (x)
       (print (+ x 3))
       (print (+ x 4)))

[2]> (foo 7)

** - Continuable Error
If you continue (by typing 'continue'): Return from BREAK loop
2. Break [4]> continue  [in clisp, anyway]


(trace function-symbol) turns on tracing of a function. function-symbol is not evaluated (don't quote it or sharp-quote it).

When a trace function is entered, the function and its arguments are printed to the screen. When the trace function exits, its return value is printed to the screen.

You can trace multiple functions at the same time.

You turn off tracing of a function with (untrace function-symbol)

[1]> (defun factorial (n)
          (if (<= n 0)
            (* n (factorial (- n 1)))))
[2]> (trace factorial)
[3]> (factorial 15)

1. Trace: (FACTORIAL '15)
2. Trace: (FACTORIAL '14)
3. Trace: (FACTORIAL '13)
4. Trace: (FACTORIAL '12)
5. Trace: (FACTORIAL '11)
6. Trace: (FACTORIAL '10)
7. Trace: (FACTORIAL '9)
8. Trace: (FACTORIAL '8)
9. Trace: (FACTORIAL '7)
10. Trace: (FACTORIAL '6)
11. Trace: (FACTORIAL '5)
12. Trace: (FACTORIAL '4)
13. Trace: (FACTORIAL '3)
14. Trace: (FACTORIAL '2)
15. Trace: (FACTORIAL '1)
16. Trace: (FACTORIAL '0)
16. Trace: FACTORIAL ==> 1
15. Trace: FACTORIAL ==> 1
14. Trace: FACTORIAL ==> 2
13. Trace: FACTORIAL ==> 6
12. Trace: FACTORIAL ==> 24
11. Trace: FACTORIAL ==> 120
10. Trace: FACTORIAL ==> 720
9. Trace: FACTORIAL ==> 5040
8. Trace: FACTORIAL ==> 40320
7. Trace: FACTORIAL ==> 362880
6. Trace: FACTORIAL ==> 
5. Trace: FACTORIAL ==> 
4. Trace: FACTORIAL ==> 
3. Trace: FACTORIAL ==> 
2. Trace: FACTORIAL ==> 
1. Trace: FACTORIAL ==> 

[4]> (untrace factorial)
[5]>  (factorial 15)

You can step through an expression's evaluation, just as in a debugger, using (step expression). The features available within the step environment are implementation-dependent.

In clisp, the step function lets you interactively type, among other things, :s (to step into an expression), :n (to complete the evaluation of the expression and step out), and :a (to abort stepping)

[1]> (defun factorial (n)
          (if (<= n 0)
            (* n (factorial (- n 1)))))
[2]> (step (factorial 4))
(step (factorial 4))
step 1 --> (FACTORIAL 4)
Step 1 [26]> :s
step 2 --> 4
Step 2 [27]> :s

step 2 ==> value: 4
step 2 --> (IF (<= N 0) 1 (* N (FACTORIAL #)))
Step 2 [28]> :s
step 3 --> (<= N 0)
Step 3 [29]> :n

step 3 ==> value: NIL
step 3 --> (* N (FACTORIAL (- N 1)))
Step 3 [30]> :s
step 4 --> N
Step 4 [31]> :s

step 4 ==> value: 4
step 4 --> (FACTORIAL (- N 1))
Step 4 [32]> :s
step 5 --> (- N 1)
Step 5 [33]> :n

step 5 ==> value: 3
step 5 --> (IF (<= N 0) 1 (* N (FACTORIAL #)))
Step 5 [34]> :n

step 5 ==> value: 6
step 4 ==> value: 6
step 3 ==> value: 24
step 2 ==> value: 24
step 1 ==> value: 24

The apropos function can be used to find all the defined symbols in the system which match a given string. Ordinarily, apropos will return everything, including private system symbols. That's not what you'd want. But the following will do the trick:

(apropos matching-string 'cl-user)

NOTE: A bug in CMUCL (CMU Common Lisp) means that it doesn't know to join the 'cl and 'cl-user packages together into just 'cl-user when responding to apropos. So if you're using CMUCL, you need to do something like:

(defun my-apropos (string)
   (apropos string 'cl)
   (apropos string 'cl-user))

...then you can call (my-apropos "compile") and you'll get the right stuff. Don't bother with this hack on CLISP, LispWorks, or other correctly-working Lisps with regard to apropos.

[ in clisp  ] 
[1]> (apropos "compile" 'cl-user)
*COMPILE-FILE-PATHNAME*                    variable
*COMPILE-FILE-TRUENAME*                    variable
*COMPILE-PRINT*                            variable
*COMPILE-VERBOSE*                          variable
*COMPILE-WARNINGS*                         variable
*COMPILED-FILE-TYPES*                      variable
COMPILE                                    function
COMPILE-FILE                               function
COMPILE-FILE-PATHNAME                      function
COMPILED-FUNCTION                          type
COMPILED-FUNCTION-P                        function
COMPILER-LET                               special operator
COMPILER-MACRO-FUNCTION                    function
DEFINE-COMPILER-MACRO                      macro
UNCOMPILE                                  function


You can disassemble a function with (disassemble function-pointer)

You can use disassemble to assess the quality of your function in terms of machine code instructions. Compiled and interpreted functions may or may not appear to disassemble differently. Disassembly is implementation-dependent and processor-dependent.

[ in clisp  ] 
[1]> (defun factorial (n)
          (if (<= n 0)
            (* n (factorial (- n 1)))))
[3]> (disassemble 'factorial)

Disassembly of function FACTORIAL
(CONST 0) = 0
(CONST 1) = 1
1 required arguments
0 optional arguments
No rest parameter
No keyword parameters
0     L0
0     (LOAD&PUSH 1)
1     (CONST&PUSH 0)                      ; 0
2     (CALLSR&JMPIF 1 50 L16)             ; <=
6     (LOAD&PUSH 1)
7     (LOAD&DEC&PUSH 2)
9     (JSR&PUSH L0)
11    (CALLSR 2 56)                       ; *
14    (SKIP&RET 2)
16    L16
16    (CONST 1)                           ; 1
17    (SKIP&RET 2)
#<COMPILED-CLOSURE FACTORIAL>     [ dunno why clisp says it's compiled ]

[ in Lispworks ] CL-USER 39 > (defun factorial (n) (if (<= n 0) 1 (* n (factorial (- n 1))))) FACTORIAL CL-USER 40 > (disassemble #'factorial) #x300F9158: #xA0E20692 ldl tmp3,nil,1682 #x300F915C: #x40FE0527 subq tmp3,sp,tmp3 #x300F9160: #xFCE00039 bgt tmp3,#x300F9248 #x300F9164: #x402035A6 cmpeq arg/mv,1,tmp2 #x300F9168: #xE4C00037 beq tmp2,#x300F9248 #x300F916C: #x23DEFFF0 lda sp,sp,-16 #x300F9170: #xB1FE0000 stl fp,sp,0 #x300F9174: #x43C0100F addl sp,0,fp #x300F9178: #xB09E0004 stl constants,sp,4 #x300F917C: #xA0830006 ldl constants,func,6 #x300F9180: #xB19E0008 stl r12,sp,8 #x300F9184: #x4610040C bis arg0,arg0,r12 #x300F9188: #xB35E000C stl ra,sp,12 #x300F918C: #xA0C4001D ldl tmp2,constants,29 ;; "call-count" #x300F9190: #x45807007 and r12,3,tmp3 #x300F9194: #x40C09006 addl tmp2,4,tmp2 #x300F9198: #xB0C4001D stl tmp2,constants,29 ;; "call-count" #x300F919C: #xF4E0000C bne tmp3,#x300F91D0 #x300F91A0: #xFD800011 bgt r12,#x300F91E8 #x300F91A4: #x47FF041F bis zero,zero,zero #x300F91A8: #x47E03401 bis zero,1,arg/mv #x300F91AC: #x47E09400 bis zero,4,result #x300F91B0: #x45EF041E bis fp,fp,sp #x300F91B4: #xA35E000C ldl ra,sp,12 #x300F91B8: #xA19E0008 ldl r12,sp,8 #x300F91BC: #xA09E0004 ldl constants,sp,4 #x300F91C0: #xA1FE0000 ldl fp,sp,0 #x300F91C4: #x23DE0010 lda sp,sp,16 #x300F91C8: #x6BFA8000 ret zero,(ra) #x300F91CC: #x47FF041F bis zero,zero,zero #x300F91D0: #x20A20B26 lda tmp1,nil,2854 #x300F91D4: #x47FF0411 bis zero,zero,arg1 #x300F91D8: #x458C0410 bis r12,r12,arg0 #x300F91DC: #x6B454000 jsr ra,(tmp1) #x300F91E0: #x400205A5 cmpeq result,nil,tmp1 #x300F91E4: #xE4BFFFF0 beq tmp1,#x300F91A8 #x300F91E8: #x45807007 and r12,3,tmp3 #x300F91EC: #xF4E00018 bne tmp3,#x300F9250 #x300F91F0: #x41809130 subl r12,4,arg0 #x300F91F4: #x420C09A6 cmplt arg0,r12,tmp2 #x300F91F8: #xE4C00015 beq tmp2,#x300F9250 #x300F91FC: #x47FF041F bis zero,zero,zero #x300F9200: #xA064002D ldl func,constants,45 ;; FACTORIAL #x300F9204: #x47E03401 bis zero,1,arg/mv #x300F9208: #xA0A30002 ldl tmp1,func,2 #x300F920C: #x40A0B405 addq tmp1,5,tmp1 #x300F9210: #x6B454000 jsr ra,(tmp1) #x300F9214: #x44000411 bis result,result,arg1 #x300F9218: #x4591041D bis r12,arg1,r29 #x300F921C: #x47A07007 and r29,3,tmp3 #x300F9220: #xF4E00011 bne tmp3,#x300F9268 #x300F9224: #x4980579D sra r12,2,r29 #x300F9228: #x4FB10400 mulq r29,arg1,result #x300F922C: #x48041786 sra result,32,tmp2 #x300F9230: #x401F0000 addl result,zero,result #x300F9234: #x4803F787 sra result,31,tmp3 #x300F9238: #x40E605A7 cmpeq tmp3,tmp2,tmp3 #x300F923C: #xE4E0000A beq tmp3,#x300F9268 #x300F9240: #x47E03401 bis zero,1,arg/mv #x300F9244: #xC3FFFFDA br zero,#x300F91B0 #x300F9248: #x20A20EF6 lda tmp1,nil,3830 #x300F924C: #x6BE50000 jmp zero,(tmp1) #x300F9250: #x20A20C8E lda tmp1,nil,3214 #x300F9254: #x47E09411 bis zero,4,arg1 #x300F9258: #x458C0410 bis r12,r12,arg0 #x300F925C: #x6B454000 jsr ra,(tmp1) #x300F9260: #x44000410 bis result,result,arg0 #x300F9264: #xC3FFFFE6 br zero,#x300F9200 #x300F9268: #x458C0410 bis r12,r12,arg0 #x300F926C: #x45EF041E bis fp,fp,sp #x300F9270: #x20A20CD6 lda tmp1,nil,3286 #x300F9274: #xA19E0008 ldl r12,sp,8 #x300F9278: #xA09E0004 ldl constants,sp,4 #x300F927C: #xA1FE0000 ldl fp,sp,0 #x300F9280: #xA35E000C ldl ra,sp,12 #x300F9284: #x23DE0010 lda sp,sp,16 #x300F9288: #x6BE50000 jmp zero,(tmp1) #x300F928C: #x47FF041F bis zero,zero,zero 78 NIL
[In CMU Common Lisp (CMUCL), just for the heck of it!] * (disassemble #'factorial) Compiling LAMBDA (N): Compiling Top-Level Form: : .ENTRY "LAMBDA (N)"(n) ; (FUNCTION (T) NUMBER) 1B0: ADD -18, %CODE 1B4: ADD %CFP, 32, %CSP 1B8: CMP %NARGS, 4 ; %NARGS = #:G0 1BC: BPNE,PN %ICC, L2 1C0: NOP 1C4: ST %A0, [%CFP+12] ; %A0 = #:G1 1C8: ST %OCFP, [%CFP] 1CC: ST %LRA, [%CFP+4] ; No-arg-parsing entry point 1D0: LDUW [%CFP+12], %A0 1D4: ADD %ZERO, 0, %A1 1D8: ADD %CODE, 104, %LRA 1DC: SETHI %hi(#x10001000), %NL0 1E0: J %NL0+944 ; #x100013B0: GENERIC-> 1E4: NOP 1E8: .LRA 1EC: MOV %OCFP, %CSP 1F0: NOP 1F4: ADD -104, %CODE 1F8: CMP %A0, %NULL 1FC: BPNE %ICC, L1 200: NOP 204: ADD %ZERO, 4, %A0 208: L0: LDUW [%CFP], %NL0 20C: LDUW [%CFP+4], %A1 ;;; [5] (<= N 0) 210: MOV %CFP, %CSP 214: MOV %NL0, %CFP 218: J %A1+5 21C: MOV %A1, %CODE 220: L1: LDUW [%CFP+12], %A0 224: ADD %ZERO, 4, %A1 228: ADD %CODE, 184, %LRA 22C: SETHI %hi(#x10000000), %NL0 230: J %NL0+740 ; #x100002E4: GENERIC-- 234: NOP ;;; [4] (IF (<= N 0) 1 (* N (FACTORIAL #))) 238: .LRA 23C: MOV %OCFP, %CSP 240: NOP 244: ADD -184, %CODE 248: LDUW [%CODE+13], %CNAME ; # 24C: ADD %ZERO, 4, %NARGS 250: LDUW [%CNAME+5], %A1 ;;; [6] (* N (FACTORIAL (- N 1))) 254: ADD %CODE, 232, %LRA 258: MOV %CFP, %OCFP 25C: MOV %CSP, %CFP ;;; [8] (- N 1) 260: J %A1+23 264: MOV %A1, %CODE 268: .LRA 26C: MOV %OCFP, %CSP 270: NOP 274: ADD -232, %CODE 278: MOV %A0, %A1 27C: LDUW [%CFP+12], %A0 280: ADD %CODE, 272, %LRA 284: SETHI %hi(#x10000000), %NL0 288: J %NL0+856 ; #x10000358: GENERIC-* 28C: NOP 290: .LRA ;;; [7] (FACTORIAL (- N 1)) 294: MOV %OCFP, %CSP 298: NOP 29C: ADD -272, %CODE 2A0: BP %ICC, L0 2A4: NOP 2A8: L2: ILLTRAP 10 ; Error trap 2AC: BYTE #x04 2AD: BYTE #x19 ; INVALID-ARGUMENT-COUNT-ERROR 2AE: BYTE #xFE, #xED, #x01 ; NARGS 2B1: .ALIGN 4