A Brief Review of LISP


1. Valid objects (S-expressions).
   Atoms: numbers: (real 1.0, integer 1)
          symbols: a consecutive sequence of characters (no space)
                   e.g., a, x, price-of-beef.
                   two special symbols: T and NIL for logical true and false.
          strings: a sequence of characters bounded by double quotes
                   e.g., "this is red".
	    (Note: LISP is case insensitive)
   Lists: a list of atoms and/or lists, bounded by "(" and ")"
          (a b c), (a (b c))
          top elements of a list
		example: top elements of list (a b c) are a, b, and c
			   top elements of list (a (b c)) are a and (b c)
          nil: empty list (same as ()).


2. Function calls
   . also a list
   . use prefix notation:  (function-name arg1 ... argn)
   . returns function value for the given list of arguments
   . functions are either provided by Lisp function library or defined by
     the user.
   . Examples:
     >(+ 1 3 5)
     9
     >(/ 3 5)
     3/5
     >(/ 3.0 5)
     0.59999999999999998
     >(sqrt 4)
     2.0


3. Evaluation of S-expression
   1) Evaluate an atom.
      numerical and string atoms evaluate to themselves;
      symbols evaluate to their values if they are assigned values,
      return Error, otherwise;
      The values of T and NIL are themselves.

   2) Evaluate a list - evaluate every top element of the list as follows,
        unless explicitly forbidden:
      . the first element is always a function name;
        evaluating it means to call the function body;
      . each of the rest elements will then be evaluated, and their values
        returned as the arguments for the function.
      . Examples
        >(+ (/ 3 5) 4)
        23/5
        >(+ (sqrt 4) 4)
        6.0
        >(sqrt x)
        Error: The variable X is unbound.

   3) To assign a value to a symbol
      >(setq x 3.0)
      3.0
      >x
      3.0
        ; setq is a special form of function;
        ; the first argument is a symbol which will not be evaluated;
        ; the second argument is a S-expression, which will be evaluated;
        : the value of the second argument is assigned to be the value of
        : the first argument
      >(setq y x)  ; the value of x is assigned as the value of y
      3.0
      >y
      3.0
      >(+ x y)
      6.0 
      . to forbid evaluation of a symbol        
      >(quote x)
      x
      >'x
      x
      >(setq z 'x)
      x
      >(+ x z)
      Error: X is not of type NUMBER ...
      . to force an evaluation, using function "eval"
      >(+ x (eval z))
      6.0

      Two more assignment functions:
      (set x y)   ; assign the value of y to the value of x. x is evaluated
                  ; first and whose value must be a symbol
                  ; "setq" is a combination of "set" and "quote"
      (setf x y)  ; similar to but more general than "setq" in that x can be
                  ; something other than a symbol.


4. Basic LISP functions 
   1) list operations:
   >(setq L '(a b c)) ; assigns a list (a b c) as the value of L
   (a b c)
   >(car L)           ; returns the first top level element of list L
   A			    ; (car L) is the same as (first L)
   >(cdr L)           ; returns the rest of list L
   (B C)		    ; (cdr L) is the same as (rest L)
   >(cadr L)          ; car of cdr of L
   B
   >(cddr L)
   (C)
   >(caddr L)
   C
   >(cdddr L)
   NIL
   >(cddddr L)
   NIL
   >(nth 2 L)         ; (nth i L) returns the ith top element of L
   C                  ; (the front element is considered 0th element)
   >(cons 'x L)       ; insert symbol x at the front of list L
   (X A B C)
   >(list 'a 'b 'c)   ; making a list with the arguments as its elements
   (A B C)            ; if a, b, c have values x, y, z, then (list a b c)
                      ; returns list (x y z) 
   >(append '(a b) '(c d)) ; appends one list in front of another
   (A B C D)
   >(reverse L)        ; reverses a list
   (C B A)
   >(length L)         ; returns the length of list L
   3

   2) Predicates (a special function which returns NIL if the predicate is false, 
	T or anything other than NIL, otherwise)
   >(< x y)
   NIL
   >(= x y)
   T
   also >, <=, >=, for numerical values 
        equal, eq for others (symbols, lists, etc.)
   >(atom x)           ; tests if x is a atom
   T
   >(atom L)
   NIL
   >(listp x)           ; tests if x is a list
   NIL
   >(listp L)
   T 
   also numberp, symbolp, zerop (the argument must be evaluated first)
   >(numberp x)
   T
   >(symbolp x)
   NIL
   >(symbolp 'x)
   T
   >(null L)            ; tests if L is a null (empty) list
   NIL                  ; L is not a null list because it has some elements
   >(null x)
   NIL                  ; X is not a null list because it is not a list
   >(null NIL)
   T

   3) Set operations ( a list can be viewed as a set whose members are the
      top elements of the list)
   >(member 'b L)      ; test if symbol b is a member (a top element) of L
   (B C)               ; if yes, returns the sublist of L starting at the
                       ; first occurrence of symbol b
   >(member 'b (cons 'b L))
   (B A B C)
   >(member x L)
   NIL                 ; if no, returns NIL

   >(union L1 L2)           ; returns the union of the two lists
   >(intersection L1 L2)    ; returns the intersection of the two lists
   >(set-difference L1 L2)  ; returns the difference of the two lists
				    ; a subset of L1 whose members are not members of L2)

   4) Conditional
   >(cond (<test-1> <action-1>)
          .
          .
          .
          (<test-k> <action-k>))
   ; each (<test-i> <action-i>) is called a clause;
   ; if test-i (start with i=1) returns T (or anything other than NIL), 
   ; this function returns the value of action-i;
   ; else, go to the next clause;
   ; usually, the last test is T, which always holds, meaning otherwise.
   ; cond can be nested (action-i may contain (cond ...))


