CSC 242: LISP Lecture 2 Notes



  
[ Updated: 11 Jan 2002 ]

  A note about these notes: they are simply a nice little summary of some of 
  the basic functions of LISP.  Wilensky does a real good job of 
  covering the fundamentals so please make sure you read the book a few times
  before attempting the problem sets.  You'll thank yourself later.


Local Variables

  (let ((var value)*) expression) 
  Each symbol var names a variable to be created with the given
  values.  Expression is then evaluated left-to-right.  The variables
  and their values are lost once the let closes.
  
  (let* ((var value)*) expression) 
  Same as above except var's are created one at a time so each value can 
  refer to any previous var.
  
  (setf var value)
  Assigns a new value to the innermost local variable named var.
  
  
  Example:
(let ((x 1) (y 2)) ;; scope: x=1 y=2 (let ((x (+ x 10)) (y (+ x 20))) ;; scope: x=10 y=21 (let* ((x (+x 100)) (y (+ x 200))) ;; scope x=111 y=311 (setf x 55) ;; x=55 ) ;; close let*, scope now: x=10 y=21 ) ;; close nested let, scope now: x=1 y=2 );; now x and y are out of scope completely

Global Variables

(defvar var value) Declares the symbol var to be a special symbol and sets the global variable it names to the value. Common to denote globals with a + or * on either side of the var name. Example: +count+ or *history-list*. (setf var value) same as before in local case. Just be careful when using setf on globals while programming.

Functions

(defun function-name (var* &rest) expression*) Defines a global function named by the symbol function-name. (funcall function arg*) Returns the result of applying function to arguments arg*). Make sure the number of your arguments matches the number required by function. (apply function list) Basically the same as above except the arguments are in a list. Examples: >(funcall #'+ 1 4 5) 10 > (apply #'+ '(1 4 5) 10 (mapcar function list*) Returns a list whose k'th element is the result of applying function to arguments which are the k'th elements of the lists. Example: >(mapcar #'(lambda (x) (+ x 10)) '(1 2 3)) (11 12 13) > (mapcar #'list '(a b c) '(1 2 3 4)) ((A 1) (B 2) (C 3)) (notice it doesn't do 4 since lists aren't the same length)

Predicates

(atom value) Returns T if value value is an atom. (consp value) if value is a cons cell, NIL if it isn't. (listp value) if value is a list, NIL if it isn't (null value) if value is NIL (not value) if value is false (NIL) (equal val1 val2) Returns T if the two arg's look the same when printed (surface equality) (eql val1 val2) Returns T if the two arg's are the same symbol, the same cons cell, or numbers with both the same type and same value. (eq val1 val2) Returns T if the two arg's are the same symbol or the same cons cell. (member object list) Checks if object is eql to an element of list. If T, returns all of list after and including object. Examples: > (eql (cons 'a NIL) (cons 'a NIL)) NIL > (equal '(a b c d) (list 'a '(b c d)) T >(eql '(a b c d) (list 'a '(b c d)) NIL

Conditionals

(cond (test expression*)*) Evaluates tests in order until it finds one that returns T, then it evaluates the respective expression. If there is no expr then it returns the test. Does NOT evaluate any test after the first that returns T. If none return T, then cond returns NIL. (cond ((null x) T) ((list x) (first x)) ((member x special-list)) (t (push x special-list))) (if (test then-expression else-expression) Evaluates test first, if T, then does then part, else it's NIL or false so do else part. If else is omitted, default is NIL. Note, only one expression can be used for then or else. (if (oddp number) (format t "number ~A is odd~%" number) (format t "it's even~%")) (when(test then-expression*) Evaluates test first, if T, then does then part, else it's NIL or false so do else part. Note no else. Also then is as long as you want. (when (oddp number) (format t "number ~A is odd~%" number) (incf +odd-count+)) * how can you make an if as powerful as a when (in that multiple expr's can be found)? Use block or progn or let: (if (oddp number) (progn (format t "number ~A is odd~%" number) (incf +odd-count+)) (format t "it's odd~%")) Case - when you want to compare a value against a series of constants. Just like in C. An example: (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")))

Iteration

(do ((var initial update)*) (end-condition result*) expression*) initially (1) evaluates the initial value expr's, (2) creates a new variable for each symbol var and assigns the associated initializer, (3) evaluates the end-condition, if T, then evaluates all result expressions returning the last one. If end-condition is false, (4) then expressions are evaluated in order, then next (5) the updates are evaluated in order and are (6) assigned to the var's and we continue with (3) above. Example: (defun show-squares (start end) (do ((n start (+ n 1))) ((> n end) 'done) (format t "~A ~A~%" n ((*n n)))) Do can be confusing at first. There are some alternatives but I’d rather see a do-loop over these (ie. Tagbody, prog) which act as do-while loops. Here's an example of how they look: (defun show-squares (start end) (let ((n start)) (prog () loop (if (> n end) 'done) (block (format t "~A ~A~%" n (* n n)) (incf n)))))) Some nicer iterators: (dolist (var initial return) expressions) Used to iterate over the elements of a list (initial is a list). (dotimes (var initial return) expressions) Initial here is a number, where var ranges from 0 to initial. In both cases return is what is returned from the iterators. It defaults to NIL.

Recursion

In mathematics, recursion is the primary means of giving a finite definition for the value of a function when the arguments to that function can be arbitrarily large. It is also the primary means of defining such functions in LISP. An example: factorial where factorial(n) returns the product of the first n integers. Factorial can be defined recursively as: factorial(n) = {1 if n = 0 n * factorial(n-1) if n > 0} Example of this definition: factorial(3) = 3 * factorial(2) 3 * (2 * factorial(1)) 3 * (2 * (1 * factorial(0))) 3 * (2 * (1 * 1)) 3 * (2 * 1) 3 * 2 6 (defun factorial(n) (cond ((=n 0) 1) (t (* n (factorial (- n 1))))) Another way to think about recursion (from Graham, p.17): A better metaphor for a function would be to think of it as a process one goes through. Recursion is natural in a process. A real-world example: say you want to write a report on Machiavelli but don’t anything about him. Process: (1) Get a copy of a relevant document (2) Look for information about Machiavelli (3) If the document cites other documents, look at those. Now let's do a recursive version of show-squares. Note this can be made more elegant. (defun show-squares (start end) (cond ((> start end)) (t (format t "~A ~A~%" start (* start start)) (show-squares (1+ start) end)))))

[ csc242 Home ]