General

Student Webpages

Introduction

An object in Lisp is either an atom, a list, an instance of a class, or other stuff (but really all you need are atoms and lists, what is this, Java?).

An atom is an “indecomposable” Lisp object (but just like real atoms, you actually can decompose them).

  • integer atoms
    • -4
    • 3193
  • real atoms
    • 3.14
    • 000.2
  • string atoms
    • "one two THREE"
    • " "
    • ""
  • symbolic atoms
    • R2D2
    • HERE-THERE-EVERYWHERE
    • SMALL

The featured data type in Lisp is the list. A list is simply a sequence of Lisp objects.

  • (2 3 5 7)
  • (SINGLE-DIGIT-PRIMES)
  • (1 RED 2 YELLOW 3 BLUE)

The key to understanding Lisp programming lies in a deep understanding of forms.

A form is an expression which can be evaluated by the Lisp interpreter.

The read-eval-print loop (REPL)

for(ever)
  x = read()
  z = eval(x)
  print(z)
end

Introductory Lisp Session

Constant forms

A constant is an expression which evaluates to itself.

Numbers, character strings, characters, and booleans are among the most commonly used constant forms.

  • numbers
    • …
  • character strings
    • …
  • characters
    • #\A
    • #\z
    • #\4
  • booleans
    • (NOT NIL) => T
    • NIL

Variable forms

A variable is a symbol which is denotationally bound to some Lisp object.

The symbol PI is pre-bound in Common Lisp.

The symbol PIE became a variable in the sample session once it was bound to CHERRY.

Variables evaluate to the values to which they are bound.

Standard forms

A standard form is a list which represents a function application in the following sense: the first element of the list represents a function; each remaining element of the list represents an unevaluated argument to that function.

Standard form evaluation is the following two-step process for evaluating a functional form:

  1. the argument forms are evaluated

  2. the function is applied to the values obtained in the first step

Examples …

  • + and max are predefined standard forms

  • double from the introductory lisp session is a standard form defined by the programmer

Special forms

A special form is like a standard form, except that one or more of the arguments to the function are not evaluated prior to application of the function.

Examples …

  • QUOTE: (quote whatever), whatever is not evaluated

  • SETF: (setf symbol object), if the first argument is a symbol, it is not evaluated; the second argument is evaluated

  • DEFUN: (defun lambda-list sequence-of-forms), neither of the two arguments are evaluated prior to applying defun

Simple Numeric List Processing

Example numeric operators …

  • +

  • -

  • *

  • /

Simple Numeric Session

List Processing

Icons of List Processing in Lisp

The CAR of a nonempty list is the FIRST element of the list. Stands for “contents of A register”.

The CDR of a nonempty list is the REST of the elements of the list. Stands for “contents of D register”.

The CONS of an object O and a list L is the list whose CAR is 0 and whose CDR is L.

Abstract Session: featuring CAR and CDR.

1) What is the CAR of (BLUE RED YELLOW)?

  • BLUE

2) What is the CDR of (BLUE RED YELLOW)?

  • (RED YELLOW)

3) What is the CAR of ((1 2) BUCKLE MY SHOE)?

  • (1 2)

4) What is the CDR of ((1 2) BUCKLE MY SHOE)?

  • (BUCKLE MY SHOE)

5) What is the CAR of ("SUNSHINE")?

  • "SUNSHINE"

6) What is the CDR of ("SUNSHINE")?

  • () or NIL

Abstract Session: featuring CONS.

1) What is the CONS of ESPRESSO and (LATTE CAPPUCCINO)?

  • (ESPRESSO LATTE CAPPUCCINO)

2) What is the CONS of (A B C) and (1 2 3)?

  • ((A B C) 1 2 3)

3) What is the CONS of PETUNIA and ()?

  • (PETUNIA)

Referencers and Constructors

A referencer is a form which returns a reference to a part of a given structure.

A constructor is a form which returns a structure constructed from some number of Lisp objects.

Note: The “icons of list processing” are all you actually need to do list processing in Lisp. The rest are for convenience.

Summary of some Referencers and Constructors

(nth NUMBER LIST) returns the element in position NUMBER of the list LIST, with indexing beginning at 0.

(list & SEQUENCE-OF-FORMS) evaluates each FORM in the SEQUENCE-OF-FORMS and then constructs a list from the values of the FORMS.

(append & SEQUENCE-OF-FORMS) evaluates each FORM in the SEQUENCE-OF-FORMS and then constructs a list by concatenating the values of the FORMS.

Evaluators

An evaluator is a function which performs function evaluation!

In Lisp, eval is the basic evaluator, but apply and funcall serve as alternative evaluators that often provide convenience and conceptual clarity.

