LISP Primitive

Atoms:

Numeric atoms: numbers, e.g. 3, 1.54
Symbolic atoms: symbols, e.g. John, Mary

Lists:

• a list of atoms

  
  

• In Lisp form:
  (John is a policeman)

• To associate a name with the list

  • (setq friends '(dick jane sally))
    (dick jane sally)

  • friends
    (dick jane sally)

• Both atoms and lists are called symbolic expressions

Lisp Procedures

• prefix notation used

• all Lisp procedures are functions (as in C)
  name of procedure
  Ô argument to procedures

  • (+ 3 4)
    7

  • (* 9 3)
    27

• A procedure supplied by Lisp itself is called a primitive
  e.g. setq, + etc.

• A procedure is itself a list (of procedure definition)

• Program and data are of the same form in list. (hence program can be stored as data.)

• In Lisp, a procedure is to be "evaluated". An expression is called a form when it is meant to be evaluated.
  The first element generally is the name of a procedure that can be used in the evaluation process.

• To suppress evaluation, use a (forward) quote ('), e.g.

  • (setq friends '(dick jane sally))

  • (setq friends (quote (dick jane sally)))

  This will suppress the evaluation of
  (dick jane sally)
  and return the original list. However,

  • (setq friends (dick jane sally))

  will cause (dick jane sally) to be evaluated, i.e. will interpret "dick" as procedure name and "jane sally" as arguments.

Basic Lisp Primitives

1. car - get the first element of the list.

   • (car '(john is a policeman)
     john

   • (car '((john is) (a policeman)))
     (john is)

2. cdr - return the tail of the list (i.e. exclude the first element)

   • (cdr '(john is a policeman))
     (is a policeman)

   • (cdr '((john is) (a policeman))
     ((a policeman))

3. combination of car & cdr:

   • (caar x) º (car (car x))

   • (cadr x) º (car (cdr x))

   • (caaar x) º (car (car (car x)))

   • (cdadr x) º (cdr (car (cdr x)))

   getting the 1^st element (car x)
   getting the 2^nd element (cadr x)
   getting the 3^rd element (caddr x) ...

Arithmetic Operations

• + - * /

  • (+ 3 2)
    5

  • (- 5 3)
    2

  • (* 4 2)
    8

  • (/ 8 2)
    4

  truncate, rem : integer division

  (setq quotient (truncate 14 4))
  3

  (setq remainder (rem 14 4))
  2

  
  
  

  Assigment of Atoms

  symbolic atoms has values

  (setq l '(a b)) evaluate '(a b) and assign the result to l
  (a b)

  (setf l '(a b)) setf can be used with other data structures
  (a b)

  
  
  

  Other list operations

  append - append a list to another list

  (append '(a b) '(c d))
  (a b c d)

  (append '(a b) nil)
  (a b)

  list - form list from elements

  (list '(a b))
  ((a b))

  (list '(a b) '(c d))
  ((a b) (c d))

  cons - construct list from an element and tail

  (cons 'a '(b c))
  (a b c)

  (cons '(a b) '(c d))
  ((a b) c d)

  
  
  

  before cons:
  after cons:
  
  How about (cons 'a 'b) ?

  
  

  (cons 'a 'b)
  (a . b) dotted pair

  (car '(a . b))
  a

  (cdr '(a . b))
  b

  length - counts the number of top-level elements in a list.

  (length '(a b))
  2

  (length '((a b) (c d)))
  2

  reverse - turn around the top level elements

  (reverse '(a b))
  (b a)

  (reverse '((a b) (c d)))
  ((c d) (a b))

  subst - substitute all occurrences of the old expression by the new expression.

  (subst 'a 'b '(a b c))
  (a a c)

  (subst 'a 'b '((a b) (b a)))
  ((a a) (a a))

  last - return a list containing only the last element of the list.

  (last '(a b c))
  (c)

  (last '((a b) (c d)))
  ((c d))

  How to get the last element?

  
  
  

  The Lisp Evaluation Process

  The Lisp evaluation process can be expressed in pseudo codes: PROC EVAL
  if S is an atom then
  if S is a number then
  return the number
  else
  return the value of S
  end if
  else
  if QUOTE is the first element of S then
  return the 2^nd elment of S
  else
  if the 1^st element of S a name indicating
  that special handling is needed then
  do not evaluate the arguments
  (e.g. setq do no eval the 1^st element)
  else
  Use EVAL on all the element of S other
  than the 1^st element.
  Apply 1^st element of S, a procedure, to the
  resulting values and return the new value.
  end if
  end if
  end if
  Lisp Functions

  A pure functional programming language should not have side effects on function calls, i.e. nothing is changed other than a value is returned by the function.

  In Lisp, many functions will cause side effects, i.e. it changes something besides the returned value, e.g. setq.

  Procedure abstraction:
  process of constructing new procedure by combining existing ones.
  (defun <procedure name> (<param1>...<param n>)
  <procedure body>)

  e.g.

  (defun f-to-c (temp)
  (/ (- temp 32) 1.8))
  f-to-c

  (f-to-c 100)
  37.778

  Binding is the process of preparing memory space for parameter value. Parameters are bound when procedures are called.

  The process of establishing a value is called assignment. Lisp always assigns values to parameters immediately after binding.

  Argument passing mechanism is thus call-by-value.

  e.g.

  (setq value 100)
  100

  (defun f-to-c (temp)
  (setq temp (- temp 32))
  (/ temp 1.8))
  f-to-c

  (f-to-c value)
  37.778

  value
  100

  Predicates

  a procedure that returns a value that signals true (T) or false (nil).

  Build-in predicates:

  (atom x) 0 whether x is an atom

  (listp x) 0 whether x is a list

  (equal a b) 0 whether a,b are the same

  (null x) 0 whether x is nil

  (= a b) 0 whether 2 numbers a,b are equal

  (member a l) 0 whether an atom a is an element of list l.
  [instead of returning T, member returns the fragment of the list that begins with the first argument]

  (member 'b '(a b c))
  (b c)

  (numberp x) 0 whether x is a number

  (> a b) 0 whether number a>b?

  (< a b) 0 whether number a<b?

  (zerop x) 0 whether number x=0?

  (minusp x) 0 whether number x<0?

  (evenp x) 0 whether number x is even?

  
  
  

  Logical Operators

  not - not return T if argument if nil, otherwise return nil.

  • (not T)
    nil

  • (not nil)
    T

  • (not 'dog)
    nil

  and - and evaluates arguments from left to right. If a nil is encountered, nil is returned immediately (lazy evaluation). Any remaining arguments are not evaluated. Otherwise, and returns the value of its last argments.

  (and (member 'dog '(dog cat))
  (member 'cat '(dog cat)))
  (cat)

  Remark: Be careful if your program relies on side effects of evaluation since not all arguments are evaluated.

  or - or evaluates its arguments from left to right. If something other than nil is encountered, it is returned immediately. Any remaining arguments are not evaluated. Otherwise or return nil.

  (or (member 'dog '(dog cat))
  (member 'cat '(cat mouse)))
  (dog cat)

  
  
  

  Conditionals

  (cond (<test1> ... <result1>)
  (<test2> ... <result2>)
  ...
  (<testn> ... <resultn>))

  search through the clauses, evaluate only the test-form until one is found whose value is non-nil. The other form of the successful clause are evaluated. The value of the last form is returned.

  all forms standing between first and last form in a clause must be there only for accomplishing side effects.

  If no successful clause, cond returns nil

  If the successful clause consists of only one form, the value of that form is returned (i.e. test and result form can be the same)
  Example:

  (cond (l 'not-empty)
  (t 'empty))

  (defun our-adjoin (item bag)
  (cond ((member item bag) bag) ; already in
  (t (cons item bag)))) ; add item in front
  our-adjoin
  [Common Lisp provide a function adjoin which perform this function]

  Bounded Variables & Free Variables

  lambda binding: relating arguments to parameters on entering a procedure

  (defun screwy-increment (param) ; param bound
  (setq param (+ param 10))
  (setq free param)) ; free is free
  screwy-increment

  (setq param 15)
  15

  (setq free 10)
  10

  (setq argument 10)
  10

  (screwy-increment argument)
  20

  free
  20

  param
  15

  argument
  10

  Notes:

  The value of argument never changes, not even inside screwy-increment.

  The value of free is permanently altered

  param is temporarily changed:
  becomes 10 on entry to screwy-increment
  become 20 on setq
  restored to 15 on exit

  Remark:

  All symbols that appear in the procedure's parameter list is bounded.

  

  Lexical Scoping

  A collection of binding is called environment.

  dynamic scoping (in older Lisp, e.g. Franz Lisp)

  value of free variable determined by the activation environment (the environment in force when the procedure requiring the free-variable value is called)

  lexical scoping (in Common Lisp)

  value of free variable determined by the definition environment (the environment in force when the procedure requiring the free-variable value was defined).

  Example:

  (defun test (x)
  (let ((name x))
  ((princ name) ;;print name
  (terpri) ;;print new line
  (test1)))
  test

  (defun test1 ()
  (princ name)
  (terpri))
  test1

  (setq name '(a b))
  (a b)

  (test '(a b c))

  Lexical Scoping:
  (a b c)
  (a b)

  Dynamic Scoping
  (a b c)
  (a b c)

  Remark: Common Lisp uses Lexical Scoping unless the variable is declared special:

  (declare (special name))

  Procedure names can be used as arguments too.

  (setq banking-procedure 'cal-interest)
  cal-interest

  (defun cal-interest (balance)
  (* balance 0.1)
  cal-interest

  (funcall banking-procedure 100.0)
  10.0

  (funcall 'cal-interest 100.0)
  10.0

  (setq account-type 'normal)
  normal

  (funcall (cond ((equal account-type 'normal)
  'cal-interest)
  ((equal account-type '90-days)
  'cal-high-interest)
  (T 'cal-no-interest))
  100.0)
  10.0

  
  
  

  Let Construct (local variables)

  (let ((<parameter1> <initial-value1>)

  (<parameter2> <initial-value2>)

  ...

  (<parametern> <initial-valuen>))

  <let body>)

  let arranges for parameters to be bounded and assigned.

  example: (a modification of adjoin):

  (defun augment (first second)
  (let ((item first)
  (bag second))
  (cond ((listp first)
  (setq item second bag first)))
  ;; item<-second, bag<-first
  (cond ((member item bag) bag)
  (t (cons item bag)))))
  argument

  Another version:

  (defun augment (first second)
  (let ((item (cond ((listp first) second)
  (t first)))
  (bag (cond ((listp second) second)
  (t first))))
  (cond ((member item bag) bag)
  (t (cons item bag)))))
  augment

  The parameters of let is assigned in parallel.

  if want to have assignment sequentially, use let* instead.

  (defun augment (first second)
  (let* ((item (cond ((listp first) second)
  (t first)))
  (bag (cond ((equal item second)
  first)
  (t second))))
  (cond ((member item bag) bag)
  (t (cons item bag)))))
  augment

  DO-loops

  do loops / for loops in other programming languages

  (do ((<param1> <initial-value1> <next-value1>)
  (<param2> <initial-value2> <next-value2>)
  ...
  (<paramn> <initial-valuen> <next-valuen>))
  (<terminating condition> <return value>)
  <do-body>)

  

  e.g. calculating mⁿ using iteration.

  (defun our-expt (m n)
  (do ((result 1 (* m result))
  (exponent n (1- exponent)))
  ((zerop exponent) result))) ; no do-body
  our-expt

  Similar to let, do perform assignment in parallel.

  do* perform assignments sequentially

  (defun our-expt (m n)
  (do* ((result m (* m result))
  (exponent n (1- exponent))
  (counter (1- exponent) (1- exponent)))
  ((zerop counter) result)))
  ;; This version saves 1 iteration and uses
  ;; sequential assignment rather than parallel

  Recursion

  e.g. Fibonacci number:

  f(n) = f(n-1) + f(n-2), n>1
  1, n=0
  0, n=1

  (defun fibonacci (n)
  (cond ((= n 0) 1)
  ((= n 1) 1)
  (t (+ (fibonacci (- n 1))
  (fibonacci (- n 2))))))
  fibonacci

  (defun our-member (item l)
  (cond ((null l) nil) ;list empty?
  ((equal item (car l)) l) ;elt1 win?
  (t (our-member item (cdr l)))))
  our-member

  
  
  

  

  Tail Recursion

  A procedure is said to be tail recursive if the value returned is either something computed directly or the value returned by a recursive call.

  A tail recursive procedure does nothing with the value returned by the recursive call, it need not remember anything.

  Example

  ;; procedure "trim-tail" trims off the first n
  ;; elements of a list and return the rest
  ;;
  (defun trim-tail (l n)
  (cond ((zerop n) l)
  (t (trim-tail (cdr l) (1- n)))))
  trim-tail

  > (trim-tail '(a b c d e f) 3)
  (d e f)

  trim-tail is a tail-recursive procedure

  a procedure using tail recursion and "call-by-value" can be replaced by one without recursion (using iteration instead)

  hence tail-recursion can be efficient provided the system can convert it to an iterative one.

  ;; this version of trim-tail uses iteration
  ;; instead of recursion
  ;;

  (defun trim-tail (l n)
  (do ((aux-list l (cdr aux-list))
  ((aux-n n (1- aux-n)))
  ((zerop aux-n) aux-list)))

  You may need to introduce auxiliary function to get a tail recursive procedure.

  
  
  

  

  ;; this procedure returns a list of the first n
  ;; elements. It is not tail recursive

  (defun trim-head (l n)
  (cond ((zerop n) nil)
  (t (cons (car l) (trim-head (cdr l)
  (1- n))))))
  trim-head

  > (trim-head '(a b c d e f) 3)
  (a b c)

  In order to achieve tail recursion, we must remember partial results.

  the partial result can be passed as argument to recursive procedure and new result is returned.

  ;; this version uses tail recursion
  ;;

  (defun trim-head (l n)
  (trim-aux l nil n))
  (defun trim-aux (l result n)
  (cond ((zerop n) (reverse result))
  (t (trim-aux (cdr l)
  (cons (car l) result)
  (1- n)))))

  Recursion can be used to analyze nested expressions:

  ;; counts atoms at all level of nesting
  (defun count-atom (l)
  (cond ((null l) 0)
  ((atom l) 1)
  ((+ (count-atoms (car l))
  (count-atoms (cdr l))))))

  
  
  

  

  Iteration on a list

  to apply a procedure to a whole list 0 MAPCAR.

  (mapcar 'oddp '(1 2 3))
  (T nil T)

  oddp is applied on each element of (1 2 3) and the result is a list.

  The procedure can take more than one argument:

  (mapcar 'equal '(1 2 3)
  '(3 2 1))
  (nil T nil)

  To use element in a list as argument to a procedure 0 apply

  (apply '+ '(1 2 3)) [º (+ 1 2 3)]
  6

  In general:
  (apply <procedure description>
  <list of arguments>)

  Example:

  count-atom can be re-written using mapcar & apply:

  (defun count-atom (l)
  (cond ((null l) 0)
  ((atom l) 1)
  (t (apply '+ (mapcar 'count-atom
  l)))))

  
  
  

  MAPCAN

  acts as if a combination of mapcar & append.

  Example:

  Suppose parents is a procedure that return a list of parents of a person. Write a procedure ancestors to find all ancestors of a person.

  
  
  

  
  
  

  (defun ancestors (person)
  (let ((p (parents person)))
  (cond ((null p) nil)
  (t (append p
  (mapcar 'ancestor p))))))

  
  
  

  if (parents William) = (John Sara)
  (parents Sara) = (Issac Mary)

  and nothing else known, then result of

  (ancestors William) =
  (John Sara nil (Issac Mary nil nil))

  which is not the desired result.

  The correct version should be:

  (defun ancestors (person)
  (let ((p (parents person)))
  (cond ((null p) nil)
  (t (append p
  (mapcan 'ancestor p))))))

  
  
  

  Association list

  a list of embedded sublists, in which the first element of each sublist is a key.

  (setq brick-a '((color red)
  (supported-by brick-b)
  (is-a brick)))
  ((color red)(supported-by brick-b)(is-a brick))

  the function assoc moves down the association list until it finds a sublist whose car(1st element) is equal to the key.

  (assoc 'color brick-a)
  (color red)

  (assoc 'size brick-a)
  nil

  
  
  

  Properties

  symbols can have properties

  to retrieve property values of a symbol 0 get

  (get 'pyramid-d 'color)
  red

  (get 'pyramid-d 'supported-by)
  brick-b

  (get 'pyradmid-d 'size)
  nil

  when nil is returned, cannot distinguish whether it is caused by
  the property value is nil or no such property exist.

  to write a property value, use setf

  (setf (get 'brick-a 'size) 'large)
  large

  (get 'brick-a 'size)
  large

  properties can be removed by remprop

  (remprop 'brick-a 'size)
  T

  (get 'brick-a 'size)
  nil

  Property lists and association list have similar function.

  Programmer to design which is more convenient.

  Combination can be used.

  (setf (get 'john 'personal-information)
  '((name (john chan)) (age 25)
  (sex M) (marital-status single)))

  (setf (get 'john 'hobby)
  '(fishing chess swim))

  (assoc 'age
  (get 'john 'personal-information))

  (member 'mahjong (get 'john 'hobby))

  Data Abstraction

  Access Procedures:

  data constructor

  data selector

  data mutator

  example:

  constructor:

  (setf (get 'brick-a 'a-list)
  '((color red)
  (supported-by brick-b)
  (is-a brick)))

  selector:

  (cadr (assoc 'color (get 'brick-a 'a-list)))

  mutator:

  (setf (cdr (assoc 'color
  (get 'brick-a 'a-list)))
  '(blue))

  This is not readable and difficult to read and modify. Should use:

  constructor:

  (defun make-brick (object color support)
  (setf (get object 'a-list)
  (list (list 'is-a 'brick)
  (list 'color color)
  (list 'supported-by support)))

  selector:

  (defun brick-color (object)
  (cadr (assoc 'color
  (get object 'a-list))))

  mutator:
  (defun set-break-color (object color)
  (setf (cdr (assoc 'color
  (get object 'a-list)))
  (list color)))

  (make-brick 'brick-b 'red 'brick-a)
  ((is-a brick)(color red)(supported-by 'brick-a))

  (brick-color 'brick-b)
  red

  (set-brick-color 'blue)
  (blue)

  data abstraction is the process of building abstract data types.

  Isolate programmers from representational details by hiding existing low-level data storage, modification and retrieval primitives underneath a layer of high level constructor, selector and mutator procedures collectively called access procedures.

  Make program easier to modify

  
  
  

  Structures

  collection of fields and field values.

  specify particular field and default values

  allow to access individual fields and modify

  not allow to inspect the internal representation (data abstraction)

  (defstruct (block) ;define the block data type
  (color nil) ;field color: default nil
  (directly-supports nil)
  (is-a 'brick)) ;field is-a: default brick

  block

  Lisp provide different access procedures:

  (setq example (make-block))
  #<block 8a47:5284> ;a block is made

  (block-color example)
  nil

  (setf (block-color example) 'blue)
  blue

  (setq example2 (make-block :color 'red
  :is-a 'pyramid))
  ;;changing the default values.

  Lambda Notation

  nameless function

  example:

  (setq groceries '(chocolate milk apple
  bread butter pear steak))

  (defun fruitp (x)
  (equal (get x 'a-kind-of) 'fruit))

  (mapcar 'fruitp groceries)
  (nil nil T nil nil T nil)

  if fruitp is not used elsewhere, no need to create a permanently stored function.

  (mapcar #'(lambda (x)
  (equal (get x 'a-kind-of) 'fruit))
  groceries)
  (nil nil T nil nil T nil)

  #' 0 lexical scoping
  ' 0 dynamic scoping

  no difference if no free variable appears in the function
  
  
  

  Example: Find the number of fruits in groceries

  (defun count-fruit (groceries)
  (apply '+ (mapcar #'(lambda (x)
  cond((equal (get x 'a-kind-of)
  'fruit) 1)
  (t 0)))
  groceries)))
  
  
  

  Combination of lambda with remove-if & remove-if-not:

  (remove-if 'fruitp groceries)
  (chocolate milk bread butter steak)

  (remove-if-not 'fruitp groceries)
  (apple pear)
  
  
  

  remove-if #'(lambda (x)
  (equal (get x 'a-kind-of) 'fruitp))
  groceries)
  (chocolate milk break butter steak)

  filtered accumulation:
  lambda helps interface procedures to argument lists:

  (defun count (type l)
  (cond ((atom l)
  (cond ((equal (get l 'a-kind-of)
  type)
  1)
  (t 0)))
  (t (apply '+ (mapcar 'count l)))))
  Ô
  count expects 2 arguments!

  Cannot introduce auxiliary function:
  (defun count1 (l)
  (count type l))
  since lexical scoping is used.

  Can use lambda instead:
  (defun count (type l)
  (cond ((atom l)
  (cond ((equal (get l 'a-kind-of)
  type)
  1)
  (t 0)))
  (t (apply '+ (mapcar #'(lambda (e)
  (count type e))
  l)))))

  since lambda is defined within count, according to lexical scoping rule, type referes to "types of count".

  
  
  

  

  funcalls

  the first argument is function, the rest are other arguments

  (fruitp 'apple)
  T

  (funcall 'fruitp 'apple)
  T

  (funcall #'(lambda (x)
  (equal (get x 'a-kind-of)
  'fruit))
  'apple)
  T
  
  
  

  Printing and Reading in Lisp

  print evaluates its single argument and prints it on a new line.

  Returns the result of evaluation

  (setq groceries '(apple orange))
  (apple orange)

  (print groceries)
  (apple orange)
  (apple orange)

  special characters such as "(", " " (blank) can be used in symbols by escape character "\" or enclose by a pair of "|".

  (setq S1 'make\ block)
  make\ block

  (setq S2 '|symbol with (blanks)|)
  |symbol with (blanks)|

  special symbols can be printed using princ

  (princ S1) make block
  make block
  make\ block

  (princ S2)
  symbol with (blanks)
  |symbol with (blanks)|

  Start a new line 0 terpri

  Formatted Printing

  Example:

  (defun table-print (items columns)
  (terpri) ;begin of line
  (table-print1 items columns 0))

  (defun table-print1 (items columns n)
  ((cond ((null items) t) ;stop when all times printed
  ((< n (car column)) ; check current position
  (table-print1 items ;repeat if not
  columns ;at column specified
  (+ n 1)))

  (t (princ (car items)) ;print next atom
  (table-print1 (cdr item)
  (cdr columns)
  (+ n (length symbol-name
  (car items))))))))

  (defun time-table()
  (let ((tabs '(0 12 24))
  (table-print '(concord lincoln waltham) tabs)
  (table-print '(6-11 6-17 6-29) tabs)))

  
  
  

  Reading

  when (read) is encountered, Lisp stops and wait for the user to type an expression.

  The expression, without evaluation, becomes the value of (read)

  (read)
  (john is a policeman)
  (john is a policeman)

  (setq sentence (read))
  (john is a policeman)
  (john is a policeman)

  sentence
  (john is a policeman)

  Lisp also provide many I/O functions, including file operations.

  Lisp provide functions on strings. See manual for detail.

  File Operations

  load lisp codes from file

  (load "prog.lsp")

  reading and writing files

  (with-open-file
  (variable filename :direction :input/output
  <expressions>)

  e.g. read the first expression from "foo.dat"

  (with-open-file
  (alpha "foo.dat" :direction :input)
  (read alpha))

  print integer 1 to 10 into file "baz.dat"

  (with-open-file
  (beta "baz.dat" :direction :output)
  (do ((n 1 (+ n 1)))
  ((> n 10))
  (print n beta)))

  Format

  ~S 0 print (without new line)
  ~A 0 princ
  ~% 0 terpri

  (setq X 'IX Y '|i x|)

  (format *standard-output*
  "The value of ~S is ~A.~%"
  The value of IX is i x.

  

  Optional Parameters

  the value of the parameters is nil if the optional parameter is not provided.

  (defun punctuate (l &optional mark)
  (cond ((not mark) (append l '(period)))
  (t (append l (list mark)))))

  (punctuate '(Is this a test) 'question-mark)
  (Is this a test question-mark)

  (punctuate '(This is a test))
  (This is a test period)

  default value can be specified in argument declaration

  (defun punctuate (l &optional (mark 'period))
  (append l (list mark)))

  There can be any number of optional parameters

  The optional parameters must be grouped at the end

  all optional parameters can be grouped in one list by &rest

  (defun punctuate (l &rest marks)
  (cond ((null marks) (append l '(period)))
  (t (append l marks))))

  (punctuate '(this is an example)
  'so 'to 'speak 'exclamation-mark)

  ;value of mark will be (so to speak exclamation-mark

  (This is an example so to speak exclamation-mark)

  
  
  

  Keyword Parameters

  argument must be supplied in a fixed order

  keyword parameters allow argument to be defined by keywords (hence no fixed order)

  (defun limit (n &key lower-bound upper bound)
  (max lower-bound (min n upper-bound)))
  limit

  (limit -4 :lower-bound 1 :upper-bound 10)
  1

  (limit -4 :upper-bound 10 :lower-bound 1)
  1

  some primitives in Lisp takes keyword parameters

  e.g.

  (member n l
  :test #'(lambda (x y)
  (< (abs (- x y)) 3)))

  keyword parameters are already optional ones

  (defun limit (n &key (lower-bound 1)
  (upper-bound 10))
  (max lower-bound (min n upper-bound)))
  limit

  (limit -4)
  1

  
  
  

  Macro

  macro can extend the language

  do not evaluate their arguments

  macro is efficient, because no function call required.

  (defmacro <macro-name> <parameter list>
  <macro-body>)

  e.g. (defmacro demo (x) (print x))
  demo
  (setq this 'value-of-this)
  value-of this
  (demo this) ;macro do not evaluate "this"
  this ;x has a value "this" and
  value-of-this ;"this" is printed by (print x)
  ;value returned is evaluated

  (defun demo1 (x) (print x))
  (demo1 this)
  value-of-this
  value-of-this

  
  
  

  Backquotes `

  like quotes ', except that any comma that appear within the scope of the backquote have the effect of unquoting the following expression.

  (setq variable 'example)
  example

  `(this is an ,variable)
  (this is an example)

  (setq variable '(more difficult example))
  (more difficult example)

  `(this is a ,variable)
  (this is a (more difficult example))

  `(this is a ,@variable)
  (this is a more difficult example)

  like filling in templates and is useful in macro definition.

  (defmacro our-if (test success-result
  &optional failure result)
  `(cond (,test ,success-result)
  (t ,failure-test)))
  our-if

  (our-if (malep x) 'male 'female)

  results in the following intermediate form:

  (cond ((malep x) 'male)
  (t 'female))

  ;;since test have the value (malep x)
  ;;unquoting test resulting in test being
  ;;evaluated and get a value (malep x)
  ;;similar for others

  Notes: macro cannot be passed as argument (while functions can). Hence cannot use mapcar, funcall etc. on macros.

  e.g. many system do not provide nested car/cdr beyond 5 levels, i.e. no (caaddr x) etc. Can use macro to define such construct:

  (defmacro caaddr (x)
  `(caar (cddr ,x)))

  backquote also simplifies printing (another example of template filling):

  (setq support 'brick-a)
  brick-a
  (setq kruft 'brick-b)
  brick-b
  (print `(,support supports ,kruft))
  brick-a supports brick-b
  brick-a supports brick-b

  
  
  

  Array

  Lisp's array is like C, start from 0 to n-1.

  example:
  Create a 2-D array (0:1023, 0:1023)

  (setq image (make-array '(1024 1024)))

  (setf (aref image 314 271) 88)

  (aref image 314 271)
  88

  example: print-image, a procedure that prints out the elements of a 2-D array, passed as the single argument

  (defun print-image (image)
  (let ((n (array-dimension image 0))
  ((m (array-dimension image 1)))
  (terpri)
  (do ((i 0 (+ i 1))) ((= i n))
  (do ((j 0 (+ j 1))) ((= j m) (terpri))
  (princ (aref image i j))
  (princ '| |))))) ;print a blank

  
  
  

  

  Case-Study: Search using Lisp

  Depth-first search

  

  0 depth first search
  Implementation:

  keep a node queue

  get a node from the queue

  expand the node

  return the node to the queue

  
  
  

  
  
  

  
  
  

  Example

  Develop of queue	Keeping path info
  (S)	((S))
  (L O)	((L S) (O S))
  (M F O)	((M L S) (F L S) (O S))
  (N F O)	((N M L S) (F L S) (O S))
  (F F O)	((F N M L S) (F L S) (O S))
  ...	...

  (defun depth (start finish)
  (depth1 (list (list start)) finish))

  (defun depth1 (queue finish)
  (cond ((null queue) nil) ;no more
  ((equal finish (car queue)) ;found
  (reverse (car queue))) ;return path
  (t (depth1 (append (expand (caar queue))
  (cdr queue))
  finish))))

  
  
  

  (defun expand (path)
  (remove-if
  #'(lambda (path) (member (car path)
  (cdr path)))
  ;flush circular path
  (mapcar #'(lambda (child) (cons child path))
  (get (car path) 'children))))

  
  
  

  Example

  

  (setf (get 'S 'children) '(A B))

  (setf (get 'A 'children) '(S B F))

  (setf (get 'B 'children) '(S A C))

  (setf (get 'C 'children) '(B F))

  (setf (get 'F 'children) '(A C))

  
  
  

  >(depth 'S 'F)
  (S A B C F)

  The queue develops as:

  ((S))
  ((A S) (B S))
  ((B A S) (F A S) (B S))
  ((C B A S) (F A S) (B S))
  ((F C B A S) (F A S) (B S))

  • Other searching techniques, such as hill-climbing or best-first search can be implemented similarly.

  

  The 8-Queens Problem

  (defun threaten (a b) ;a,b are dotted pairs
  (cond ((or (null a) (null b)) nil)
  ((or (= (car a) (car b)) ;same row
  (= (cdr a) (cdr b)) ;cam col
  (= (- (car a) (cdr a))
  (- (car b) (cdr b)));diag /
  (= (+ (car a) (cdr a))
  (+ (car b) (cdr b)));diag \
  t)
  (t nil)))

  (defun safe (a lb) ;a is safe wrt lb, list
  (cond ((null lb) t) ; of queens
  ((threaten a (car lb)) nil)
  (t (safe a (cdr lb)))))

  (defun queen (n) ;n queen problem
  (queen-aux n 0 nil));insert queen at level0

  (defun queen-aux (n m queue) ;insert queen at
  (do ((temp 0 (+ temp 1))) ; level m
  ((= temp n) nil)
  (cond ((safe (cons m temp) queue)
  (cond ((= (+ m 1) n)
  (print
  (append queue
  list(cons m temp)))))
  (t (queen-aux n (+ m 1)
  (append queue
  list(cons m temp)))))
  )))

  >(queen 4)
  ((0.1)(1.3)(2.0)(3.2))
  ((0.2)(1.0)(2.3)(3.1))
  nil