COMMON LISP

AN INTRODUCTION

© Copyright S.Lynch (1994, 1997, 2001). All rights reserved.
This document may be copied & distributed free of charge for educational purposes only.



Contents



introduction



the basics

What follows is some sample dialog with the Common Lisp (CL) system, the == at the start of each line is the CL prompt. The ; introduces a comment, comments start with a ; character and end at the end of the line.

CL evaluates expressions as soon as they are complete and prints the value. for example '1' is an expression with a value of 1


==
== 1
1
== 'banana   ; this is an expression with a value 'banana'
BANANA       ; note that CL does everything in uppercase
==

the ' character tells CL to treat what follows as a literal rather than something like a variable name. Individual data items (like 1 & 'banana) are called atoms. The central data structure in CL is the list. A list is anything between '(' & ')'.


==
== '(the cat sat on the mat)	; this is a list of 6 words
(THE CAT SAT ON THE MAT)	; note ' stops CL trying to evaluate the list
==

now a list whose 2nd element is a list


==
== '(the (cat sat) on the mat)
(THE (CAT SAT) ON THE MAT)
== 

a list can hold different types of items


== 
== '(Liverpool 1 Middlesbrough 5)
(LIVERPOOL 1 MIDDLESBROUGH 5)
== 

the empty list is a special list, sometimes called nil


== 
== ()
NIL
== 
== nil
NIL
== 



CL statements are lists

In general (but not absolutely always) CL does one of two things with a list.
  1. 1: if it has a ' character in front of it it treats it as a list of words etc
  2. 2: without the ' character CL assumes the list is a function call, the layout for this type of list is a function followed by its arguments ie: ( function arg1 arg2 ... )
    In this case CL first evaluates the args, then calls the function.
eg: to add 3 & 5


== 
== (+ 3 5)
8

CL has all the normal arithmetic operators (some like + & - can take any number of arguments)


== 
== (- 10 2 3)
5
== 

more complex arithmetic expressions are expressed by nesting Fn. calls


== 
== (+ 1 (- 5 3) )
3
== 



CL Fn.s to manipulate lists

much of the power of CL comes from its ability to manipulate lists CAR is a Fn. that returns the head of a list