5. Define functions (heavy use of recursive definitions)
   (defun func-name (arg1 ... argn) func-body)

   examples:

   (defun member (x L)
      (cond ((null L) nil)            ; base case 1: L is empty
            ((equal x (car L)) L)     ; base case 2: x=first(L)
            (t (member x (cdr L)))    ; recursion: test if x is in rest(L)
      )
   )

   (defun intersection (L1 L2)
      (cond ((null L1) nil)
            ((null L2) nil)
            ((member (car L1) L2)
                (cons (car L1) (intersection (cdr L1) L2))))
            (t (intersection (cdr L1) L2))
      ))
      Example: (intersection '(a b c) '(b a b c)) returns (a b c)
    		   (intersection '(b a b c) '(a b c)) returns (b a b c)

   (defun set-difference (L1 L2)
	(cond ((null L1) nil)
		((null L2) L1)
		((not (member (car L1) L2)) 
			(cons (car L1) (set-difference (cdr L1) L2)))
		(t (intersection (cdr L1) L2))
	)
    )

    Define functions iteratively.

    (dolist (x L result) body)
      ; for each top level element x in L, do body(x);
      ; x is not equal to an element of L in each iteration, but rather
      ; x takes an element of L as its value;

    (dotimes (count n result) body)
      ; do body n times. count starts with 0, ends with n-1

    Note: "result" is optional, to be used to hold the computing result.
      If result is specified, the function will return the value of "result",
      returns NIL, otherwise. (may change global variables as side effects.)

    (defun sum1 (L)
      (setq y 0)
      (dolist (x L y) (setq y (+ y x))))

    (defun sum2 (L)
      (setq y 0)
      (dolist (x L y) (setq y (+ y (eval x)))))

    (defun sum3 (L)
      (setq y 0)
      (dotimes (count (length L) y) (setq y (+ y (nth count L)))))

    (defun sum4 (L)
      (setq y 0)
      (dotimes (count (length L) y) (setq y (+ y (eval (nth count L))))))

    Example:
    >(setq L1 '(1 2 3))
    (1 2 3)
    >(setq L2 '(a b c))
    (A B C)
    >(dotimes (count 3) (set (nth count L2) (nth count L1)))
    NIL
    >a
    1
    >(sum1 L1)
    6
    >(sum1 L2)
    Error: ...
    >(sum2 L2)
    6
    >(sum3 L1)
    6
    >(sum3 L2)
    Error: ...
    >(sum4 L2)
    6


6. Functions in LISP library
   1) Predicates:zerop, plusp, evenp, oddp, integerp, floatp 
   2) Arithmetic operations: +, -, *, / add 1, subtract 1, 
   3) Comparisons: =, /=, < ,> ,<= ,> ; equal, eq
   4) Logical connector: and, or, not
   5) Rounding: floor,ceiling, truncate, round 
   6) Others: max, min, abs, sqrt,
	(exp number) Returns e raised to the power of the argument number, 
	   where e is the base of natural logarithm. 
	(expt Base-number Power-Number) Returns Base-number raised to the 
	   power of the Power-number.
	(log number & Optional base-number) Returns the logarithm of the number 
	   in base base-number. The default base is e.  
	(isqrt number) Returns the greater inter less than equal to the exact 
	   positive square-root of the number.
	(signum number) Returns -1, zero, or 1 according if the number is negative, 
	   zero, or positive.


