• Lisp programs are expressed as lists.
  

• cons builds lists.
  

• build up lists by consing new elements onto an empty list
  

  (cons 'a (cons 'b nil))
  (list 'a 'b)
  

• nil and t evaluates to itself.
  
• (null nil) returns true of the empty list.
  
• (not nil) returns true, since the argument nil is false.
  

• format, the most general output function
  

  (format t "~A plus ~A = ~A. ~%" 2 3 (+ 2 3))
  

  • output
    

    2 plus 3 = 5. 
    NIL
    

    • First line is displayed by format.
      
    • Second line is the value returned by the call to format.
      
  • First argument, t indicates the output is to be sent to the default place.
    
  • Second argument is a string.
    
    • ~A indicates a position to be filled.
      
    • % indicates a newline.
      
• read, the standard function for input
  
  • read is a complete Lisp parser, it is very powerful. It parses what it reads, and returns the Lisp object that results.
    

• let, define local variables
  
• defparameter, define global variable
  
  • Such a variable will then be accessible everywhere, except in expressions that create a new local variable with the same name.
    
  • It is conventional to give global variables begin and end with asterisks.
    
• defconstant, define global constants
  
  • No need to give distinctive name for them.
    
• boundp, check if some symbol is the name of a global variable or constant.
  

• setf the most general assignment operator. The return value is the last VAL in the list.
  

  (defparameter *glob* 99)
  (setf *glob* 98)
  

  • 98
    