==
== (car '(a b c))
A
== 

CDR is a Fn. that returns a list with its head removed


== 
== (cdr '(a b c))
(B C)
== 
== (car '((a b)c) )
(A B)
== 
== (car (car '((a b)c) ) )
A
== 
== (cdr (cdr '(a b c) ) )
(C)
== 
== (cdr (cdr '(a(b c)) ) )
NIL
== 

CONS is a Fn. that puts an item on to the front of a list


== 
== (cons 'a '(b c) )	; note ' before a
(A B C)
== 
== (cons '(a) '(b c) )
((A) B C)
== 
== (cons '(a b) '(c d) )
((A B) C D)
== 
== (cons 'a nil)
(A)
==

LIST is a fn that takes any number of args and returns the value of those args in a list


== 
== (list 'a 'b 'c)
(A B C)
== 
== (list (car '(a b c))
==       (car '(d e f))
==       (cdr '(the cat sat) )
== )
(A D (CAT SAT))
==



defining functions

DEFUN is used to define functions, it has the following form:
	(DEFUN    ( ...list of args... )
		
	)
an example which defines a Fn. called elem-two that returns the 2nd element of a list. Note that '-' can be used as a character in Fn. names.


== 
== (defun elem-two ( alist )	; Fn. called elem-two takes 1 arg called alist
==      (car (cdr alist) )
== )
ELEM-TWO
== 
== (elem-two '(a b c) )
B
== (elem-two '(a (b(c)) d) )
(B (C))
== 
== (elem-two (elem-two '(a (b(c)) d) ))
(C)
== 

DEFUN is an exception to the general rule that a Fn's args are evaluated before the Fn is applied. DEFUN takes as its args: a name, an arg list and some expressions that define what the Fn is to do. These are not evaluated (in the conventional sense) when DEFUN is called.
Fn.s can be defined to take any number of args:


==
== (defun double-cons (item1 item2 lis)
==      (cons item1 (cons item2 lis))
== )
DOUBLE-CONS
==
== (double-cons 'the 'cat '(ate the budgie))
(THE CAT ATE THE BUDGIE)
==
==



conditional statements

IF is a Fn. that takes the following form
( IF     test     then-part     else-part)


==
== (if ( > 3 5 )		; this is the test part
==      3		; the value to return if the test is true (ie: not nil!)
==      5		; value to return if test is false (ie: test returns nil)
== )
5
== 
== (defun bigger ( a b )	; Fn bigger takes 2 args
==      (if (> a b)
==          a
==          b
==      ))
BIGGER
== 
== (bigger 4 6)
6
== 
== (bigger 6 4)
6
== 

COND is another conditional fn which limits the need for nested IF's, its layout is as follows:
(COND   (  test-1  actions-1  )
        (  test-2  actions-2  )
              :       :
        (  test-n  actions-n  )
    )
COND starts evaluating its tests (starting at the 1st one), when it finds a test that does not return nil it evaluates the corresponding actions and returns that value.


== 
== (defun silly ( n )
==      (cond ( (equal n 1)
==              'one
==            )
==            ( (equal n 2)
==              'two
==            )
==            ( T       ; this is always true
==              'something-else
==            )
==      ))
SILLY
== 
== (silly 1)
ONE
== (silly 2)
TWO
== (silly 31.4)
SOMETHING-ELSE
== 
==



boolean functions

various boolean Fn.s are also available in CL


== 
== ( < 5 4 )
NIL
== 
== ( > 5 4 )
T
== 

note that false is expressed by CL as nil and true as T. In fact, in most cases CL considers anything that is not nil to be true. CL functions only return T when there is no non-nil value it can return which could be of any use. null is a function that returns true if its arg is the empty list or nil


==
== (null nil)
T
== (null () )
T
== (null ( < 5 4 ) )
T
== (null ( > 5 4 ) )
NIL
==
== (null '(a b c))
NIL
== 
== (null 'banana)
NIL
== 



OR & AND

OR & AND work in a similar way in CL as in other languages. AND takes any number of args and starts evaluating them in order. If any arg evaluates to nil, then AND stops evaluating and returns nil. If all its args are non nil, then AND returns the value of its last arg.


== 
== (and ( > 5 3 ) (equal 1 1) 'success)
SUCCESS
==
== (and ( > 5 3 ) (equal 1 2) 'success)
NIL
==
== (and  'a  T  '(ha ha ha)  'ug)
UG
== 
== (and  'a  T  nil  'ug)
NIL
== 

OR is similar except that OR evaluates its args until it finds one that evaluates to non nil, at which point it stops evaluating & returns that first non nil value.


== 
==
== (or ( > 5 3 ) (equal 1 2) )
T
==
== (or ( < 5 3 ) (equal 1 2) )
NIL
==
== (or nil nil 'a 'b nil 'c)
A
== 
== (or nil nil)     ; or returns nil only if all its args evaluate to nil
NIL
== 



using variables

So far all the examples and problems have approached lisp as a purely functional language, ie: every CL expression has been evaluated to produce a result which is shuffled back through other expressions until eventually a result is returned to the top level and printed. None of the examples have expected CL expressions to be evaluated in other ways.

SETF is a CL Fn which returns a value but is normally used for its other effects: assigning values to variables, or in CL jargon - binding values to symbols. Variable names are like Fn names: letters, numbers & a few special characters. In particular, CL allows *'s to be included in variable names & by convention ALL global variable names should start and end with a *.


== 
==
== (setf alist '(a b c))
(A B C)
==
== alist
(A B C)
==
== (car alist)
A
==

notice that setf returns the value that it binds to the given variable, this allows multiple assignments to be carried out.


==
== (setf num1 (setf num2 0) )
0
==
== (list num1 num2)
(0 0)
==
==

One last point to note is that CL allows variables to change type (integer, real, character etc) quite freely.


==
== (setf num 2)             ; integer
2
==
== (setf num (/ num 5) )    ; fraction
2/5
==
== (setf num (* num 10) )   ; integer again
4
==
== (setf num 'thirty-four)  ; symbol
THIRTY-FOUR
==



Repetition in CL



repetitive constructs in CL

Consider writing a Fn which takes one +ve integer arg N, and returns the sum of all integers from 1 to N. The following algorithm produces such a sum by using an UNTIL loop to sum in reverse (from N down to 1).
    sum-upto( N )
        vars sum = 0
        until N = 0 do
            sum + N -> sum
            N - 1 -> N
        enduntil
        return: sum
To reshape this algorithm for CL two changes are made. First the until structure is removed & instead the sum-upto Fn is called again & again. Second, the Fn is given sum as an extra arg which is assumed to be 0 the first time around.
    sum-upto( N, sum )          initial values: sum = 0
        if N=0 then
            return: sum
        else
            sum + N -> sum
            N -> N -1
            return: sum-upto( N, sum )
        endif
Or a more concise algorithm would be:
    sum-upto( N, sum )          initial values: sum = 0
        if N=0 then
            return: sum
        else
            return: sum-upto( N-1, sum+N )
        endif
In CL this is written as below


==
== (defun sum-upto ( N &optional (sum 0) )
==      (if  (= N 0)
==           sum
==           (sum-upto (- N 1) (+ sum N))
==      ))
SUM-UPTO
==
== (sum-upto 5)
15
==

TRACE is a Fn that follows the action of other Fn's & describes their action. It makes it easier to see what is happeneing when sum-upto calls itself. Note, the Fn UNTRACE stops this infm being printed.


==
== (trace sum-upto)
(SUM-UPTO)
==
== (sum-upto 4)
> SUM-UPTO 4
!> SUM-UPTO 3 4
!!> SUM-UPTO 2 7
!!!> SUM-UPTO 1 9
!!!!> SUM-UPTO 0 10
!!!!< SUM-UPTO 10
!!!< SUM-UPTO 10
!!< SUM-UPTO 10
!< SUM-UPTO 10
< SUM-UPTO 10
10
==
==

2nd example: This example is of a repetitive process which works on a list rather than on a number. The algorithm is in the form for CL. The Fn counts the number of items in a list (like the CL Fn LENGTH). It works by repeatedly taking the CDR of the given list until it reaches the empty list, counting 1 for every CAR it strips off on the way. The 'len' arg to the Fn is the one that holds the count and has an assumed initial value of zero.
    list-len( lis, len )            initial values: len = 0
        if null( lis ) then           ; if empty list is reached then
            return: len                     ;    answer is len
        else
            cdr( lis ) -> lis               ; strip 1 item off lis
            len + 1 -> len                  ; add 1 to len
            return: list-len( lis, len )    ; go round again
        endif
More consisely
    list-len( lis, len )            initial values: len = 0
        if null( lis ) then
            return: len
        else
            return: list-len( cdr(lis), len+1 )
        endif
In LISP


==
== (defun list-len (lis &optional (len 0) )
==      (if (null lis)
==          len
==          (list-len (cdr lis) (+ 1 len))
==      ))
LIST-LEN
==
== (list-len '(egg spam and chips))
4
==
 ==
== (trace list-len)
(LIST-LEN)
==
==
== (list-len '(egg spam and chips))
> LIST-LEN (EGG SPAM AND CHIPS)
!> LIST-LEN (SPAM AND CHIPS) 1
!!> LIST-LEN (AND CHIPS) 2
!!!> LIST-LEN (CHIPS) 3
!!!!> LIST-LEN NIL 4
!!!!< LIST-LEN 4
!!!< LIST-LEN 4
!!< LIST-LEN 4
!< LIST-LEN 4
< LIST-LEN 4
4
==

3rd example: This example is of a repetitive Fn which works on a list but which may find its result before it reaches the empty list. It is a function which takes 2 args, an item and a list. The Fn returns true if it finds the item somewhere in the list, or false if it doesn't.
    is-present( item, lis )
        if null( lis ) then                       ; if empty list reached
            return: false                          ;   then return false
        elseif item = car(lis) then               ; if item is same as 1st
            return: true                          ; element of list then
        else                                      ;    return true
            return: is-present( item, cdr(lis) )  ; else try rest of list
        endif
in Lisp:


==
== (defun is-present (item lis)
==      (cond ( (null lis)
==              nil
==            )
==            ( (equal item (car lis))
==              T
==            )
==            ( T
==              (is-present item (cdr lis))
==            )
==      ))
IS-PRESENT
==
== (is-present 'beans '(egg sossage beans chips))
T
==
== (is-present 'banana '(egg sossage beans chips))
NIL
==
==
== (trace is-present)
(IS-PRESENT)
==
== (is-present 'beans '(egg sossage beans chips))
> IS-PRESENT BEANS (EGG SOSSAGE BEANS CHIPS)
!> IS-PRESENT BEANS (SOSSAGE BEANS CHIPS)
!!> IS-PRESENT BEANS (BEANS CHIPS)
!! < IS-PRESENT T
!< IS-PRESENT T
< IS-PRESENT T
T
==
==
== (is-present 'banana '(egg sossage beans chips))
> IS-PRESENT BANANA (EGG SOSSAGE BEANS CHIPS)
!> IS-PRESENT BANANA (SOSSAGE BEANS CHIPS)
!!> IS-PRESENT BANANA (BEANS CHIPS)
!!!> IS-PRESENT BANANA (CHIPS)
!!!!> IS-PRESENT BANANA NIL
!!!!< IS-PRESENT NIL
!!!< IS-PRESENT NIL
!!< IS-PRESENT NIL
!< IS-PRESENT NIL
< IS-PRESENT NIL
NIL
==

a more concise way of writing this Fn (& probably the way most lisp programmers would write it) is as follows


==
== (defun is-pres (item lis)
==      (if (null lis)
==          nil
==          (or (equal item (car lis))
==              (is-pres item (cdr lis))
==          )
==      ))
IS-PRES
==
==
== (is-pres 'beans '(egg sossage beans chips))
T
== (is-pres 'banana '(egg sossage beans chips))
NIL
==
==



another repetitive strategy

Reconsider the sum-upto Fn which takes one integer arg N and returns the sum of all integers from 1 to N. The first version of this Fn accumulated its sum as it progressed. That Fn was designed by first considering an iterative algorithm using UNTIL. This new version is based on the premis that:

The sum of integers from 1 to N = N + sum of integers from 1 to (N-1)
AND the sum when N=0 is 0

the algorithm
    sum-upto( N )
        if N=0 then
            return: 0
        else
            return: N + sum-upto( N-1 )
        endif
in lisp


(defun sum-upto ( N )
    (if (= N 0)
        0
        (+ N (sum-upto (- N 1)) )
    ))


==
== (sum-upto 5)
15
==
== (trace sum-upto)
(SUM-UPTO)
==
== (sum-upto 4)
> SUM-UPTO 4
!> SUM-UPTO 3
!!> SUM-UPTO 2
!!!> SUM-UPTO 1
!!!!> SUM-UPTO 0
!!!!< SUM-UPTO 0
!!!< SUM-UPTO 1
!!< SUM-UPTO 3
!< SUM-UPTO 6
< SUM-UPTO 10
10
==

The list-len Fn can be redesigned in a similar way, based on the premis that:

the length of a list is 1 + the length of its cdr
AND the length of an empty list is 0


The algorithm
    list-len( lis )
        if null( lis ) then
            return: 0
        else
            return: 1 + list-len( cdr(lis) )
        endif
In lisp


(defun list-len ( lis )
    (if (null lis)
        0
        (+ 1 (list-len (cdr lis)) )
    ))


==
== (list-len '(a b c))
3
==
== (trace list-len)
(LIST-LEN)
==
== (list-len '(a b c))
> LIST-LEN (A B C)
!> LIST-LEN (B C)
!!> LIST-LEN (C)
!!!> LIST-LEN NIL
!!!< LIST-LEN 0
!!< LIST-LEN 1
!< LIST-LEN 2
< LIST-LEN 3
3
==

The first style of repetitive construction in these notes is known as TAIL RECURSION. Tail recursive forms produce their final result first in the deepest edition of the Fn (the one that was activated last - see trace infm). In CL some of these Fn.s are built using &optional args. The two examples just covered are HEAD RECURSIVE, these forms produce the final result in the first Fn called after the process of recursion has almost finished. Some of the time the choice between using head or tail recursion is unimportant, sometimes tail recursive forms are more efficient. Head recursive Fn.s are especially useful in list processing applications. They allow action to be performed on each element of a list without disrupting the order of the list. Consider a Fn to increment every element of a list of numbers, so

	(inc-list '(1 2 7 5))   =>   (2 3 8 6)

A verbose algorithm
    inc-list( lis )
        vars newcar, newcdr, newlist          ; do without these later
        if null( lis ) then                   ; if empty list
            return: nil                       ;    return empty list
        else                                  ; if non empty list
            car(lis) + 1 -> newcar            ;    add 1 to car
            inc-list( cdr(lis) ) -> newcdr    ;    inc-list deals with cdr
            cons( newcar, newcdr ) -> newlist ;    cons newcar & newcdr
            return: newlist                   ;    return result
        endif

Consise algorithm
    inc-list( lis )
        if null( lis ) then
            return: nil
        else
            return: cons( car(lis) + 1, inc-list( cdr(lis) )   )
        endif
lisp


(defun inc-list ( lis )
    (if (null lis)
        nil
        (cons (+ 1 (car lis))
              (inc-list (cdr lis))
        )
    ))


==
== (inc-list '(1 2 5 7))
(2 3 6 8)
==
== (trace inc-list)
(INC-LIST)
==
== (inc-list '(2 5 7))
> INC-LIST (2 5 7)
!> INC-LIST (5 7)
!!> INC-LIST (7)
!!!> INC-LIST NIL
!!!< INC-LIST NIL
!!< INC-LIST (8)
!< INC-LIST (6 8)
< INC-LIST (3 6 8)
(3 6 8)
==

As a rule of thumb there is a generalised algorithm for applying some Fn. (called F for example) to each member of a list. It is easy to see how this algorithm works for inc-lis. In the case of inc-lis F is a function which adds one to its arg. The algorithm is as follows.
    head-rec-list( lis )
        if null( lis ) then
            return: nil
        else
            return: cons( F( car(lis) ), head-rec-list( cdr(lis) ) )
        endif
Not ALL such head recursive Fn.s fit this algorithm precisely (an example follows), but most of these are at least loosely described by it. del-item is a Fn which deletes an item from a list, ie:

	(del-item 'the '(the cat sat on the mat))   =>   (cat sat on mat)

    del-item( itm, lis )
        if null(lis) then
            return: nil
        elseif itm = car(lis) then                ; if car needs deleting
            return: del-item( itm, cdr(lis) )     ;    bypass car &
                                                  ;    recurse on cdr
        else                                      ; otherwise
            return: cons( car(lis),               ;    recurse on cdr then
                          del-item( itm, cdr(lis) ))  ;cons on car
        endif
In lisp


(defun del-item ( itm lis )
    (cond ( (null lis)
            nil
          )
          ( (equal (car lis) itm)
            (del-item itm (cdr lis))
          )
          ( T  ; else
            (cons (car lis) (del-item itm (cdr lis)) )
          )
    ))


==
== (del-item 'the '(the cat sat on the mat))
(CAT SAT ON MAT)
==
==
== (trace del-item)
(DEL-ITEM)
==
== (del-item 'x '(x a x b))
> DEL-ITEM X (X A X B)
!> DEL-ITEM X (A X B)
!!> DEL-ITEM X (X B)
!!!> DEL-ITEM X (B)
!!!!> DEL-ITEM X NIL
!!!!< DEL-ITEM NIL
!!!< DEL-ITEM (B)
!!< DEL-ITEM (B)
!< DEL-ITEM (A B)
< DEL-ITEM (A B)
(A B)
==



repetition with nested lists

So far all repetitive forms working on lists have dealt with lists of atoms. Consider the problem of developing a Fn sum-list which produces the sum of a list of numbers. Extend this problem by allowing the list to contain sublists of numbers which should also be added into the sum.

	(sum-list '(1 3 (2 (2) 1)) )  =>  9
a few versions, 1st a head recursive approach (note LISTP is a Fn which takes one arg & returns true if that arg is a list, otherwise LISTP returns false).


(defun sum-list ( lis )
    (cond ( (null lis)
            0
          )
          ( (listp (car lis))
            (+ (sum-list (car lis))
               (sum-list (cdr lis)) )
          )
          ( T ; car is atom
            (+ (car lis) (sum-list (cdr lis)) )
          )
    ))


== (sum-list '(1 (2 3) 4 5))
15
==
== (trace sum-list)
(SUM-LIST)
==
== (sum-list '(1 (2 3) 4 5))
> SUM-LIST (1 (2 3) 4 5)
!> SUM-LIST ((2 3) 4 5)
!!> SUM-LIST (2 3)
!!!> SUM-LIST (3)
!!!!> SUM-LIST NIL
!!!!< SUM-LIST 0
!!!< SUM-LIST 3
!!< SUM-LIST 5
!!> SUM-LIST (4 5)
!!!> SUM-LIST (5)
!!!!> SUM-LIST NIL
!!!!< SUM-LIST 0
!!!< SUM-LIST 5
!!< SUM-LIST 9
!< SUM-LIST 14
< SUM-LIST 15
15
==

another head recursive form:


(defun sum-list ( lis )
    (if (null lis)
        0
        (+  (if (listp (car lis))
                (sum-list (car lis))
                (car lis)  )
            (sum-list (cdr lis))
        )
    ))

now a tail recursive form


(defun sum-list ( lis &optional (sum 0) )
    (cond ( (null lis)
            sum
          )
          ( (listp (car lis))
            (sum-list (cdr lis) (sum-list (car lis) sum) )
          )
          ( T ; car is atom
            (sum-list (cdr lis) (+ sum (car lis)) )
          )
    ))


==
== (sum-list '(1 (2 3) 4 5))
> SUM-LIST (1 (2 3) 4 5)
!> SUM-LIST ((2 3) 4 5) 1
!!> SUM-LIST (2 3) 1
!!!> SUM-LIST (3) 3
!!!!> SUM-LIST NIL 6
!!!!< SUM-LIST 6
!!!< SUM-LIST 6
!!< SUM-LIST 6
!!> SUM-LIST (4 5) 6
!!!> SUM-LIST (5) 10
!!!!> SUM-LIST NIL 15
!!!!< SUM-LIST 15
!!!< SUM-LIST 15
!!< SUM-LIST 15
!< SUM-LIST 15
< SUM-LIST 15
15
==

another tail recursive form


(defun sum-list ( lis &optional (sum 0) )
    (if (null lis)
        sum
        (sum-list (cdr lis)
                  (if (listp (car lis))
                      (sum-list (car lis) sum)
                      (+ sum (car lis))
                  ))
    ))

A 2nd example is a Fn inc-list that takes a list of numbers as its only arg. inc-list increments each number in the list. Allowing args to contain nested lists adds only a little extra complexity:


(defun inc-lis ( lis )
    (cond ( (null lis)
            nil
          )
          ( (listp (car lis))
            (cons (inc-lis (car lis)) (inc-lis (cdr lis)) )
          )
          ( T
            (cons (+ 1 (car lis)) (inc-lis (cdr lis)) )
          )
    ))

==
== (inc-lis '(1 (2 3) 4))
(2 (3 4) 5)
==
== (trace inc-lis)
(INC-LIS)
==
== (inc-lis '(1 (2 3) 4))
> INC-LIS (1 (2 3) 4)
!> INC-LIS ((2 3) 4)
!!> INC-LIS (2 3)
!!!> INC-LIS (3)
!!!!> INC-LIS NIL
!!!!< INC-LIS NIL
!!!< INC-LIS (4)
!!< INC-LIS (3 4)
!!> INC-LIS (4)
!!!> INC-LIS NIL
!!!< INC-LIS NIL
!!< INC-LIS (5)
!< INC-LIS ((3 4) 5)
< INC-LIS (2 (3 4) 5)
(2 (3 4) 5)
==

Or alternatively


(defun inc-lis ( lis )
    (if (null lis)
        nil
        (cons (if (listp (car lis))
                  (inc-lis (car lis))
                  (+ 1 (car lis))  )
              (inc-lis (cdr lis))
        )
    ))



the matcher

Another example is a Fn called matches. The matches Fn will become more sophisticated over the next few pages of notes, but for now it is equivalent to the equals Fn which compares two lists (possibly containing nested lists) for equality. Loosely the algorithm is:
    matches( L1, L2 )
        if {both lists empty} then
            return: true
        elseif {one list empty} then
            return: false
        elseif {car L1 is a list} AND {car L2 is a list} then
            return: true if matches( car(L1), car(L2) )
                        AND matches( cdr(L1), cdr(L2) )
                    otherwise false
        else {car's of L1 & L2 are not both lists}
            return: true if car(L1) = car(L2)
                        AND matches( cdr(L1), cdr(L2) )
                    otherwise false
        endif
in Lisp:


(defun matches ( l1 l2 )
    (cond ( (and (null l1) (null l2) )
            T
          )
          ( (or (null l1) (null l2) )
            nil
          )
          ( (and (listp (car l1)) (listp (car l2)) )
            (and (matches (car l1) (car l2))
                 (matches (cdr l1) (cdr l2)) )
          )
          ( T
            (and (eql (car l1) (car l2))
                 (matches (cdr l1) (cdr l2)) )
          )
    ))

Note: the equality Fn used within matches is EQL, the difference between CL's various equality Fn.s will be detailed later but for now you can assume that EQL works as you would expect with atoms but cannot reliably detect equal lists.


==
== (matches '(a (b c)(d)) '(a (b c)(d)))
T
==
== (matches '(a (b c)) '(a (b c) d))
NIL
==

 
== (trace matches)
(MATCHES)
==
== (matches '(a (b c) d) '(a (b c) d))
> MATCHES (A (B C) D) (A (B C) D)
!> MATCHES ((B C) D) ((B C) D)
!!> MATCHES (B C) (B C)
!!!> MATCHES (C) (C)
!!!!> MATCHES NIL NIL
!!!!< MATCHES T
!!!< MATCHES T
!!< MATCHES T
!!> MATCHES (D) (D)
!!!> MATCHES NIL NIL
!!!< MATCHES T
!!< MATCHES T
!< MATCHES T
< MATCHES T
T
==
== (matches '(a (b c) d) '(a (b d) c))
> MATCHES (A (B C) D) (A (B D) C)
!> MATCHES ((B C) D) ((B D) C)
!!> MATCHES (B C) (B D)
!!!> MATCHES (C) (D)
!!!< MATCHES NIL
!!< MATCHES NIL
!< MATCHES NIL
< MATCHES NIL
NIL
==

In the spirit of matching, the second list L2 is now going to be called the 'pattern'. The matcher can be made more flexible by allowing wild-card symbols to be used in the pattern. Wild-cards are, as far as the matcher is concerned, equal to any single atom in the list to be matched. The wild-card symbol I will use is = So:


==
== (matches '(a b c) '(a = c))
T
==
== (matches '(the cat ate the rat) '(the cat = the =))
T
==

The last section dealt with a matches Fn which allowed for wild-cards. The problem with wild-cards is that they do not capture the items that they match with. Matches will have much greater capabilities if it can be used to pick out items from the matched list and store them for later use. Eg:

(matches '(the cat sat) '(the {get_item_into X} sat) ) => T

{get_item_outof X} => CAT

By convention the syntax used in the pattern for {get_item_into X} is (? X), so the matches expression will be

(matches '(the cat sat) '(the (? X) sat) ) => T

Before considering the syntax for the {get_item_outof ...} expresion it is necessary to find a convenient way to attach values to symbols (eg: to attach "CAT" to X as above).

association lists

Arrays are a numerically indexed data structure. Lists can also be numerically indexed (see later section). Association lists (A-lists) provide a way to symbolically index a list. An A-list is a list of associations, an association is a list whose car is the association name & whose cdr holds its value.


==
== (setf cat '( (legs 4) (tail 1) (eats fish) )  )
((LEGS 4) (TAIL 1) (EATS FISH))
==

ASSOC retrieves named associations


==
== (assoc 'tail cat)
(TAIL 1)
==

SECOND is a Fn returning the second element of a list. CL has sensibly named Fn.s from FIRST to TENTH. SECOND is sometimes used with ASSOC.


==
== (second (assoc 'legs cat))
4
==

New associations are added to A-lists by CONSing them on


==
== cat
((LEGS 4) (TAIL 1) (EATS FISH))
==
== (setf cat (cons '(name kitty) cat) )
((NAME KITTY) (LEGS 4) (TAIL 1) (EATS FISH))
==
== (second (assoc 'name cat))
KITTY
==

associating values with matches

We will extend matches so that it recognises items of the form (? symbol) in its 2nd (pattern) arg. When such an item is found matches should make an association whose name is the symbol following the ? and whose value is the corresponding item in its 1st arg. Matches should build up an association list which it will return as its result. Eg:
	(matches '(a b c) '(a (? s1) (? s2)) )
	=>    ( (s2 c) (s1 b) )
When matching with a pattern which contain no ? items, matches will not build an association list. In this case we must make sure that matches does not return nil as nil indicates that the two lists do not match. The matcher used in these notes always associates the entire pattern with a symbol called "*BIND".


==
== (matches '(fish chips peas) '(fish chips peas))
((*BIND (FISH CHIPS PEAS)))
==

Now consider a Fn called matchout which takes 2 args. One arg is an association list typically produced by matches. The other is a list which may contain forms like (^ symbol), these forms are replaced by the symbol's value as found in the association list.


==
== (setf asl (matches '(the cat ate the rat) '(the (? subj)(? act) the rat)))
((ACT ATE) (SUBJ CAT) (*BIND (THE (|?| SUBJ)(|?| ACT) THE RAT)))
==
== (matchout '(a pitbull (^ act) the (^ subj)) asl)
(A PITBULL ATE THE CAT)
==

It is now possible to extend matches so that it recognises items like (^ symbol) in its pattern arg & replaces them with the relevant value during the course of matching.


==
== (matches '(spam spam egg and spam) '((? x) (^ x) (? y) and (^ x)) )
((Y EGG) (X SPAM) (*BIND ((|?| X) (|^| X) (|?| Y) AND (|^| X))))
==

the final pattern matcher

So far we have only considered the matcher working with individual items rather than lists of them. It is possible to extend the matcher to deal with lists, the syntax used is as follows: = wild-card for 1 item == wild-card for 0 or more items (? symbol) associate 1 item with symbol (?? symbol) associate 0 or more items with symbol (^ symbol) push-out value associated with symbol as 1 item (^^ symbol) push-out value associated with symbol as a series


==
== (setf a-list (matches '(a b c d) '( (? first) (?? rest) ) ))
((REST (B C D)) (FIRST A) (*BIND ((|?| FIRST) (|??| REST))))
==
== (matchout '(start (^ rest) end) a-list)
(START (B C D) END)
==
== (matchout '(start (^^ rest) end) a-list)
(START B C D END)
==
== (setf a-list (matches '(a b c d) '( (? first) == (? last) )))
((LAST D) (FIRST A) (*BIND ((|?| FIRST) == (|?| LAST))))
==
== (second (assoc 'first a-list))
A
== (second (assoc 'last a-list))
D
==

A decent pattern matcher is something most CL programmers have as part of their standard toolkit (unfortunately CL does not provide one so they all have to write their own), it has many uses. A slightly silly example of what you can do with a handfull of patterns & a matcher follows.

Some patterns:


    '(  (   (I like (?? A))         (what do you like about (^^ A))     )
        (   ((?? A) are (?? B))     (you think (^^ A) are (^^ B))       )
        (   (I am (?? A))           (why do you think you are (^^ A))   )
        (   (== problem ==)         (tell me about this problem)        )
        (   ( == )                  (how very interesting)              )
    )

==
== (talk *match-lis*)

(HELLO HOW ARE YOU) == (I have a bit of problem)

(TELL ME ABOUT THIS PROBLEM) == (I am a fried egg)

(WHY DO YOU THINK YOU ARE A FRIED EGG) == (all the best people are fried eggs)

(YOU THINK ALL THE BEST PEOPLE ARE FRIED EGGS) == (I think so)

(HOW VERY INTERESTING) == ()
BYE
==



using variables



declaring variables

The following list could be a fragment of a simple knowledge network


(setf *fragment*
   '(   (dog        (legs 4)
                    (tail 1)
                    (diet carnivore)
                    (ako mammal)
        )
        (spaniel    (color black-white)
                    (ears floppy)
                    (ako dog)
                    (manner gentle)
        )
        (fido       (ako spaniel)
                    (color brown)
        )
    ))

Finding details directly attached to any item is no problem, we could use assoc.

(assoc 'spaniel *fragment*)

(assoc 'ears (cdr (assoc 'spaniel *fragment*)) )
Problems arise when we want some detail but do not know where it is held. For example, if we want to know how many legs Fido has then, unless we look at the kn net, we have no idea whether to look for the infm at the level of Fido, spaniel or dog. What is needed is a general purpose Fn which will track up ako links if necessary. This type of process is called inheritance.

To do this we will have to use variables. Local variables to a Fn can be declared after the word &aux in the arg list but although they occur in the arg list they are not args of any kind. &aux variables should be declared after &optional args and any other type of arg you meet later in the notes. &aux variables, like &optional args, can be declared simply as a variable name or as a list of the form (var-name initial-value). There is no limit to the number of variables declared after the &aux.


(defun inherit ( object spec kn-net
    &aux (subnet (cdr (assoc object kn-net)) )
    )
    (if (null object)   ; object=nil when ako links exhausted
        nil
        (or (cdr (assoc spec subnet))
            (inherit (second (assoc 'ako subnet)) spec kn-net)
        )
    ))

==
== (inherit 'fido 'legs *fragment*)
(4)
==
== (inherit 'fido 'color *fragment*)
(BROWN)
==
== (inherit 'fido 'manner *fragment*)
(GENTLE)
==

CL programmers don't like &aux args/vars much and almost always prefer to use LET which is another form which allows variable declaration, LET has the following form:
	(let ( ...list of variables... )
	     
	     )
as with &aux etc, any variable declared can be a simple variable, or a variable & initial value list. If there are a number of initial values to be assigned then these values are calculated in parallel. LET* is similar to let, but its initial values are calculated in series.


(defun inherit ( object spec kn-net )
    (if (null object)
        nil
        (let (  (subnet (cdr (assoc object kn-net)))  )
             (or (cdr (assoc spec subnet))
                 (inherit (second (assoc 'ako subnet))
                          spec kn-net)
             ))
    ))



variable scope

In general, variables are lexically scoped. They are in scope only in the textual block in which they are declared. So variables declared at the start of a let statement can only be refered to inside that statement. Args declared in a defun statement are only in scope inside that Fn body. So if fun1 calls fun2, fun1's args are not available in fun2.

Forms like let & defun (& some more that come later) will 'shadow' an existing variable if they declare a new variable of the same name.


(defun var-test (X Y)
    (let ( (X (* 2 Y)) )    ; let X shadows defun X
        (print X)           ; print writes its arg, see below
        )                   ; let closes, let X no longer exists
    X )


==
== (var-test 2 3)

6 2
==

SETF, like other CL Fn.s, returns a value and (in CL terms) alters the binding of a data object as a side effect. Often it is useful to carry out such expressions for the benefit of their side effects (ie: to set a variable) without having to use the value returned by them. Put another way, the simplest way to do something may be to evaluate a series of expressions, returning the value of one of them.

sequences

There are two Fn.s PROG1 & PROGN which take a series of expressions & evaluate them all. PROG1 returns the value of the 1st expression, PROGN returns the value of the last.


==
== (prog1 (car '(x y z))
==        (setf a 'the)
==        (setf b 'cat)
==        (setf c 'sat))
X
==
== (list a b c)
(THE CAT SAT)
==
== (progn (car '(x y z))
==        (setf a 'the)
==        (setf b 'cat)
==        (setf c 'sat))
SAT
==

PROGN type sequences (those that return the last value) exist implicitly in the body of DEFUN, in the actions parts of COND and in some other Fn.s which will be introduced later. With other Fn.s (eg: IF) the programmer must make sequences by using PROGN or PROG1.

Input & Output



basic output

PRINT is the basic output Fn, it has two variations PRIN1 & PRINC. PRINT prints a newline & then its arg followed by a single space. PRIN1 just prints its arg with no leading newline or trailing space. PRINC behaves like newline unless special characters are included in its arg. All three Fn.s return their arg.


==
== (setf x 'banana)
BANANA
==
== (print x)

BANANA BANANA
==
== (progn (print x) '-end)

BANANA -END
==
== (progn (prin1 x) '-end)
BANANA-END
==
== (progn (princ x) '-end)
BANANA-END
==

printing certain characters can be a problem in lisp (eg spaces, brackets and control characters), these characters can be preceded with \ to have them printed normally.


==
== (print 'the\ cat)

|THE CAT| |THE CAT|         ; CL treats this as a special sort of string
==
== (princ 'the\ cat)        ; PRINC returns the same as PRINT but its printed
THE CAT|THE CAT|            ; representation leaves out flag characters like |
==

strings containing special characters can be delimited by | or " to have them printed without causing problems. Using | is probably more efficient than " (" " delimits the string data type)


==
== (print '|b a n a n a| )

|b a n a n a| |b a n a n a|
== (princ '|b a n a n a| )
b a n a n a|b a n a n a|
==



format

FORMAT allows more flexible output FORMAT is a complicated but useful Fn, its structure is:
(format  dest  string  -args- )
FORMAT writes to the device implied by 'dest', if 'dest' is T then FORMAT writes to the terminal (ie: stdout). 'string' is a string between " characters. In its most simple form FORMAT works a bit like print (except it returns nil).


==
== (format T "the cat sat.")
the cat sat.NIL
==

The string given to FORMAT can contain any no. of a wide range of special characters (or more accurately format directives). These alter the way the string is printed. Only a few special characters are covered here. Specials are introduced with ~ (if not they are treated as normal characters). Special characters include:
%  throw newline
&  throw newline unless already thrown
t  move to horisontal tab (eg ~9t moves to column 9)
a  print next value from -args- (FORMAT's 3rd arg)
d  print next value in decimal
b  print next value in binary, o octal, x hex



==
== ; a few examples
== (format T "~%hello~&~&ha~17tgosh its~a ~d ~b"
==           'nearly 314 12)

hello
ha               gosh itsNEARLY 314 1100NIL
==



basic input

READ is the general input Fn for CL. In its simplest form READ takes no args and reads a lisp object from the key board, returning that object as its value.


==
== (read) (the cat sat)
(THE CAT SAT)
==
== (read)                        ; read bypasses spaces & newlines
==         (the cat sat)
(THE CAT SAT)
==

note that READ does not evaluate what is read so no need for 'evaluation can be forced if neccesary using EVAL (EVAL evaluates its arg)


==
== (read)
==      (+ 2 2)
(+ 2 2)
== (eval (read))
==      (+ 2 2)
4
==

EVAL is a powerful Fn not covered in these notes, eval aids auto program construction & evaluation (and many other things !) eg:


==
== (eval (list 'car ''(a b c d)) )
A
==



iteration

CL has a variety of iterative forms. Iteration is less versatile than recursion but can be more efficient. These notes consider DOTIMES, DOLIST & DO. DOTIMES is of the form:

	(dotimes ( var limit result ) body )

DOTIMES is like a for loop in other languages. As above var is the control variable, limit is the upperbound, result is the expression that DOTIMES evaluates as it finishes, and body is a list of CL expressions that are evaluated each iteration. Note: the control variable varies between 0 & (upperbound minus 1).


==
== (dotimes (x 4 'finished)
==      (print x) )         ; print writes its arg to the terminal

0
1
2
3 FINISHED
==

DOLIST is of a similar form:
	(dolist ( var list result ) body )

in this case the control variable takes the value of successive items in list


==
== (dolist (x '(a b (c d)) 'finished)
==      (print x) )

A
B
(C D) FINISHED
==

DO is a general iterative form

DO is of the form:
   (do ( locals )
       ( test result )
       body )

DO repeatedly evaluates the expressions in body until its test returns non nil, it then evaluates result & returns that value. locals is a list of variables which are only in scope within DO. Variables must be given with an initial value (as may be given with &optional args etc).

DO, DOTIMES & DOLIST can all be prematurely terminated using RETURN, a Fn which takes 1 arg which is evaluated to form the result of the termination.

eg: to return 1st negative no. in a list (or nil if none are found)


==
== (defun neg-num ( lis )
==      (dolist (x lis nil)
==          (if (< x 0)
==              (return x)
==          )
==      ))
NEG-NUM
==
== (neg-num '(1 2 3 -4 -5) )
-4
==
== (neg-num '(1 2 3 4))
NIL
==

WHEN & UNLESS are two conditional Fn.s often used with RETURN. They are of the form:

(when test expression) - if test is non nil then evaluate expression
(unless test expression) - if test is nil then evaluate expression

note: DO evaluates the initial values for all of its locals in parallel. If this is inconvenient then DO* is a similar Fn except that its initial values are evaluated in series.

Back to neg-num (above), tracing the operation of iterative Fn.s is more hassle than tracing recursive fn.s. The most obvious way to trace through neg-num is to use a print statement. It is useful to provide a mix of text & values in such a print statement so it is obvious that what is being printed is for debugging purposes. A convenient way of doing this is to use the backquote character ` instead of the usual quote. If a list is preceded by backquote then CL quotes (as usual) all items within the list except those following a comma. Items following a comma are evaluated.


==
== '(normal quote (+ 3 4))
(NORMAL QUOTE (+ 3 4))
==
== `(back quote ,(+ 3 4))
(BACK QUOTE 7)
==
== (setf var1 '(a b c))
(A B C)
== (setf var2 'spam)
SPAM
==
== `(back quote ,var1 ,var2)
(BACK QUOTE (A B C) SPAM)
==
==
== ; using this idea in neg-num to help tracing
==
== (defun neg-num ( lis )
==      (dolist (x lis nil)
==          (print `(*DEBUG neg-num X= ,x))
==          (if (< x 0)
==              (return x)
==          )
==      ))
NEG-NUM
==
== (neg-num '(1 2 -3 4 5))

(*DEBUG NEG-NUM X= 1)
(*DEBUG NEG-NUM X= 2)
(*DEBUG NEG-NUM X= -3) -3
==
== (neg-num '(1 2 6))

(*DEBUG NEG-NUM X= 1)
(*DEBUG NEG-NUM X= 2)
(*DEBUG NEG-NUM X= 6) NIL
==

This brief note on the use of backquote & comma does not do justice to a mechanism which, in older versions of lisp, programmers had to develop for themselves. Many CL programmers habitually use backquote & comma for a variety of effects which would be a lot of hassle if done in other ways.

function forms



symbols and values

Symbols in Common Lisp can have more than one type of value associated with them at any given time. These notes investigate the ways in which function values can be bound to symbols.


==
== (defun adder (num1 num2)	; define adder as a function
==      (+ num1 num2) )
ADDER
== 
== (setf adder 'kipper)		; set adder to have a value
KIPPER
== 
== adder
KIPPER
== 
== (adder 4 5)			; adder is bound to both value AND Fn forms
9
==

INSPECT is a function which which examines all values associated with a symbol. It gives infm about the function name, any value bound to it (value), any function bound to it (function), the origin of the symbol, was it first used by the CL system or the programmer (package) and any property list associated with it (plist) [note: these notes do not deal with property lists]. Inspect is function which allows you to interact with it, to stop this interaction type 'q'.


== 
== (inspect 'adder)     ; inspect works on the name of a symbol, need quote
A symbol
  {0}      Name:  "ADDER"
  [1]     Value:  KIPPER
  [2]  Function:  #
  {3}   Package:  #
  [4]     Plist:  NIL
inspect>  q
==

The symbol adder has 2 values associated with it a value "KIPPER" & a function. Usually when we access a symbol as if it is a variable we get its value part & when we access it as if it were a function, we get its function part.


== (setf x adder)
KIPPER
== 
== x
KIPPER
== 
== (x 2 3)

;;; MISHAP - Applying undefined function X
;;; DOING    :  (X 2 3)

== (inspect 'x)
A symbol
  {0}      Name:  "X"
  [1]     Value:  KIPPER
  [2]  Function:  #
  {3}   Package:  #
  [4]     Plist:  NIL
inspect>  q
==

The fn called "FUNCTION" is used to access the fn part of a symbol directly,note (FUNCTION symbol) is usually abbreviated to #'symbol


== adder
KIPPER
== 
== (function adder)
#
== 
== #'adder
#
== 
== (setf x #'adder)
#
== 
== (x 2 3)

;;; MISHAP - Applying undefined function X
;;; DOING    :  (X 2 3)

== (inspect 'x)
A symbol
  {0}      Name:  "X"
  [1]     Value:  #
  [2]  Function:  #
  {3}   Package:  #
  [4]     Plist:  NIL
inspect>  q
==

FUNCALL calls a fn attached to value part of a symbol, SYMBOL-FUNCTION gives us access to the function part of a symbol for setf.


== (funcall x 2 3)
5
== 
== (setf (symbol-function 'x) #'car)
#
== 
== (inspect 'x)
A symbol
  {0}      Name:  "X"
  [1]     Value:  #
  [2]  Function:  #
  {3}   Package:  #
  [4]     Plist:  NIL
inspect>  q

== (x '(a b c))
A
== 
== (funcall x 1 2)
3
== 

So, symbols can have more than one value associated with them at any time. The reason for looking at this aspect of symbols is that knowing how to access the function part of a symbol allows us to call some special fn.s which take other fn.s as their args.

mapping functions

MAPCAR is a fn which takes 2 args, a function (not just the name of a function) and a set of args. MAPCAR returns a list of the results of successive function calls.


== 
== (defun inc (x) (1+ x) )
INC
== 
== (mapcar #'inc '(11 22 33 44) )
(12 23 34 45)
== 
== (trace inc)
(INC)
== 
== (mapcar #'inc '(11 22 33 44) )
 > INC 11
 < INC 12
 > INC 22
 < INC 23
 > INC 33
 < INC 34
 > INC 44
 < INC 45
(12 23 34 45)
== 
== 
MAPCAR can be used with Fn.s taking more than one arg
== 
== (defun addem (a b) (+ a b) )
ADDEM
== 
== (mapcar #'addem '(1 2 3) '(4 5 6) )
(5 7 9)
== 
== (trace addem)
(ADDEM)
== 
== (mapcar #'addem '(1 2 3) '(4 5 6) )
 > ADDEM 1 4
 < ADDEM 5
 > ADDEM 2 5
 < ADDEM 7
 > ADDEM 3 6
 < ADDEM 9
(5 7 9)
== 

there are a number of functions which take functions as args (see Steele) remove-if takes a test (a fn) & a list & returns the list with those items that satisfy the test removed.


== 
== (defun gt5 (n) (> n 5) )
GT5
== 
== (remove-if #'gt5 '(1 9 2 8 3 7 4 6 5))
(1 2 3 4 5)
== 
== (remove-if #'numberp '(a 1 b 2 c 3 d 4))
(A B C D)
==



anonymous functions

Often functions supplied to mapcar etc are only used in such calls & Lisp offers a way of describing these functions without doing a defun. Instead we use LAMBDA to define an anonymous function.


== 
== (setf spud #'(lambda (a b) (list a b) ) )
#
== 
== (inspect 'spud)
A symbol
  {0}      Name:  "SPUD"
  [1]     Value:  #
  [2]  Function:  #
  {3}   Package:  #
  [4]     Plist:  NIL
inspect> q

== (funcall spud 'hooray 'henry)
(HOORAY HENRY)
== 
== (remove-if #'(lambda (n) (and (> n 3) (< n 6)) )
==            '(1 2 3 4 5 6 7 8 9))
(1 2 3 6 7 8 9)
== 

consider an example which uses the booklist from previous exercises


(setf booklist
 '( (1261 Chomsky   (formal grammars)
                    (computing linguistics philosophy))
    (1853 Thompson  (brain functions)
                    (physiology psychology computing))
    (2009 Winston   (lisp 3rd edition)
                    (lisp expert-systems))
  ))

the author is the cadr of each list in booklist, so to list all the authors


== 
== (mapcar #'cadr booklist)
(CHOMSKY THOMPSON WINSTON)
==

to list all computing books we can use remove-if-not


== 
== (remove-if-not #'(lambda (book)
==                       (member 'computing (elt book 3)))
==                booklist)
((1261 CHOMSKY (FORMAL GRAMMARS) (COMPUTING LINGUISTICS PHILOSOPHY))
 (1853 THOMPSON (BRAIN FUNCTIONS) (PHYSIOLOGY PSYCHOLOGY COMPUTING)))
== 
==

Careful use of lambda allows some powerful constructions to be built. The function defined next is used to build other functions. Work through the example until you understand what is going on. This type of strategy is very powerful.


== 
== (defun subject (name)
==      #'(lambda (book) (member name (elt book 3))
==      ))
SUBJECT
== 
== (setf computing-book (subject 'computing))
#
== 
== (remove-if-not computing-book booklist)
((1261 CHOMSKY (FORMAL GRAMMARS) (COMPUTING LINGUISTICS PHILOSOPHY))
 (1853 THOMPSON (BRAIN FUNCTIONS) (PHYSIOLOGY PSYCHOLOGY COMPUTING)))
== 
==

an example using lambda This example is based on a data structure which captures the state of a small world of blocks. In the world are some cubes and wedges, each colored red or blue, and a table. The Lisp code retrieves information from the data structure. *blocks* is a global variable used to hold the data which is in the form of a set of triples, each with the structure (relation object value).


(setf *blocks*
    '(  (isa    b1  cube)       (isa    b2  wedge)
        (isa    b3  cube)       (isa    b4  wedge)
        (isa    b5  cube)       (isa    b6  wedge)
        (color  b1  red)        (color  b2  red)
        (color  b3  red)        (color  b4  blue)
        (color  b5  blue)       (color  b6  blue)
        (on     b1  table)      (on     b2  table)
        (on     b5  table)
    ))

The first function, called 'entry-type' takes a relation name and a value it makes a one argument boolean function which returns true when given a triple with that relation and value.


(defun entry-type ( reln valu )
    #'(lambda (entry)
            (and (eql (car entry) reln)
                 (eql (caddr entry) valu) )
    ))

== 
== (setf color-blue (entry-type 'color 'blue))
#
== 
== (funcall color-blue '(color sky blue))
T
== 
== (funcall color-blue '(color bus red))
NIL
== 
== (funcall color-blue '(isa lemon fruit))
NIL
==

remove-if-not can be used with color-blue to get the set of triples describing objects as blue.


==
== (remove-if-not color-blue *blocks*)
((COLOR B4 BLUE) (COLOR B5 BLUE) (COLOR B6 BLUE))
==

mapcar and second will then give the names of blue objects.


==
== (mapcar #'second (remove-if-not color-blue *blocks*))
(B4 B5 B6)
== 
 ==
== ; two more calls to entry-type
==
== (setf isa-cube (entry-type 'isa 'cube))
#
==
== (setf on-table (entry-type 'on 'table))
#
==

Lisp has a range of functions which treat lists as sets of objects. The set intersection function is useful to get a list of blue cubes.


==
== (intersection (mapcar #'second
==                       (remove-if-not color-blue *blocks*))
==               (mapcar #'second 
==                       (remove-if-not isa-cube *blocks*))
==               ))
(B5)
==

Now for a general purpose function which combines some of the ideas above. It returns the names of those blocks which satisfy a set of criteria. It takes, as its arguments, a list of functions like color-blue, on-table etc and a list of triples (ie: *blocks).


(defun select (fn-list data-list
    &optional
        (set (mapcar #'second
                 (remove-if-not #'(lambda (entry) 
                                         (eql (car entry) 'isa))
                                data-list
         )))
    )
    (if (null fn-list)
        set
        (select (cdr fn-list) 
                data-list
                (intersection 
                     set
                     (mapcar #'second
                             (remove-if-not (car fn-list) 
                                            data-list)
                     ))
        )))
== 
== (select `(,color-blue ,isa-cube) *blocks*)
(B5)
== 
== (select `(,(entry-type 'color 'red) ,on-table ,isa-cube)
==         *blocks*)
(B1)
== 
== (select `(,(entry-type 'color 'red) ,on-table) *blocks*)
(B1 B2)
==



These notes end here, for more information check out Winston & Horn or Steele.