LISP FUNDAMENTALS

Math operations in Common Lisp are probably different than what you're used to.

Common Lisp math operations use prefix notation: the math operator is a function that comes at the beginning of the parenthesis, and all numbers afterward evaluated using that operator, from left to right. In school, we learn math using infix notation, where the operators are placed between each number.

(+ (* 5 5 5) (/ 18 2) (- 20 3)) ; using infix notation: 5 * 5 * 5 + 18 / 2 + 20
                                ; - 3

Let's look at a slightly more complicated example of Common Lisp syntax:

(defun cube (x)
  (* x x x))

After the opening parenthesis comes defun, a built-in special form. Special forms have different evaluation rules compared to regular function calls. defun is used to define a function. The function above is given the name cube. After giving the function a name, we define it's parameters, the data it takes as arguments to run the operations inside the function. The function takes one argument: x.

Notice that cube isn't evaluated as a variable. The x in (x) isn't initially interpreted as a function to be called.

defun is a special operator where the first argument it receives is a symbol designating the name to give the function, and the second argument is a list of arguments that the function is expected to receive when it's called. The forms that follow afterward are called the body of the function.

There are several other special forms with their own syntax. We'll cover them later.

Common Lisp supports both global variables, but also lexically scope variables. There are several ways to define variables.

You can use setf to reassign values to variables you've already introduced.

(setf *debug* nil)

However, if this variable hasn't been introduced yet, you'll get an error.

Use defvar to introduce a global variable without a value.

(defvar *debug*)

To change the value of a defvar variable, you need to call setf on the variable. If you do decide that you want to add a value, or change the initial value, you can't simply redefine the defvar and recompile the form.

(defvar *debug* t)
*debug*

ResultNIL

Still nil.

You have to use setf to modify the value of a defvar variable.

