Introduction to LISP

Syntax

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

   Lexemes

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.

   Constants

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 ")".

    Variables

    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.

    Operators

    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.

    Note

    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.

Arithmetic

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

    Relations

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

    Tests/Predicates

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?

    Logical

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.

    Lists

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

    Functional

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

    Printing

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:

Quotation

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

   Assignment

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

   Selection

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))

   Iteration

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

    Blocks

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

    Control

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

    Files

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

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

Hints

• (1) Let LISP do the work for you!
  • (1a)Forget efficiency! Quickly break down complex problems into simple ones (top-down) in the clearest way you can. Then code and test solutions to the simple problems bottom up. Once they works, and only if the user complains you can speed it up.
  • (1b)LISP is the main program! Aim for lots of useful but small functions. Give the user a wide choice of "programs" to run. Use them yourself.
  • (1c)LISP functions are often recursive.
  • (1d)Don't waste time planning input/output. LISP functions are given lists as data by the interpreter and outputs a list as a result to the standard output.
• (2)Forget assignments, sequences, and loops! Look for ways to classify the givens (COND, ATOM, NULL, MINUSP...) plus ways to decompose them (CAR, CDR,...) plus ways to assemble an answer (+, CONS, LIST, APPEND, ...)
• (3) Divide and conquer. Look for known functions: predefined, defined later, or the function being defined.

• (4) layout LISP carefully with indented sublists. For example:

   	 (DEFINE (length L)

   	   (COND

   	     ((NULL L)  0)

   	     ((ATOM L)  1)

   	     (   T (+ 1 (LENGTH (CDR L)) ))

   	   )

   	 )

• (6) When in doubt add right parentheses.

• (7) End all CONDs with a (T something) pair

Details

Scoping

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 ...).

   Axioms

   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.

   Abbreviations

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>>

Glossary

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>>