cs161 Lisp Primer and Links

LISP

Many thanks to Adam Pingel for access to previous Lisp notes.

Getting started

The version of LISP that we will be using in class is gcl, which is available on the SEAS machines.

Here's a sample gcl session:

{exposition} 2> gcl
GCL (GNU Common Lisp)  Version(2.3) Mon Mar 13 14:49:55 PST 2000
Licensed under GNU Library General Public License
Contains Enhancements by W. Schelter

>(+ 1 2) 

3

>

Editors/Interpreters

LispWorks from Xanalysis

GCL for Windows

Emacs FAQ

Quick Reference

The following is a quick guide to lisp, even shorter than the above "primer." It is recommended that if you want to fully understand lisp you go through one of the guides, but this section may be useful for a quick check for a certain operator. Let me know if there is anything else you want added to this section and I will do my best to put it up here.

Prefix notation and math operators

LISP expressions are written using prefix notation. Here are some example mathematical expressions using +, -, *, and /. Also note that these expressions can be nested.

>(- 2 1)

1

>(+ 1 0)

1

>(* 2 8)

16

>(/ 4 2)

2

>(+ 3 (- 10 6))    Nested expression

7

>(* 4 2.0)         Notice that we can force the result type to real

8.0

Non-numeric atoms

In addition to numbers, we can also refer to non-numeric literals by prepending the symbol with a single quote character. This tells the LISP interpreter not to evaluate the symbol. Note that these are case-insensitive.

>'a

A

>'C

C

>'LONG_symbol-foo  

LONG_SYMBOL-FOO

Lists

The list is the fundamental building block of LISP expressions. As with the symbols in the previous point, lists must be prepended with a single quote character to prevent the interpreter from evaluating them.

>'(1 2 3)

(1 2 3)

>'(+ 1 1)

(+ 1 1)

>'((a b) (c d))

((A B) (C D))

Nil, the empty list

There is a special symbol called NIL that is a synonym for the empty list. As we shall see in the next point, it is also interpreted as the Boolean false.

>nil

NIL

>'()

NIL

Boolean expressions

LISP uses NIL to mean Boolean false. Any other value is considered to be true, though LISP uses a particular value, T, to represent true. The functions and, or, and not have the standard meaning.

>(not nil)

T

>(or t)

T

>(or t nil)

T

>(and t nil)

NIL

>(not (and t nil))

T

Equality

= is used to compare numerical values. equal is used to compare complex expressions. gcl's versions of these operators can take more than two arguments. This is not true of all lisps.

>(= 1 1)

T

>(= 3 4)

NIL

>(equal '(1 3) '(1 3))

T

>(equal 'a 'a)

T

>(equal 'a 'b)

NIL

>(equal 'a 'a 'a)

T

>(= 1 1 1)

T

if and cond control structures

if requires three arguments: 1) the condition, 2) the true clause, and 3) the false clause.

cond takes a variable number of arguments. Each argument has two parts, a condition and the action to take if that condition is true. Evaluation of a cond expression iterates through argument until an argument with a true condition is found. When writing a cond expression, make sure that at least one of the conditions will be true for any argument. A common way to ensure this is to end the list of cond arguments with an expression whose condition is t. This is illustrated below.

>(if (= 1 0) 'a 'b)

B