(defvar *no-changey* 'no)
*no-changey*

ResultYES

(setf *no-changey* 'yes)
*no-changey*

ResultYES

Use defparameter to introduce a global variable with a starting value that can be modified by recompiling the defparameter form.

(defparameter *debug* nil)
*debug*

ResultNIL

(defparameter *debug* t)
*debug*

ResultT

Global variables defined with defvar and defparameter are surrounded with * by convention.

Use defconstant to introduce a global variable that has a value that can't be modified.

(defconstant +pi+ 3.14)
+pi+

Result3.14

(setf +pi+ 42)

ResultPis a constant and thus can't be set.

If you try to recompile the defconstant with a different value, you'll be given the option to redefine the constant via a restart.

(defconstant +pi+ 42)

ResultThe constant PIis being redefined (from 3.14 to 42)

Constant variable names are surrounded with + by convention.

Use let to introduce or reassign a local variable.

(let ((name 'micah))
  name)

ResultMICAH

You can also reassign a global variable temporarily.

(defparameter *var* 'outside)
*var*                   

ResultOUTSIDE

(let ((*var* 'inside))  
  *var*)              

ResultINSIDE

And the value outside the let will remain.

*var*

ResultOUTSIDE

If you need to use a variable defined within a let within the same let form then you need let*.

This let form will break:

(let ((data 'data)
      (clean-data data))
  clean-data)

ResultThe variable DATA is unbound.

Change the let to let* to make it work properly:

(let* ((data 'data)
       (clean-data data))
  clean-data)

ResultDATA

While variables are an important kind of symbol, they aren't the only kind of symbol. Function names, package names, class names, etc. are all symbols. Symbols themselves are a data structure and can hold more than one piece of information.

There are several functions for getting at the data saved in a symbol.

While most of the time you'll use defparameter, let, defun, etc. to define symbols, sometimes you'll need to do symbol surgery, constructing and interning symbols in manually. Some of the above functions will come in handy for those kinds of operations.

There are several different kinds of parameters you can define. The most common will be required parameters. Parameters defined without any other options are required.

(defun my-fun (this-is-required))

If you don't want a parameter to be required, you can use the &optional lambda list keyword to make it optional.

(defun fun-with-optional (a &optional b)
  (format nil "The values passed: ~a and ~a.~&" a b))

(fun-with-optional 5)

ResultThe values passed: 5 and NIL.

The default value for optional arguments not passed is nil. You can set the default value.

(defun fun-with-optional (a &optional (b 10))
  (format nil "The values passed: ~a and ~a.~&" a b))

(fun-with-optional 5)

ResultThe values passed: 5 and 10.

You can create a predicate that will return whether the value was supplied or the default is being used.

(defun fun-with-optional (a &optional (b 10 b-supplied-p))
  (if b-supplied-p
      (format nil "The values passed: ~a and ~a (passed by user).~&" a b)
      (format nil "The values passed: ~a and ~a (default).~&" a b)))

By convention the predicate is named *-supplied-p, with * being the name of the parameter. It's value is t if the user supplied an argument in that position, otherwise it defaults to nil.

Using the default value of the optional argument:

(fun-with-optional 5) 

ResultThe values passed: 5 and 10 (default).

With a value passed to the optional argument position:

(fun-with-optional 5 10)

ResultThe values passed: 5 and 10 (passed by user).

All parameters following the &optional lambda list keyword will be optional. This is true of all lambda list keywords.

(defun fun-with-lots-of-options (&optional (a 1) (b 2) (c 3))
  (+ a b c))

If you want an argument to be both optional, but also want the user to be able to set the argument in any position by name, then you can use the &key keyword.

(defun fun-with-keys (&key a b c)
  (+ a b c))

(fun-with-keys :a 1 :b 2 :c 3)         

As with &optional, you can specify default values.

(defun fun-with-keys (&key (a 1) (b 2) (c 3))
  (+ a b c))

*-supplied-p predicates can also be specified.

(defun fun-with-keys (&key (a 1 a-supplied-p) (b 2 b-supplied-p) (c 3 c-supplied-p))
  (format nil "~a (~a) + ~a (~a) + ~a (~a) = ~a~&"
          a a-supplied-p
          b b-supplied-p
          c c-supplied-p
          (+ a b c)))

(fun-with-keys :a 5 :c 7)

Result5 (T) + 2 (NIL) + 7 (T) = 14

You can collect arbitrary arguments into a list with &rest.

(defun add (&rest args)
  (apply #'+ args))

(add 1 2 3 4 5)

Result15

It is possible to mix the different kinds of parameters.

As a general rule, you don't want to mix &optional and &key parameters.

(defun do-not-mix (&optional (a 1) (b 2) &key (c 3))
  (+ a b c))

(do-not-mix :c 5)                       

ResultThe value
  :C
is not of type
  NUMBER

Use one or the other, but not both.

You can mix &optional and &rest, but mixing &key and &rest will also result in an error. You don't need the &key to have named arguments in your &rest args anyway.

(defun rest-args-as-plist (&rest args)
  args)

(rest-args-as-plist :a 1 :b 2 :name 'micah)

Result(:A 1 :B 2 :NAME MICAH)

We'll see a bit later what's going on in loop below, but this is just to say that you can have an arbitrary number of key-value pairs in your &rest argument.

(let ((args (rest-args-as-plist :a 1 :b 2 :name 'micah)))
  (loop :for (k v) :on args :by #'cddr
        :when (eql k :name)
          :append v))

ResultMICAH

In Common Lisp, the value returned by the last expression called in a form will be the return value.

(defvar *some-var*)
(defun do-a-bunch-of-stuff ()
  (setf *some-var* "I assigned a value to *some-var*.")
  (let ((num 5))
    (square-then-double num)
    (random 10)
    "I am the value that this function will return"))
(do-a-bunch-of-stuff)

There are cases, however, when you might want to do an early return, especially when looping. You can do that with return.

It's possible to return multiple values using the values function.

(defun return-a-bunch-of-stuff ()
  (values
   (+ 2 7)
   (* 7 7)
   (/ 100 25)))
(return-a-bunch-of-stuff)
                                        ; => 9, 49, 4

A simple let won't bind all of the values returned by a function that returns multiple values. Instead, only the first value will be bound.

(let ((val (return-a-bunch-of-stuff)))
  val)
                                        ; => 9 (4 bits, #x9, #o11, #b1001)

If you need to bind multiple values, use multiple-value-bind.

(multiple-value-bind (a b c)
    (return-a-bunch-of-stuff)
  (format t "~a * ~a * ~a = ~a" a b c (* a b c)))
                                        ; 9 * 49 * 4 = 1764 => NIL

Sometimes you might want to take a list and break it into pieces–called destructuring. For that, there's destructuring-bind.

(destructuring-bind (a b c)
    (list 1 2 3)
  (format t "~a * ~a * ~a = ~a" a b c (* a b c)))
                                        ; 1 * 2 * 3 = 6 => NIL

This destructuring can be done on arbitrarily deep trees of cons cells.

(defparameter *deep-tree* `(defun function-name (a lambda-list)
                            (let ((b :some-value))
                              b)))

(destructuring-bind (the-defun the-function-name (the-a the-lambda-list)
                     (the-let ((the-b the-value-bound-to-b))
                      the-b-at-the-end))
    *deep-tree*
  the-value-bound-to-b)
                                        ; => :SOME-VALUE

When a variable is passed to a function, a new, local variable is introduce with the value of the variable passed to the function.

(defvar *some-num* 5)
(defun add-5 (num) ; local variable num is introduced
  (setf num (+ num 5)))

;; num is assigned the value of *some-num*
(add-5 *some-num*) ; => 10
;; add-5 does not modify *some-num*
*some-num* ; => 5, not 10

If you want to modify the value of the global variable, you need to use setf on the global variable directly.

(defun add-5 ()
  (setf *some-num* (+ *some-num* 5)))
(add-5)
some-num ; => 10

(defparameter *names* '(Micah Greg Takae Marcia Ena Mikasa))

(defun add-name (name sequence)
  (setf sequence (push name sequence)))
(add-name 'Guy *names*)

Common Lisp functions are first-class. Many of Lisp's functions can take functions as arguments.

To pass a function as an argument, you have a few options.

You can use function:

(mapcar (function square-then-double) '(1 2 3 4 5))

Or, more commonly, use the reader macro #':

(mapcar #'square-then-double '(1 2 3 4 5))

Or you can use anonymous functions.

You can use anonymous functions with lambda:

((lambda (x) (* x x)) 5)

Result25

Lambdas are useful when using functional programming functions like mapcar or remove-if-not.

(mapcar (lambda (x) (+ (* x x) (* x x))) '(1 2 3 4 5))

Result(2 8 18 32 50)

Because lists are so fundamental in Lisp, there are many functions for manipulating lists.

length returns how many items are in the list:

(length '(Gerald Sussman stole my wife and kicked my dog that skallywag))

reverse returns a new list that has the order of the elements of the initial list reversed:

(reverse '(1 2 3 4 5))

first, second … tenth get items in a list based on their position in the list:

(let ((my-list '(common lisp is a general purpose multi-paradigm programming
                 language)))
  (list (first my-list)
        (second my-list)
        (ninth my-list)))

Result(COMMON LISP LANGUAGE)

member searches for a single item in a list:

(member 'general '(common lisp is a general purpose multi-paradigm programming
 language))

nth selects individual items by their index:

(nth 4 '(common lisp is a general purpose multi-paradigm programming language))

position tells you the index of an item in a list:

(position 'general '(common lisp is a general purpose multi-paradigm programming language))

append combines two lists:

(append '(this list is a list) '(a list))

Lists are a very simple data structure capable of making other data structures. Consider the linked list of cons cells above:

(cons 'defun (cons 'sum (cons (cons 'x
                                     (cons 'y nil))
                               (cons
                                (cons '+
                                      (cons 'x (cons 'y nil)))
                                nil))))

While it is simply a linked list of cons cells, it's useful to think of it another way: a tree. Each cons cell has two parts: a car and a cdr. The car holds a leaf in the tree, whereas the cdr holds either another branch (in the common case) or another leaf. When working with lists as a tree, you can use car and cdr to access those two positions.

(defparameter *my-tree* (cons 'defun (cons 'sum (cons (cons 'x
                                     (cons 'y nil))
                               (cons
                                (cons '+
                                      (cons 'x (cons 'y nil)))
                                nil)))))

(car *my-tree*)

ResultDEFUN

(cdr *my-tree*)

Result(SUM (X Y) (+ X Y))

copy-tree returns a copy of a tree of cons cells:

(copy-tree *my-tree*)

subst returns a new list that substitutes leaves in the tree:

(subst 'z 'y *my-tree*)

Result(DEFUN SUM (X Z) (+ X Z))

sublis does the same with multiple leaves in the tree:

(sublis '((sum  . subtract)
          (+    . -)
          (x    . a)
          (y    . b))
        *my-tree*)

Result(DEFUN SUBTRACT (A B) (- A B))

sublis takes a special type of list for its first argument: an association list, otherwise known as an alist or table. A table is a list with nested dotted lists–lists that have a non-nil leaf in the cdr position.

(defparameter *en-to-ja-table* '((one   . ichi)
                                 (two   . ni)
                                 (three . san)
                                 (four  . yon)
                                 (five  . go)))

With tables, the car is a key and the cdr is a value. You can search a table by either key or value using assoc and rassoc.

(assoc 'two en-to-ja-table)
(rassoc 'ni en-to-ja-table)

Lists can also be treated like sets–an unordered sequence of unique elements.

With adjoin, you can a single unique element into one list.

(adjoin 'three '(one two three))

Result(ONE TWO THREE)

Notice that 'three only occurs once. Since it was already in the "set", it wasn't added.

(adjoin 'four '(one two three))

Result(ONE TWO THREE FOUR)

Contents of two sets can be compared to form new sets:

(defparameter *pizza* '(salty sweet cheese sauce round carbs))
(defparameter *cake* '(sweet chocolate brown carbs round))

intersection returns a set of unique elements that are present in both *pizza* and *cake*:

(intersection *pizza* *cake*)

Result(CARBS ROUND SWEET)

union returns a set that combines all unique elements of both *pizza* and *cake*:

(union *cake* *pizza*)

Result(SAUCE CHEESE SALTY SWEET CHOCOLATE BROWN CARBS ROUND)

set-difference returns a set that includes all of the elements in *cake* that are not present in *pizza*:

(set-difference *cake* *pizza*)

Result(BROWN CHOCOLATE)

Or vise versa:

(set-difference *pizza* *cake*)

Result(SAUCE CHEESE SALTY)

subsetp returns t if a set is a subset of some other set or nil otherwise:

(defparameter *cheese-pizza* '(salty cheese sauce round carbs))
(subsetp *cheese-pizza* *pizza*)

ResultT

For symbols, variables, lists, and other objects, you need to use one of eq, eql, equal, or equalp. Each of them tests equality of different degrees. If you come from Python or JavaScript you'll usually expect functionality similar to equal or equalp.

eq will test equality of identity. Do these two objects share the same place in memory?

(defparameter *deez-nums* '(1 2 3 4 5))
(defparameter *your-nums* '(1 2 3 4 5))
(defparameter *gods-nums* '(one two three four five))

(eq *deez-nums* *your-nums*)                ; NIL, two different lists.
(eq *deez-nums* *deez-nums*)                ; T, same list.
(eq *gods-nums* '(one two three four five)) ; NIL
(eq 'one 'one)                              ; T, symbols are reused when they
                                            ; are from the same package.
(eq '(1 2 3 4 5) '(1 2 3 4 5))              ; NIL, two lists are constructed
                                            ; separately.
(eq #\a #\a)                                ; T
(eq #\a #\A)                                ; NIL
(eq "hello" "hello")                        ; NIL, strings are arrays of
                                            ; characters and are constructed
                                            ; separately.
(defparameter *greeting* "Hello, world!")
(eq *greeting* *greeting*)                  ; T, same array of characters.

eql is the same as eq, except that if the arguments are characters or numbers of the same type then their values (not their places in memory) are compared.

equal tests structural similarity.

(equal '(1 2 3) '(1 2 3))               ; T
(equal '(1 3 2) '(1 2 3))               ; NIL
(equal "hello" "hello")                 ; T
(equal "HELLO" "hello")                 ; NIL
(equal 1 1.0)                           ; NIL, different types

equalp is further lenient:

(equalp #\a #\A)                        ; T
(equalp "hello" "HELLO")                ; T, good for case-insensitive testing
                                        ; of characters or strings
(equalp 1 1.0)                          ; T, good for testing numbers across
                                        ; number types
(equalp '(1 2 3) '(1 3 2))              ; NIL

Characters and strings have their own equality operators: char-equal and string-equal.

(char-equal #\a #\A)                    ; T, same as (equalp #\a #\A)
(string-equal "hello" "HELLO")          ; T, same as (equalp "hello" "HELLO")

Additionally, there are tests like char-greaterp, string=, char<, etc.

For more detail you should look at the Hyperspec.

Common Lisp has the typical logical operators.

and tests if more than two forms are true. All forms are evaluated left-to-right, and evaluation stops if any inner forms return nil. The and form returns the value returned by the last form inside it if all forms in it evaluate to t.

(and 't 5)          ; => 5
(and 't 5 'hello)   ; => HELLO
(and 'nil 5 'hello) ; => NIL

or returns the value of the first form that evaluates to true. If no form passed to it returns a true value, it returns nil.

(or 5 't 'nil 'hello)                  ; => 5
(or 'nil (> 1 5) (eq "hello" "hello")) ; => NIL

or will stop evaluating forms on the first form that evaluates to true.

(or 'nil (> 5 10) (eq "hello" "hello")  ; all evaluate to nil
    (print "Evaluated, returns true.")
    (print "Not evaluated."))

ResultEvaluated, returns true.

not will return t if the inner form returns nil, and nil if that form returns t.

(not (= 1 1))  ; => NIL
(not (oddp 2)) ; => T

There are a number of different conditional forms. Of course, there is trusty ol' if. if is a special operator. It takes a test argument. If the test returns true, the next form is evaluated. If the test returns false, then the form after that is evaluated.

(if (> 10 1)                   ; if
    '10-is-greater-than-1      ; then branch
    '10-is-not-greater-than-1) ; (optional) else branch

If you don't need a second (else) branch, you can use when or unless:

(let ((num 0))
  (when (<= 1 num 10)
    (format t "~&FROM WHEN EXPRESSION: ~a is between 1 and 10" num)
    (print num)
    (print (+ num num)))

  (unless (<= 1 num 10)
    (format t "~&FROM UNLESS EXPRESSION: ~a is not between 1 and 10" num)
    (print num)
    (print (+ num num))))

(unless test ...) is equivalent to (when (not test) ...).

One of the upsides of not having an else branch is that you can do multiple operations after the test with when and unless.

cond takes lists of tests and forms to evaluate if the test returns t. The parentheses can be tricky here.

(cond (test form-to-evaluate-if-test-returns-t)
      (test form-to-evaluate-if-test-returns-t))

Here is a practical example:

(defparameter *monster-happiness-meter* 49)
(let ((mhm *monster-happiness-meter*))
  (cond
    ((>= 0 mhm)     (format t "~&Get this monster lifting weights at the gym, now!")    'take-monster-to-gym)
    ((<= 70 mhm 89)  (format t "~&This monster is pretty happy.")                       'hang-out-with-monster)
    ((<= 50 mhm 69)  (format t "~&This monster is feeling a little down.")              'invite-monster-to-lunch)
    ((<= 30 mhm 49)  (format t "~&Get this monster's mommy on the phone.")              'call-monsters-mommy)
    ((<= 1 mhm 29)   (format t "~&Did this monster's grandma die or something?")        'console-monster)
    (t              (format t "~&This is the catchall fallback expression.")            'fallback)))

ResultCALL-MONSTERS-MOMMY

cond will stop evaluating on the first form that returns t.

case takes a key expression and then some clauses. It evaluates the clauses in order. If the value of the first item of a clause is eql to the value returned by the key expression, the rest of the items in the clause are evaluated.

case is part of the family of case forms: case, ccase, ecase, typecase, ctypecase, and etypecase. If you know case statements from other languages, you understand the basic idea.

case and typecase do nothing if no match is found. If you want to trigger errors when no match is found (rather than providing an fallback clause), use ecase and etypecase. If you want the option to provide a value for the key expression and continue the program, use ccase and ctypecase.

(defparameter *env* :DEVELOPMENT)

(defun check-environment ()
  (case *env*
    (:DEVELOPMENT "logging EVERYTHING")
    (:PRODUCTION "locking in and locking down")))

(check-environment)         ; => "logging EVERYTHING"

(let ((*env* :PRODUCTION))
  (check-environment))      ; => "locking in and locking down"

(let ((*env* :AWS))
  (check-environment))      ; => NIL

case will return nil when none of the other cases match. You can set the fallback case using t or otherwise.

(defun check-environment ()
  (case *env*
    (:DEVELOPMENT "logging EVERYTHING")
    (:PRODUCTION "locking in and locking down")
    (otherwise "you gotta set your *env* to :DEVELOPMENT or :PRODUCTION")))

(let ((*env* :AWS))
  (check-environment))

Resultyou gotta set your envto :DEVELOPMENT or :PRODUCTION

If you want to return an error if the argument falls through all the checks, use ecase.

(defun check-environment ()
  (ecase *env*
    (:DEVELOPMENT "logging EVERYTHING")
    (:PRODUCTION "locking in and locking down")))

(let ((*env* :AWS))
  (check-environment))

Result:AWS fell through ECASE expression.
Wanted one of (:DEVELOPMENT :PRODUCTION).
[Condition of type SB-KERNEL:CASE-FAILURE]
Restarts:
0: [RETRY] Retry SLY evaluation request.
1: [*ABORT] Return to SLY's top level.
2: [ABORT] abort thread (#<THREAD tid=11923 "slynk-worker" RUNNING {70071BE463}>)

If you want a continuable error, use ccase.

(defun check-environment ()
  (ccase *env*
    (:DEVELOPMENT "logging all errors")
    (:PRODUCTION "locking in and locking down")))

(let ((*env* :AWS))
  (check-environment))

Result:AWS fell through CCASE expression.
Wanted one of (:DEVELOPMENT :PRODUCTION).
[Condition of type SB-KERNEL:CASE-FAILURE]
Restarts:
0: [STORE-VALUE] Supply a new value for ENV.
1: [RETRY] Retry SLY evaluation request.
2: [*ABORT] Return to SLY's top level.
3: [ABORT] abort thread (#<THREAD tid=11955 "slynk-worker" RUNNING {7007B83833}>)

Notice that now you can store a value in *env*. If you do, it will retry the case check with that value.

The typecase family works the same, but will check the type of value returned by the key expression.

(let ((x 5))
  (typecase x
    (list 'this-is-a-list)
    (number 'this-is-a-number)
    (function 'this-is-a-function)
    (otherwise 'i-dont-know-what-this-is)))

ResultTHIS-IS-A-NUMBER

handler-case is another member of the case family that works on conditions and errors. We'll look at it more in the chapter on Errors & Conditions.

You can iterate by using a functional programming style mapping. You've seen it in action already:

(mapcar #'square-then-double '(1 2 3 4 5))

(mapcar #'first '((1 2 3 4 5) (one two three four five) (what is going on here) (once
 upon a time)))

Result((1 ONE WHAT ONCE))

There are several varieties of mapping functions. mapcar is the most common. The most general mapping function is map.

;; Go through each character in the string and upper case it. Return a string.
(map 'string #'char-upcase "hello")

Result"HELLO"

;; Take an item from each of the lists and multiply them, returning a list.
;; Finishes at the end of the shortest list.
(map 'list #'* '(2 4 6 8) '(3 5 7 9 11 13 15) '(10 10 10))

Result(60 200 420)

You can reduce multiple values down to one value by applying some function to successive items in the sequence with reduce.

(reduce #'+ '(2 2 2))

Result6

(reduce #'* '(2 2 2))

Result8

(reduce #'append '((2 2 2) (3 3 3) (4 4)))

Result(2 2 2 3 3 3 4 4)

If you define a function to use for reducing, it needs to take two arguments:

(defun sum (x y) (+ x y))

Call it with reduce:

(reduce #'sum '(1 1 1 3 4 5 6 7))

Result28

You can filter the contents of a sequence with remove-if-not:

(remove-if-not #'oddp '(1 2 3 4 5 6 7 8 9 10))

Result(1 3 5 7 9)

You can define your own predicate and pass it to remove-if-not:

(defparameter *dangerous-animals* '(lion tiger bear snake shark))

(defun safe-animal-p (animal)
  (not (member animal *dangerous-animals*)))

(remove-if-not #'safe-animal-p '(dog cat monkey lion hamster shark snake bear
 koala frog))

Result(DOG CAT MONKEY HAMSTER KOALA FROG)

(defun greater-than-50-p (num)
  (> num 50))

(remove-if-not #'greater-than-50-p '(40 50 30 90 80 10 70 100 25 60 55 2))

Result(90 80 70 100 60 55)

You can also use remove-if:

(defun dangerous-animal-p (animal)
  (member animal *dangerous-animals*))

(remove-if #'dangerous-animal-p '(dog cat monkey lion hamster shark snake bear
 koala frog))

Result(DOG CAT MONKEY HAMSTER KOALA FROG)

The most popular iterating construct in Common Lisp is the loop macro:

(loop :for item :in '(one two three)
      :do (print item))

loop is a macro that uses its own syntax. If you come from Python or JavaScript, it doesn't look so strange, but it looks different from typical Lisp code.

(loop :for n :in '(1 2 3 4 5)
      :collect (* 2 (sqrt n)))

Result(2.0 2.828427 3.4641016 4.0 4.472136)

The loop macro

If you only need to test the sequence, check-all-even could be rewritten using every.

(every #'evenp '(2 4 6 8 10))
                                        ; => T
(every #'evenp '(1 4 6 8 10))
                                        ; => NIL

every runs a test on all items of a sequence and returns t if the test returns t for every item.

Similarly, some tests all items of a sequence, but will return t as soon as the test returns t for an item.

(some #'oddp '(2 4 6 8))
                                        ; => NIL
(some #'oddp '(1 4 6 8))
                                        ; => T

notevery runs a test on all items of a sequence and returns t if the test returns nil for every item.

(notevery #'oddp '(1 3 5))
                                        ; => NIL
(notevery #'oddp '(1 2 3 5))
                                        ; => T

notany runs a test on all items of a sequence and returns t if the test returns nil for one item.

(notany #'oddp '(2 4 6))
                                        ; => T
(notany #'oddp '(1 2 4 6))
                                        ; => NIL

There are times when it's necessary to do an early return. We saw an example with check-all-even:

(defun check-all-even (nums)
  (dolist (i nums t)
    (format t "~&Looking at ~a..." i)
    (when (oddp i)
      (format t "~&Ooops, this is odd!")
      (return nil))))

The result-form set for dolist is t, meaning that when we get to the end of the list we should return t.

However, when we spot an odd number, we need to return from the dolist loop early using (return nil).

Strings in Common Lisp are vectors of characters. As a result, all operations that can be used on sequences can be used on arrays.

concatenate combines two or more sequences–meaning it can combine lists, vectors, or strings. The first argument specifies the output type.

(concatenate 'list '(#\h #\e #\l #\l #\o #\space) '(#\w #\o #\r #\l #\d))

Result(######\  #####)

(concatenate 'vector '(#\h #\e #\l #\l #\o #\space) '(#\w #\o #\r #\l #\d))

Result#(######\  #####)

(concatenate 'string '(#\h #\e #\l #\l #\o #\space) '(#\w #\o #\r #\l #\d))

Result"hello world"

(concatenate 'string "hello " "world")

Result"hello world"

length can not only tell you the number of items in a list, it can also tell you the number of characters in a string.

(length "hello world")

Result11

reverse can place characters in a string in reverse order.

(reverse "YOU WILL REWRITE THAT THING IN COMMON LISP IMMEDIATELY")

Result"YLETAIDEMMI PSIL NOMMOC NI GNIHT TAHT ETIRWER LLIW UOY"

map is the most general of the mapping functions. If you pass string as the result type, you can run character operations on the string and get back a new string.

(map 'string #'char-upcase "hello")

Result"HELLO"

There are also functions specialized to work on strings.

The previous map call can be simplified using string-upcase.

(string-upcase "almighty")

Result"ALMIGHTY"

You can probably guess what string-downcase does.

string= and string-equal can be used to test if two strings are the same. string= is case-sensitive, string-equal is case-insensitive.

(string= "almighty" "almighty")         ; => T
(string= "almighty" "Almighty")         ; case-sensitive => NIL
(string-equal "almighty" "ALMIGHTY")    ; case-insensitive => T

There are other string comparison operators: string>, string/=, string-not-greaterp, etc.

Streams are either a source or destination for some data. Common Lisp uses streams for reading and writing files, etc.

Use with-open-file to create a block where a streaming connection with some file is active.

(with-open-file (stream #P"io-test.txt" :direction          :output
                                        :if-exists          :supersede
                                        :if-does-not-exist  :create)
  (format stream "~&Put this in the test file.~&This will be on a new line.~&"))

with-open-file is a macro providing a shortcut to using the lower-level functions open and close combined with unwind-protect. It ensures that the connection to the file is closed before leaving the block.

An exhaustive explanation of all the options open and with-open-file can take are in the Hyperspec.

If you want to read a file, set :direction to :input and use one of read, read-line, or read-char.

(with-open-file (stream #P"io-test.txt" :direction :input :if-exists :supersede
 :if-does-not-exist :create)
  (loop for line = (read-line stream nil nil)
        while line
        do (format t "~a~&" line)))

Common Lisp functions for working with file systems, paths, etc. are generally not portable between Lisp implementations. The package UIOP is the defacto-standard source of portable path and filesystem utilities. Even with UIOP, pathnames can still be tricky.

format is used to write strings to output streams. The first argument is the stream. If set to t, then it will send the input to *standard-output*, which is the output stream to the REPL.

(format t "~&Almighty Lisp~%")

However, as in the with-open-file examples, you can also use format to write to files, etc.

format has an extensive set of control-string directives used for customizing how text is formatted. All of the directives begin with tilde, such as ~a, ~&, etc. They also have an extensive set of modifiers. Complex format strings are vaguely similar to regular expressions and tend to get just as hairy.

I will cover the bare minimum here. Refer to the Hyperspec to learn all of the directives. I will explain any other directives as necessary.

Tilde a will output the data in human readable, "Aesthetic" format.

(format t "~a" (aref "hello" 0))

Resulth => NIL NOTE: not #

format takes an arbitrary number of arguments after the format string. For each argument, you need to supply another Tilde a or some other directive.

Tilde % and Tilde & output newlines. Tilde % will always output a newline. Tilde & will only output a newline if the output stream is not on a newline already.

(defparameter *alist* '((:micah 'male '40 'married 'japan)
                        (:takae 'female '35 'married 'japan)
                        (:mom 'female '71 'married 'america)
                        (:papa 'male '74 'married 'america)))

(loop for row in *alist*
      do (format t "~&~a: ~a~%" (first row) (rest row)))

ResultMICAH: ('MALE '39 'MARRIED 'JAPAN)
TAKAE: ('FEMALE '34 'MARRIED 'JAPAN)
MOM: ('FEMALE '70 'MARRIED 'AMERICA)
PAPA: ('MALE '74 'MARRIED 'AMERICA)
=> NIL

Tic-tac-toe works like this:

• There are two players.
• Each take turns putting their "piece" on the board–either an X or an O.
• If either player gets three of their pieces in a row vertically, horizontally, or diagonally, they win.
• If all spaces are filled without any player winning, it's a draw.

The game is simple, so the data representation can be simple.

(defvar *board*)

(defun reset-board ()
  (setf *board* (list 'board
                      0 0 0
                      0 0 0
                      0 0 0)))

(defparameter *player-one* 1)
(defparameter *player-two* 10)

The board is a flat list of 0's representing empty spaces. board is a filler symbol to make later code more intuitive to understand. We use setf to assign the globally scoped *board* variable to the value '(board 0 0 0 0 0 0 0 0).

We represent player "pieces" as 1 and 10.

• Type the above code into a buffer named tic-tac-toe.lisp.
• Compile each form individually with Sly->Compilation->Compile Defun
• Without typing anything more, practice evaluating the symbols *player-one* and *player-two* with Sly->Evaluation->Eval Defun.
• Type (reset-board) in the buffer and then evaluate that form. What is the value of *board*?

Now that we have our data representations settled, we need a way to manipulate it.

(defun place-piece (board piece position)
  (setf (nth position board) piece)
  board)

Using setf with nth here is similar to doing something like var[n] = my-value in other languages. You setf to a place, such as a variable, a hashtable key, list position, array index, etc.

Here we assign the place in our *board* to the value of piece. The last value returned by the last form evaluated in a function becomes that function's return value. We return the board to be able to show the updated board to the players.

We also need a way to map positions on the board to all possible winning positions–Touretzky calls them triplets.

(defparameter *triplets* '((1 2 3) (4 5 6) (7 8 9) 
                           (1 4 7) (2 5 8) (3 6 9) 
                           (1 5 9) (3 5 7)))       

The first three triplets are horizontal winning positions, the second three are vertical, and the last two are diagonal.

Next, we need a way to calculate the state of those triplets.

(defun sum-triplet (board triplet)
  (+ (nth (first triplet) board)
     (nth (second triplet) board)
     (nth (third triplet) board)))

(defun compute-sums (board)
  (mapcar (lambda (triplet) (sum-triplet board triplet)) *triplets*))

mapcar is one of the many built-in functions that takes a function as an argument. mapcar will apply the function to each item in the sequence and collect them into a list, returning the list.

Let's test it out by placing some pieces manually.

(reset-board)
(place-piece *board* *player-one* 1)
(place-piece *board* *player-two* 2)
(place-piece *board* *player-one* 5)
(place-piece *board* *player-two* 9)
(place-piece *board* *player-one* 7)
(place-piece *board* *player-two* 3)
(place-piece *board* *player-one* 4)

Result(BOARD 1 10 10 1 1 0 1 0 10)

Now let's test compute-triplet.

(compute-sums *board*)

Result(21 2 11 3 11 20 12 12)

We can see now that player one, represented as 1s on the board, occupies all three spaces in a triplet. We have a winner, but our program doesn't know that yet. Let's add win and tie detection.

(defun winner-p (board)
  (let ((sums (compute-sums board)))
    (or (member (* 3 *player-one*) sums)
        (member (* 3 *player-two*) sums))))

(defun tie-p (board)
  (not (member 0 board)))

Test them on the current board:

(winner-p *board*)

Result(3 11 20 12 12)

(tie-p *board*)

ResultNIL

member is called a semi-predicate: it searches a sequence like sums for an item like (* 3 *player-one*). If none is found, it returns nil. If one is found, however, it doesn't return t; it returns a list of the item plus the rest of the list after the item.

We can add pieces to the board, calculate the state of the board, and detect a winner. If we make an interface for two human players, we can have a game.

We need a way to show the board to players using format. Instead of trying to do everything at once, we'll break it down into pieces, starting with converting player pieces from numbers to letters

(defun convert-to-letter (piece)
  (ecase piece
    (0  " ")
    (1  "X")
    (10 "O")))

(defun opponent (piece)
  (if (= piece 1)
      10
      1))

Test convert-to-letter:

(convert-to-letter 1)

ResultX

(convert-to-letter 10)

ResultO

Now let's print a row from the board.

(defun print-row (x y z)
  (format t "~& ~a | ~a | ~a ~%" (convert-to-letter x) (convert-to-letter y) (convert-to-letter
 z)))

Now let's print the entire board.

(defun print-board (board)
  (format t "~&")
  (print-row (nth 1 board) (nth 2 board) (nth 3 board))
  (format t "-----------")
  (print-row (nth 4 board) (nth 5 board) (nth 6 board))
  (format t "-----------")
  (print-row (nth 7 board) (nth 8 board) (nth 9 board))
  (format t "~&~%"))

(print-board *board*)

ResultX | O | O 
 X | X |   
 X |   | O 
=> NIL

Here's where having board as a filler item in the *board* list is useful: the calls to nth here are more intuitive.

Now we need to get player input. We need to ensure that our input is well-formed and that the move from the player is legal.

(defun read-legal-move (piece board)
  (let ((move (read)))
    (cond ((not (integerp move))                                                    
           (format t "~&Moves must be a number between 1-9. Your move: ~a~%" move) 
           (print-board board)                                                   
           (read-legal-move piece board))                                           
          ((not (and (>= move 1) (>= 9 move)))
           (format t "~&Choose a space between 1 and 9.")
           (print-board board)
           (read-legal-move piece board))
          ((/= (nth move board) 0)
           (format t "~&You must place a piece on an empty space.")
           (print-board board)
           (read-legal-move piece board))
          (t move))))

The function read is how we request user input from the REPL. In the cond form–which can look pretty hairy to our new Lisp brothers–we run a few checks. integerp is a predicate function (with names typically ending with p -p) that checks if the user input is an integer. If the player input isn't a number, we tell them we need a number, print the board, and let the player try again.

The next check makes sure that the number the user inputted was a number between 1 and 9.

Finally, we need to check that the space chosen by the player is empty.

If the move passes all the checks, then the cond will evaluate the final form (t move). This is the conventional way of providing a default branch in the cond if all other conditions return nil. In this instance, we just return move.

Now we can make a move.

(defun move (piece board)
  (format t "~&It's ~a's turn.~%" (convert-to-letter piece))
  (print-board board)
  (let* ((move (read-legal-move piece board))
         (updated-board (place-piece board piece move))
         (winner (winner-p updated-board)))
    (cond (winner
            (format t "~a wins!" (convert-to-letter (/ (first winner) 3))))
          ((tie-p updated-board)
            (format t "It's a tie!"))
          (t (move (opponent piece) board)))))

(defun play-game ()
  (reset-board)
  (print "X goes first")
  (move *player-one* *board*))

let* is how we bind locally-scoped variables. let*, unlike the regular let, can bind variables to values that were computed earlier in the form. We pass move to place-piece and bind updated-board to the value returned. If we used let instead, we would get an error.

At this point, the human-vs-human version of the game is feature-complete. What we want now is to add a computer opponent.

At minimum, the computer needs to do the following:

• If there is a winning move, choose it.
• If there is a blocking move, choose it.
• Otherwise, take a random position.

That's easy to do:

(defun choose-move (board)
  (or (make-three-in-a-row board)    
      (block-opponent-win board)    
      (take-random-position board)))

or will evaluate its arguments in order. It will stop evaluation on the first argument that returns a non-nil value.

The computer needs to know if a winning move is available. There is a winning move available if any of the triplets sum to 20.

First, let's make a test board.

(defparameter *test-board* '(board
                             10 1 0
                             10 1 0
                             0 0 0))

What we want to is to find a triplet that sums to 20.

(find-if (lambda (triplet) (= 20 (sum-triplet *test-board* triplet))) ,*triplets*)

Result(1 4 7)

find-if takes a predicate function and returns the first value in a sequence that evaluates to t when the predicate is applied to it. It iterates over *triplets*, and tests if any of the triplets on the board sum up to 20.

If we find a triplet with a winning move, we want to return the position on the board to take. That means we need to find the element in the winning triplet that is 0.

(find-if (lambda (element) (= 0 (nth element *test-board*)))
         (find-if (lambda (triplet) (= 20 (sum-triplet *test-board* triplet))) *triplets*))

Result7

Since we need to do the same thing to check if we need to block…

(find-if (lambda (element) (= 0 (nth element *test-board*)))
         ;; Notice (= 2 ...), not (= 20 ...)
         (find-if (lambda (triplet) (= 2 (sum-triplet *test-board* triplet))) *triplets*))

Result8

…we can make this one function.

;; NOTE: bug left purposefully for teaching purposes
(defun win-or-block (board target-sum)
  (let ((target-triplet (find-if (lambda (triplet) (= target-sum (sum-triplet *test-board* triplet)))
                                 *triplets*)))
    (when target-triplet
        (find-if (lambda (element) (= (nth element board) 0)) target-triplet))))

Test it. Passing 2 checks if we need to block; passing 20 checks if we can win:

(win-or-block *test-board* 2)

Result8

(win-or-block *test-board* 20)

Result7

Now that we have a function that can find spaces to either win or block a win, we can call it with the appropriate target-sum in our win and block strategies.

(defun make-three-in-a-row (board)
  (let ((move (win-or-block board (* 2 *player-two*))))
    (when move
        (list move (format nil "~&I see a winning move at ~a.~%" move)))))

(defun block-opponent-win (board)
  (let ((move (win-or-block board (* 2 *player-one*))))
    (when move
        (list move (format nil "~&Danger! Loss imminent! Moving to block at
 ~a.~%" move)))))

(make-three-in-a-row *test-board*)

Result(7 "I see a winning move at 7. ")

(block-opponent-win *test-board*)

Result(8 "Danger! Loss imminent! Moving to block at 8. ")

We will return a list with the move and also the strategy employed.

If the computer is going first, it should just take a random position.

(defun take-random-position (board)
  (let ((move (+ 1 (random 9))))
    (cond ((= 0 (nth move board))
           (place-piece board *player-two* move)
           (list move "Picking random position."))
          (t
           (take-random-position board)))))

random will choose a semi-random value between 0 and the argument passed. Unfortunately, there is no way to specify the beginning of the "range". Since we need to pick a number between 1 (remember the filler BOARD symbol) and 9 inclusive, we add 1 to the result.

Since the random position chosen may be occupied, the catchall branch simply makes a recursive call to take-random-position to try again.

Right now, move calls itself with the opponent player. We'll need a human-move and computer-move to give us the ability to let the computer choose.

(defun human-move (board)
  (format t "~&It's ~a's turn.~%" (convert-to-letter *player-one*))
  (print-board board)
  (let* ((move (read-legal-move *player-one* board))
         (updated-board (place-piece board *player-one* move))
         (winner (winner-p updated-board)))
    (cond (winner
           (print-board updated-board)
           (format t "~a wins!" (convert-to-letter (/ (first winner) 3))))
          ((tie-p updated-board)
           (print-board updated-board)
           (format t "It's a tie!"))
          (t (computer-move board)))))

(defun computer-move (board)
  (format t "~&It's ~a's turn.~%" (convert-to-letter *player-two*))
  (print-board board)
  (let* ((move-and-strategy (choose-move board))
         (move (first move-and-strategy))
         (strategy (second move-and-strategy))
         (updated-board (place-piece board *player-two* move))
         (winner (winner-p updated-board)))
    (format t "~&My move: ~a~%" move)
    (format t "~&My strategy: ~a~%" strategy)
    (cond (winner
           (print-board updated-board)
           (format t "~a wins!" (convert-to-letter (/ (first winner) 3))))
          ((tie-p updated-board)
           (print-board updated-board)
           (format t "It's a tie!"))
          (t (human-move board)))))

(defun play-game-with-computer ()
  (reset-board)
  (if (y-or-n-p "Do you want to go first, human?")
      (human-move *board*)
      (computer-move *board*)))

The y-or-n-p function takes user input like read does, but it only accepts two possible inputs: y or n, meaning yes or no. It evaluates to t for yes and nil for no.

The simple data representation we chose at the beginning has made it fairly easy to get a simple human-vs-computer tic-tac-toe game made. However, the computer is very dumb. It doesn't think ahead and doesn't recognize different human strategies. Let's change that.

Tic-tac-toe has a rather unfun characteristic: if played well by both players, every game will end in a draw.

For our computer strategies, then, we are going to be mostly reacting to the human player, recognizing different strategies and countering them perfectly. By the end, we'll totally drain what little fun can be had from the game. But the coding will be fun, so let's go.

There are two strategies you can employ that can guarantee a victory if the opponent doesn't react correctly: the squeeze play and a two-on-one play.

(defparameter *squeeze* (list 'board 1 0 0 0 10 0 0 0 1))
(print-board *squeeze*)

ResultX |   |   
OX => NIL

(defparameter *two-on-one* (list 'board 1 0 0 0 1 0 0 0 10))
(print-board *two-on-one*)

ResultX |   |   
XO => NIL

The squeeze happens when one player takes two corners and one player takes the middle. The two-on-one happens when one player takes the corner and the middle, and the other player takes a corner as well. In both scenarios, O is guaranteed to lose if X plays properly.

To avoid these two scenarios, the computer must recognize possible strategies being deployed against it and react correctly.

• If the computer is in the middle between two human pieces, it's a possible squeeze.
  • To counter, take a side: don't take a corner.
• If the computer is in a corner and the human has the middle and the corner lining up his pieces against the computer, it's a possible two-on-one.
  • To counter, take a corner: don't take a side.

Right now, the computer reads the board as a list of triplets and identifies possible wins and danger. But to ensure both players end the game disappointed, the computer needs to recognize some other characteristics of the board: corners and sides.

(defparameter *corners* '(1 3 7 9))
(defparameter *sides* '(1 2 3 4 6 7 8 9))

Let's start by detecting a squeeze.

First, we need to search the board and cross-reference the triplets, looking for any triplet with values that reduce to 12

(defun detect-squeeze (board)
  (find-if (lambda (triplet)
               (= 12 (sum-triplet board triplet)))
           *triplets*))

(detect-squeeze *squeeze*)

Result(1 5 9)

(detect-squeeze *two-on-one*)

Result(1 5 9)

We need to know for sure this is a diagonal triplet, though.

(defun diagonal-p (triplet)
  (every (lambda (item)
             ;; Every item is either a corner or the middle.
             (or (member item *corners*)
                 (= 5 item)))
         triplet))
(defun detect-squeeze (board)
  (find-if (lambda (triplet)
               ;; Add AND and DIAGONAL-P
               (and (= 12 (sum-triplet board triplet))
                    (diagonal-p triplet)))
           *triplets*))

Let's try again:

(detect-squeeze *squeeze*)

Result(1 5 9)

(detect-squeeze *two-on-one*)

Result(1 5 9)

Both still return the same result.

every runs a predicate function on a sequence and returns t if the predicate evaluated to t for every element of the sequence. In diagonal-p, it checks if every element of the triplet is either a corner or the middle space.

We also need to know who is in the middle.

(defun human-in-middle-p (board)
  (= (nth 5 board) *player-one*))

;; Add TARGET-SUM as an argument.
(defun detect-squeeze (board target-sum)
  (find-if (lambda (triplet)
               ;; Use TARGET-SUM.
               (and (= target-sum (sum-triplet board triplet))
                    (diagonal-p triplet)
                    ;; Add HUMAN-IN-MIDDLE-P.
                    (not (human-in-middle-p board))))
           *triplets*))

Now the two boards produce different results:

(detect-squeeze *squeeze* 12)

Result(1 5 9)

(detect-squeeze *two-on-one* 12)

ResultNIL

Finally, we just need to be sure that we're at the beginning of the game. The player may have already blocked the squeeze or two-on-one, or the game may have otherwise progressed beyond the first diagonals.

(defun side-empty-p (board)
  (find-empty-position board *sides*))

(defun find-empty-position (board search-area)
  (find-if (lambda (x) (= 0 (nth x board))) search-area))

(defun detect-squeeze (board target-sum)
  (let ((squeeze-p
          (find-if (lambda (triplet)
                       (and (= (sum-triplet board triplet) target-sum)
                            (diagonal-p triplet)                           
                            (not (human-in-middle-p board))               
                            (side-empty-p board)))                       
                   *triplets*)))
    (when squeeze-p
        (find-empty-position board *sides*))))

If we see a squeeze, we need to counter. To counter a squeeze, we need to take a side (not a corner). So we look for an empty position in one of the *sides*.

If we test detect-squeeze, we should get an empty space on one of the sides:

(detect-squeeze *squeeze* 12)

Result2

2 is the space between corner 1 and 3, so it's given an expected return value.

detect-two-on-one is nearly identical to detect-squeeze:

(defun detect-two-on-one (board target-sum)
  (let ((two-on-one-p
          (find-if (lambda (triplet)
                       (and (= (sum-triplet board triplet) target-sum)
                            (diagonal-p triplet)
                            (human-in-middle-p board) 
                            (side-empty-p board)))
                   *triplets*)))
    (when two-on-one-p
      (find-empty-position board *corners*))))

Test both detection functions against both boards:

(detect-squeeze *two-on-one* 12)
(detect-squeeze *squeeze* 12)
(detect-two-on-one *two-on-one* 12)
(detect-two-on-one *squeeze* 12)

Resultdetect-squeeze on two-on-one: NIL
detect-squeeze on squeeze: 2
detect-two-on-one on two-on-one: 3
detect-two-on-one on squeeze: NIL

With that, we just need a couple of small wrappers to encapsulate our strategies.

(defun block-squeeze-play (board)
  (let ((move (detect-squeeze board (+ (* *player-one* 2) *player-two*))))
    (when move
      (list move "I'm being squeezed! Taking side space."))))

(defun block-two-on-one-play (board)
  (let ((move (detect-two-on-one board (+ (* *player-one* 2) *player-two*))))
    (when move
      (list move "It's two-on-one! Taking corner space."))))

Finally, we update choose-move by adding our two new strategies.

(defun choose-move (board)
  (or (make-three-in-a-row board)
      (block-squeeze-play board)         ; Added
      (block-two-on-one-play board)      ; Added
      (block-opponent-win board)
      (take-random-position board)))

Now you have a finished AI that will force a draw every game. Try playing it and enjoy infinite draws.

With this, you have gotten your first experience writing a program in Almighty Common Lisp. It may have been painful: if you aren't using structural editing modes like lispy-mode or paredit-mode, you had to make sure to keep your parentheses balanced and moving code around may have been harder than you expected. However, with practice, you'll be stacking parens like an expert.