[Skip Navigation] [Remove Frame] [CS320] [Text Version] lisp.intro.html Sat Dec 23 08:00:16 PST 2006


    Introduction to LISP


        LISP uses a simple, rigid, and unambiguous syntax
      1. expression::=constant | variable | "(" operator #S_expression ")".


      2. word::= # word_char,
      3. word_char::=any character except parentheses, quotes, and commas,
      4. string::= quote #(char ~ quote) quote.

        LISP ignores upper and lower case outside strings. White space is used to separate adjacent words and otherwise significant only inside strings. The meaning of aword is determined by their place in the input.


      5. constant::=number | string | "NIL" | "T" | quoted_list.
      6. string::= double_quote #non_quote double_quote.
         		NIL	is for False and the empty list (),
         		T	is for True,
      7. quoted_list::= "(QUOTE" list")" | "'" list. The QUOTE operator stops the interpreter from evaluating QUOTE's arguments. So (+ 1 2) has value 3 but (QUOTE (+ 1 2)) has value (+ 1 2).

        A list can be empty (NIL), an atom (word, number, string), a pair, or a list of lists between parentheses.

      8. list::= NIL | atom | CONS_pair | linked_list.
      9. atom:::= string | number | word.
      10. CONS_pair::= "(" list "." list ")", a constructed pair.
      11. linked_list::= "(" #list ")".


        Lisp allows you to associate a value with an atom. You can then use that atom in place of the value. Normally, this is done when a function is called: the arguments are bound to the values of the actual parameters. You can also change the values bound to an atom. We call such atoms variables:
      12. variable::=word bound to a value. Notice that inside a QUOTE a variable stands for itself and is not treated as having a value.


        All operators are applied to their arguments like this:
      13. (operator args) Many operators evaluate their arguments before the start to work and are called functions. Addition (+) and multiplication (*) are typical functions. The rest of the operators are called macros. QUOTE, DEFINE, COND and IF are examples of macros.
      14. operator::= function | macro. Functions and macros look alike - an atom.


        The meaning of a word depends on where it is placed. Inside a QUOTE it is a constant, by itself it should be a variable, and at the start of a S_expression (after the parentheses) it should be an operator. If a word should be a variable but has no value then LISP reports and error and stops evaluating the expression. Similarly if a word should be an operator then interpretation stops with an error and no value.

        For example: (QUOTE +) outputs +, (+ ....) adds up the arguments, and + gives an "undefined value" error.

        Defining New Functions

        Functions are declared in two ways:
      15. (DEFINE (name args) S_expression)
      16. (DEFUN name (args) S_expression...)

        Both create a global meaning for the name and allow it to be used as an operator:

      17. (Name actual_arguments)

      18. (DEFINE (N args) e) - Afterwards N means (lambda (args) e) and so has dynamically scoped variables. Because e is evaluated when called it's non- local variables are interpreted in the environment of the call... not the definition.

      19. (DEFUN N (args) e) is similar but with static scoped variables. N is bound to a kind of a compiled function that is called like this (N args). The compilation occurs in the environment of the definition and so non-local variables refer the those defined at the time and place of definition.

      . . . . . . . . . ( end of section Syntax) <<Contents | End>>

      Some Functions

        XLISP has many ready made functions. Here is a partial list. We keep a complete list online, see below. The most important functions are in capitals. Optional arguments are in square brackets. e is an S_expression, t any condition, f any function, s is a symbol, n is a numerical expressions.


      1. (* n...) multiply
      2. (+ n...) add
      3. (- n...) subtract, negate
      4. (/ n...) divide
      5. (1+ n) add one
      6. (1- n) subtract one
      7. (abs n) the absolute value of a number
      8. (cos n) (sin n) (tan n) trig functions
      9. (exp n) exponential of n
      10. (expt n1 n2) n1 to the n2 power
      11. (float n) converts to a floating point
      12. (max n...) (min n...) the largest/smallest
      13. (random n) random number between 1 and n-1
      14. (rem n...) remainder after division
      15. (sqrt n) compute the square root of n
      16. (truncate n) truncates float n to an integer


      17. (/= n1 n2) test for not equal to
      18. (< n1 n2) test for less than
      19. (<= n1 n2) test for less than or equal to
      20. (= n1 n2) test for equal to
      21. (> n1 n2) test for greater than
      22. (>= n1 n2) test for greater than or equal to


      23. (ATOM e) is this an atom?
      24. (consp e) is this a non-empty list?
      25. (eq e1 e2) (eql e1 e2) (equal e1 e2) Various equality tests.
      26. (evenp n) is n even?
      27. (listp e) is this a list (not a null or atom)?
      28. (member e1 e2) is e1 an item in e2?
      29. (minusp n) is n negative?
      30. (NULL e) is this an empty list?(sometimes NULLP)
      31. (numberp e) is e a number?
      32. (oddp n) is n odd?
      33. (plusp n) is n positive?
      34. (ZEROP n ) is n zero?


      35. (AND [e]...) a logical and (short-circuited)
      36. (NOT e) is e false? = (null e)!
      37. (OR [e]...) logical or (short-circuited??)
      38. NIL Constant with effect of false
      39. T predefined constant with effect of true.
      40. Any non-NIL value is treated as false.


      41. (APPEND [e]...) append lists
      42. (assoc e1 e2) Find pair (x y) in e2 with x=e1, returns y.
      43. (CAR e) return the first item of CONS-pair e
      44. (CDR e) return the second item of Cons-pair e
      45. (CONS e1 e2) construct a new Cons-pair
      46. (cxxr e) cadr, caar, cdar, cddr (cxxxr e) all cxxxr combinations(x::=a|d)
      47. (cxxxxr e) all cxxxxr combinations
      48. (last e) return the last list node of list e
      49. (length e) the length of a list or string
      50. (LIST [e]...) constructs a list of values
      51. (NTH n e) the nth item of e
      52. (nthcdr n e) the nth cdr of e
      53. (reverse e) reverse a list

        Strings and Characters

      54. (char e1 n) nth character in string e1
      55. (strcat [e]...) concatenate strings


      56. (apply f args) apply a f to args
      57. (funcall f [args]...) call function with args
      58. (LAMBDA (args) e) a function that given args returns value of e.
      59. (mapc f e) (mapcar f e) (mapl f e) (maplist f e) apply f to all (cars, cdrs, elements) in e


      60. (prin1 e ...) print e
      61. (princ e ) print without quoting
      62. (print e) print e on a new line
      63. (terpri ) terminate the current print line
      64. (write-char character) write a character

      . . . . . . . . . ( end of section Some Functions) <<Contents | End>>

      Some Macros

        XLISP has many macros. Here are some:


        'e::=(QUOTE e) return e unevaluated #'e::= (function e) quote a function
      1. #(e...)::= an array


      2. (setq s e) set the value of a symbol s to e


      3. (COND [pair]...) select first pair=(t e) with t non-null and evaluate e.

      4. (COND (e1 e2 ) more)
        If value(e1) is Not NIL NIL
        (COND (e1 e2 ) more) returns value of e2 (COND more)
      5. (case e [case]...) select by case
      6. case::=(value [e]...)

      7. (if e1 e2 [e3]) if e1 then e2 else e
      8. =(COND(e1 e2)(T e3))


      9. (do ([binding]...) (t) e...) loop
      10. (do* ([binding]...) (t) e...) loop
      11. (dolist (s list) e...) for s in list
      12. (dotimes (s e1) e2...) s in 0..e1-1


      13. (LET ( (s e1)...) e2...) block{LIST s=e1;... .e2..}
      14. (progn [e]... en) execute sequentially{...}
      15. (prog ([binding]...) [e]...) begin...end/{...}


      16. (EXIT) exit XLISP
      17. (return e) cause a prog to return value
      18. (trace atom...)
      19. (untrace atom...)


      20. (LOAD filename [vflag [pflag]]) load a file

      . . . . . . . . . ( end of section Some Macros) <<Contents | End>>




        Each function call adds new local variables to the environment by (1) evaluating the actual arguments, and (2) binding them as values to the formal arguments. These local assignment are removed when the function returns.

        The first LISP was defined by an interpreter - called EVALQUOTE. It used dynamic scoping with shallow binding and associated a "P-list"(Property List) with each atom. Nowadays LISPs (including Scheme) use static scoping but the P-Lists remains a useful tool.

        In our LISP (XLISP) the

      1. (DEFUN name (args) S_expression) macro defines the function and ensures static scoping by binding the environment of the definition into the function code. This creates something called a closure.

        I added the

      2. (DEFINE (name args) S_expression) macro to XLISP. I stayed close to the original EVALQUOTE model and used the name's P-list to bind the name to a LAMBDA_expression. The result is that 'define' uses dynamic binding.

        The LISP block structure:

      3. (LET ((variable val)...) S_expression...) introduces a local set of variables each with a value. Each S_expression is executed in turn and use the variables. If an S_expression defines a function by using '(DEFUN ...) it has access to a set of variables that nobody else can touch. However, the function names have global scope and so can be called from outside the (LET ...).


        Every LISP S_expression evaluates to one of a NIL, an atom, or a CONS-pair. Thus it is useful to study how these kinds of things behave. LISP is "logical" in the sense that its inventors had a set of well defined assumptions (axioms) that they wanted LISP to implement. Here are some of them:

        For all LISP expressions x,y:

      4. (CAR (CONS x y)) = x
      5. and (CDR (CONS x y)) = y.

        If x is a Cons-pair then

      6. (CONS (CAR x) (CDR x) ) = x.

        No Cons-pair is also an atom:

      7. not (ATOM (CONS x y)).

        No Cons-pair is NIL:

      8. for no x,y ( (CONS x y) != NIL ).

        The above describe the simple behavior of CAR, CDR, CONS, NIL and so on. The following are more complex and do not have to be mastered.

        More Advanced Axioms

        First we have an induction axiom that states that if a property(P) is true of NIL and all atoms, and is preserved when new lists are constructed, then it is true of all lists:
        (induction): if P(NIL) and for all x(if (ATOM x) then P(x)) and for all x,y( if P(x) and P(y) then P(CONS x y) ) then for all x(P(x)).

        The induction rule essentially limits lists to precisely those that can be constructed from NIL and the atoms.

        The following recursion axiom permits us to reason about simple recursive definitions. It states the circumstances when we can conclude that two functions f and g are always equal.
        (recursion): if for all x:atom( f(x) = g(x) ) and f(NIL)=g(NIL) and for some H, all x( (if not(ATOM x) then f(x) = H(x, f(CAR x), f(CDR x))) and (if not(ATOM x) then g(x) = H(x, g(CAR x), g(CDR x))) ) then f=g.

        The recursion result allows us to conclude that a particular form of recursion gives a unique function or perhaps is undefined.

        The above are more for interest than to be memorized.


      9. (CADR x) = (CAR (CDR x))
      10. (CDDR x) = (CDR (CDR x))
      11. (CDAR x) = (CDR (CAR x))
      12. (CAAR x) = (CAR (CAR x)) and so on for CADDR, CADDDR, CDDDR, ...
      13. (NTH 1 x) = (CAR x)
      14. (NTH n x) = (CAR (NTH (- n 1) X))

        Inside LISP

        The data in LISP is a list. Internally all lists are either empty, atomic or a CONS-pair (Constructed Pair)
      15. list::= nil | atomic | Cons-pair. In practice these are (1) the null pointer, (2) a pointer to a string, (3) a pointer to an object with two pointers called 'car' and 'cdr' respectively

         		cons [  car  |  cdr  ]

        A CONS-pair-pair is constructed like this: (CONS 'A 'B) and is printed (A . B). It is also called a "Dotted pair"

        Lists of more than 2 items are encoded using CONS-pairs as follows:

      16. (LIST 'A 'B 'C 'D)
      17. becomes ( A B C D )
      18. = (A . (B . (C. (D . NIL))))

        See Also

        Here is a page of pointers to many WWW pages on LISP: [ lisp.html ] The Source code for LISP is online. You may download and make copies of this code, compile it on your machine and use it any non-profit way you like. Do not sell it - improve it and give it away.

        [ http://cse.csusb.edu/dick/cs320/lisp/src/ ]

      . . . . . . . . . ( end of section Details) <<Contents | End>>


    1. LAMBDA_expression::=expresses a function by listing its formal arguments and an S_expression that when evaluated gives the result: (LAMBDA (arguments) S_expression).

    . . . . . . . . . ( end of section Introduction to LISP) <<Contents | End>>