Common Lisp Friday

Introduction

by Peter Hillerström / @peterhil

Lisp History

Lisp was invented by John McCarthy in 1958 while he was at the Massachusetts Institute of Technology (MIT).

McCarthy published it’s design in a paper entitled “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” (HTML|PDF) in 1960, in which he showed that with a few simple operators and a notation for functions, one can build a Turing-complete language for algorithms.

Family of languages

Lisp (historically, LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized Polish prefix notation.

Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today.

Lisp has changed a great deal since its early days, and a number of dialects have existed over its history.

Lisp Dialects

Today, the most widely known general-purpose Lisp dialects are Common Lisp and Scheme.

Timeline of Lisp dialects
1955 1960 1965 1970 1975 1980 1985 1986 1990 1995 2000 2005 2012
Lisp 1.5 Lisp 1.5
Maclisp Maclisp
ZetaLisp ZetaLisp
NIL NIL
Interlisp Interlisp
Common Lisp Common Lisp
Scheme Scheme
ISLISP ISLISP

The parenthesis

(S-expressions)

Xkcd – Lisp cycles

The syntax

(function parameter second-parameter third-parameter)
CL-USER> (+ 3 7 5)
15
CL-USER> (first (list "a" "b"))
"a"

Quoting to prevent evaluation (equivalent ways):

(quote (a b c))
'(a b c)

The vocabulary

Link | The standard in HTML

What’s in the name?

Lisp = List processing language

Atom
(list t nil 0 0.5 1.0d0 #C(0 1) 'symbol #'function :keyword)
Cons
CL-USER> (cons 1 2)
(1 . 2)
Linked list
(list 42 69 613)
(cons 42 (cons 69 (cons 613 nil)))
In the original LISP there were two fundamental data types: atoms and lists

Common Lisp

Language features

Language features

Common Lisp is a general-purpose, dynamic multi-paradigm programming language.

Common Lisp includes CLOS, an object system that supports multimethods and method combinations.

Facilitates evolutionary and incremental software development, with iterative compilation* into efficient run-time programs.

*) With optional type annotation and casting, which can be added later when profiling and optimising. The compiler can be told on a per-module or per-function basis which type safety level is wanted, using optimize declarations.

Extensible through standard features such as Lisp macros` and reader macros#.

`) Compile-time code rearrangement accomplished by the program itself.
#) Extension of syntax to give special meaning to characters reserved for this purpose.

Functional programming

Defining functions

Function definition:

(defun name (parameter*)
  "Optional documentation string."
  body-form*)
Name
can be any symbol.
Parameter list
defines the variables that will be used to hold the arguments passed to the function when it’s called. Different flavors of parameters handle required, optional, multiple, and keyword arguments.
Documentation string
will be associated with the name of the function and can later be obtained using the DOCUMENTATION function.
Body
of a DEFUN consists of any number of Lisp expressions. They will be evaluated in order when the function is called and the value of the last expression is returned as the value of the function. The RETURN-FROM special operator can be used to return immediately from anywhere in a function.

First-class functions

First-class functions are functions that take other functions as arguments or return functions.

Referring functions

To be able to pass functions around, you need to refer to a function value of a symbol using function:

CL-USER> (function >)
#<FUNCTION >>
CL-USER> #'>
#<FUNCTION >>
The #' notation is a Common Lisp shortcut way of the above and more commonly used.

Sort a list using the > and < function:

CL-USER> (sort (list 5 2 6 3 1 4) #'>)
(6 5 4 3 2 1)
CL-USER> (sort (list 5 2 6 3 1 4) #'<)
(1 2 3 4 5 6)

First-class functions

First class functions make it possible to
describe very general operations.

Sort a list according to the first element of each sub-list:

CL-USER> (sort (list '(9 "A") '(3 "B") '(4 "C")) #'< :key #'first)
((3 "B") (4 "C") (9 "A"))

Sort by the second element of each sub-list:

CL-USER> (sort (list '(9 "A") '(3 "B") '(4 "C")) #'string< :key #'second)
((9 "A") (3 "B") (4 "C"))
The function #'second is an alias for #'cadr, which
in turn is equivalent to (car (cdr (list FOO BAR))), in this case BAR.

First-class functions

Another example

Sort trie branches with a predicate.

(defun sort-trie-branch (trie predicate &key (key #'key) (stable nil))
  "Sort a trie node’s branches with a predicate function."
  (let ((branches (copy-list (branches trie)))
        (sort (if stable #'stable-sort #'sort)))
    (setf (branches trie)
          (funcall sort branches predicate :key key))
    trie))
Using this function while traversing the trie, the whole tree can be sorted. But this is a bad example for functional programming. Can you tell why? It modifies the trie in-place, which is unacceptable in functional programming.
It should instead generate a new trie instance by copying it.

Functional programming

Anonymous functions

Defined by lambda expressions:

(lambda (parameters) body)
One way to think of LAMBDA expressions is as a special kind of function name where the name itself directly describes what the function does. This explains why you can use a LAMBDA expression in the place of a function name with #': 
(funcall #'(lambda (x y) (+ x y)) 2 3) ⇒ 5
You can even use a LAMBDA expression as the "name" of a function in a function call expression. If you wanted, you could write the previous FUNCALL expression more concisely: 
((lambda (x y) (+ x y)) 2 3) ⇒ 5
An important use of LAMBDA expressions is in making closures, functions that capture part of the environment where they're created.

Functional programming:
Higher-order functions and sequences

Map and reduce

MAP

(map 'list #'* '(1 2 3) '(4 5 6)) ⇒ (4 10 18)

REDUCE

(reduce #'* '(1 2 3 4 5)) ⇒ 120

MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST and MAPCON

mapc function &rest lists+ ⇒ list-1
mapcar function &rest lists+ ⇒ result-list
mapcan function &rest lists+ ⇒ concatenated-results
mapl function &rest lists+ ⇒ list-1
maplist function &rest lists+ ⇒ result-list
mapcon function &rest lists+ ⇒ concatenated-results

Functional programming:
Higher-order functions and sequences

Folds

Different kind of folds using reduce:
Left fold without initial value 
(reduce func list)
CL-USER> (reduce #'pair (range 1 6))
"((((1 + 2) + 3) + 4) + 5)"
Right fold without initial value 
(reduce func list :from-end t)
CL-USER> (reduce #'pair (range 1 6) :from-end t)
"(1 + (2 + (3 + (4 + 5))))"
Left fold 
(reduce func list :initial-value initval)
CL-USER> (reduce #'pair (range 1 6) :initial-value 0)
"(((((0 + 1) + 2) + 3) + 4) + 5)"
Right fold 
(reduce func list :from-end t :initial-value initval)
CL-USER> (reduce #'pair (range 1 6) :initial-value 0 :from-end t)
"(1 + (2 + (3 + (4 + (5 + 0)))))"
  
(defun range (start end) (loop for i from start below end collect i))
(defun pair (x y &optional (op #\+)) (format nil "(~A ~A ~A)" x op y))

Functional programming:
Higher-order functions and sequences

Filter

Filter with REMOVE-IF: 
(remove-if inverted-pred list)
(remove-if (complement pred) list)
(remove-if-not pred list)
Note! The function remove-if-not has been deprecated in favor of the equivalent remove-if where the predicate is complemented.

Functional programming:
Higher-order functions and sequences

Zip

Zip and Unzip can be made using Mapcar:

CL-USER> (defparameter nums '(1 2 3))
CL-USER> (defparameter tens '(10 20 30))
CL-USER> (defparameter firstname "Alice")

;; Zips
CL-USER> (mapcar #'list nums tens)
((1 10) (2 20) (3 30))

CL-USER> (mapcar #'list nums tens (coerce firstname 'list))
((1 10 #\A) (2 20 #\l) (3 30 #\i)) — truncates on shortest list

;; Unzips
CL-USER> (apply #'mapcar #'list (mapcar #'list nums tens (coerce firstname 'list)))
((1 2 3) (10 20 30) (#\A #\l #\i))

Object oriented features

Common Lisp
Object System

Instances are created by a function
Automatic and custom accessor functions
Multiple inheritance
Inheritance of slot options
Slots can be modified programmatically
Generic functions and methods (multimethods)
Method combination
Meta-programming with Meta object Protocol (MOP)
For a good introduction about these features, read
A brief guide to CLOS by Jeff Dalton.

Common Lisp Object System

Instances

defclass
Define a class
(defclass person ()
  ((name :accessor person-name
         :initform 'bill
         :initarg :name)
   (age :accessor person-age
        :initform 10
        :initarg :age)))

Common Lisp Object System

Instances

Create an instance with function
make-instance
(make-instance 'person :name 'jill :age 100)
It’s often a good idea to define your own constructor functions, rather than call make-instance directly, because you can hide implementation details and don't have to use keyword parameters for everything: 
(defun make-person ((name 'bill) (age 10))
  (make-instance 'person :name name :age age))
(make-person 'jill 100)
Instance creation can be customised with
initialize-instance

Macros

The programmable
programming language

The definition of DEFMACRO:

(defmacro name (parameter*)
  "Optional documentation string."
  body-form*)
...is very similar to that of DEFUN.
The big difference is the backquote syntax, as seen in the following macro example: 
(defmacro do-primes ((var start end) &body body)
  `(do ((,var (next-prime ,start) (next-prime (1+ ,var))))
       ((> ,var ,end))
     ,@body))
A useful way to think about the backquote syntax is as a particularly concise way of writing code that generates lists. For instance, `(,a b) might be read as (list a 'b)

Read Macros Defining Your Own for more information.

Useful Resources

The Common Lisp HyperSpec Cliki – The Common Lisp Wiki

The book “Practical Common Lisp” by Peter Siebel

Take this REPL,
my brother and may
it serve you well!

Instructions for the hackathon

There are many implementations of the ANSI Common Lisp standard, two implementations that you can use in the hackathon are SBCL and Clozure Common Lisp.

If you feel confident using basic Emacs editing command, I recommend using SBCL with Emacs and SLIME. Otherwise I recommend installing Clozure CL.

Also install Quicklisp if using either Common Lisp implementation.

Steps for installing SBCL with SLIME and Emacs

SBCL is acronym for Steel Bank Common Lisp.
SLIME is acronym for Superior Lisp Interaction Mode for Emacs.

1) Install SBCL

➜ sudo port install sbcl

2a) Install SLIME and Emacs using Macports

There are two alternative methods of installing SLIME.

Install SLIME with MacPorts or apt-get
(will also install emacs and Emacs.app)

➜ sudo port install slime

Copy dot.emacs into ~/.emacs to have the settings for SLIME as described by the port install

2b) Install SLIME and Emacs using Quicklisp

There are two alternative methods of installing SLIME.

Install Quicklisp (see instructions)

Type within Lisp REPL:

* (ql:quickload "quicklisp-slime-helper")

Add this to your ~/.emacs:

(load (expand-file-name "~/quicklisp/slime-helper.el"))
;; Replace "sbcl" with the path to your implementation
(setq inferior-lisp-program "sbcl")

3) Optionally install Aquamacs

4) Start SLIME with SBCL

➜ open -a /Applications/MacPorts/Emacs.app
OR 
➜ open -a /Applications/Aquamacs.app

Type in Emacs or Aquamacs:

meta-x slime
(meta key is usually mapped to option, tapping ESC before the key also works)

Steps for installing Clozure Common Lisp (CCL)

Takes ~30 min. with hassling around and
asking questions and/or googling.

1) Check out Clozure Common Lisp from the Subversion [~2-3 min]

➜ svn co http://svn.clozure.com/publicsvn/openmcl/release/1.8/darwinx86/ccl

2) Build it

[~5 min] 
➜ cd ccl
➜ ./dx86cl64 --no-init
Welcome to Clozure Common Lisp Version 1.8-r15286M  (DarwinX8664)!
? (rebuild-ccl :full t)
; lots of output
? (quit)

3) Install the command line start script and set the ccl directory env variable

[~1 min] 
➜ sudo cp scripts/ccl64 /usr/local/bin
➜ export CCL_DEFAULT_DIRECTORY="`pwd`"  # put this into .zshrc or .bashrc
➜ echo $CCL_DEFAULT_DIRECTORY         
/Users/peterhil/Programming/Lisp/ccl
➜ rehash  # if using zsh

4) Build the Cocoa IDE

[~ 1 min] 
➜ ccl64
Welcome to Clozure Common Lisp Version 1.8-r15485M  (DarwinX8664)!
? (require :cocoa-application)
; lots of output
➜ open Clozure\ CL64.app/

5) Optional – start CCL inside Emacs or Aquamacs using SLIME:

Install SLIME as described in SBCL instructions above.

In Emacs or Aquamacs type: 
meta-- meta-x slime RETURN
ccl64
(meta key is usually mapped to option, tapping ESC before the key also works)

Steps for installing Quicklisp

➜ cd ~
➜ curl -O http://beta.quicklisp.org/quicklisp.lisp
➜ sbcl --load quicklisp.lisp  # replace sbcl with ccl64 if using Clozure CL
* (quicklisp-quickstart:install)
; Try to install some package (CL-PPCRE is a regexp library written by Edi Weitz):
* (ql:quickload "cl-ppcre")
; Search for available libraries:
* (ql:system-apropos "vecto")
; Add Quicklisp to your Lisp's init file:
* (ql:add-to-init-file)
; Done
* (quit)