• When the first argument to setf is a symbol that is not the name of a local variable, it is taken to be a global variable.
  

  (setf x (list 'a 'b 'c))
  (setf (car x) 'w)
  

  • Create a global variable implicitly, just by assigning values.
    
  • It is a better to use explicit defparameter.
    
  • The first argument to setf can be almost any expression that refers to a particular place. The value of the second argument is inserted in the place referred to by the first.
    

• Give even number of arguments to setf, is equivalent to multiple separate calls to setf in sequence.
  

  (setf a b
        c d
        e f)
  

• setf vs setq
  
  • Go with setf everywhere unless you have a reason not to.
    

• You may be surprised to discover how few you really need side-effects. And the more side-effects you do without, the better off you’ll be.
  

• do macro is the fundamantal iteration operator
  

  (defun show-squares (start end)
    (do ((i start (+ i 1)))
        ((> i end) 'done)
      (format t "~A ~A ~%" i (* i i))
      (format t "~%")))
  (show-squares 2 5)
  

  • do create variables
    
  • The first argument is a list of variable specification.Each element of this list can be of the form (var initial update). Here it only has one element: (i start (+ i 1)).
    
  • The second argument should be a list containing one or more expression.
    
    • The first expression is used to test whether iteration should stop. In this case, the test expression is (> i end).
      
    • The remaining expressions in the list will be evaluated in order when iteration stops, and the value of the last will be returned as the value of the do. So show-squares will always return “done”.
      
  • The remaining arguments to do comprise the body of loop, which will be evaluated, in order, on each iteration.
    

• dolist is a simpler iteration operators to iterate through elements of a list.
  

  ;; return the length of list
  (defun our-length (lst)
    (let ((len 0))
      (dolist (obj lst)
        (setf len (+ len 1))
        (format t "element is ~A ~%" obj))
      len))
  

  • dolist takes an argument of the form (variable expression), followed by a body of expressions.
    
  • variable bound to successive elements of the list returned by expression.
    
  • Loop above says, for each obj in lst, increment len.
    

By default, the function named by the first element is applied to rest of the list. And the rest of the list is evaluated by normal evaluation rule. So, if we want to refer to a function not at the start of the list, we have to use #' notiation.

• function is a special operator, its abbreviation is #', sharp-quote.
  
  • (function +)
    
  • #'+
    

• apply takes a function and a list of arguments for it, and returns the result of applying function to the arguments:
  

  (apply #'+ '(1 2 3))
  (apply #'+ 1 1 '(1 1 1))
  

  • It can be given any number of arguments, so long as the last is a list.
    

• funcall
  

  (funcall #'+ 1 2 3)
  

  • It does the same but does not need the argument to be packaged in a list.
    
  • It could not handle case the argument is a list.
    
• To refer literally to a function, we use what’s called a lambda expression.
  
  • A lambda expression is a list containing the symbol lambda, followed by a list of parameters, followed by a body of zero or more expressions.
    

  • A lambda expression can be considered as the name of a function.
    

    ((lambda (x) (+ x 100)) 1)
    

    • Like an ordinary function name, a lambda expression can be the first element of a function call.
      

  • Or by affixing a sharp-quote to a lambda expression.
    

    (funcall #'(lambda (x) (+ x 100))
             1)
    

• The built-in Common Lisp types form a hierarchy of subtypes and supertypes. The type t is the supertype of all types, so everything is of type t.
  

  (typep 27 'integer)
  (typep nil 't)
  

• nil is both an atom and a list.
  
• each call to cons, Lisp allocates a new piece of memory with room for two pointers.
  
• use equal to check if two lists had the same elements
  

• Why Lisp has no pointer?
  

  (setf x '(a b c))
  (setf y x)
  
  (eql x y)
  

  • The location in memory associated with the variable x does not contain the list itself, but a pointer to it.
    
  • Whenever you assign one variable the value of another, the two variables will have eql values.
    
  • The reason Lisp has no pointers is that every value is conceptually a pointer. When you assign a value to a variable or store it in a data structure, what gets stored is actually a pointer to the value. When you ask for the contents of the data structure or the value of the variable, Lisp returns what it points to.
    
• copy-list, takes a list and returns a copy of it.
  
  • the return value is like a new bus with the same passengers.
    

  • simple copy-list
    

    (defun our-copy-list (lst)
      (if (atom lst)
          lst 
          (cons (car lst) (our-copy-list (cdr lst)))))
    

• append returns the concatenation of any number of lists:
  

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

  • returns (A B C D E F)
    
• nthcdr, find the nth cdr.
  
• nth, find the element at a given position in a list.
  
  • equivalent to car of nthcdr
    
• last, returns the last cons in a list
  
  • To get the last element of a list, take car of the last.
    
• caddr equals car of cdr of cdr.
  

• mapcar, takes a function and one or more lists, and returns the result of applying the function to elements taken from each list, until some list runs out.
  

  (mapcar #'(lambda (x) (+ x 10))
          '(1 2 3))
  

  • (11 12 13)
    

• maplist
  

  (maplist #'(lambda (x) x)
           '(a b c))
  

  • ((A B C) (B C) (C))
    
  • calls the function on successive cdrs of the lists.
    

• copy-tree, copies both the car and cdr of each cons, while copy-list copies only the cdr.
  

  (defun our-copy-tree (tr)
    (if (atom tr)
        tr 
        (cons (our-copy-tree (car tr))
              (our-copy-tree (cdr tr)))))
  

• subst vs substitute
  
  • substitute can replace element in list
    
  • subst can replace element in tree
    

• The advantage of recursion is precisely that it lets us view algorithm in a more abstract way.
  
• Do not use traces of all the invocation to see a recursion is correct. Use math induction.
  
  • case 0 (base case)
    
  • case n+1, given n.
    

• member
  

  (member 'b '(a b c))
  (member 'z '(a b c)) 
  (member '(a) '((a) (z)))
  (member '(a) '((a) (z)) :test #'equal)
  

  • Test if an element is a member of the list. When member returns true, it returns the part of the list beginning with the object it was looking for.
    
  • Can use keyword argument :test to pass the equality test function. By default, member use eql.
    

  • Can use keyword argument :key which specify a function to be applied to each element before comparison.
    

    (member 'a '((a b) (c d)) :key #'car)
    

    • Here, we test if there was an element whose car was a.
      

  • If there an element whose car is equal to 2
    

    (member 2 '((1) (2)) :test #'equal :key #'car)
    

• member-if, to find an element satisfying an arbitary predicate. A simple implementation:
  

  (defun our-member-if (fn lst)
    (and (consp lst)
         (if (funcall fn (car lst))
             lst
             (our-member-if fn (cdr lst)))))
  
  (our-member-if #'oddp '(2 3 4))
  

  • (3 4)
    
• adjoin, conses the object onto the list only if the object is not already a member, like a conditional cons.
  

• union
  

  (union '(a b c) '(c b s))
  

  • (a b c s)
    

• intersection
  

  (intersection '(a b c) '(b b c))
  

  • (b c)
    

• set-difference
  

  (set-difference '(a b c d e) '(b e))
  (set-difference '(a b c) '(b c e f a))
  

  • return what is missing for the second list comparing with the first list
    

• sequence include both list and vector. It represents a series of objects in a particular order.
  
• length
  

• subseq, copy part of a sequence
  

  (subseq '(0 1 2 3 4 5) 2)
  

  • (2 3 4 5)
    
  • second argument is required, is the position of the first element to be included.
    
  • third argument is optional, is the position of the first element not to be included.
    

• reverse
  

  (reverse '(a b c))
  

  • return a sequence with the same elements
    

• A test for palindrome which is a sequence tha reads the same in either direction:
  

  (defun mirror? (s)
    (let ((len (length s)))
      (or (zerop len)
          (equal s
                 (reverse s)))))
  
  (mirror? '(a b a))
  (mirror? '(a b b a))
  (mirror? '(a b c))
  

• sort
  

  (sort '(1 2 3 4 5) #'>)
  (sort '(1 4 3 2 5) #'(lambda (x y)
                         (< x y)))
  

• A function which returns the nth largest element of a list:
  

  (defun nthmost (n lst)
    (nth (- n 1)
         (sort (copy-list lst) #'>)))
  (nthmost 2 '(0 2 1 3 8))
  

  • return 3
    

• every and some
  

  (every #'oddp '(1 3 4))
  (every #'> '(1 3 5) '(0 2 4))
  (every #'> '(1 3 5) '(0 10))
  

• (push obj lst) == (setf lst (cons obj lst))
  
• Use dolist and push we could build iterative version of reverse.
  

• pushnew macrio is a variant of push that uses adjoin instead of cons
  

  (let ((x '(a b)))
    (pushnew 'c x)
    (pushnew 'a x))
  

  • (C A B)
    

• Known as proper lists
  

  (defun proper-list? (x)
    (or (null x)
        (and (consp x)
             (proper-list? (cdr x)))))
  

  • all the list we’ve built so far have been proper lists.
    

• A cons that isn’t proper list is called a dotted list.
  

  (setf pair (cons 'a 'b))
  

  • (A . B)
    
  • In dot nation, the car and cdr of each cons are shown separated by a period.
    

• A list of conses is called an assoc-list or alist.
  
• It is natural to use conses to represent mappings.
  

• use assoc to retrievie the pair associated with a given key.
  

  (setf trans '((+ . "add") (- . "subtract")))
  (assoc '+ trans)
  
  (assoc '+ '((+ "add") (- "subtract")))
  

  • (+ . “add”)
    

• the graph
  

  digraph {
      label="resubmit failed metering data";
      "start" [shape=doublecircle]
  }
  

• Allocating memory from the heap is somethimes generically known as consing.
  
• Consing will always cost something. Use destructive function which try to re-use most of the structure of the list passed to them as argument (see chapter12.4).
  

• make-array
  

  (setf arr (make-array '(2 3) :initial-element nil))
  

• aref, retrieve array element
  

  (aref arr 0 0)
  

  • retrieve an element of an unitialized array are undefined.
    

• Set array element
  

  (setf (aref arr 0 0) ' b)
  arr
  

  • #2A((B NIL NIL) (NIL NIL NIL))
    
  • To denote a literal array, we use the #na syntax, that n is the number of dimensions in the array, in this case it is 2.
    

• One dimension array is also called vector
  

  (setf vec (make-array 4 :initial-element 0))
  

• Create an fill vector in a single step by calling vector
  

  (vector "a" 'b 3)
  

• Set vector
  
  • aref could do the job
    

  • svref is a faster option
    

    (setf (aref arr 0 0) ' b)
    (setf (svref vec 0) 100)
    vec
    

(defun b-search (obj vec)
  (let ((len (length vec)))
    (if (zerop len)
        nil
      (b-finder obj vec 0 (- len 1)))))

(defun b-finder (obj vec low high)
  (let ((mid (round (/ (+ low high) 2))))
    (cond ((eql obj (aref vec mid))
           mid)
          ((< obj (aref vec mid))
           (b-finder obj vec low (- mid 1)))
          ((> obj (aref vec mid))
           (b-finder obj vec (+ mid 1) high)))))

(setf v #(0 1 3 4 6 7 8 9 10))
(b-search 4 v)

• Notice use # to create vector.
  

3

• Strings are vectors of characters.
  
• Individual character c as #\c.
  

• char-code returns the number associated with a character.
  

  (char-code #\c)
  

• numeric comparision on characters
  

  (sort "elbow" #'char<)
  

  • “below”
    
• Both sequence functions and array functions work on them.
  
  • (aref “abc” 1)
    
  • Faster access, (char "abc" 1)
    

• Replace/set element of string
  

  (let ((str (copy-seq "Merlin")))
    (setf (char str 3) #\K)
    str)
  

  • Return “MerKin”
    
  • Notice the copy action: copy-seq
    
• Compare to strings
  
  • Use the general equal.
    
  • string-equal ignores case.
    
• Build strings
  
  • The most general way is to use format.
    
  • Use concatenate to join several strings together.
    

• Sequence in common lisp includes
  
  • lists
    
  • vectors (and therefore strings)
    
• Common ones:
  
  • remove
    
  • length
    
  • subseq
    
  • reverse
    
  • sort
    
  • every
    
  • some
    
  • mirror?
    
• Retriev elements of sequences:
  
  • nth for lists
    
  • aref and svref for vectors
    
  • char for strings
    
  • elt works for sequences of any kind.
    

• Many sequence functions take one or more keyword arguments:
  

  key parameter	default	purpose
  :key	identity
  :test	eql
  :from-end
  :start
  :end

  • position, returns the position of an element in a sequence, or nil if it is not found.
    

    (position #\a "fantasia" :start 3 :end 5)
    

  • :key argument is a function that is applied to each element of a sequence before it is considered.
    

    (position ' a '(( c d) (a b)) :key #'car)
    

  • :test
    

    • Its argument could be any function with two arguments.
      

      (position 3 '(1 0 7 5 ) :test #'<)
      

    • When match a list, might want to use equal instead of eql.
      

  • A function find the second word in a sentence:
    

    (defun second-word (str)
      (let ((p1 (+ (position #\  str) 1)))
        (subseq str p1 (position #\  str :start p1))))
    
    (second-word "one two three.")
    

  • position-if, find an element satisfying a predicate of one argument
    

    (position-if #'oddp '(2 3 4 5))
    

  • similar to position-if
    

    • find-if
      

      (find-if #'(lambda (x)
                   (eql (car x) 'complete))
               lst)
      
      ;; would be better randered as
      (find 'complete lst :key #'car)
      

    • member-if
      

  • remove-duplicates
    

    (remove-duplicates "abracadabra")
    

    • remove
      
    • remove-if
      
  • reduce
    
    • It boiling down a sequence into a single value.
      

    • It takes at least two arguments
      

      (reduce #'(lambda (a b)
                  (+ a b))
              '(1 2 3))
      

      • a function of two arguments
        
      • a sequence.
        

A program can take a string like “16 Aug 1980” and return a list of integers representing the day, month, and year

;; some general-purpose parsing functions

;; token is for extracting the tokens from a string
;; Given a string a test function, it returns a list of the substrings whose characters satisfy the function.
(defun tokens (str test start)
  (let ((p1 (position-if test str :start start)))
    (if p1
        (let ((p2 (position-if #'(lambda (c)
                                   (not (funcall test c)))
                               str :start p1)))
          (cons (subseq str p1 p2)
                (if p2
                    (tokens str test p2)
                  nil)))
      nil)))
;; demo: (tokens "abc12 3cde.f" #'alpha-char-p 0) returns ("abc" "cde" "f")

(defun constituent (c)
  (and (graphic-char-p c)
       (not (char= c #\ ))))
;; (tokens "abc12 3cde.f" #'constituent 0)

;; parse-date takes a date in the specified form and returns a list of integers representing its components:
(defun parse-date (str)
  (let ((toks (tokens str #'constituent 0)))
    (list (parse-integer (first toks))
          (parse-month (second toks))
          (parse-integer (third toks)))))

(defconstant month-names
  #("jan" "feb" "mar" "apr" "may" "jun" "jul" "aug" "sep" "oct" "nov" "dec"))

(defun parse-month (str)
  (let ((p (position str month-names :test #'string-equal)))
    (if p
        (+ p 1)
      nil)))

(parse-date "16 Aug 1980")

• graphic-char-p include all the characters we can see including space character.
  
• Tokens will be strings seperated by whitespaces.
  

• define structure, will automatically defines helper functions for us:
  

  (defstruct point
    x
    y)
  

  • make-point
    

    (setf p (make-point :x 0 :y 0))
    

  • point-p, each point will be of type point, then structure, then atom, then t.
    
  • copy-point
    
  • access functions
    
    • point-x
      

    • point-y
      

      (setf (point-y p) 2)
      

• Specify default values by enclosing the field name and a default expression in a list.
  

  (defstruct polemic
    (type (progn
            (format t "What kind of polemic was it?")
            (read)))
    (effect nil))
  
  (make-polemic)
  

• Control how struct is displayed and the prefix used in the names of the access function.
  

  (defstruct (point (:conc-name p)
                    (:print-function print-point))
    (x 0)
    (y 0))
  
  ;; Here, the access function has been changed to px, py instead of point-x and point-y
  (defun print-point (p stream depth)
    (format stream "#<~A, ~A>" (px p) (py p)))
  
  (make-point)
  

  • :conc-name
    
  • :print-function
    

  #<0, 0>
  

;; node has 3 fields: element stored in node, left and right children of node
(defstruct (node (:print-function (lambda (n s d)
                                    (format s "#<~A>" (node-elt n)))))
  elt
  (l nil)
  (r nil))

;; A BST is either nil, or a node whose l and r field are BSTS.
;; bst-insert take an object, a BST, and an ordering function
;; It will ret urn a BST that contains the object. Like cons, it does not modify the BST given as the second argument.
(defun bst-insert (obj bst <)
  (if (null bst)
      (make-node :elt obj)
    (let ((elt (node-elt bst)))
      (if (eql obj elt)
          bst
        (if (funcall < obj elt)
            (make-node
             :elt elt
             :l (bst-insert obj (node-l bst))
             :r (node-r bst))
          (make-node
           :elt elt
           :r (bst-insert obj (node-r bst))
           :l (node-l bst)))))))

;;
(defun bst-find (obj bst <)
  ;; todo
  )

(defun bst-min (bst)
  ;; todo
  )

(defun bst-max (bst)
  ;; todo
  )

(defun bst-remove)

(defun bst-traverse)

• A Binary Search Tree(BSTs) is either nil, or a node whose left and right fields are BSTs.
  

• make-hash-table, create hash table
  

  (setf ht (make-hash-table))
  

  • That is it, no required arguments
    

• gethash, retrieve the value associated with a given key
  

  (gethash 'color ht)
  

  • It returns two values: NIL, NIL
    
    • The first is the value associated with the key.
      
    • The second says whether the hash table has any value stored under that key. It is nil to indicate the first nil was returned by default, not because nil was explicitly associated with color.
      

• setf + gethash to associat a value with a key.
  

  (setf (gethash 'color ht) 'red)
  (gethash 'color ht)
  

  • It returns: RED, T. The second return value proves that we get a real stored object.
    

• The key and the object stored in hash table can be of any type.
  

  (setf bugs (make-hash-table))
  (push "Does't take keyword arguments."
    (gethash #'> bugs))
  

  • Use functions as keys and strings as entries to keep some kind of information about functions.
    
  • Remember (push obj lst) == (setf lst (cons obj lst)).
    

• Use hash tables instead of lists to represent sets.
  

  (setf fruit (make-hash-table))
  (setf (gethash 'apple fruit) t)
  
  ;; Now to test membership, just call gethash
  (gethash 'apple fruit)
  

  • Since gethash returns nil by default, a new-make hash table is also, convoniently, a empty set.
    

• remhash, removes an entry from a hash table
  

  (remhash 'apple fruit)
  

  • The return value shows if there was an entry to remove.
    
• maphash, call a two arguments function on a hashtable’s every key/value pair.
  
  • It always returns nil, but you can save the values by passing a function that will accumulate them in a list.
    
• Key options in hashtable
  
  • :size, specify the expected elements (hashtable still could expand)
    
  • :test, specify the equality for keys. By default, it is eql.
    

• progn
  

• block
  

  (block head
    (format t "Here we go.")
    (return-from head 'done)
    (format t "It will not be evaluated"))
  

  • The body of a function defined with defun is implicitly enclosed in a block with the same name as the function:
    

    (defun foo ()
      (return-from foo 27))
    (foo)
    

  • Many Common Lisp operators that take a body of expressions implicitly enclose the body in a block named nil, including
    

    • All iteration constructs
      

      (dolist (x '(a b c d))
        (format t "~A " x)
        (if (eql x 'c)
            (return 'done)))
      

• tagbody, can use gotos.
  

  (tagbody 
     (setf x 0) 
   top 
     (setf x (+ x 1)) 
     (format t "~A " x) 
     (if (< x 10) (go top)))
  

  • Atoms appearing in the body are interpreted as labels
    
  • Giving such a label, go sends control to the expression following it.
    
  • This operator is mainly something that other operators are built upon, not something you would use yourself.
    
• In generall, nearly all the time you will use progn.
  

* Context

• let creates a new lexical context.
  

• Entering a let is conceptually equivalent to doing a function call.
  

  (let ((x 7)
        (y 2))
    (format t "Number")
    (+ x y))
  
  ;; This is as same as
  ((lambda (x y) 
     (format t "Number") 
     (+ x y))
  

  • Remeber that a lambda expression is like the name of a function, we can use one, as we would a function name, as the first element in a function call.
    

• let*, is used to create variable to depend on another variable.
  

  (let* ((x 1)
         (y (+ x 1)))
    (+ x y))
  

  • It is equivalent to a series of nested lets.
    

    (let ((x 1)) 
        (let ((y (+ x 1))) 
            (+ x y)))
    

• let and let*, their initial values default to nil.
  

• destructuring-bind, a generalization of let.
  

  (destructuring-bind
      (w (x y) . z)
      '(a (b c) d e f)
    (list w x y z))
  

• if
  
• when
  
  • The body will be evaluated only if the test expression returns true.
    
• unless
  
  • The body will be evaluated only if the test expression returns false.
    
• cond
  

• case
  

  (defun month-length (mon) 
    (case mon 
      ((jan mar may jul aug oct dec)
       31) 
      ((apr jun sept nov)
       30) 
      (feb
       (if (leap-year) 29 28)) 
      (otherwise "unknown month")))
  

  • A case expression begins with an argument whose value will be compared against the keys in each clause.
    
    • The value of that argument is compared (using eql) to the key/s at the head of each clause.
      
  • Each clause begin with either a key, or a list of keys, followed by zero or more expressions.
    
  • The keys are treated as contants; they will not be evaluated.
    
  • The default clause may have the key t or otherwise.
    
  • If no clause succeeds, or the successful clause contains only keys, then the case returns nil.
    

• do
  

  (let ((x 'a))
    (do ((x 1 (+ x 1))
         (y x x))
        ((> x 5))
      (format t "(~A ~A) " x y)))
  

  • do has 3 arguments
    

    • First one, is
      

      ((x 1 (+ x 1))
       (y x x))
      

      • each possible of the form (variable initial update).
        
    • Second one, is a list containing one or more expressions.
      
      • The first expression is used to test whether iteration should stop.
        
      • The remaining expression will be evaluated in order when iteroation stops.
        
      • The value of the last will be returned as the value of the do.
        
    • Third one is body which will be evaluated during each iteration.
      
  • (1 A) (2 1) (3 2) (4 3) (5 4)
    
  • Here, the y get the previous value of x, not the current one.
    

• do*
  

  (let ((x 'a))
    (do ((x 1 (+ x 1))
         (y x x))
        ((> x 5))
      (format t "(~A ~A) " x y)))
  

  • (1 1) (2 2) (3 3) (4 4) (5 5)
    
  • Any initial or update form can refer to a variable from a previous clause, and it will get the current value.
    

• dolist
  

  (dolist (x '(abed) (+ 1 1)) 
    (format t "~A " x))
  

  • The third expression within the initial list will be evaluated and returned as the value of the dolist.
    

• dotimes
  

  (dotimes (x 5 (* x x))
    (format t "~A " x))
  

  • Interates over the integers.
    
  • The third express can refer to the iteration variable.
    
• mapcar vs mapc
  
  • mapc doesn not cons up a new list as a return value. So the only reason to use it is for side-effect.
    
  • mapc always returns its second argument.
    

  • They both can traverse multiple lists in parallel.
    

    (mapcar #'cons 
            '(1 2 3 4)
            '(a b c d))
    
    (mapc #'(lambda (x y)
              (format t "~A ~A ~%" x y))
          '(1 2 3 4)
          '(a b c d))
    

• Common-lisp can return multiple values.
  
  • Multiple values make it possible to have lookup functions that can distinguish between finding nil and failing to find something.
    
    • gethash
      

• values function returns multiple values. It returns exactly the values you give it as argument:
  

  (values 'a nil (+ 2 3))
  

• If a values expression is the last thing to be evaluated in the body of a function, its return values become those of the function. Multiple value are passed on intact through any number of returns:
  

  ((lambda ()
     ((lambda ()
        (values 1 2)))))
  

• If something is expecting only one value, all but the first will be discarded.
  

  (let ((x (values 1 2)))
    x)
  

• Using values with no argument will return no values. Something expecting one will get nil.
  

• multiple-value-bind, to receive multiple values.
  

  (multiple-value-bind (x y z) (values 1 2)
    (list x y z))
  
  (multiple-value-bind (s m h) (get-decoded-time)
    (format nil "~A:~A:~A" h m s))
  

• multiple-value-call
  

  (multiple-value-call #'+ (values 1 2 3 4 5))
  (multiple-value-call #'list (values 1 2 3 4 5))
  

• multiple-value-list
  

  (multiple-value-list (values 'a 'b 'c '1 '2 '3))
  

• catch and throw
  

  (defun super ()
    (catch 'abort
      (sub)
      (format t "We will never see this")))
  
  (defun sub ()
    (throw 'abort (+ 1 1)))
  
  (super)
  

  • If there is no pending catch with the right tag, the throw causes an error.
    

  2
  

• error, interrupts execution, It transfers control to the List error handler.
  

• unwind-protect, like “finally” in other languages
  

  (setf x 1)
  (catch 'abort
    (unwind-protect
         (throw 'abort 99)
      (format t "Cleanup")
      (setf x 3)))
  x
  

  • unwind-protect is useful for certain actions followed by cleanup or reset.
    

• fboundp, decide if a symbol is bounded to a function.
  
• symbol-function, retrieve the associated function from symbol
  

• documentation, retrieve documentation of a function
  

  (fboundp '+)
  (symbol-function '+)
  
  (defun foo (x)
    "Documentation goes here."
    x)
  (documentation 'foo 'function)
  

• labels, define local functions (defun defines global functions).
  

  (labels ((add10 (x) (+ x 10))
           (consa (x) (cons 'a x)))
    (consa (add10 3)))
  

  • It is a kind of let for functions.
    

  • Local functions defined by a labels can refer to any other functions defined there, including themselves.
    

    (labels ((len (lst)
               (if (null lst)
                   0
                 (+ (len (cdr lst)) 1))))
      (len '(a b c)))
    

• &rest, make function takes varying number of arguments.
  

  (defun our-funcall (fn &rest args)
    (apply fn args))
  

• &optional, make function take optional parameters (default to certain values). Ordinary parameters are called required parameters.
  
  • If the symbol &optional occurs in the parameter list of a function, then all the arguments after it are optional, and default to nil.
    
  • The default for an optional parameter can be any list expressions. It will be evaluated each time a default is needed.
    

• &key , all the parameters after it are optional. When the function is called, these parameters will be identified by symbolic tags precede theme.
  

  (defun keylist (a &key x y z)
    (list a x y z))
  
  (keylist 1 :y 3 :x 2)
  

• code seg01
  

  (defun combiner (x)
    (typecase x
      (number #'+)
      (list #'append)
      (t #'list)))
  
  ;; assume the args are same type of data
  (defun combine (&rest args)
    (apply (combiner (car args))
           args))
  
  (combine 2 3)
  (combine '(a b) '(c d))
  

• lexical variable
  
  • They are only valid within the context where they are defined.
    
  • They will continue to be valid for as long as something is using the context.
    

• Function returned from the scope of lexical variable still hold the context of that variable.
  

  (setf fn (let ((i 3))
             #'(lambda (x)
                 (+ x i))))
  
  (funcall fn 2)
  

  • Here, (fn 2) will report error “Undefined function FN called with arguments (2) .”
    
  • When a function refers to a variable defined outside it, it is call a free variable.
    
  • Definition: A function that refers to a free lexical variable is called a closure.
    
  • That variable must persist as long as the function does.
    
  • In short: a closure is a combination of a function and an environment.
    
• How to create a closure?
  
  • Closures are created implicitly whenever a function refers to something from the surrounding lexical environment.
    

• Identify the closure in it:
  

  (defun add-to-list (num lst)
    (mapcar #'(lambda (x)
                (+ x num))
            lst))
  

  • Here, since the num within the lambda expression is free, so we are passing a closure to mapcar.
    

• A more conspicuous example:
  

  (defun make-adder (n)
    #'(lambda (x)
        (+ x n)))
  (funcall (make-adder 100) 100)
  

  • In lambda expression, that n is free variable. So that lambda expression becomes a closure.
    

• Closure could replace global variable, it could protect that free variable from unintended references.
  

  (let ((counter 0))
    (defun reset ()
      (setf counter 0))
    (defun stamp ()
      (setf counter (+ counter 1))))
  
  (list (stamp) (stamp) (reset) (stamp))
  

  • Closures could share free variables.
    

• complement, take a predicate and returns the opposite predicate
  

  (defun our-completement (f)
    #'(lambda (&rest args)
        (not (apply f args))))
  
  (mapcar (our-completement #'oddp)
          '(1 2 3 4))
  

• compose
  

  (defun compose (&rest fns)
    (destructuring-bind (fn1 . rest) (reverse fns)
      ;; fn1 is #'sqrt, rest is (#'round #'list)
      #'(lambda (&rest args)
          (reduce #'(lambda (v f)
                      (funcall f v))
                  rest
                  :initial-value (apply fn1 args)))))
  
  (mapcar (compose #'list #'round #'sqrt)
          '(4 9 16 25))
  

  • reduce
    
    • v, the first parameter takes the initial value and the accumulated result.
      
    • f, the second parameter takes the next item from the list rest.
      
• disjoin
  <>
  
• conjoin
  
• curry
  
• recurry
  
• always
  

• local variables are nearly always lexical variable (from lexical scope)
  
• global variables are always special variables (from dynamic scope)
  

• Under lexical scope, a symbol refers to the variable that has that name in the context where the symbol appears/defined.
  

  (let ((x 10))
    (defun foo ()
      x))
  
  (let ((x 20))
    (foo))
  

  • Local variables have lexical scope by default: the result is 10.
    
  • We define a function in an environment where there is a variable called x, then the x in the body will refer to that variable, regardless of any x that might exist where foo is called.
    
• Under dynamic scope, we look for a variable in the environment where the function is called, not in the environment where it is defined.
  

• special
  

  (let ((x 10))
    (defun foo ()
      (declare (special x))
      x))
  
  (let ((x 20))
    (declare (special x))
    (foo))
  

  • return 20
    
  • To cause a variable to have dynamic scope, we must declare it to be speciall in any context where it occurs.
    
  • Now, x refers to whatever special x exists at the time the function is called.
    
  • A declare can begin any body of code where new variables are created.
    

• Global variables established by calling setf at the toplevel are implicitly special.
  

  (setf x 40)
  (foo)
  

  • return 40
    
  • It is recommended to use defparameter to make a program clearer (explicitly special declaration).
    
• Where is dynamic scope useful
  
  • It is used to give some global variable a new value temporarily.
    

  • ex:
    

    (let ((*print-base* 16))
      (princ 32))
    

    returns
    

    20
    32 (6 bits, #x20, #o40, #b100000)
    

    • The two results are the same value “32”. The first (the output generated by princ) is in hexadecimal because *print-base* was 16 when it is printed. The second (the value it returns) in decimal because outside the let expression, *print-base* reverts to its previous value 10.
      

• compiled-function-p
  

  (compiled-function-p #'+)
  

• compile
  
• compiled function vs interpreted function
  
• compile-file
  
  • create a compiled version of the source file, same base name with a different extension.
    
  • all function in that file will be compiled
    

• When the containing function is compiled, the inner function should also be compiled.
  

  (compile 'make-adder)
  (compiled-function-p (make-adder 2))
  

• Functional programming: recursive algorithms are less likely to involve side-effects.
  
• Recursive data structure
  
  • Lisp’s implicit use of pointer makes it easy to have recursive defined data structures.
    
  • A list is either nil, or a cons whose cdr is a list.
    

• Streams are objects representing source/destinations of characters.
  
• *standard-input* and *standard-output*.
  
• pathname is a portable way of specifying a file.
  
• open, open a file
  
  • take a pathname
    
  • returns a stream that points to that file.
    
  • :direction
    
    • :output, for read
      
    • :input, for write
      
    • :io, for both
      
  • :if-exists
    
    • usually it should be: :supersede
      

• ex01: open a file and write something
  

  (setf path (make-pathname :name "myfile"))
  (setf str (open path :direction :output
                       :if-exists :supersede))
  (format str "Something~%")
  (close str)
  

  • Nothing is guaranteed about its a file’s content until you close it.
    

• ex02: open a file and read from it
  

  (setf str (open path :direction :input))
  ;; read a line of text
  (read-line str)
  ;; always close it
  (close str)
  

• Use with-open-file instead of open.
  

  (with-open-file (str path :direction :output
                            :if-exists :supersede)
    (format str "Something~%"))
  

  • In that argument (list), that str is bounded to a stream created by passing the remaining arguments to open.
    
  • It automatically close the file.
    

• read-line
  

  (progn
    (format t "Please enter your name")
    (read-line))
  

  • 1st argument: a stream; if the stream is omitted, it will default to *standard-input*.
    
  • 2nd argument: whether or not to cause an error on encountering end-of-file.
    
  • 3rd: what to return instead, if the previous argument is nil.
    

• Ex01:
  

  (defun pseudo-cat (file)
    (with-open-file (str file :direction :input)
      (do ((line (read-line str nil 'eof)
                 (read-line str nil 'eof)))
          ((eql line 'eof))
        (format t "~A~%" line))))
  

• read, read exactly one expression as Lisp object.
  
  • Avoid using read directly to process user input.
    

• read-from-string, useful with read-line to process user input.
  

  (read-from-string "123 b c")
  

  • returns
    

    123 (7 bits, #x7B, #o173, #b1111011)
    4 (3 bits, #x4, #o4, #b100)
    

    • the first is the first expression it read
      
    • the second indicating the position in the string at which it stopped reading.
      

• prin1, generate output for programs.
  
• princ, generate output for people.
  
• terpri, print a new line.
  
• format has many format directives
  
  • ~A, a placeholder
    

  • ~F, print right-justified floating-point numbers. And Format directives can take arguments.
    

    (format nil "~30,10,,,'_F" 26.21875123132141412423232323232)
    

    1. the total number of characters to be printed.
       
    2. the number of digit to print after the decimal
       
    3. the number of digit to shift the decimal point to the left (thereby effectively multiplying the number by 10)
       
    4. the charaters to print instead of the number if it is too long to fit in the space allowed by the first argument.
       
    5. the charaters to print to the left before the digits start (it is blank here).
       

  • a simply example
    

    (format nil "~,2,,,F" 26.21875)
    ;; equals
    (format nil "~,2F" 26.21875)
    

  • You should round the number explicitly before printing it.
    

• symbol-name, get symbol’s name
  

  (symbol-name 'abc)
  

  • By default, common-lisp is not case-sensitive.
    

    (eql 'abc 'ABC)
    

  • Use vertical bar as special syntax to refer to symbols whose name contain whitespaces or other things that might otherwise be significant to the reader.
    

    (list '|Lisp 1.5| '|| '|abc| '|aBc| '|ABC|)
    

    • returns: (|Lisp 1.5| || |abc| |aBc| ABC)
      

• Every symbol has a property-liist, or plist (it is not alist which is a list of cons).
  

  (get 'alizarin 'color)
  (setf (get 'alizarin 'color) 'red)
  
  ;; now the color property of alizarin is red
  (get 'alizarin 'color)
  
  ;; get the plist of symbol
  (symbol-plist 'alizarin)
  

  • get, takes a symbol and a key of any type; returns the value associated with that key in the symbol’s property list.
    
  • symbol-plist
    

• Symbol is a substantial object, it contains
  
  • name
    
  • package
    
  • value
    
  • function
    
  • plist
    
• When two variables are set to the same symbol, it is the same as when two variables are set to the same list: both variables have pointers to the same object.
  

• Packages are symbol tables, mapping names(strings) to symbols.
  

• intern, A symbol that belongs to a package is said to be interned in that package.
  

  (intern "foo")
  

  • Most symbols are interned when they are read.
    
  • So, the above expression create a symbol “foo” and intern it in the current package.
    
  • The second return value shows whether the symbol already existed.
    
• Not all symbols are interned, unintended symbols are called gensyms used in macro.
  

• export, only symbols that you explicitly export will be visible in other packages.
  
• Those exported symbols have to be preceded (qualified) by the name of the packages that owns them.
  

• Ex01
  

  (defpackage "MY-APPLICATION"
    (:use "common-lisp" "my-utilities")
    (:nicknames "APP")
    (:export "WIN" "LOSE" "DRAW"))
  
  (in-package my-application)
  

  • It uses two other packages which means that symbols exported by these packages will be accessible without package qualifiers.
    
  • code in other package will be able to refer to them as e.g: app:win.
    
  • The defpackage is followed by an in-package that makes the current package be my-application.
    

• Keywords are symbols in keyword package.
  
• You can refer to them anywhere simply as :x instead of keyword:x.
  

• When a symbol is the name of a special variable, the value of the variable is stored in a field within the symbol.
  

  (setf foo 123)
  (symbol-value 'foo)
  

  • symbol-value function refers to that field.
    

• If your program operates on words, it is often a good idea to use symbol instead of string. Because symbols are conceptually atomic.
  
  • symbol can be compared using eql
    
  • string needed to be compared character-by-character with string-equal or string=.
    

• Generate random text based on sample text
  

  (defparameter *words* (make-hash-table :size 10000))
  
  (defconstant maxword 100)
  
  (defun read-text (pathname)
    (with-open-file (s pathname :direction :input)
      (let ((buffer (make-string maxword))
            (pos 0))
        (do ((c (read-char s nil :eof)
                (read-char s nil :eof)))
            ((eql c :eof))
          (if (or (alpha-char-p c)
                  (char= c #\'))
              (progn
                (setf (aref buffer pos) c)
                (incf pos))
              (progn
                (unless (zerop pos)
                  (see (intern (string-downcase (subseq buffer 0 pos))))
                  (setf pos 0))
                (let ((p (punc c)))
                  (if p
                      (see p)))))))))
  
  ;; punc
  (defun punc (c)
    (case c
      (#\. '|.|)
      (#\, '|,|)
      (#\; '|;|)
      (#\! '|!|)
      (#\? '|?|)))
  
  (let ((prev '|.|))
    (defun see (symb)
      (let ((pair (assoc symb (gethash prev *words*))))
        (if (null pair)
            (puch (cons symb 1) (gethash prev *words*))
            (incf (cdr pair))))
      (setf prev symb)))
  
  

file:~/code/capture-org/common-lisp/examples/ray-tracing.lisp

• Crossing the line at compile-time.
  
• defmacro, like defun function, but instead of defining the value call should produce, it defines how a call should be translated.
  

• macroexpand-1
  

  (defmacro nil! (x)
    (list 'setf x nil))
  
  (macroexpand-1 '(nil! x))
  
  
  (defun test ()
    )
  
  (test)
  

• THe secret to understanding macros is to understand how they are implemented. They are just functions that transform expressions. If you pass an expression of the form (nil! a) to this function:
  

  (lambda (expr)
    (apply #'(lambda (x)
               (list 'setf x nil))
           (cdr expr)))
  

  • It will return (setf a nil).
    

• By using backquote instead of a call to list, we can write macro definitions that look like expansions they will produce.
  

  (defmacro nil! (x)
    `(setf ,x nil))
  

• ,@ is useful in macros that have rest parameters representing, for example, a body of code
  

  • suppose we want a while macro that will evaluate its body as long as initial test expression remain true
    

    (let ((x 0))
      (while (< x 10)
        (printc x)
        (incf x)))
    

  • its macro definition
    

    (defmacro while (test &rest body)
      `(do ()
           ((not ,test))
         ,@body))
    

• When you start writing macros, you have to start thinking like a language designer.
  
• gensyms usually print as symbole preceded by #: in macro expansions.
  
• Use macroexpand-1 to learn macro design from your lisp implementation.
  

• Have to be written as macros: “because all have to control the way in which their argument are evaluated”.
  

(defclass graphic ()
  ((color :accessor graphic-color :initarg :color)
   (visible :accessor graphic-visible :initarg :visible
            :initform t)))

(defclass screen-circle (circle graphic)
  ())

• second argument is a list of superclasses.
  
• A class inherits the union of the slots of its superclasses. So, screen-circle will have four slots.
  
• accessors and initargs works as they would for their superclasses.
  

  • we could to define initform to provide default value
    

    (defclass screen-circle (circle graphic)
      ((color :initform 'purple)))
    

• The rule of traversing to create the precedence list.
  
  1. Start at the bottom of the network.
     
  2. Walk upward, always taking the leftmost unexplored branch.
     
  3. If you are about to enter a node and you notice another path entering the same node from the right.
     Then instead of entering the node, retrace your step until you get to a node with an unexplored path leading upward. Go back to step 2).
     
  4. When you reach the node representing t, you are done.
     
• The key (step 3) is no class appears in the precedence list before one of its subclasses.
  

• A generic function is a function made up of one or more methods. Methods are defined with defmethod.
  

  • Here, we use defmethod create a method which creates a generic function (now, it has only one method).
    

    (defmethod combine (x y)
      (list (x y)))
    

  • Interesting things happened here: we can continue to add new methods for it.
    

    (defclass  stuff ()
      ((name :accessor name
             :initarg :name)))
    
    (defclass ice-cream (stuff) ())
    (defclass topping (stuff) ())
    
    ;; The specialization of a method indicate the kinds of arguments to which it applies
    (defmethod combine ((ic ice-cream)
                        (top topping))
      (format nil "~A ice-cream with ~A topping."
              (name ic)
              (name top)))
    
    
    (combine (make-instance 'ice-cream :name 'fig)
             (make-instance 'topping :name 'fizzz))
    (combine 23 'wwooo)
    

    • Parameters are specialized: each one appears in a list with the name of a class.
      
    • Lisp will use the most specific method for which the classes of the arguments match the specialization of the parameters.
      

    • Any combination of the parameters in a method can be specialized.
      

      (defmethod combine ((ic ice-cream) x)
        (format nil "~A ice-cream with ~A."
                (name ic)
                x))
      

• Methods can also be specialized on types (or more precisely, the classes that mirror types)
  

  (defmethod combine ((x number)
                      (y number))
    (+ x y))
  

• Method can even be specialized on individual objects, as determined by eql.
  

  (defmethod combine ((x (eql 'powder))
                      (y (eql 'spark)))
    'boom)
  

• The parameter lists of all the methods for a generic function must be congruent.
  
• Only required parameters can be specialized.
  
• We could overwrite a method with the same qualifiers and specializations.
  

• standard method combination, callinga generic function invokes
  

  1. The most specific around-method, if there is one
     
     • Then, at its own discretion, the around-method may itself invoke the primary method, via call-next-method.
       
  2. Otherwise in order:
     
     1. All before-methods, from most specific to least specific.
        
     2. The most specific primary methods.
        
     3. All after-methods, from least specific to most specific.
        

  The value returned is the value of the around-method (case 1), or the value of the most specific primary method (case 2).
  

• Speicify the type of method combination to be used by a generic function with a :method-combine clause in a call to defgeneric.
  
• The following symbols can be used as the second argument to defmethod or in the :method-combine option to defgeneric.
  

• Example
  

  (defgeneric price (x)
    (:method-combination +))
  
  (defclass jacket ()
    ())
  (defclass trousers ()
    ())
  (defclass suit (jacket trousers)
    ())
  
  (defmethod price + ((jk jacket))
    350)
  (defmethod price + ((tr trousers))
    200)
  
  (price (make-instance 'suit))
  

  • Now, the price method will use + method combination.
    
  • Any defmethod for price must have + as the second argument.
    
  • Operator method combination can be understood as if it resulted in the evaluation of a Lisp expression whose first element was some operator, and whose arguments are calls to the applicable primary method, in order of specificity.
    

  550
  

• In common lisp, packages are the standard way to distinguish between publich and private information.
  

• Example
  

  (defpackage "CTR"
    (:use "COMMON-LISP")
    (:export "COUNTER" "INCREMENT" "CLEAR"))
  
  (in-package ctr)
  
  (defclass counter ()
    ((state :initform 0)))
  
  (defmethod increment ((c counter))
    (incf (slot-value  c 'state)))
  
  (defmethod clear ((c counter))
    (setf (slot-value c 'state) 0))
  

• In the message-passing model, methods are of objects.
  
• In generic function model, they are specialized for objects.
  

  • In message-passing, we only specialize the first parameter.
    

    (move obj 10)
    

    • that obj is the specialized first parameter.
      
• Message-passing model is a subset of the generic function model.
  

• tailp
  

  (defun our-tailp (x y)
    (or (eql x y)
        (and (consp y)
             (our-tailp x (cdr y)))))
  

  • determin if x is the tail of y
    
• List sharing structure vs their elements sharing structure.
  
  • List sharing structure means sharing structure as lists.
    

• copy-list
  

  (defun our-copy-list (lst)
    (if (null lst)
        nil
        (cons (car lst) (our-copy-list (cdr lst)))))
  

  • return a list doesn’t share top-level list structure with the original
    

• copy-tree
  

  (defun our-copy-tree (tr)
    (if (atom tr)
        tr
        (cons (our-copy-tree (car tr))
              (our-copy-tree (cdr tr)))))
  

(defun make-queue ()
  (cons nil nil))


(defun enqueue (obj q)
  (if (null (car q))
      (setf (cdr q) (setf (car q) (list obj)))
      (setf (cdr (cdr q)) (list obj)
            (cdr q) (cdr (cdr q))))
  (car q))

(defun dequeue (q)
  (pop (car q)))

(setf q1 (make-queue))

(progn
  (enqueue 'a q1)
  (enqueue 'b q1)
  (enqueue 'c q1))

(dequeue q1)
(enqueue 'd q1)
(enqueue 'z q1)

• Notice, the return value of setf is the last value in the setf list, not the result of modified variable.
  

• They are not meant to be called for their side-effects.
  
• delete vs remove
  
• nconc vs append
  

• mapcan vs mapcar
  

  (mapcan #'list
          '(a b c)
          '(1 2 3 4))
  (mapcar #'list
          '(a b c)
          '(1 2 3 4))
  

  • TODO: review, mapcan, mapcar, mapc, maplist
    

• The current package is always stored in the global variable *package*.
  
• find-package, return the package with a given name.
  
• package-name, returns the name of a package.
  
• symbol-package, takes a symbol and returns the package in which it is interned.
  

• Different symbols with the same print-name can coexist in different packages.
  

  (setf sym 99)
  ;; switch to package mine from package common-lisp-user
  (setf *package*  (make-package 'mine
                                 :use '(common-lisp)))
  
  common-lisp-user::sym
  

  • switch current package
    
  • refer symbol interned from other package
    
  • You shouldn’t use “::” to refer symbols from other packages.
    

• Use exported symbols from other package
  

  (in-package common-lisp-user)
  (export 'bar)
  (setf bar 5)
  
  ;; use single ":" to refer the exported symbol from other packages 
  (in-package mine)
  common-lisp-user:bar
  
  ;; go further, make current package share symbol from other package
  (import 'common-lisp-user:bar)
  bar
  
  ;; get access to all symbols exported by other package
  (use-package  'common-lisp-user)
  ;; Now, no qualifier is needed for symbols exported by the user package.
  

• Operations on packages are not usually done at toplevel.More often the calls are contained in source files.
  
  1. Begin a file with a defpackage and an in-package.
     
  2. See 8.5 Multiple Packages