>(cond ((= 1 0) 'x) ((= 2 3) 'y) (t 'z))

Z

Checking for the empty list: the "null" predicate

There is a built-in predicate for checking whether a list is nil called null.

>(null nil)

T

>(null 'a)

NIL

>(null '(c d))

NIL

atom and listp predicates

Often times when writing a recursive function (as well as many other situations) it is useful to know whether a variable is a list or not. The predicates listp and atom do this.

>(listp '(1 2 3))

T
>(listp 'a)

NIL
>(atom '(1 2 3))

NIL
>(atom 'a)

T

Taking lists apart: car and cdr

To refer to sub-parts of a list, use car or cdr. car returns the element at the head of the list. cdr returns the list that is everything except the head of the list. first is a synonym for car, and rest is a synonym for cdr.

>(car '(a b))

A

>(cdr '(a b))

(B)

>(car '((c d) (e f)))

(C D)

>(cdr '((c d) (e f)))

((E F))

>(car nil)

NIL

>(cdr nil)

NIL

>(rest '(a b))

(B)
>(first '(a b))

A

Constructing lists: cons, list, and append

The three ways of creating lists are cons, list, and append. Their behaviors are best illustrated with examples.

>(cons 'a '(b c))

(A B C)

>(list 'a 'b 'c)

(A B C)

>(append '(a) '(b c))

(A B C)

Variables, scope, and let

Variables are created with let statements. The variables created are scoped to the let statement, and can be masked if an enclosed let expression redefines the variable.

>(let ((a 4)) (* a 2))

8

>(let ((a 3) (b 9)) (/ b a))

3

>(let ((a 3)) (let ((a 4)) (* a a)))

16

Defining functions: defun

New functions are defined with the defun operator. The variables are listed in parenthesis after the function name.

>(defun double (x)
    (* 2 x)
)

DOUBLE

>(double 10)

20

>(defun listdouble (l)
    (append l l)
)

LISTDOUBLE

>(listdouble '(a b c))

(A B C A B C)

Example of recursion on numbers: fibonacci

>(defun fibonacci (x)
   (cond
      ((<= x 1) 1)
      (t        (+ (fibonacci (- x 1)) (fibonacci (- x 2))))
   )
 )

FIBONACCI

>(fibonacci 5)

8

Example of recursion on lists: reverse

>(defun reverse (l)
   (cond
     ((null l) nil)
     (t        (append (reverse (cdr l)) (list (car l))))
   )
 )

Warning: REVERSE is being redefined.
REVERSE

>(reverse '(a b c))

(C B A)

Example of variable binding

>(defun doubleexpr (s)
   (list '* 2 s)
 )

DOUBLEEXPR

>(doubleexpr 5)

(* 2 5)

>(doubleexpr 'a)

(* 2 A)

comments

The semicolon (;) is LISP's comment character.

>;this is a comment
(+ 1 2)

3

load

From an interactive gcl session, you can do (load "hw1.lsp") to interpret the specified lisp file. However, we will be excuting your code with the following command line:

gcl -eval '(load "hw1.lsp" )'

io

To get input from a user, you can print a prompt to *query-io* using the format operator, and then do a read-line on *query-io*. Let's demonstrate this by putting the following code in a file called "askquestion.lsp":

(format *query-io* "Type something here: ")
(let ((response (read-line *query-io*)))
 (format *query-io* "Your response was ~A~%" response)
)

If we run the code from the shell like so, we will see something like this. The bold characters are the ones I typed.

{landfair} 36> gcl -eval '(load "askquestion.lsp" )'
GCL (GNU Common Lisp)  Version(2.3) Mon Mar 13 14:49:55 PST 2000
Licensed under GNU Library General Public License
Contains Enhancements by W. Schelter
Type something here: foo foo foo
Your response was foo foo foo

The format operator takes format strings that may remind you of C's printf. One useful and non-obvious format string is demonstrated below:


>(format *query-io* "These are the contents of the list: ~{ ~S~}~%" '(A B C))
These are the contents of the list:  A B C
NIL

There are a couple of handy predicates that get yes/no input from the user:


>(y-or-n-p "is this useful?")

is this useful?  (Y or N) Y

T

>(yes-or-no-p "is this useful?")

is this useful?  (Yes or No) no

NIL

symbols vs. strings vs. characters

The string operator is used to convert a symbol into a string. To convert from a string into a symbol, see the discussion here. Also check out the string-equal operator (demonstrated below).

>(string 'foo)

"FOO"

>(string-equal "yes" "Yes it is" :start1 0 :end1 2 :start2 0 :end2 2)

T

Rob Adams found these goodies on the CL Cookbook (see link above):


(defun explode (string) (loop for char across string collect char))
(defun compress (string) (concatenate 'string string))

>>(explode "this is a test")

(#\t #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t)
>>(compress (explode "this is a test"))

"this is a test"

Unfortunately, these don't work on the ancient version of gcl installed on the SEAS machines. Rob supplied a version of "explode" that is compatable with the version of gcl we will be using:

(defun explode-iter (string current)
  (if (= current (array-total-size string))
      nil
      (cons (aref string current) (explode-iter string (+ current 1)))
  )
)
(defun explode (string)
  (explode-iter string 0)
)

eval

eval does the obvious thing to a lisp expression. This is possible because lisp expressiona are really just lists like every other complex data structure.

>(list '+ 3 4)

(+ 3 4)

>(eval (list '+ 3 4))

7

lambda, closures, apply, funcall, and mapcar

I'll talk about these more in discussion section. One thing to note here is that the word "thunk" is often used as a synonym for "closure".

A closure is defined as a double whose two elements are a pointer to code and a pointer to an environment. In the adder example below, the reason we need the "environment pointer" is that we need a way to remember what n was bound to at the time that (adder 3) was created.

This particular "adder" example comes from the CL Cookbook.

>(defun adder (n)
    (function (lambda (x) (+ x n)))
)

ADDER

>(adder 3)

(LAMBDA-CLOSURE ((N 3)) () ((ADDER BLOCK #<@001C2F40>)) (X) (+ X N))

>(apply (adder 3) '(4))

7

>(funcall (adder 3) 4)

7

>(mapcar (adder 3) '(1 2 3 4))

(4 5 6 7)

Given these definitions, we can define our own mapcar by recursively applying funcall.


>(defun ourmapcar (closure args)
    (cond
       ((null args) nil)
       (t           (cons (funcall closure (car args)) (ourmapcar closure (cdr args))))
    )
)

OURMAPCAR
>(ourmapcar (adder 3) '(1 2 3 4))

(4 5 6 7)

Finally, note the special #' symbol that can replace (function ...). The adder example above could be rewritten as:

>(defun adder (n)
     #'(lambda (x) (+ x n))
)

ADDER
>(adder 3)        

(LAMBDA-CLOSURE ((N 3)) () ((ADDER BLOCK #<@001C2ED8>)) (X) (+ X N))

>(funcall (adder 3) 4)

7

There are two slightly different ways of using mapcar. One is by passing it a lambda block, which is created by simply prepending the #' in front of the function name. The other is to pass it a closure:

>(defun increment (i)
  (+ i 1)
)

INCREMENT

>#'increment

(LAMBDA-BLOCK INCREMENT (I) (+ I 1))

>(mapcar #'increment '(1 2 3))

(2 3 4)

>#'(lambda (x) (increment x))

(LAMBDA-CLOSURE () () () (X) (INCREMENT X))

>(mapcar #'(lambda (x) (increment x)) '(1 2 3))

(2 3 4)

compose

Let's take a look at a "higher-order" function, which means that it takes functions as arguments. The compose function is the same as in mathematics. f(g(x)) = compose(f,g)(x)

>(defun increment (i)
  (+ i 1)
)

INCREMENT
>(defun square (z)
  (* z z)
)

SQUARE
>(defun compose (f g)
   #'(lambda (x) (funcall f (funcall g x)))
)

COMPOSE
>(funcall (compose #'increment #'square) 3)

10

curry and uncurry


>(defun printthree (arg1 arg2 arg3)
   (format *query-io* "arg1 = ~A, arg2 = ~A, arg3 = ~A~%" arg1 arg2 arg3)
)

PRINTTHREE

>(printthree 3 4 4) 
arg1 = 3, arg2 = 4, arg3 = 4
NIL

> (defun curry (function &rest args)
    (function (lambda (&rest more-args)
      (apply function (append args more-args)))))

CURRY

>(curry #'printthree 'a)

(LAMBDA-CLOSURE
    ((ARGS (A))
     #'(LAMBDA-BLOCK PRINTTHREE (ARG1 ARG2 ARG3)
         (FORMAT *QUERY-IO* "arg1 = ~A, arg2 = ~A, arg3 = ~A~%" ARG1
                 ARG2 ARG3)))
    () ((CURRY BLOCK #<@001C2F48>)) (&REST MORE-ARGS)
  (APPLY FUNCTION (APPEND ARGS MORE-ARGS)))

>(apply (curry #'printthree 'a) '(b c))
arg1 = A, arg2 = B, arg3 = C
NIL

>(curry #'printthree 'a 'b)

(LAMBDA-CLOSURE
    ((ARGS (A B))
     #'(LAMBDA-BLOCK PRINTTHREE (ARG1 ARG2 ARG3)
         (FORMAT *QUERY-IO* "arg1 = ~A, arg2 = ~A, arg3 = ~A~%" ARG1
                 ARG2 ARG3)))
    () ((CURRY BLOCK #<@001C2F30>)) (&REST MORE-ARGS)
  (APPLY FUNCTION (APPEND ARGS MORE-ARGS)))

>(apply (curry #'printthree 'a 'b) '(c))
arg1 = A, arg2 = B, arg3 = C
NIL

>(defun uncurry (f)
    #'(lambda (x y)  (funcall (funcall f x) y))
)

>(defun uncurry (f)
    #'(lambda (x y)  (funcall (funcall f x) y))
)

UNCURRY

>(uncurry (curry #'+ 1))

(LAMBDA-CLOSURE
    ((F (LAMBDA-CLOSURE ((ARGS (1)) #'#) ()
            ((CURRY BLOCK #<@001C2E90>)) (&REST MORE-ARGS)
          (APPLY FUNCTION (APPEND ARGS MORE-ARGS)))))
    () ((UNCURRY BLOCK #<@001C2E88>)) (X Y)
  (FUNCALL (FUNCALL F X) Y))