Just Some Place

/ Blarchive / About Me / Notes and Misc / Uses / Photos /

Learn Lisp The Hard Way Stuff

This is my journey through the Learn Lisp The Hard Way book.

Common Lisp Bootcamp

Syntax Overview

Everything is an object that is represented by s-expressions.

S-expressions are formally defined as either an atom or a list. Lists of one or more elements are implemented as cons cells. Atoms are any object which is not a cons.

Examples of atoms: 

94  ; => 94 (7 bits, #x5E, #o136, #b1011110)

'a-quoted-symbol  ; => A-QUOTED-SYMBOL

#\greek_small_letter_lambda  ; => #\GREEK_SMALL_LETTER_LAMDA

"this is a string"  ; => "this is a string"

nil  ; => NIL

'()  ; => NIL

()  ; => NIL

t  ; => T

The single quoted expressions tell the lisp to not evaluate the quoted form. It's a way to switch the code expression to a data expression. 

'()  ; => NIL

'(this is a list of symbols)  ; => (THIS IS A LIST OF SYMBOLS)

(quote (this is another list of symbols))  ; => (THIS IS ANOTHER LIST OF SYMBOLS)

'another-quoted-symbol  ; => ANOTHER-QUOTED-SYMBOL

When not quoted, lists are treated as code. These are called forms. 

(+ 10 20 (* 30 2))  ; => 90 (7 bits, #x5A, #o132, #b1011010)

(princ "Hello, from Lisp!") ; Hello, from Lisp! => "Hello, from Lisp!"

(loop for item in '(this list will get printed in titlecase) do (format t "~@(~A~) " item))
; This List Will Get Printed In Titlecase  => NIL

Expressions, Parentheses and Return Values

Everything is read as or expanded into an s-expression. Quoting is one way to disable evaluation for a nested s-expression.

Some operations are destructive and change the environment in-place. These functions are typically named with a prepended "N" by convention. 

;; define a couple of variables
(defvar *test-list-a* (list 1 2 3))  ; => *TEST-LIST-A*
(defvar *test-list-b* (list 'd 'e 'f))  ; => *TEST-LIST-B*

;; append returns a new list from its args
(append *test-list-a* *test-list-b*)  ; => (1 2 3 D E F)

*test-list-a*  ; => (1 2 3)
*test-list-b*  ; => (D E F)

;; now for something destructive: NCONC is in-plcae list concatenation
(nconc *test-list-a* *test-list-b*)  ; => (1 2 3 D E F)
*test-list-a*  ; => (1 2 3 D E F)

;;

Expressions are expected to return a value, with little exception. A function call is expected to return the value of the last form in its body as the value of the entire function. 

;; a typical anonymous function call - the last form in its body is (+ x x)
;; so the function call returns (+ 2 2) => 4
((lambda (x) (+ x x)) 2)  ; => 4 (3 bits, #x4, #o4, #b100)

;; here, the return result of (+ x x) is not assigned so it is essentially lost
;; the function moves on to the next form, (* x x), which is returned
((lambda (x) (+ x x) (* x x)) 10)  ; => 100 (7 bits, #x64, #o144, #b1100100)

;; here we capture the return values of both (+ x x) and (* x x) as
;; lexical values SUM and PRODUCT. Using the VALUES function we can
;; return multiple values from a form instead of just one.
((lambda (x) (let ((sum (+ x x)) (product (* x x))) (values sum product))) 10) ; => 20, 100

;; note that calling VALUES with nothing gives us an expression with no return result
(values)  ; => ; No value

Note that as far as the lisp reader is concerned, the following representations are the same: 

'(a b c)  ; => (A B C)
'(a
  b
  c)  ; => (A B C)
(list 'a 'b 'c)  ; => (A B C)
;;

Always remember: Lisp code is meant to be simple and elegant.

Lisp code is meant to be simple and elegant; if you find yourself staring into an impenetrable confusion of parenthesis-chaos, your code is too complex for you to manage. Using techniques for decomposition and refactoring also presented in this book, you will learn how to write beautiful and elegant programs as well as the Common Lisp language itself.

Lists, cons-cells and memory

There is a need to separate the representation and implementation os s-expressions. In common lisp, s-expressions are defined by their implementation…their representation is only treated as an interface to the underlying objects.

Lists are a proper type, descending from sequences. A list only conses as long as there are values to be consed. Consider: 

(list)  ; => NIL

(list 'a)  ; => (A)

(list 'a nil)  ; => (A NIL)

(cons 'a nil)  ; => (A)

Again, lists are built upon cons-cells. 

;; this
(list 'a 'b 'c) ; => (A B C)

;; is the same as
(cons 'a (cons 'b (cons 'c nil))) ; => (A B C)

;; while this
(list 'a 'nil) ; => (A NIL)

;; is the same as
(cons 'a (cons nil nil)) ; => (A NIL)

The end of a chain of cons-cells normally terminates in nil, but you can have the cdr of a cons-cell point to a value too, and eliminate the need for an extra consing by using dot-notation. 

;; this
'(a . b)  ; => (A . B)
;; is the same as
(cons 'a 'b)  ; => (A . B)

A list of dot-notation pairs is called an association list, or alist for short. 

'((a . b)
  (c . d)
  (e . f)) ; => ((A . B) (C . D) (E . F))

So what is a cons-cell?

A Cons-Cell is a pair of pointers, the car and the cdr—acronyms for "Contents of Address Register" and "Contents of Decrement Register", respectively. The car is usually a pointer to a value, while the cdr can be a pointer to the car of another cons-cell, a pointer to NIL, or in the case of a dotted-pair, another pointer to a value.

i.e.: (car . cdr)

Reconsidering some examples from above in a new light: 

;; this creates three cons-cells,
;; the quoted symbols 'A, 'B and 'C each in the CAR of their own cons-cell
(list 'a 'b 'c) ; => (A B C)

;; it would be the same as typing this:
(cons 'a (cons 'b (cons 'c nil))) ; => (A B C)

;; or this:
'(a . (b . (c . nil))) ; => (A B C)

;; or this:
'(a b c . nil) ; => (A B C)

;; or simply this:
'(a b c) ; => (A B C)
;;

It is recommend to limit the number of times that your code conses. Note that the dotted pair only has to cons once, while a two item list that contains the same information conses twice. By using an alist instead of other list-based data structures (such as plists) you are already ahead of the game.

Symbols and namespaces

Common Lisp is referred to as a Lisp 2. This means it has separate namespaces for both functions and variables. This would let the user bind and assign both a function and a variable to, say, foo and evaluate (foo foo) and the lisp knows how to distinguish by the location in the form. The reader macro #' can also be used to refer to the function definition in an argument location, (apply #' foo foo). Please don't do this as it's bad form. 

;; just because you can
;; doesn't mean you should
(defvar foo 1)  ; => FOO

(defun foo (foo)
  (+ foo foo)) ; => FOO

(foo foo) ; => 2 (2 bits, #x2, #o2, #b10)

In the above, there are three separate bindings of the symbol foo:

  1. The global variable foo, bound by the defvar to the value of 1
  2. The function definition of foo, along with…
  3. The parameter named foo in the function foo.

This is because in addition to having separate namespaces for Functions and Variables, Common Lisp is also both dynamically and lexically scoped. Dynamic scoping is special and explicit in Common Lisp; lexical scoping is more intuitive and implicit—in other words, you have to specifically declare a symbol to be special to use its dynamic binding from within a lexical scope where the symbol could be lexically bound and assigned as a different variable, while many forms introduce an implicit lexical scope. For this reason there is a naming convention for top-level, dynamic variables, called "earmuffs" 

;; Top level, dynamic variables can be declared with DEFVAR or DEFPARAMETER
(defvar *my-dynamic-var* "I'm special!")  ; => *MY-DYNAMIC-VAR*

;; Note that the variable names are qualified with a pair of asterisks.
;; These are commonly referred to as "earmuffs".
(defparameter *my-extra-special-dynamic-var* "I'm special, too!")  ; => *MY-EXTRA-SPECIAL-DYNAMIC-VAR*

;; An obvious way to introduce a lexical scope is with a LET form
;; for binding and assigning lexical scope.
(let ((one 1)
      (two 2)
      (three 3))
  (+ one two three)) ; => 6 (3 bits, #x6, #o6, #b110)

;; To put things together:
(defvar *one* 1)  ; => *ONE*

(let ((one 1.0))
  (+ one *one*)) ; => 2.0

Aside: The package system The common lisp package system allows to create custom read-tables for the environment. When defining a package, one has to explicitly import any symbols that should be available in the package namespace - this includes the symbols of the common lisp language itself. This is done with the :use keyword expression. 

(in-package :cl-user)

(defpackage #:my-new-package
  (:nicknames #:newpack)
  (:use :cl :cl-user)
  (:export #:mad-adder))

(in-package :my-new-package)

(defvar *my-private-var* "I'm not exported from the package.")

(defun mad-adder (n &rest rest)
  "An addition function for MY-NEW-PACKAGE."
  (apply #'+ n rest))

After loading and compiling the file, we can: 

;; This:
(newpack:mad-adder 1) ; => 1 (1 bit, #x1, #o1, #b1)

;; is the same as:
(my-new-package:mad-adder 1) ; => 1 (1 bit, #x1, #o1, #b1)

;; if a symbol is not exported, you have to use two colons
;; between the package and symbol names:
newpack::*my-private-var* ; => "I'm not exported from the package."

Prefix Notation

Remember that the car of an evaluated list has to be a valid operator, the cdr of the evaluated list is itself a list of arguments to the operator. Also, lists are implemented as Cons-Cells. 

;; Polish Prefix Notation
(operator . (list of parameters))

Valid operators can be a symbol representing a function, macro or special operator; or a lambda expression representing an anonymous function.

Macros are tricky, they can be expanded into normal lisp code at various times; reader macros are expanded at read time, defmacro forms are expanded at compile time. There are various techniques for controlling when and where macros are expanded.

Common Lisp Style Guide

There are no hard and fast rules on style, but these are some generally decent ideas.

Symbols and naming

Symbol names should be descriptive, short, typed in all lowercase, with words separated by a single hyphen. 

(defun my-addition-function (&rest rest)
  (apply #'+ rest))  ; => MY-ADDITION-FUNCTION

(deftype my-integer-type ()
  '(and integer
    (satisfies plusp))) ; => MY-INTEGER-TYPE

(defvar my-hash-table (make-hash-table :test 'equal))
 ; => MY-HASH-TABLE

;; Note that symbol names created from strings should
;; be in all caps:
(intern "MY-NEW-INTERNED-SYMBOL")
 ; => MY-NEW-INTERNED-SYMBOL, NIL

;; ..or, you'll have to reference it in surrounding
;; hbars as a literal, case-sensitive symbol:
(intern "my-funky-interned-symbol")
 ; => |my-funky-interned-symbol|, NIL

The use of hbars is syntactiv and not stylistic. It is, generally, only going to be used for foreign-function interfaces.

Global Variables, those declared as top-level forms with defvar or defparameter, should be named with *earmuffs*. 

;; This is a built-in variable:
*package*  ; => #<PACKAGE "COMMON-LISP-USER">

;; so is this:
*print-base*  ; => 10 (4 bits, #xA, #o12, #b1010)
;;

Earmuffs are stylistic and are not parsed as syntactic tokens by the lisp reader.

Another convention for symbol names uses a pair of plus-signs to wrap symbol names of constants: 

(defconstant +my-new-constant+ 1.0) ; => +MY-NEW-CONSTANT+

Package internal symbols are sometimes prepended with a percent sign, %, and not exported with the package API. 

;; An example package
(defpackage #:my-new-package
  (:use :cl)
  (:export #:mad-adder))  ; => #<PACKAGE "MY-NEW-PACKAGE">

(in-package :my-new-package) ; => #<PACKAGE "MY-NEW-PACKAGE">

;; Do some wonky stuff with a package-internal function
(defun %madder (x)
  (declare (integer x))
  (apply #'+ (loop for i from 1 upto x
                   collect (* x i)))) ; => %MADDER

;; Write an exported interface to your package internal function
(defun mad-adder (x)
  "Call %MADDER with integer argument X."
  (%madder x)) ; => MAD-ADDER

(in-package :cl-user) ; => #<PACKAGE "COMMON-LISP-USER">

(my-new-package:mad-adder 10)  ; => 550 (10 bits, #x226)

;;This will throw an error:
;; (my-new-package:%madder 10)

Predicate functions - boolean tests - will typically end with a suffixed "p". If it's a multiword symbol already separated by dashes, the append the suffix as "-p". If it's a single word or mnemonic symbol name, the "p" can be appended sans dash. 

(bit-vector-p #*01010001) ; => T

(integerp 10) ; => T

Parentheses, Indentation and Whitespace

Parentheses should all close on the same line, when ending multiple forms. Use a good editor to help with paren balancing and demarcation if needed.

Use spaces, not tabs, to indent code. Bodies should be indented two spaces from the parent form, while parameters and list members can be lined up into columns when they take up too many characters to fit on an ideal line of code. 

;; IF is a special operator and does not have a body expression
(if t t nil)

;; but, you'll most normally want to split the form for clarity.
;; Note how the three parameters line up
(if t
    (format t "Then: True~%")
    (format t "Else: False~%"))

;; WHEN does have a body expression, so its body is not lined up with the test-form parameter
(when t
  (format t "This is true, too!"))

Don't use the Tab character to force a table-like structure into code, it disrupts the flow: 

;; This is a bad choice:
(defclass march-hare ()
  ((name        :type string    :initarg name           :initform "Haigha"      :accessor name)
   (tea-time-p  :type boolean   :initarg :tea-time-p    :initform t             :accessor tea-time-p)
   (tie         :type string    :initarg :tie           :initform "bow-tie"     :accessor tie)))

;; This is a good choice:
(defclass march-hare ()
  ((name :type string :initarg :name :initform "Haigha" :accessor name
         :documentation "The name of the March Hare.")
   (tea-time-p :type boolean :initarg :tea-time-p :initform t :accessor tea-time-p
               :documentation "Whether or not it's tea-time.")
   (tie :type string :initarg :tie :initform "bow-tie" :accessor tie
        :documentation "The style of tie the March Hare is wearing."))
  (:documentation "'The March Hare will be much the most interesting, and perhaps as this is May it won't be raving mad--at least not so mad as it was in March.' -- Lewis Carroll"))

Comments and Documentation

Always comment and document code.

There are few conventions around code comments: 

;;;; Four semi colons for file headers, copyright and licensing details

;;; Three semi colons for descriptive text

;; Two semi colons for commentary on the immediately following text

; One semi colon for in-line comments, inside code blocks

Decomposition, Refactoring, Abstraction

Code should be clear and focused. Break code up to the smallest reusable pieces.

Printing, Streams, Strings

Strings

Lisp has four types of strings:

  1. The standard string type
  2. A simple-string
  3. base-string
  4. simple-base-string

Those apart from the string type are specialized, so generally use the string type.

The simplest way to create a string - which are self-evaluating - is with double-quotes: 

"this is a string" ; => "this is a string"

"here's another string!" ; => "here's another string!"

The entire string is treated as an atom. Underneath, it is actually a specialized vector of character objects. Recall an atom is anything not a Cons.

Strings can contain any character without escaping, with two exceptions: a double-quote and a backslash. 

"This contains a \"double quotes\"." ; => "This contains a \"double quotes\"."

"This contains an escaped backslash: \\." ; => "This contains an escaped backslash: \\."

Note that you get back exactly what you typed.

In general, string objects are Unicode in common lisp, as UTF-8. A quick check would be if char-code-limit returns 1114112. 

char-code-limit  ; => 1114112 (21 bits, #x110000)

A more specialized check, that only works with sbcl, can use lisp's read-time-conditionals: 

#+sb-unicode (format nil "~C" #\cuneiform_sign_an_plus_naga_opposing_an_plus_naga)
 ; => "𒀰"

Again, that is not portable. That specific test also would require cuneiform fonts installed, such as ttf-akkadian.

Characters are unitary tokens, and there are two kinds of character objects: graphic and non-graphic.

Literal character objects can be entered with the sharpsign-backquote syntax: 

#\a ; => #\a

#\A ; => #\A

#\Space ; => #\

#\Newline ; => #\Newline

#\Tab ; => #\Tab

Note that the space character has both a graphic and non-graphic representation.

It's possible to get a list of characters from a string: 

(coerce "hello, multiverse!" 'list)
 ; => (#\h #\e #\l #\l #\o #\, #\  #\m #\u #\l #\t #\i #\v #\e #\r #\s #\e #\!)

While not portable, some lisp implementations allow one to refer to any character beyond the ASCII range using a character object with its Unicode name. Replace the space word separators with underscores: 

#\subscript_three
 ; => #\SUBSCRIPT_THREE
#\greek_small_letter_lamda
 ; => #\GREEK_SMALL_LETTER_LAMDA
#\greek_capital_letter_sigma
 ; => #\GREEK_CAPITAL_LETTER_SIGMA
#\cuneiform_sign_an_plus_naga_opposing_an_plus_naga
 ; => #\CUNEIFORM_SIGN_AN_PLUS_NAGA_OPPOSING_AN_PLUS_NAGA

Character codes - character objects all have numeric values called codes, that can be obtained with char-code. 

(code-char #x61) ; => #\a

(char-code #\a) ; => 97 (7 bits, #x61, #o141, #b1100001)

Most of the time one wants to work with strings instead of characters. You can get a one-character string object directly from a character object by calling the string function on it. 

(string #\greek_small_letter_lamda)  ; => "λ"

This only takes one argument, a character or a string; it isn't smart and doesn't know how to do much in the way of type conversion.

Using the coerce function (as from above) one can convert a list of characters into a 'string. 

(coerce '(#\( #\greek_small_letter_lamda #\)) 'string) ; => "(λ)"

Printing

All of the ways to handle printing in lisp are built upon the write function, you will rarely use it directly though it is good to know about. It takes a lot of options. 

;; The simplest way to call WRITE is with one parameter
(write "hello") ; "hello" => "hello"

(write 10); 10 => 10 (4 bits, #xA, #o12, #b1010)

(write 'hello); HELLO => HELLO

The write function will use sensible defaults depending on what object type is used. But, say we wanted to change some of the ways to display an integer: 

(write 10000 :base 16 :radix t); #x2710 => 10000 (14 bits, #x2710)

(write 10000 :base 8 :radix t); #o23420 => 10000 (14 bits, #x2710)

(write 10000 :base 2 :radix t); #b10011100010000 => 10000 (14 bits, #x2710)

The :radix keyword parameter is a generalized boolean. This means that any "non-NIL" value you pass to it will be read the same as "True", even if you don't supply t itself. The only time it will be treated as "False" is when you specifically pass it NIL.

Note that the write examples returned the same value twice above. The default :stream is *standard-output* and just happens to be where the function return values are sent when working at a REPL. We'll learn later how to set where this stuff should go.

The difference in the second set is that write first prints the object passed into it using the parameters passed, then it also returns the original object as well.

The print function family

There is also a function for printing called print. It works by passing an object in to be printed, as well as a stream to print to. It will print the object between a new-line character and a space. Note that print will print objects readably, i.e. in a format suitable to be read by the lisp reader and escaping special characters. 

(print "hello, multiverse!")
; "hello, multiverse!"  => "hello, multiverse!"

(print "hello again, multiverse!" t) ; => "hello again, multiverse!"

(print "hello, multiverse, are you there?" nil)
; "hello, multiverse, are you there?"  => "hello, multiverse, are you there?"

;; Now for an equivalent version using the `write' function:
(progn (terpri t)
       (write "hello, multiverse!" :stream t :escape t)
       (write-char #\Space t)) ; => #\

There is no need to pass the second parameter to print, the default is nil, so the third is the same as the first. There are a few new concepts introduced in the equivalent version as well:

  1. progn is a special operator that tells lisp to evaluate each expression sequentially in the order they appear.
  2. terpri stands for "terminate printing" and is used to send a new-line character to a stream. This is how the print function is implemented as well.
  3. We see two new keyword parameters for the write function. :stream and :escape. These tell where to print the object parameter and whether or not to escape what has been printed.
  4. The write-char function is like write, but only prints a single character object to the stream.

Also note that above it would seem as though the last string was not printed, but it was returned at the linked REPL. Only the space character was returned, as it is the last form in the body.

The next printing function is prin1. Similar to print, with the exception that it does not output a preceding newline or a trailing space. Its emphasis is on printing readably for the lisp reader - in other words it's intended use is to have its output be used again as source code. It also sets :escape to t, so special characters are printed escaped. 

(prin1 "Although largely uninteresting, this \"string\" has escaped characters in it.")
; "Although largely uninteresting, this \"string\" has escaped characters in it." => "Although largely uninteresting, this \"string\" has escaped characters in it."

(prin1 "Remember, since the backslash (\\) is the escape character, it needs to be escaped too.")
; "Remember, since the backslash (\\) is the escape character, it needs to be escaped too." => "Remember, since the backslash (\\) is the escape character, it needs to be escaped too."

(prin1 "\Y\o\u\ \c\a\n\ \a\l\s\o\ \e\s\c\a\p\e\ \e\v\e\r\y\ \c\h\a\r\ \i\f\ \y\o\u\ \w\a\n\t\e\d\.")
; "You can also escape every char if you wanted." => "You can also escape every char if you wanted."

Next is the princ function. Use this when the output is intended for users and not the lisp reader. This sets :escape and :readably to nil, so users can see the string as intended and not as typed into lisp. 

(princ "Hello, multiverse!"); Hello, multiverse! => "Hello, multiverse!"

(princ "My name is \"Colin\"."); My name is "Colin". => "My name is \"Colin\"."

Again note that the function still returns the original object, after outputting to the stream.

The format function

The format function is the fully supported way to insert arbitrary data into a string.

The format function uses a special type of string with its own internal syntax, called control sequences. These are made up of the tilde character and control character itself, along with certain infix parameters to customize the behavior.

A common control sequence is the aesthetic control sequence: ~A. It consumes an argument and inserts that into the string, printed the same way as the princ function would print it. Another control sequence is the standard control: ~S. It consumes an argument and prints it as the way prin1 would. Next would be the ~W, or write, control sequence. This also consumes an argument and prints the way the write function would.

Examples: 

;; This calls the `format' function, tells it to return the formatted
;; string to the stream NIL and creates a format string that consumes
;; one argument to be printed aesthetically. That argument is "Steve".
(format nil "Hello, my name is ~A." "Steve")
 ; => "Hello, my name is Steve."

This next example consumes two arguments and outputs to the nil stream: 

(format nil "Hello, my name is ~A ~A." "Steve" "Rogers")
 ; => "Hello, my name is Steve Rogers."

Here are examples of the other introduced control characters: 

(format t "Aesthetically formatted: ~A" "Aesthetic")
; Aesthetically formatted: Aesthetic => NIL

(format t "Standardly formatted: ~S" "Standard")
; Standardly formatted: "Standard" => NIL

(format t "Writtenly formatted: ~W" "Written")
; Writtenly formatted: "Written" => NIL

Note that when we send the format output to the *standard-output* stream, t, the output string is printed and the format function returns nil, instead of another string object.

Also note that with both the standard and written controls, the arguments are printed literally, with quotes and all.

Here are some other control sequence examples, we'll explain them in a bit: 

(format nil "~~") ; => "~"

(format nil "H~CO" #\subscript_two) ; => "H₂O"

(format nil "~R" 10000) ; => "ten thousand"

(format nil "~X" 10000) ; => "2710"

(format nil "~D" 10000) ; => "10000"

(format nil "~O" 10000) ; => "23420"

(format nil "~B" 10000) ; => "10011100010000"

(format nil "~%Hello, ~A!" "Steve");  => "
; Hello, Steve!"

(format nil "~&I said, hello!") ; => "I said, hello!"

What those did:

  1. ~~: printed a tilde symbol, does not consume anything
  2. ~C: prints a character, consumes.
  3. ~R: formats an integer as a string, consumes.
  4. ~X, ~D, ~O, ~B: hexadecimal, decimal, octal, binary, respectively, all consume.
  5. ~%: force insertion of a #\Newline character, does not consume.
  6. ~&: Inserts a #\Newline character only if the output stream is not already at the beginning of a line, does not consume.

Pathnames

Lisp has a special way of handing files using pathname objects. These enable platform-agnostic file handling, generally.

Pathname objects are represented using the reader macro syntax of #P"...". They look like strings preceded by a sharp-P, but have more internal structure.

There is a lot that can be obtained from a pathname: 

(truename ".") ; => #P"/home/swrogers/projects/llthw/"

(pathname-directory (truename ".")) ; => (:ABSOLUTE "home" "swrogers" "projects" "llthw")

(pathname-host (truename ".")) ; => #<SB-IMPL::UNIX-HOST {10000E6B53}>

(pathname-name (truename ".")) ; => NIL

(pathname-type (truename ".")) ; => NIL

It is expected to receive nil for pathname-name and pathname-type.

Let's try with a new file: llthw-ex-1-2-14.lisp 

;; an empty common lisp file

(truename "llthw-ex-1-2-14.lisp") ; => #P"/home/swrogers/projects/llthw/llthw-ex-1-2-14.lisp"

(pathname-name (truename "llthw-ex-1-2-14.lisp")) ; => "llthw-ex-1-2-14"

(pathname-type (truename "llthw-ex-1-2-14.lisp")) ; => "lisp"

(file-namestring (truename "llthw-ex-1-2-14.lisp")) ; => "llthw-ex-1-2-14.lisp"

To explain what those are doing, if it is not obvious: truename takes a regular string that represents a pathname object, called a pathname designator. This can be either a relative or full pathname namestring, a file stream or an actual pathname object.

The other functions in the above examples only take a proper pathname object.

Note that file-namestring returns just the file's namestring for a pathname object to a file. If given a pathname object to a directory it will return an empty string, "". There are other functions related to this: 

(truename "llthw-ex-1-2-14.lisp") ; => #P"/home/swrogers/projects/llthw/llthw-ex-1-2-14.lisp"

(file-namestring (truename "llthw-ex-1-2-14.lisp")) ; => "llthw-ex-1-2-14.lisp"

(namestring (truename "llthw-ex-1-2-14.lisp")) ; => "/home/swrogers/projects/llthw/llthw-ex-1-2-14.lisp"

(directory-namestring (truename "llthw-ex-1-2-14.lisp")) ; => "/home/swrogers/projects/llthw/"

(host-namestring (truename "llthw-ex-1-2-14.lisp")) ; => ""

(enough-namestring (truename "llthw-ex-1-2-14.lisp")) ; => "llthw-ex-1-2-14.lisp"

Streams

Streams are the basics of I/O in lisp.

They are objects, just like characters, strings, integers and pathnames, that can be designated for input, output or both.

There are a few ways to make string streams manually for input and output. Bi-directional streams can only be made from existing input and output streams.

Some examples: 

(make-string-input-stream "hello?")
 ; => #<SB-IMPL::STRING-INPUT-STREAM {1004625E23}>

(read (make-string-input-stream "hello!"))
 ; => HELLO!

(with-input-from-string (s "It's the multiverse!")
  (read s))
 ; => IT

(with-output-to-string (out)
  (with-input-from-string (in "\"Can I ask who's calling?\"")
    (let ((io (make-two-way-stream in out)))
      (format io "~A It's the Jovian moon, Io!" (read io)))))
 ; => "Can I ask who's calling? It's the Jovian moon, Io!"

make-string-input-stream just returns the stream object itself.

The read function is the entry point into the lisp reader. Here, it sees what it believes to be a symbol, so it just returns the symbol (uninterned).

The with-input-from-string macro creates the input stream and binds it to a local variable, s in this case, for the body of the macro. In this case, since the read function expects the same input as the lisp reader, what is sent to it needs to be escaped (i.e. Lisp data), which it is not here, the IT is parsed as just a symbol that ends at the single quote. Should we read from that stream multiple times, we'd see the symbols 'S, THE, MULTIVERSE!.

Finally, make-two-way-stream demonstrates creating an input and output stream object from an existing input stream, in, and the output stream that is created and bound by with-output-to-string, out.

To read and write from files, you need to use a file-stream object.

File streams can be created manually with open, but we'll go with the simplest case and use the with-open-file macro. 

(with-open-file (s "./monkey.txt" :direction :output :if-does-not-exist :create :if-exists :supersede)
  (format s "I had a little monkey,~%Brought him to the country,~%Fed him on ginger-bread...~%"))
 ; => NIL

(with-open-file (s "./monkey.txt" :direction :input)
  (format t "~&;;; ~A" (read-line s)))
; ;;; I had a little monkey, => NIL

(with-open-file (s "./monkey.txt" :direction :input)
  (do ((line (read-line s) (read-line s nil 'eof)))
      ((eq line 'eof) "-- Marilyn Manson")
    (format t "~&;;; ~A~%" line)))
; ;;; I had a little monkey,
; ;;; Brought him to the country,
; ;;; Fed him on ginger-bread...
;  => "-- Marilyn Manson"

Don't worry too much about the do form, it will be covered later. Just know that it iterates over the lines in the opened file until it reaches the end-of-file, then it returns a string in this case.

Binary streams, work similarly to file streams: open an input, output or bi-directional file stream and specify that you're working with bytes: 

(with-open-file (b "./binary-monkey.txt" :direction :output :element-type 'unsigned-byte :if-exists :supersede)
  (write-byte 109 b)
  (write-byte 111 b)
  (write-byte 110 b)
  (write-byte 107 b)
  (write-byte 101 b)
  (write-byte 121 b))  ; => 121 (7 bits, #x79, #o171, #b1111001)
                       ;

By setting the :element-type to unsigned-byte, we can use the write-byte function on the stream.

Extra Credit:

Rewrite the above example three times to use a do loop I showed you before, and a list of the numbers 109, 111, 110, 107, 101, and 121; represent these integers in hexadecimal, octal, and binary notation, respectively.

If you do it right, you should only have to call the write-byte function once in your do loop.

Also write the code to read the file back into Lisp as a string, and transform it into ALL-CAPS. Hint: you can do this either with format or the function string-upcase.

Prompting Users - Lisp has two built-in functions for prompting users: y-or-n-p and yes-or-no-p and both are predicate functions. They return either T or NIL. 

(y-or-n-p "Is your name Steve?")
;; NIL

(yes-or-no-p "Are you sure?")
;; T

(y-or-n-p "Are you a ~S?" 'monkey)
;; NIL

There is a lisp pretty printer, pprint, that can output better looking lisp code to make things easier to read: 

(pprint '(defun monkey (a b c) "a monkey function" (let ((d 4) (e 5) (f 6)) (values (list a b c) (list d e f)))))

(DEFUN MONKEY (A B C)
  "a monkey function"
  (LET ((D 4) (E 5) (F 6))
    (VALUES (LIST A B C) (LIST D E F)))); No value

Extra Credit / Exercises in getting input from users.

  • read: this procedure can read from a stream. (read) entered into the repl would do nothing, until you typed something else and entered return. It invokes the lisp reader to read s-expressions.

  • eval: used to evaluate something that has been read. Some forms are self-evaluating. 

    (eval (read)) ; => 12345 (14 bits, #x3039) ;; read in 12345
(eval (read)) ; => "A String" ;; read in "A String"

Sequences Exercises If you have an existing buffer you want to destructively read into, you can use read-sequence: 

(let ((dest (make-list 5)))
  (read-sequence dest *standard-input*)
  dest)
;; read in: abcde
;; (#\a #\b #\c #\d #\e)

;; The procedure will not read in more input than what
;; will fit into the specified buffer:
(let ((dest (make-list 3)))
  (read-sequence dest *standard-input*)
  dest)
;; read in: abcdefghi
;; (#\Newline #\a #\b)

The actual return value of read-sequence is the number of stream elements it consumed, and the buffer can be of any sequence type..

Lists and List Operations

Cons-Cells are one of two essential forms of expressions in lisp. Atoms are the other. Atoms are, by definition, self-evaluating, and everything interesting that can be done in lisp is essentially a list operation. There are two kinds of list operations: Consing and Non-consing.

Cons-cells are the smallest compound data structure in lisp and is effectively a pair of pointers. Use the consp predicate to check if an object is a cons-cell and use cons function to create them, i.e. consing. 

(consp 5) ; => NIL

(consp "a") ; => NIL

(consp 'a) ; => NIL

(consp (cons 'a 'b)) ; => T

Cons-cells can be created with the cons function. Again, this is called consing. 

(cons 'a 'b) ; => (A . B)

(cons 1 2) ; => (1 . 2)

(cons "one" "two") ; => ("one" . "two")

Note the special dot-notation syntax that is returned at the repl. We can use that format directly, as opposed to calling cons: 

(cons 'a 'b) ; => (A . B)

'(a . b) ; => (A . B)

;; The two representations are equal:
(equal (cons 'a 'b) '(a . b)) ; => T

Cons-cells need not be homogeneous data: 

(cons 'a 2) ; => (A . 2)

(cons 1 "two") ; => (1 . "two")

(cons "a" 'b) ; => ("a" . B)

Getting component values back from a cons-cell is done with car and cdr. To get the value from the first slot of a cons-cell, use car: 

(cons 'a 'b) ; => (A . B)

(car (cons 'a 'b)) ; => A

To get the value from the second slot of a cons-cell, use the cdr function: 

(cons 1 2) ; => (1 . 2)

(cdr (cons 1 2)) ; => 2 (2 bits, #x2, #o2, #b10)

cons, car and cdr are purely functional and do not mutate their arguments. 

(defvar *a* (cons 1 2)) ; => *A*

*a* ; => (1 . 2)

(cdr *a*) ; => 2 (2 bits, #x2, #o2, #b10)

*a* ; => (1 . 2)

(cons 3 (cdr *a*)) ; => (3 . 2)

*a* ; => (1 . 2)

As would be expected, the evaluation aborts with an error when attempting to use cdr or car on something that is not a cons-cell. Unless that something is an empty list or NIL. Which just returns NIL. 

;; These are errors
;; (car 1)
;;
;; (cdr 'a)
;;
;; (car "a")
;;
;; (cdr #(1 2)) ; does not work on vectors

;; These, however, do work:
(car nil) ; => NIL

(cdr nil) ; => NIL

(car ()) ; => NIL

(cdr ()) ; => NIL

Lists are either an empty list or a chain of cons-cells that end with an empty list. 

(listp nil) ; => T

(listp (cons 5 nil)) ; => T

If you cons something onto the empty list, you get a list of that thing: 

(cons 5 nil) ; => (5)

More fun, representing linked list: 

(cons 3 (cons 2 (cons 1 nil))) ; => (3 2 1)

Another way to create lists is to use the list function. It is effectively a shorthand version of stringing together a line of cons commands, with the final value being cons-ed onto NIL. 

(list 3 2 1) ; => (3 2 1)

(list 1 2 3) ; => (1 2 3)

(cons 1 (cons 2 (cons 3 nil))) ; => (1 2 3)

(equal (list 1 2 3) (cons 1 (cons 2 (cons 3 nil)))) ; => T

(list 1 (list 2 3) (list 4 (list (list 5) 6 7 8))) ; => (1 (2 3) (4 ((5) 6 7 8)))

It's possible to chain calls to car and cdr to fetch values from a nested structure 

(cons (cons 1 2) 3) ; => ((1 . 2) . 3)

(car (car (cons (cons 1 2) 3))) ; => 1 (1 bit, #x1, #o1, #b1)

(defparameter *tree* (list 1 (list 2 3) (list 4 (list (list 5) 6 7 8)))) ; => *TREE*

*tree* ; => (1 (2 3) (4 ((5) 6 7 8)))

(car (cdr (car (cdr *tree*)))) ; => 3 (2 bits, #x3, #o3, #b11)

;; It's common enough that there are shorthands for some of these:
(car *tree*) ; => 1 (1 bit, #x1, #o1, #b1)

(cadr *tree*) ; => (2 3)

(cadadr *tree*) ; => 3 (2 bits, #x3, #o3, #b11)

(cddr *tree*) ; => ((4 ((5) 6 7 8)))

(cdddr *tree*) ; => NIL

The shorthand functions from above are actual functions, not a reader syntax based on the number of a's and d's, so nothing redonkulous like caddadddaaar.

Should one want to destructively modify a list, such as to implement a mutable stack, you can use the push function. 

(defvar *stack* nil) ; => *STACK*

(push 1 *stack*) ; => (1)

*stack* ; => (1)

(push 2 *stack*) ; => (2 1)

(push 3 *stack*) ; => (3 2 1)

*stack* ; => (3 2 1)

To destructively remove the first element from a list, use pop: 

*stack* ; => (3 2 1)

(pop *stack*) ; => 3 (2 bits, #x3, #o3, #b11)

*stack* ; => (2 1)

(pop *stack*) ; => 2 (2 bits, #x2, #o2, #b10)

(pop *stack*) ; => 1 (1 bit, #x1, #o1, #b1)

*stack* ; => NIL

(pop *stack*) ; => NIL

*stack* ; => NIL

Similar to cons, push is not limited to the existing type of its target: 

(defvar *stack* nil) ; => *STACK*

*stack*  ; => NIL

(push 1 *stack*) ; => (1)

(push "b" *stack*) ; => ("b" 1)

(push 'c *stack*) ; => (C "b" 1)

(push (list 4 5) *stack*) ; => ((4 5) C "b" 1)

*stack* ; => ((4 5) C "b" 1)

In addition to car and cdr, cons-cells can be manipulated with the first and rest functions. These are just different names for the same functions, car and cdr respectively. 

(cons 'a 'b) ; => (A . B)

(car (cons 'a 'b)) ; => A

(first (cons 'a 'b)) ; => A

(cons 1 2) ; => (1 . 2)

(cdr (cons 1 2)) ; => 2 (2 bits, #x2, #o2, #b10)

(rest (cons 1 2)) ; => 2 (2 bits, #x2, #o2, #b10)

Another function, last, retrieves the last cons-cell in a series: 

(last (cons 1 (cons 2 (cons 3 nil)))) ; => (3)

(last (cons 1 2)) ; => (1 . 2)

(last (list 3 4 5)) ; => (5)

When dealing with linked lists, to get to a particular element from the middle one can chain together car and cdr: 

(car (cdr (cdr (cdr (list 0 1 2 3 4 5))))) ; => 3 (2 bits, #x3, #o3, #b11)

(cadddr (list 0 1 2 3 4 5)) ; => 3 (2 bits, #x3, #o3, #b11)

Or, use the nth function: 

(nth 3 (list 0 1 2 3 4 5)) ; => 3 (2 bits, #x3, #o3, #b11)

(nth 4 (list 0 1 2 3 4 5)) ; => 4 (3 bits, #x4, #o4, #b100)

(nth 5 (list 0 1 2 3 4 5)) ; => 5 (3 bits, #x5, #o5, #b101)

Appending lists together is the job of the append function. 

(append (list 1 2 3) (list 4 5 6)) ; => (1 2 3 4 5 6)

(append (list 6 5 4 3) (list 2 1)) ; => (6 5 4 3 2 1)

The append function takes a &rest argument, it can take any number of lists. 

(append (list 'a 'b 'c 'd) (list 'e 'f) (list 'g)) ; => (A B C D E F G)

(append (list 1) (list 2) (list 3) (list 4)) ; => (1 2 3 4)

Passing one list to append is pointless: 

(append (list 1 2 3)) ; => (1 2 3)

(list 1 2 3) ; => (1 2 3)

Like car, cdr, first, rest, last and nth, append is functional and will return a new list rather than mutating any of its arguments 

(defvar *lst* (list 1 2 3 4 5)) ; => *LST*

*lst* ; => (1 2 3 4 5)

(append *lst* (list 6 7 8)) ; => (1 2 3 4 5 6 7 8)

*lst* ; => (1 2 3 4 5)

(append (list -3 -2 -1 0) *lst*) ; => (-3 -2 -1 0 1 2 3 4 5)

*lst* ; => (1 2 3 4 5)

(append (list 0) *lst* (list 6)) ; => (0 1 2 3 4 5 6)

*lst* ; => (1 2 3 4 5)

The destructive equivalent of append is nconc. With this, one can create circular lists. 

(defparameter *cycle* (list 'a 'b)) ; => *CYCLE*

(first *cycle*) ; => A

(second *cycle*) ; => B

(third *cycle*) ; => NIL

(fourth *cycle*) ; => NIL

;; Before creating an actual cycle we have to tell the
;; interpreter to print them (otherwise the request to
;; print a circular list would never return due to common
;; lisp not being a lazy language)

(setf *print-circle* t) ; => T

(nconc *cycle* *cycle*);  => (A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A
 ; B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B
 ; A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A
 ; B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B
 ; A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A
 ; B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B
 ; A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A
 ; B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B
 ; A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A
 ; B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B
 ; A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A
 ; B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B
 ; A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A
 ; B A B A B ...)

(third *cycle*) ; => A

(fourth *cycle*) ; => B

(loop repeat 15 for elem in *cycle* collect elem) ; => (A B A B A B A B A B A B A B A)

While nconc is great for creating a simple cycle, we can also use direct mutation to create more elaborate structures. Here we have a structure that branches back onto itself twice. It's a rather large object. 

(defparameter *knot* (list 1 2 3 4 (cons nil nil))) ; => *KNOT*

(setf (car (nth 4 *knot*)) (cdr *knot*));  => (2 3 4
 ; ((2 3 4
 ;   ((2 3 4
 ;     ((2 3 4
 ;       ((2 3 4 ((2 3 4 ((2 3 4 ((2 3 4 ((2 3 4 ((2 3 4 (#))))))))))))))))))))

(setf (cdr (nth 4 *knot*)) (cddr *knot*)) ;; ridiculousness ensues...

;; *knot* is a structure that branches back on itself twice

(defun cycle-walk (count cycle &key (turn #'car))
  (loop with place = cycle
        repeat count for elem = (car place)
        unless (consp elem) do (format t "~a " elem)
          do (setf place (if (consp elem)
                             (funcall turn elem)
                             (cdr place))))) ; => CYCLE-WALK

(cycle-walk 25 *knot* :turn #'car); 1 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4  => NIL

(cycle-walk 25 *knot* :turn #'cdr); 1 2 3 4 3 4 3 4 3 4 3 4 3 4 3 4 3 4  => NIL

(let ((dir))
  (defun switch (pair)
    (setf dir (not dir))
    (if dir
        (car pair)
        (cdr pair)))) ; => SWITCH

(cycle-walk 25 *knot* :turn #'switch); 1 2 3 4 2 3 4 3 4 2 3 4 3 4 2 3 4 3 4  => NIL

Another way to construct tree structures is with quote or '. 

(quote (1 2 3)) ; => (1 2 3)

'(1 2 3) ; => (1 2 3)

(list 1 2 3) ; => (1 2 3)

;; The structures are equivalent this way as well
(equal (quote (1 2 3)) '(1 2 3)) ; => T

(equal '(1 2 3) (list 1 2 3)) ; => T

The difference between list and quote is that list means "Return the list of these arguments", while quote / ' means "Return this argument without evaluating it". 

(defparameter *test* 2) ; => *TEST*

(list 1 *test* 3) ; => (1 2 3)

'(1 *test* 3) ; => (1 *TEST* 3)

(list (+ 3 4) (+ 5 6) (+ 7 8)) ; => (7 11 15)

'((+ 3 4) (+ 5 6) (+ 7 8)) ; => ((+ 3 4) (+ 5 6) (+ 7 8))

Because quote suppresses evaluation it can be used to more easily build deeply nested structures: 

(list 1 (list 2 3) (list 4 (list (list 5) 6 7 8))) ; => (1 (2 3) (4 ((5) 6 7 8)))

'(1 (2 3) (4 ((5) 6 7 8))) ; => (1 (2 3) (4 ((5) 6 7 8)))

Take care not to use quoted data for mutation though. The structures produced may be the same, but mutating a quoted structure is undefined in the Common Lisp language spec. This makes it implementation dependent. 

(defvar *listed* (list 3 2 1)) ; => *LISTED*

(defvar *quoted* '(3 2 1)) ; => *QUOTED*

(push 4 *listed*) ; => (4 3 2 1)

*listed* ; => (4 3 2 1)

(push 4 *quoted*) ; => (4 3 2 1)

*quoted* ; => (4 3 2 1)

In this case, using sbcl, they act alike.

Extra Credit: Look-up Lists and Trees

Lisp has a couple of special types of look-up lists that have more structure than just position: Association Lists and Property Lists, alists and plists. These are key–value pairs and are generally used as data, though they can be used as code, and are the basis for all structured data such as Hash Tables, Structs, Classes, Database Tables and more.

alist's and plist's are two basic ways of representing linear-lookup key–value structures.

An alist is a list of cons cells: 

'((a . 1) (b . 2) (c . 3))
 ; => ((A . 1) (B . 2) (C . 3))

A plist is a flat list of expressions, whose every odd element is a key and every even element is a value: 

(list 'a 1 'b 2 'c 3) ; => (A 1 B 2 C 3)

Both constructs are of type list: 

(listp '((a . 1) (b . 2) (c . 3)))
 ; => T
(listp (list 'a 1 'b 2 'c 3))
 ; => T

Which can make things difficult to tell whether or not a particular construct is either a plain list, an alist or plist.

  • Plists

    With a plist as a flat list with an even number of elements and the odd elements as keys and even elements as values of the proceeding key: 

    (list 'a 1 'b 2) ; => (A 1 B 2)

(list :foo "a" :bar "b") ; => (:FOO "a" :BAR "b")

    Use the function getf on a plist and a key will try to find that key in the plist. If found, then the return value will be that keys' value: 

    (getf (list :foo "a" :bar "b") :bar) ; => "b"

(getf (list :foo "a" :bar "b") :foo) ; => "a"

    getf takes an optional argument, default, which it will return if the given key is not found in the plist. The default of default is NIL. 

    (getf (list :foo "a" :bar "b") :mumble) ; => NIL

(getf (list :foo "a" :bar "b") :mumble 'great-googly-moogly) ; => GREAT-GOOGLY-MOOGLY

    getf might generate an error, even with a default value provided, should it be attempted on an odd-length list. The error generated is a MALFORMED PROPERTY LIST.

    As with all cons cells, a plist can be heterogeneously typed: 

    (list :a 1 :b 'two :c "three") ; => (:A 1 :B TWO :C "three")

(getf (list :a 1 :b 'two :c "three") :b) ; => TWO

(getf (list :a 1 :b 'two :c "three") :c) ; => "three"

    This goes for keys as well as values. However, note that getf test its keys by pointer equality, which means that you can't really use compound structures as a key in a plist: 

    (list 1 :a 'two :b "three" :c) ; => (1 :A TWO :B "three" :C)

(getf (list 1 :a 'two :b "three" :c) 1) ; => :A

(getf (list 1 :a 'two :b "three" :c) 'two) ; => :B

(getf (list 1 :a 'two :b "three" :c) "three") ; => NIL

    Due to their nature as a flat list, one can add keys to an existing plist using cons or append: 

    (list :a 1 :b 2 :c 3)
 ; => (:A 1 :B 2 :C 3)

(let ((plist (list :a 1 :b 2 :c 3)))
  (cons :d (cons 4 plist)))
 ; => (:D 4 :A 1 :B 2 :C 3)

(let ((plist (list :a 1 :b 2 :c 3)))
  (cons :d (cons 4 plist))
  plist)
 ; => (:A 1 :B 2 :C 3)

(let ((plist (list :a 1 :b 2 :c 3)))
  (append (list :d 4 :e 5) plist))
 ; => (:D 4 :E 5 :A 1 :B 2 :C 3)

(let ((plist (list :a 1 :b 2 :c 3)))
  (append (list :d 4 :e 5) plist)
  plist)
 ; => (:A 1 :B 2 :C 3)

    It is possible to mutate a plist by using setf, as with most other values: 

    (defparameter *plist* (list :a 1 :b 'two :c "three"))
 ; => *PLIST*

(getf *plist* :b)
 ; => TWO

(setf (getf *plist* :b) 'three)
 ; => THREE

(getf *plist* :b)
 ; => THREE

*plist*
 ; => (:A 1 :B THREE :C "three")

    The key that is set in that way does not need to exist already: 

    *plist*
 ; => (:A 1 :B THREE :C "three")

(setf (getf *plist* :d) 71)
 ; => 71 (7 bits, #x47, #o107, #b1000111)

(getf *plist* :d)
 ; => 71 (7 bits, #x47, #o107, #b1000111)

    Though the order of the new keys may not be what you would expect: 

    *plist*
 ; => (:D 71 :A 1 :B THREE :C "three")

    Removing keys from a plist also involves removing the associated value/values. There is a destructive procedure, remf, that does this: 

    *plist*
 ; => (:D 71 :A 1 :B THREE :C "three")

(remf *plist* :b)
 ; => T

*plist*
 ; => (:D 71 :A 1 :C "three")
  • Alists

    An alist is a list of cons-cells. The first element of the cons-cell is taken to be the key and the rest is taken to be the value. 

    '((a . 1) (b . 2) (c . 3))
 ; => ((A . 1) (B . 2) (C . 3))

(list (cons :foo "a") (cons :bar "b"))
 ; => ((:FOO . "a") (:BAR . "b"))

    Calling assoc on a key and an alist will try to find the key in the alist. If found, the return value will be the whole located cons-cell. 

    (assoc 'b '((a . 1) (b . 2) (c . 3)))
 ; => (B . 2)

(assoc 'a '((a . 1) (b . 2) (c . 3)))
 ; => (A . 1)

    Calling assoc on malformed alist's may yield errors. 

    ;; (assoc 'c '((a . 1) (b . 2) c))
;; The value
;;   C
;; is not of type
;;   LIST
;;    [Condition of type TYPE-ERROR]

    The above error refers to the trailing c, which is not a list. assoc compares the given key with the car of each element in the given list, and c has no car.

    As with plist's, alist's may be heterogeneously typed: 

    '((a . 1) (b . "two") (c . three) (d . #(#\f #\o #\u #\r)))
 ; => ((A . 1) (B . "two") (C . THREE) (D . #(#\f #\o #\u #\r)))

(assoc 'b '((a . 1) (b . "two") (c . three) (d . #(#\f #\o #\u #\r))))
 ; => (B . "two")

(assoc 'd '((a . 1) (b . "two") (c . three) (d . #(#\f #\o #\u #\r))))
 ; => (D . #(#\f #\o #\u #\r))

    …both keys and values: 

    '((1 . a) ("two" . b) (three . c) (#(#\f #\o #\u #\r) . d))
 ; => ((1 . A) ("two" . B) (THREE . C) (#(#\f #\o #\u #\r) . D))

(assoc 'three '((1 . a) ("two" . b) (three . c) (#(#\f #\o #\u #\r) . d)))
 ; => (THREE . C)

(assoc 1 '((1 . a) ("two" . b) (three . c) (#(#\f #\o #\u #\r) . d)))
 ; => (1 . A)

    Unlike with plist's, an alist can use compound keys. This is because assoc accepts a test (or test-not) argument, to specify the test to run to determine key equity. 

    (assoc "two" '((1 . a) ("two" . b) (three . c) (#(#\f #\o #\u #\r) . d)) :test #'equal)
 ; => ("two" . B)

(assoc #(#\f #\o #\u #\r) '((1 . a) ("two" . b) (three . c) (#(#\f #\o #\u #\r) . d)) :test #'equalp)
 ; => (#(#\f #\o #\u #\r) . D)

    alist's are just cons-cells, so one can use cons to insert items: 

    (let ((alist '((a . 1) (b . "two") (c . three))))
  (cons (cons 'd 'four) alist))
 ; => ((D . FOUR) (A . 1) (B . "two") (C . THREE))

(let ((alist '((a . 1) (b . "two") (c . three))))
  (cons (cons 'd 'four) alist)
  alist)
 ; => ((A . 1) (B . "two") (C . THREE))

    We can also use the standard remove or remove-if functions on an alist: 

    (remove 'b '((a . 1) (b . "two") (c . three)) :key #'car)
 ; => ((A . 1) (C . THREE))

(remove-if (lambda (p) (eq 'c (car p))) '((a . 1) (b . "two") (c . three)))
 ; => ((A . 1) (B . "two"))

(remove-if
 (lambda (pair)
   (numberp (car pair)))
 '((a . 1) (1 . a) (b . "two") (2 . b) (c . three)))
 ; => ((A . 1) (B . "two") (C . THREE))

    alist's can be mutated as with most other objects: 

    (defparameter *alist* '((a . 1) (b . 2) (c . 3)))
 ; => *ALIST*

(setf (cdr (assoc 'b *alist*)) 42)
 ; => 42 (6 bits, #x2A, #o52, #b101010)

*alist*
 ; => ((A . 1) (B . 42) (C . 3))

    Unlike with a plist, however, the key that is being mutated in an alist has to exist, otherwise an error will be thrown.

    To add a key to an alist is an explicit operation: 

    (push '(foo . 43) *alist*)
 ; => ((FOO . 43) (A . 1) (B . 42) (C . 3))

*alist*
 ; => ((FOO . 43) (A . 1) (B . 42) (C . 3))

    To remove a key from an alist use setf and other previously discussed approaches: 

    *alist*
 ; => ((FOO . 43) (A . 1) (B . 42) (C . 3))

(setf *alist* (remove 'b *alist* :key #'car))
 ; => ((FOO . 43) (A . 1) (C . 3))

*alist*
 ; => ((FOO . 43) (A . 1) (C . 3))
  • Efficiency and Alternatives to ALISTs and PLISTs

    Both alist's and plist's exhibit linear lookup issues, requiring traversal of the entire list to find any given key. 

    (trace eq)
 ; => (EQ)

(assoc 'b '((a . 1)(b . 2)(c . 3)(d . 4)) :test #'eq)
;; 0: (EQ B A)
;;   0: EQ returned NIL
;;   0: (EQ B B)
;;   0: EQ returned T
 ; => (B . 2)

(assoc 'd '((a . 1)(b . 2)(c . 3)(d . 4)) :test #'eq)
;;   0: (EQ D A)
;;   0: EQ returned NIL
;;   0: (EQ D B)
;;   0: EQ returned NIL
;;   0: (EQ D C)
;;   0: EQ returned NIL
;;   0: (EQ D D)
;;   0: EQ returned T
 ; => (D . 4)
  • Trees

    By picking keys that can be sorted instead of comparing for equality one can use a tree structure. It does take a bit more work though. A tree is typically recursively defined as either:

    1. A value followed by two trees (left branch and right branch)

    2.The terminal value (which marks the end of the tree).

    Such as: 

    '((1 . a) nil nil)
 ; => ((1 . A) NIL NIL)

'((2 . b) ((1 . a) nil nil) ((3 . c) nil ((4 . d) nil nil)))
 ; => ((2 . B) ((1 . A) NIL NIL) ((3 . C) NIL ((4 . D) NIL NIL)))

    Here, the "value" is a key-value pair in the style of an alist and the terminal value is nil. The keys are also sorted, everything in the left branch has a lesser key than the value of that tree, while everything in the right branch has a greater key.

    Here is a lookup function: 

    (defun lookup (key sorted-tree)
  (let ((k (caar sorted-tree)))
    (cond ((null sorted-tree) nil)
          ((> k key)
           (lookup key (second sorted-tree)))
          ((< k key)
           (lookup key (third sorted-tree)))
          (t
           (first sorted-tree)))))
 ; => LOOKUP

    (trace lookup)
 ; => (LOOKUP)

(lookup 4 '((2 . b) ((1 . a) nil nil) ((3 .c) nil ((4 . d) nil nil))))
;;  0: (LOOKUP 4 ((2 . B) ((1 . A) NIL NIL) ((3 .C) NIL ((4 . D) NIL NIL))))
;;    1: (LOOKUP 4 ((3 .C) NIL ((4 . D) NIL NIL)))
;;       2: (LOOKUP 4 ((4 . D) NIL NIL))
;;       2: LOOKUP returned (4 . D)
;;     1: LOOKUP returned (4 . D)
;;   0: LOOKUP returned (4 . D)
 ; => (4 . D)

    Let's define a functional interface to trees: 

    (defun tree (val left right)
  (list val left right))
 ; => TREE

(defun tree-value (tree)
  (first tree))
 ; => TREE-VALUE

(defun tree-left (tree)
  (second tree))
 ; => TREE-LEFT

(defun tree-right (tree)
  (third tree))
 ; => TREE-RIGHT

(defun lookup (key tree)
  (if (null tree)
      nil
      (let ((k (car (tree-value tree))))
        (cond ((> k key) (lookup key (tree-left tree)))
              ((< k key) (lookup key (tree-right tree)))
              (t (tree-value tree))))))
 ; => LOOKUP

    A naive insert function: 

    (defun insert (key value tree)
  (if (null tree)
      (tree (cons key value) nil nil)
      (let ((k (car (tree-value tree))))
        (cond ((> k key)
               (tree (tree-value tree)
                     (insert key value (tree-left tree))
                     (tree-right tree)))
              ((< k key)
               (tree (tree-value tree)
                     (tree-left tree)
                     (insert key value (tree-right tree))))
              (t tree)))))
 ; => INSERT

    An example run: 

    (defparameter *lst*
  '((5 . e)(3 . c)(4 . d)(2 . b)(1 . a)(7 . g)(6 . f)(8 . h)(9 . i)(10 . j)))
 ; => *LST*

(reduce
 (lambda (memo pair)
   (insert (car pair) (cdr pair) memo))
 *lst* :initial-value nil)
 ; => ((5 . E) ((3 . C) ((2 . B) ((1 . A) NIL NIL) NIL) ((4 . D) NIL NIL))
 ; ((7 . G) ((6 . F) NIL NIL) ((8 . H) NIL ((9 . I) NIL ((10 . J) NIL NIL)))))

(defparameter *tree*
  (reduce
   (lambda (memo pair)
     (insert (car pair) (cdr pair) memo))
   *lst* :initial-value nil))
 ; => *TREE*

Resource

Second Draft (in-progress) ยท Learn Lisp The Hard Way

Date: 2025-11-20 Thu 00:00

Emacs 29.3 (Org mode 9.7.34)