![[Santa Clara University]](../images/top.gif){kind=small}
and Computer Science
|
|
||
|
Department of
Mathematics and Computer Science |
|
|
||
(print '(Hello World!))
LISP was developed by John McCarthy during 1958-59 and published and defined in the article: J. McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I," Communications of the ACM, v. 3, n. 4 (April 1960), pp 184--95.
An overview of LISP appeared in another article in the MAA Monthly: Wand, "What is LISP?" v. 91, n. 1 (Jan 1984), pp 32-42.
LISP is the classical example of a Functional programming language. "Statement" are functions that return values and can be used as argument to other functions. Because of the intrinsic functional nature of LISP, recursion is a more natural way to code functions, although iteration is also possible.
Humorously, some people suggest that LISP is actually an acronym for "Lots of Idiotic Senseless Parentheses."
One feature of many implementations of LISP is extended precision integer arithmetic.
Script started on Wed Mar 15 13:30:48 2000
math 21: more fact.lsp
(defun fact (x)
(prog (temp)
(setq temp 1)
loop (cond ((zerop x) (return temp))
( T (setq temp (* temp x))
(setq x (1- x)) (go loop))
)
)
)
math 22: lisp
AKCL (Austin Kyoto Common Lisp) Version(1.619) Thu Oct 7 15:46:49 PDT 1993
Contains Enhancements by W. Schelter
>(load "fact.lsp")
Loading fact.lsp
Finished loading fact.lsp
T
>(fact 100)
9332621544394415268169923885626670049071596826438162146859296389521759999322
9915608941463976156518286253697920827223758251185210916864000000000000000000
000000
>(bye)
Bye.
math 23: exit
exit
script done on Wed Mar 15 13:31:48 2000
Let f(x,y) = x + y.Note that data in LISP are written as lists, and program operations are also written as lists. The language, in a sense, makes no distinction between "program" and "data."
We could substitute "+" for "f" and write
+(x,y) = x + y.
If we move the left parenthesis, we get a LISP expression corresponding in meaning to the original algebraic expression, i.e.,
(+ x y) corresponds to x + y.
< s-expr > --> < atom > | "(" < s-expr > " . " < s-expr > ")"
| "(" < s-expr > { < s-expr > } ")"
< atom > --> < literal > | < numeric >
< numeric >--> < integer > | < real >
The second option for an s-expression is the "dotted pair" form, and
the third option is the "list" form.
Thus, the second option states that an s-expression is any atom
or dotted pair of s-expressions or list of s-expressions.
|
|
_____V_____ <==> (A . B)
| | |
|/___|___\| where A and B are
____/ \____ "atoms."
|A | | B|
|__| |__|
|
|
_____V_____ <==> (A . (B . C))
| | |
|/___|___\|
____/ \______
|A | | | |
|__| |/_|_\|
__ / \___
|B | | C|
|__| |__|
(((A . B) . C) . (D . E))
|
|
_____V_____ <==> (A . NIL)
| | |
|/___|___\|
____/ \
|A | NIL
|__|
|
|
_____V_____ <==> (A . (B . NIL))
| | |
|/___|___\|
____/ \______
|A | | | |
|__| |/_|_\|
__ / \
|B | NIL
|__|
|
|
_____V_____ <==> ((A . (B . NIL)) . (C . NIL))
| | |
|/___|___\|
____/ \______
| | | | | |
|_|_| |/_|_\|
/ \___ / \
A | | | C NIL
|_|_|
/ \
B NIL
(S1 . (S2 . (S3 . ... (Sn . NIL ) ... )))can be written as
(S1 S2 S3 ... Sn)
I.e., in C++, we would write (diagram) a list as:
_______ _______ _______
| | | | | | | | /|
--->| X | -|-->| Y | -|-->| Z | / |
|___|___| |___|___| |___|/__|
In LISP, we would diagram this list (more correctly) as:
_______ _______ _______
| | | | | | | | | _____
--->| | -|-->| | -|-->| | -|-->|_NIL_|
|_|_|___| |_|_|___| |_|_|___|
| | |
_V_ _V_ _V_
|_X_| |_Y_| |_Z_|
and this structure is a tree rotated counter-clockwise
45o. I.e., before rotation, it is a tree similar to
those presented above:
|
/ \
X / \
Y / \
Z nil
This structure is written in full "dot"-notation
(A . ((B . NIL) . NIL)) corresponds to:
___ ___
----[_|_]----[_|_]----NIL
| _|_
A [_|_]----NIL
|
B
which corresponds to (A (B)).
(A . ((B . (C . NIL)) . (D . (E . NIL)))) corresponds to:
LISP integers (for practical purposes) have no maximum size. (This features is not true in some PC-freeware versions, e.g., XLISP.) Since LISP is based on lists, large integers can be implements as a list of smaller integers. Appropriate arithmetic is automatic.
Ratios are rational numbers written as a fraction of integers. E.g., 7/3 is a ratio.
Reals are written with a decimal point and at least one digit to the right of the decimal point. E.g., 1. is an integer, but 1.0 is a real number.
Complex numbers are written as a list of two elements preceded by #c. E.g., #c(2 3) is the complex number 2+3i.
NOTE: There are standard abbreviations for the repeated composition of CAR and CDR. Each abbreviation begins with C and ends with R and includes a string of (up to 4) A's and D's within. Thus,Pictorially, we have the following:
quote or ' E.g., (quote (add sugar to tea)) results in (add sugar to tea)
- one argument (s-expression)
- value is the argument UNevaluated
or '(a b c) results in (a b c).car E.g., (car '(a . b)) results in a
- one argument (non-atomic s-expression)
- value is the left part of the root dotted pair
Note: If the argument is a valid list, the return value is equivalent to first element of the list as an element.
E.g., (car '(a b c)) results in a
and (car '((a b) (c d)) results in (a b).cdr E.g., (cdr '(a . b)) results in b
- one argument (non-atomic s-expression)
- value is the right part of the root dotted pair
Note: If the argument is a valid list, the return value is equivalent to list with the first element omitted (as a list).
E.g., (cdr '(a b c)) results in (b c)
and (cdr '((a b) (c d)) results in ((c d)).___ ___ ___ (A B C) <==> -->[_|_]--->[_ _]--->[_|_]--->NIL | | | A B C(car '(A B C)) corresponds to the left portion of the root node which is merely the atom A.(cdr '(A B C)) corresponds to the right portion of the root node which is
___ ___ --->[_|_]--->[_|_]--->NIL | | B Cwhich is the list (B C).
cons
"construct"E.g., (cons 1 2) results in (1 . 2)
- two arguments (s-expressions)
- value is a new dotted pair with the first argument as the CAR and the second as the CDR.
(cons 'A '(B C)) results in (A B C)
(cons 'A NIL) results in (A).setq E.g., (setq a '(1 2 3)) means that a has the value of the list (1 2 3).
- two arguments (first is a literal atom, second is any s-expressions)
- value is the value of the second argument
- side-effect: the first argument takes on the value of the second argument as its "value" (association).
Thus, (car a) results in 1 and (cdr a) results in (2 3).
(cadr x) is equivalent to (car (cdr x))
(cdar x) is is equivalent to (cdr (car x))
(cadar x) is is equivalent to (car (cdr (car x)))
etc.
| atom |
(atom '(A B C)) results in NIL. |
| NULL |
(NULL '()) results in T (NULL '(A B C)) results in NIL. NOTE: This function can be used to detect the end of a list. |
| EQ |
(EQ 1 '(1 2)) results in NIL NOTE that the next function is similar, but is non-elementary. |
| EQUAL |
(EQUAL '(A) '(A)) results in T BUT (EQ '(A) '(A)) results in NIL. |
| numberp |
|
| oddp |
|
| zerop |
|
| plusp |
|
| member |
(member 1 '(2 (1 2) 3)) return the value of NIL. |
(+ x y) returns x+y [OTHER LISPs may use PLUS] (* x y) returns x*y [OTHER LISPs may use TIMES] (- x y) returns x-y [OTHER LISPs may use DIFFERENCE] (/ x y) returns x/y [OTHER LISPs may use QUOTIENT]NOTE: With Common LISP, if both x and y are integers, the result from a division is given as an integer or as an integer ratio. To convert the value to a real number, one needs to multiply it by 1.0 or use real numbers as arguments.
Each of these four arithmetic functions admit of more than two arguments. In this case, the operator is applied successively after evaluating the arguments from left to right.
(1+ x) returns x+1 [OTHER LISPs may use ADD1] (1- x) returns x-1 [OTHER LISPs may use SUB1]A sample translation of C/C++ code to LISP:
B = 2;
C = 3;
A = 3*(B+C);
translates into
(setq b 2)
(setq c 3)
(setq a (* 3 (+ b c)))
Common LISP also has two functions for "remaindering" after
division, rem and mod. Both return the
same answer when the result of a division is a positive number,
but when the result is negative, the results are different.
See a reference book for the technicalities.
(LAST list) returns last dotted pair of list
(LENGTH list) returns the length of list
(NCONC list1 list2) concatenates list1 and list2 together into one list, destroying the old list1 and list2 as independent lists. List1 has been changed and list2 is part of it. This basically takes the rightmost NIL in list1 and replaces it by a pointer to list2.
(APPEND list1 list2) creates a new list which is the concatenation of list1 and list2 without changing list1 or list2.
NOTE: The visible output of NCONC and APPEND with the same arguments would be the same. But the functions work in significantly different ways.
(REVERSE list) creates a new list which is the reverse of list.
(NREVERSE list) reverses pointers in old list (on the "top" level). The old list has been changed.
(RPLACA list y) replaces (CAR list) with y.
(RPLACD list y) replaces (CDR list) with y.
NOTE: These are "non-elementary" fucntions. It is possible to construct these functions as combinations of elementary functions (and the use of recursion).
(> x y) returns T if number x is greater than number y
(>= x y) returns T if number x is greater than or equal to
number y
(< x y) returns T if number x is less than number y
(<= x y) returns T if number x is less than or equal to
number y
(= x y) return T if numbers x and y are equal
MATHEMATICAL FUNCTIONS:
(expt base exponent) returns the value of the base raised
to the power of the exponent
Common LISP includes the standard mathematical functions taking
a single argument, such as sqrt, gcd, lcm, exp, abs, sin, cos, tan,
asin, sinh, asinh and others.
| eval |
|
(eval '(+ 1 2))
results in 3
(setq a '(b 1 2))
(setq a (cons '+ (cdr a)))
(eval a)
results in 3
NOTE: One can image the LISP system itself as being the
function EVAL.
NOTE: This function is central to the power of LISP. By means of this function, DATA becomes PROGRAM and thus, a PROGRAM can modify itself and thus, in some sense, "learn."
COND takes several two-element lists as arguments.
The first element in each of these lists is a conditional expression and
the other element is an action. E.g.,
(COND (condition1 action1)
(condition2 action2)
(condition3 action3)
...
(condition-m action-m) )
The first condition that evaluates to T has its corresponding
action performed--all others are ignored.
(setq a 1)
(cond ((zerop a) (setq b 2))
((oddp a) (setq b 5))
(t (setq b 7)))
What is the value of b?
(Older versions of LISP included the word "LAMBDA" as well, a nod to the origins of LISP.)
In general, a function definition takes the form:
(DEFUN function_name input_var_list action)
COMMON LISP allows more than one action. They are merely listed
in order.
Example 1: Function to see if EL is in list LIST.
(defun contains (EL LIST)
1) (cond ((null LIST) NIL)
2) (t (cond ((equal EL (CAR LIST)) T)
3) (t (contains el (cdr LIST)))))))
Think recursively!The CAR is not a list. To test to see if EL equals the CAR (and thus whether EL is in LIST), we use EQUAL (line 2). If EQUAL returns T, we are done; if NIL (false) we continue our search.
CDR is a list. To test to see if EL is in this section of the original LIST, we re-use CONTAINS (line 3).
In the extreme case, LIST may be NIL (e.g., when we have run out of elements to test in a list and take the CDR, we get the null list) (line 1).
Example 2: Function to compute the length of list LIST.
(defun howlong (LIST)
1) (cond ((null LIST) 0)
2) ((atom LIST) 0)
3) ((null (cdr LIST)) 1)
4) (t (1+ (howlong (cdr LIST))))))
Once again we try to think recursively, and try to use "divide
and conquer" techniques.
Given a list, if the CDR is NIL, there is only one element in that
list, so the length must be 1 (line 3).
If the CDR is not NIL, i.e., if LIST is a list, we use recursion
to find the length of the CDR and add 1 to that result (line 4).
For example,
(3 4 2 1 5)
| \________/
CAR CDR ===> howlong is the CDR? => 4
\____________/
length of complete list => 1 + 4 => 5
In extreme cases, LIST may be an atom (line 2) or NIL (line 1).
Because of this, LISP provides sequential flow functions that also allow internal branching (and thus provide for looping). More recent versions of LISP (including Common LISP), provide for explicit loop constructs.
The classical LISP sequential function is PROG.
The branch function is GO.
The return function is RETURN.
PROG takes several arguments. The first is a list of local
variables. The other arguments are functions executed in the
order they are included.
PROG provides a means to group several actions together (such
as the { ... } pair in C/C++). As in C/C++, such a "block" also
can have local variables declared.
The value of the PROG construct is the value explicitly returned
by the RETURN statement if the PROG includes one and if it is
is executed. Otherwise, PROG returns NIL.
GO takes one argument, a literal atom, which acts as a label before any function within the PROG. Its value is NIL. Its side-effect is to transfer flow of the code to the function following the literal atom.
RETURN takes one argument. Its value is the value of the argument. Its side-effects are (1) that its value becomes the value of the PROG in which it is found and (2) that the execution of the PROG structure terminates.
PROG statements were needed in early versions of LISP for the same reason why braces are needed in C/C++, namely to group multiple statements together as one unit. PROG with a GO also was the only way to create an iterative loop in earlier versions of LISP. In most cases, Common LISP does not require a PROG to group statements. Common LISP also provides alternative means for repetition.
Example: Sequential/iterative version of the length function howlong.
(defun howlong2 (list)
(prog (temp num)
(setq temp list)
(cond ((atom temp) (return 0))
((null temp) (return 0)))
(setq num 0)
loop (setq num (1+ num))
(setq temp (cdr temp))
(cond ((null temp) (return num))
( t (go loop)))))
This approach uses a pointer temp to point to the list.
Each time through the loop, the CAR is omitted, and temp is
reset to the (cdr temp). At the same time, num is
incremented by 1. When temp has been reset to the end
of the list, NIL, num indicates the length of list.
NOTICE that this versions is about double the length of the recursive version (in section I-8, Example 2)!
An attempt to translate the recursive version into a C++-like language would result in code such as:
class node
{public:
node * info;
node * next;
};
int howlong(node * list)
{
if (list == NULL)
return 0;
else if (atom(list))
return 0;
else if (list->next == NULL)
return 1;
else
return (1 + howlong(list->next));
}
Note that this code is problematic since it would be difficult
to code a function atom to determine whether the
input list was either a pointer to a list or a character
atom or an integer.
The corresponding iterative version might look like the following:
int howlong2(node * list)
{
node * temp;
int num;
temp = list;
if (atom(list))
return 0;
else
{
num = 0;
do{
num++;
temp = temp->next;
}
while(temp!=NULL);
return num;
}
}
(DEFUN FACT (X)
(PROG (ANS)
(SETQ ANS 1)
LOOP (COND ((ZEROP X) (RETURN ANS))
(T (SETQ ANS (* ANS X))
(SETQ X (1- X))
(GO LOOP))
)
)
)
But, PROG and GO are neither part of "pure" LISP and, since they can
lead to "spaghetti" code as in other languages, modern programmers
recommend avoiding such constructs when possible.
To include iteration, more recent dialects (such as Common LISP) have include iteration functions.
(DO (
(var_1 init_val_1 step_1)
(var_2 init_val_2 step_2)
...
(var_n init_val_n step_n) )
( end_test
end_action_1
end_action_2
...
end_action_k
return_value )
body_action_1
body_action_2
...
body_action_m
)
This DO construct is common in most dialects of MACLISP and
Common LISP. It is a looping structure which eliminates the need
for the PROG and GO structures of "ancient" LISP.
The DO construct consist of three major sections:
(defun fact (x)
(do (
(temp x (1- temp)) ;sets temp to x initially and
; decrements temp each time through loop
(ans 1) ;sets ans to 1 initially
) ; (used as culmulative product)
((zerop temp) ans) ;exit condition and return value
(setq ans (* ans temp)) ;body of loop
)
)
DOTIMES loop
(DOTIMES
(loop_var end_value opt_return_value)
body_action_1
body_action_2
...
body_action_m
)
This DOTIMES construct is available in most dialects of
Common LISP. It is a counted loop in which the actions
indicated in the body of the loop are performed the number of
times determined by the limit indicated for the loop_var.
When the actions in the loop are being executed, the value of
loop_var begins with 0 and goes up to but
does not include end_value. As soon as loop_var
reaches the value of end_value the structure is exited with
the value of the structure being that of opt_return_value (which
is optional).
For example,
(defun fact (x)
(setq ans 1)
(dotimes
(i x ans) ; i is loop var and x is upper limit
; with ans being the return variable
(setq ans (* (1+ i) ans))
)
)
Generalized LOOPThe WHEN construct's structure is as follows:
(WHEN predicate_expression (RETURN return_value))
The predicate_expression could be any test that evaluates
to T or NIL.
The LOOP contruct itself has this structure:
(LOOP
body_action_1
body_action_2
...
body_action_m
)
The LOOP executes all body_actions in the order listed
repeatedly.
One of the body_actions must be some sort of test (such as
the WHEN) in order to break out of the loop.
For example,
(defun fact (x)
(setq ans 1)
(loop
(setq ans (* x ans))
(setq x (1- x))
(when (zerop x) (return ans))
)
)
(Other dialects may use an exclamation point or COMMENT as a function name.)
Call by Value: Most LISP functions and user-defined functions have parameters passed via call-by-value. The actual parameters are first evaluated, and then these values are bound to the formal parameters. None of the parameter is changed in the calling program upon completion of the function, except via the function return value.
Call by Name: In a few LISP functions (e.g., COND, QUOTE, DEFUN), the actual parameters are not evaluated but stored as a literal string. These parameters are evaluated only when needed (used).
Some authors speak about "pure" LISP which does not use PROG (nor RETURN nor GO). It is a lisp that involves (because arithmetic functions), the primitives CAR, CDR, CONS, EQ, ATOM, QUOTE, COND, DEFUN alone.
The following are some of the more common commands:
(PRINT a) prints the value of a (on the monitor). (Remember that each evaluation of a function will return the function's value to the monitor. (PRINT a) is intended for returning one or more values in the midst of a program, rather than as the final value.)
(TERPRI) induces a carriage return (on the monitor).
(SETQ IN1 (OPEN "FOO.LSP" :DIRECTION :INPUT))
where IN1 can be any local atom. This associates the local
atom IN1 with the disk file FOO.LSP. A similar process is
necessary with C++ when using disk files, e.g.,
#include<fstream.h>
ifstream Infile;
Infile.open("in.dat");
Then to READ from file FOO.LSP, use:
(READ IN1) reads one s-expression from the file associated with IN1 and return the s-expression as its value.
(READ-CHAR IN1) reads one character.
(Other functions are possible -- see a complete Common LISP manual.)
To CLOSE the file associated with IN1:
(CLOSE IN1)
In a similarly fashion, to OPEN file BAR.LSP in your directory and prepare it as an
OUTPUT file:
(SETQ OUT1 (OPEN "BAR.LSP" :DIRECTION :OUTPUT))
Then to PRINT to BAR.LSP, use:
(PRINT s-exp OUT1) to print in a form which can later be used by READ, with a preceding NEWLINE and followed by SPACE and escape characters if necessary.
(PRIN1 s-exp OUT1) to print in form which can later be used by READ, without any surrounding spaces but with escape characters if necessary.
(PRINC s-exp OUT1) is like PRIN1 except special characters are printed without other marks (with NO escape characters).
(TERPRI OUT1) forces a carriage return in file OUT1.
A-lists can be used in many ways, but one use is to provide a way to reference values (i.e., bindings) of variables upon recursive function calls (and returns). Since recursion is common, there needs to be a way to reference the "most recent" binding of a given variable. This is done via the association list (A-list).
New associations are usually added before the CAR of the A-list, resulting in new CAR. When a value is needed corresponding to a specific atom (i.e., variable), the list is searched starting with the CAR and at the first discovery of the desired atom, the value associated with it is used.
In any A-list, it is possible that a literal atom may appear several times. When the list is searched, however, only the instance nearest to the head of the list is identified.
If the atom is a function name, its property list will contain an indicator giving the function type.
The major functions used with P-Lists are the following:
(SETF (GET x z) y) --- gives x the z-property value of y. [OTHER LISPs may use (PUTPROP x y z).] If x and z are atoms (used as names), they should be preceded by a quote mark. For example,
(setf (get 'sam 'eyes) 'blue)
In a language such as Icon, in which "arrays" could have character
strings as subscripts, this LISP function could be seen to be
equivalent to sam["eyes"] = "blue".
(GET x z) --- gets the value of the z-property of x. If x and z are atoms (used as names), they should be preceeded by a quote mark. For example,
(get 'sam 'eyes)
should return the value BLUE (assuming the earlier value setting).
(REMPROP x z) --- removes the z-property from the P-List of x.
(SYMBOL-PLIST x) --- returns the entire P-List of x (with all the values of the properties).
Memory is divided into a static area and a dynamic area. The static area contains the translator (if it exists), the interpreter, I/O interface, and the garbage collector. The dynamic area contains the various lists (A-List, Oblist, LAVS, and P-Lists) along with the user program code.
(defun towers (num from to aux)
(cond ((not (zerop num))
(towers (1- num) from aux to)
(print (list 'move 'disk num 'from from 'to to))
(towers (1- num) aux to from)
)))
(towers 5 'a 'b 'c)
(defun exp (x y)
(cond ((zerop y) 1)
( (* x (exp x (1- y))))))
(exp 2 3)
(defun length (x)
(cond ((null x) 0)
( (1+ (length (cdr x)))) ))
(defun member (x y)
(cond ((null y) nil)
((equal x (car y)) T)
( (member x (cdr y))) ))
(defun append (x y)
(cond ((null x) y)
((cons (car x) (append (cdr x) y))) ))
Script started on Wed Apr 7 21:11:37 1999
math 21: cat foo.lsp
(defun for (a)
(prog ()
loop (print (car a))
(setq a (cdr a))
(cond ((not (null a)) (go loop)))))
(defun rev (x)
(cond ((null (cdr x)) (print (car x)))
((prog () (rev (cdr x))
(print (car x))))))
math 22: lisp
AKCL (Austin Kyoto Common Lisp) Version(1.619) Thu Oct 7 15:46:49 PDT 1993
Contains Enhancements by W. Schelter
>(+ 1 2)
3
>(setq a 2)
2
>(setq b '(a 2 3))
(A 2 3)
>(car b)
A
>(cdr b)
(2 3)
>(cons '+ (cdr b))
(+ 2 3)
>(setq c (cons '+ (cdr b)))
(+ 2 3)
>c
(+ 2 3)
>(eval c)
5
>(load "foo.lsp")
Loading foo.lsp
Finished loading foo.lsp
T
>(setq d '(1 2 3 4 5 6 7))
(1 2 3 4 5 6 7)
>d
(1 2 3 4 5 6 7)
>(rev d)
7
6
5
4
3
2
1
NIL
>(for d)
1
2
3
4
5
6
7
NIL
>(bye)
Bye.
math 24: exit
math 25:
script done on Wed Apr 7 21:13:45 1999
This page is maintained by Dennis C. Smolarski, S.J.
dsmolarski@math.scu.edu
Last updated: 29 March 2000. Minor corrections: 29 April 2002,
12 October 2005, 8 November 2007.