(eval FORM) evaluates FORM.

(apply FUNCTION LIST-OF-ARGUMENTS) applies FUNCTION to LIST-OF-ARGUMENTS.

(funcall FUNCTION & LIST-OF-ARGUMENTS) applies FUNCTION to LIST-OF-ARGUMENTS.

Predicates

A predicate is a function which takes some number of arguments and returns a boolean value.

COND

  1. Any number of cases
  2. Any number of forms in a case
  3. Only one case fires – the first for which the first experssion in the case evaluates to non-NIL.
  4. The value of the COND is the value of the last form evaluated in the case that is selected – or NIL if no case fires.
(defun sign (n)
  (cond
    ((> n 0) 'positive)
    ((< n 0) 'negative)
    (T       'zero)))

List Processing

> (singletonp '(MONDAY))
T
> (singletonp '())
NIL
> (singletonp '(ONE TWO THREE))
NIL
;; Graci's definition
(defun singletonp (the-list)
  (cond
    ((null the-list)       NIL)
	((null (cdr the-list)) T)
	;; can just leave this part off to return NIL
	(T                     NIL)))

;; My definition
(defun singletonp (the-list)
  (and (car the-list) (not (cdr the-list))))
> (rac '(ONE TWO THREE))
THREE
> (rac '(MONDAY))
MONDAY

Thoughts:

  • rac of (A) is A
  • rac of (A B C D) is the rac of (cdr '(A B C D)) => (B C D)
;; Returns the last element of the list
(defun rac (the-list)
  (cond
    ((singletonp the-list) (car the-list))
    (T                     (rac (cdr the-list)))))
> (rdc '(A B C D))
(A B C)
> (rdc '(S))
()

Thoughts:

  • rdc of (x) is ()
  • rdc of (A B C D) is the cons of A and the rdc of (cdr '(A B C D)) => (B C D)
;; Returns all but the rac of the list
;; (pronounced "rudder cdr")
(defun rdc (the-list)
  (cond
    ((singletonp the-list) ())
	(T                     (cons (car the-list) (rdc (cdr the-list))))))
  • snoc of x and () is (x)
  • snoc of x and (a b c) is the cons of the car of (a b c) with the snoc of x with the cdr of (a b c)
(defun snoc (x the-list)
  (cond
    ((null the-list) (cons x the-list))
    (T               (cons (car the-list) (snoc x (cdr the-list))))))
(defun sum (x)
  (if (null x)
    0
    (+ (car x) (sum (cdr x)))))
> (iota 6)
(1 2 3 4 5 6)
> (iota 0)
()
(defun iota (n)
  (cond
    ((= n 0) ())
    (T       (snoc n (iota (- n 1))))))
> (evenp 5)
NIL
> (evenp 6)
T
> (numberp 'FOUR)
NIL
> (numberp 4)
T
> (numberp '(4))
NIL

Keyword Arguments

Arguments are sometimes given names! This is generally done either to provide flexibility or to add integrity to the code.

Rest Arguments

A “rest” parameter will bind any “left over” items into a list for subsequent use in the function. (demo next time)

(defun demorest (f &rest r)
  (format T "F = ~A~%" F)
  (format T "R = ~A~%" R))

> (demorest 1 2 3 4)
F = 1
R = (2 3 4)
NIL
> (demorest 'A 'B 'C 'D 'E 'F)
F = A
R = (B C D E F)
NIL

(defun name (&rest r)
  r)
> (name 'craig 'graci)
(CRAIG GRACI)
> (name 'jose 'aldo 'silva 'da 'costa)
(JOSE ALDO SILVA DA COSTA)

Mapping Functions

;; mapcar which accepts 1 list argument ;;
(defun apply-to-all-1 (fun lst)
  (let ((f (car lst))
        (r (cdr lst)))
    (cond
      ((null lst) ())
      (T          (cons (funcall fun f)
                        (apply-to-all-1 fun r))))))
; demo
> (apply-to-all-1 #'car  '((A B) (C D) (E F)))
(A C E)
> (apply-to-all-1 #'cadr '((A B) (C D) (E F)))
(B D F)
> (apply-to-all-1 #'iota (iota 5))
((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5))

;; mapcar which accepts 2 list arguments ;;
(defun apply-to-all-2 (fun lst1 lst2))
; demo
> (apply-to-all-2 #'expt '(1 2 3 4 5) '(2 2 2 2 2))
(1 4 9 16 25)
> (apply-to-all-2 #'list '(a b c d) '(1 2 3 4))
((A 1) (B 2) (C 3) (D 4))
> (apply-to-all-2 #'cons '(a b c d) '(1 2 3 4))
((A . 1) (B . 2) (C . 3) (D . 4))

In general, we use mapcar.

mapcar:

  • takes
    • a function of N arguments
    • N lists of equal lengths
  • applies the function to each of the
    • first elements of the lists
    • second elements of the lists
    • …
    • last elements of the lists
  • returns a list of the values computed
[1]> (mapcar #'- '(1 2 3))
(-1 -2 -3)
[2]> (mapcar #'- '(1 2 3) '(4 5 6))
(-3 -3 -3)
[3]> (mapcar #'- '(1 2 3) '(4 5 6) '(7 8 9))
(-10 -11 -12)

Association Lists

An association list (a-list) is a list of cons-cell objects, each of which represents a key/datum pair by means of its car and its cdr – or by means of its cdr and its car … depending on how you look at it.

Remark: The function mapcar provides a nice mechanism for constructing a-lists. The functions assoc and rassoc are nice functions for referencing data in a-lists.

Notes:

1) The functions assoc and rassoc make use of the function eq by default.

2) In real applications with large data sets you tend to use hash tables rather than a-lists.

Property Lists

A property list or p-list is a simply a list of pairs associated with a symbol.

Functions that tend to be used for p-list processing:

  • get
    • satan’s evil transmutation function (setf)
  • symbol-plist
  • remprop

State Spaces

An object is a set of properties together with a set of behaviors.

The state of an object is a set of bindings for the properties of the object.

A world is a collection of objects.

The state of a world is a set of bindings for all of the objects in the world.

The state space of an object is the set of all possible sets of bindings for the properties of the object.

The state space of a world is the set of all possible sets of bindings for all of the all of the objects in the world.

A state space operator is an operator that maps one state of the world to another state.

A state space program description is a triple consisting of

  1. I: a set of initial states
  2. G: a set of goal states
  3. O: a set of state spaces operators

All in the context of S, some state space that fits the program.

A state space problem solution is a triple consisting of

  1. i: one of the initial states in I
  2. g: one of the goal states in G
  3. x: a finite sequence of state space operators that transforms i into g

A state space search is the problem of finding a sequence of state space operators that transforms an initial state into a goal state.

Example: Three coins problem

Statement: Given three coins arranged (T T H), make them all the same in exactly three moves, where a move amounts to turning a coin over.

Objects of “the” state space:

The state space will consist of four objects, each with just one property

  • coin L (leftmost coin): with one property – its top face (which will have either T or H for its value)
  • coin C (centermost coin)
  • coin R (rightmost coin)
  • counter V, which takes on non-negative values

Representation of a state:

We will represent in the form <LCR V>, where each of L, C, and R is either T or H, and V is a non-negative integer.

  • initial state set: I = { <TTH 0> }
  • state space operators: O = { OL, OC, OR }
    • OL = <LCR V> -> <L'CR V+1>
    • OC = <LCR V> -> <LC'R V+1>
    • OR = <LCR V> -> <LCR' V+1>
  • goal state set: G = { <TTT 3>, <HHH 3> }

3 coin problem

State Space Search

Two basic forms

  • Breadth-first search (BFS)
  • Depth-first search (DFS)

Implementation idea

In either case, the idea is to maintain two lists of noes, an unexplored lists, which nodes not yet examined are placed and an explored list, on which nodes that have been examined are placed.

To find a solution (i, g, x) to a state space problem defined by (I, G, O) do…

  • establish a list of unexplored nodes called unexplored, and place all of the initial states on it.
  • establish a list, called explored and bind it to the empty list.
  • perform the following iteration:
repeat
if (UNEXPLORED is empty) then
    report "NO SOLUTION"
    BREAK
end

bind ESTATE to the next UNEXPLORED state

if (ESTATE has been explored) then
    CONTINUE
else if (ESTATE is the goal) then
    report "SOLUTION FOUND"
    return ESTATE
else
    generate the children of ESTATE, and call them KIDS
    place kids on UNEXPLORED
    place ESTATE on EXPLORED
end

Prior to iterating:

  • e - nil
  • c - nil
  • u - (<TTH 0>)
  • x - nil

After 1 pass:

  • e - <TTH 0>
  • c - (<HTH 1>, <TTH 1>, <TTT 1>)
  • u - (<HTH 1>, <TTH 1>, <TTT 1>)
  • x - (<TTH 0>)

After 2 passes:

  • e - <HTH 1>
  • c - (<HHH 2>, <THH 2>, <HTT 2>)
  • u - (<TTH 1>, <TTT 1>, <HHH 2>, <THH 2>, <HTT 2>)
  • x - (<TTH 0>, <HTH 1>)

BFS vs DFS (implementation)

Breadth-first search is implemented by maintaining unexplored as a queue (first in, first out list, or FIFO).

Depth-first search is implemented by maintaining unexplored as a stack (last in first out list, or LIFO).

The Water Jug Problem

A simple instance…

You have a sink, with an unlimited supply of water. You have two unmarked jugs, a 4-gallon jug, and a 3-gallon jug. How can you get exactly two gallons in the four gallon jug?

Solution:

  • fill 3 gallon jug with sink
  • empty 3 gallon jug into 4 gallon jug
  • fill 3 gallon jug with sink
  • fill 4 gallon jug with 3 gallon jug
  • empty 4 gallon jug into sink
  • empty 3 gallon jug into 4 gallon jug

State space representation of the water jug problem.

Let x represent the number of gallons in the 4-gallon jug. Let y represent the number of gallons in the 3-gallon jug.

The state space points: { (x, y) | x ϵ { 0, 1, 2, 3, 4 } and y ϵ { 0, 1, 2, 3 } }.

Initial state set: { (0, 0) }

Goal state set: { (2, 0), (2, 1), (2, 2), (2, 3) }

Operations:

  1. Fill jug one:

    (x, y) | x < 4 -> (4, y)

  2. Fill jug two:

    (x, y) | y < 3 -> (x, 3)

  3. Empty jug one:

    (x, y) | x > 0 -> (0, y)

  4. Empty jug two:

    (x, y) | y > 0 -> (x, 0)

  5. Pour from jug two to fill jug one:

    (x, y) | x + y >= 4 and x < 4 and y > 0 -> (4, y-(4-x))

  6. Pour from jug one to fill jug two:

    (x, y) | x + y >= 3 and x > 0 and y < 3 -> (x-(3-y), 3)

  7. Dump from jug two into jug one:

    (x, y) | x < 4 and y > 0 -> (x+y, 0)

  8. Dump from jug one into jug two:

    (x, y) | x > 0 and y < 3 -> (0, x+y)

I like to think of there being 2 general functions:

  1. fillFrom(x, y), where x,y can be either jug, and y can also be the sink

  2. emptyInto(x, y), where x,y can be either jug, and x can also be the sink

CLOS

The Common Lisp Object System.

Modelling a coin.

(defclass coin ()
  ((face    :accessor coin-face    :initarg :face :initform 'h)
   (history :accessor coin-history                :initform ())))

(defmethod display ((c coin))
  (format t "[~A,~A]"
    (write-to-string (coin-face    c))
    (write-to-string (coin-history c))))

(defmethod to-string ((c coin))
  (format nil "[~A,~A]"
    (write-to-string (coin-face    c))
    (write-to-string (coin-history c))))

(defmethod flip ((c coin))
  (setf (coin-face c)
        (nth (random 2) '(h t)))
  (setf (coin-history c)
        (append (coin-history c) (list (coin-face c))))
  nil)

(defmethod turn ((c coin))
  (if (eq (coin-face c) 't)
    (setf (coin-face c) 'h)
    (setf (coin-face c) 't))
  (setf (coin-history c)
        (append (coin-history c) (list (coin-face c))))

  nil)

(defmethod forget ((c coin))
  (setf (coin-history c) ()))

(defmethod flip-for-h ((c coin))
  (flip c)
  (when (not (eq (coin-face c) 'h))
    (flip-for-h c)))

(defmethod flip-for-hh ((c coin))
  (flip-for-h c)
  (flip c)
  (when (not (eq (coin-face c) 'h))
    (flip-for-hh c)))

(defmethod flip-for-hhh ((c coin))
  (flip-for-hh c)
  (flip c)
  (when (not (eq (coin-face c) 'h))
    (flip-for-hhh c)))

(defmethod flip-for-n-h ((c coin) (n integer))
  (if (= n 1)
    (flip-for-h c)
    (progn
      (flip-for-n-h c (1- n))
      (flip c)
      (when (not (eq (coin-face c) 'h))
        (flip-for-n-h c n)))))

(defun times-to-h ()
  (let ((c (make-instance 'coin)))
    (flip-for-h c)
    (length (coin-history c))))

(defun times-to-h-iter (i acc)
  (if (> i 0)
    (times-to-h-iter (1- i) (+ acc (times-to-h)))
    acc))

(defun times-to-h-avg (N)
  (/ (times-to-h-iter N 0)
     N))

Genetic Algorithms

A Darwinian process is a process involving replication, selection, and variation.

Universal Darwinism is simply the idea that Darwinian processes explain/create a wide range of phenomena.

Evolutionary programming is a style of computer programming inspired by Darwin’s theory of evolution by natural selection.

A genetic algorithm is an evolutionary program in which individuals are data structures of some sort.

A genetic program is an evolutionary program in which individuals are computer programs of some sort.