7. Other features
   1) Property lists:
      Assigning/accessing properties (attribute-value pairs) of a symbol

      To assign a property:  (setf (get object attribute) value)
      To obtain a property:  (get object attribute)

      Example: 
      >(setf (get 'a 'heights) 8)  ; cannot use "setq" here
      8
      >(get 'a 'height)
      8
      >(setf (get (cadr L2) 'height) 9)
      9
      >(get 'b 'height)
      9

   2) Associative list: attach a list of properties to a symbol, each property
      can be retrieved by key (property symbol)

      >(setf sarah '((height 6) (weight 100) (sex "F")))
      ((HEIGHT 6) (WEIGHT 100) (SEX "F"))
      >(assoc 'weights sarah)
      (WEIGHT 100)
      
   3) mapcar: (mapcar #'p-name L)
      transform list L to another list by performing procedure p-name to each
      top level element of L.

      Example:
      >(mapcar #'eval L2)
      (1 2 3)

      Use previously defined function: (defun sq1 (x) (* x x))
      >(mapcar #'sq1 L1)
      (1 4 9)

      Define the function within mapcar (un-named), use lambda notation
      >(mapcar #'(lambda (x) (setq x (+ 1 (eval x)))) L2)
      (2 3 4)

      Transformation over more than one lists
      >(mapcar #'= L2 (reverse L2))
      (NIL T NIL)
      >(mapcar #'+ '(1 2 3) '(3 2 1))
      (4 4 4)
      >(mapcar #'* L1 L1 L1)
      (1 8 27)

   4) input/output 
      on screen: print/read 
      >(print (get 'a 'height))
      8
      8
      >(print L2)
      (A B C)
      (A B C)
      >(setq p (read))
      10 ;typed on the screen
      10
      >p
      10

      with external file: 
      (with-open-file (<stream-name> <file-name> :direction :input or :output)
        ...  )

      >(with-open-file (data "in.dat" :direction :input)
         (setq L3 nil)
         (dotimes (count 5) (setq L3 (cons (read data) L3))))
      >L3
      (5 4 3 2 1)
      >(with-open-file (result "out.dat" :direction :output)
         (dotimes (count 5) (print (+ 1 (nth count L3)) result)))
      NIL
      (an external file "out.dat" is created and contains
       6
       5
       4
       3
       2
      )

   5) Some new primitive/functions
      Access a list
      first, second, ..., tenth ; extension of CAR, return the ith element
      rest, last                ; extension of CDR, return a list

      Conditional
      (if <test> body1 body2)   ; do body1 if test is true, body2, otherwise
      (when <test> body)        ; do body when test is true
      (unless <test> body)      ; do body when test is false

   6) Miscellaneous
      %clisp                    ; enter Common Lisp of CMU (on gl.UMBC.edu)
      (bye) or (quit) 
		or <ctrl>-D         ; exit CLISP
      (load "file-name")        ; load in a file
      (ed "file-name")          ; enter vi editor
      (compile-file "file-name"); the compiled version is in file-name.o
                                ; then load in file-name.o
      (compile 'func-name)      ; compile a particular function
      (time (func-name arg1 ... argn))
                                ; print real & run time for executing func-name