Tony Henry CLASS: CS320
Yvonne Osuna PROFESSOR: Dr. Botting
DUE DATE: 12-13-90
LISP
HISTORY
LISP was created by John McCarthy and his students in the late
1950's. One of the first LISP programs did calculus problems at a level of
university freshmen. Another did geometric analogy problems of the sort
found in intelligence tests. Newer programs have been developed in LISP
that configure computers, diagnosed infections of the blood, understood
electronic circuits, evaluated geological formations, planned investments,
scheduled factories, designed fasteners, invented interesting mathematics
and a lot of others.
LISP is a language in which most research on representation is
done. These programs contribute to educational and intelligent support
systems. LISP was originally developed for solving problems in artificial
intelligence. It is a higher level programming language. as well as the
oldest and most widely used functional programming language. All LISP
dialects include imperative language features, such as variables,
assignment statements, and iteration.
LISP can increase productivity by enabling programmers to write big
programs much faster and far less expensively. LISP machines are
high-powered work stations programmed from top to bottom in LISP. The
operating system, the user utility programs, the editors, the compilers,
and the interpreters can all be written in LISP, which shows how powerful
LISP can be. LISP is a good tool for the computer scientist and computer
engineer to understand because of the power of symbol manipulation.
LISP has two primitive data types : atoms and lists. Atoms which are
identifiers are symbols of LISP. Numeric constants are also considered
atoms. Lists are specified by delimiting their elements with parentheses.
Lists are stored as single-linked list structures and referenced by a
pointer to it's first element.
It also has a powerful set of primitive operations:
A constructor - for constructing a composite list from two
components.
Two selectors car and cdr for, respectively selecting the first
component and the remainder of the list.
Two predicates atom[x] and eq[x, y] which test whether x is an atom
and whether two atoms x and y are identical.
A compound conditional of the form [p1->a1;p2->a2;...;p(n)->a(n)]
which may be read as "if p1 then a1 else if p2 then a2 ...else if p(n) then
a(n)" and results in execution of the action a(i) corresponding to the
first true predicate p(i).
Binding operators lambda[x;f] and label[s;f] which bind free
instances of x in f so that they, respectively, denote function arguments
and recursive function calls. These operators provide for handling
functions which have functions as arguments in the lambda calculus.
LISP contributed a great deal to our understanding of programming
language theory. It is also the most influential and widely used
artificial intelligence language probably because of it's simplicity and
power. LISP is one of the most important developments of programming
languages.
Design primarily for symbolic data processing, LISP is a formal
mathematical language. All data are in the form of symbolic expressions,
usually referred to as S-expressions. S-expressions are of indefinite
length and have a branching tree type of structure so that significant
sub-expressions can be readily isolated.
Most elementary type S-expression is the atomic symbol. Atomic
symbol is a string of no move than thirty numbers and capital letters; the
first character must be a letter.
If an S-expression is not a atomic symbol, then it would be composed
of these elements in the following order: a left parenthesis, and
S-expression, a dot, an S-expression and a right parenthesis.
DATA SYNTAX
letter ::= "A" | "B" | ... | "Z",
number ::= "1" | "2" | ... | "9",
atomic_symbol ::= letter atom_part,
atom_part ::= empty | letter atom_part | number atom_part,
empty ::= "",
S_expression ::= atomic_symbol | "(" S_expression "."S_expression ")" |
list,
list ::= "(" S_expression # S_expression ")".
ELEMENTARY FUNCTIONS
cons ::= "(" "cons" expression1 expression2 ")".
the cons function has two arguments and is used to build larger
S-expressions from smaller ones.
EX. (cons A B) --> (A . B)
car ::= "(" "car" S_expression ")".
has one argument an will produce the first part of its
composite argument. Undefined if argument is atomic.
EX. (car (A . B)) --> A
cdr ::= "(" "cdr" S_expression ")".
has one argument, it produces the second part of the composite
argument. Undefined if argument is atomic.
In LISP the values TRUE and FALSE are represented by the atomic
symbols T and F, respectively. A function where the value is either TRUE
or FALSE is called a predicate.
eq ::= "(" "eq" S_expression1 S_expression2 ")".
this predicate is a test for equality on two atomic symbols.
Undefined for non-atomic arguments.
EX. (eq (A A)) --> T or (eq (A B)) --> F
atom ::= "(" "atom" S_expression ")".
this is a test for an atomic symbol; where TRUE if atomic
symbol and FALSE if its composite.
EX. (atom (C . D)) --> F
LIST NOTATION
There is a alternate form of S-expressions than Dot Notations
discussed up until now which is called List Notation. Lists are similar to
Dot Notation in that lists are of the form (f1 . (f2 . (... . (fn .
NIL)...))). The NIL is a terminator for a list (which can also can be used
as FALSE). The null list () is identical to NIL. List Notation can always
be writing is Dot Notation
In LISP either a space or a comma can be used in separating items in
a list. (A, B, C) is identical to (A B C).
EX. (A B C) = (A . (B . (C . NIL)))
(A B (C D)) = (A . (B . ((C . (D . NIL)) . NIL)))
((A)) = ((A . NIL) . NIL)
(A) = (A . NIL)
cxxr ::= "(" "c"("a"|"d")("a"|"d")"r" S_expression")",
cxxxr ::= "(" "c"("a"|"d")("a"|"d")("a"|"d")"r"S_expression")",
cxxxxr ::= "("
"c"("a"|"d")("a"|"d")("a"|"d")("a"|"d")"r"S_expression")".
Where the "a" correspond to the first S-expression value in a
expression and "d" corresponds to the rest of the list in a dot expression.
The last "a" or "d" in the name actually signifies the first operation in
order to be performed, since it is nearest to the argument.
EX. (cadr (A B C)) --> (car(cdr(A B C))) --> B
(cadadr(A (B C) D)) --> C
One can create a conditional expression is LISP. The is done in the
following form:
conditional_expression ::= "("predicate_1 function_1#("("predicate_n
function_n")")")".
In this function, the predicate is tested for the value of either TRUE or
FALSE. If the value is TRUE then the entire conditional expression is
equal to the value of the function. If the value is FALSE then it will
test the next predicate in the expression. This will continue until it
finds a predicate which is true or comes to the end of the expression. If
there is no value which is true, the expression will be undefined.
EX. (eq(car(x) A) cons(B cdr(x)) T x)
This example is testing if 'car(x)' is equal to 'A'. If it is
then it replaces the car of 'x' with 'B'. If 'car(x)' is not equal to 'A'
then it tests the next predicate. Since the T is equal to TRUE then the
value x remains unchanged.
We need a way to define functions and make them available to the user.
This is done by using the pseudo-function define:
DEFINE := "DEFINE (" #(FUNCTIONS DEFINED) ")"
; This is the old CYBER LISP
Example:
DEFINE ((
(MEMBER (LAMBDA (A X) (COND ((NULL X) F)
( (EQ A (CAR X) ) T) (T (MEMBER A (CDR X))) )))
(UNION (LAMBDA (X Y) )COND ((NULL X) Y) ((MEMBER
(CAR X) Y) (UNION (CDR X) Y)) (T (CONS (CAR X)
(UNION (CDR X) Y))) )))
(INTERSECTION (LAMBDA (X Y) (COND ((NULL X) NIL)
( (MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECTION
(CDR X) Y))) (T (INTERSECTION (CD X) Y)) )))
))
It's value is a list of functions defined, here it is MEMBER,UNION, and
INTERSECTION.
Here are some other useful functions:
append ::= "(" "append S_expression1 S_expression2")",
this function concatenates S_expression2 onto the end of
S_expression one.
EX. (append((A B)(C D E)) --> (A B C D E)
member ::= "(" "member" S_expression1 S_expression2 ")",
This predicate is true if the S_expression1 occurs among the
elements of list in S_expression2.
pairlis ::= "(" "pairlis" S_expression_1
S_expression_2 S_expression_3 ")",
This function gives the list of pairs of corresponding element
of the lists S_expression_1 and S_expression_2, and appends this to the
list S_expression_3. The resultant list of pairs, which is like a table
with two columns, is called an association list.
EX. (pairlis((A B C) (U V W) ((D . X)(E . Y)))
--> ((A . U)(B . V)(C . W)(D . X)(E . Y))
assoc ::= "(" "assoc" S_expression_1 S_expression_2 ")",
If S_expression_2 is an association list such as the one formed
by pairlis in the above example, then 'assoc' will produce the first pair
whose first term is S_expression_1. Thus it is a table searching function.
EX. (assoc(B ((A . (M N)), (B . (car X)), (C . (QUOTEM)),
(C . (CDR X)))) --> (B . (car X))
sublis ::= "(" "sublis" atomic_symbol S_expression ")",
Here S_expression_1 is assumed to be an association list of the
form ((u_1 . v_1)...(u_n . v_n)), where the u's are atomic, and
S_expression is an S-expression. What 'sublis does, is to treat the u's as
variables when they occur in S_expression, and to substitute the
corresponding v's from the pair list.
EX. (sublis(((X . SHAKESPEARE)(Y . (THE TEMPEST))) ,
(XWROTE Y))) -->(SHAKESPEARE WROTE (THETEMPEST))
ARITHMETIC
LISP has is method of handling fixed-point and floating numbers and
logical words. Functions and predicates are in the system for handling
arithmetic and logical operations and making basic test.
Numbers are stored in the computer as though they were a special type
of atomic symbol.
NOTE:
1. Numbers may occur in S-expressions as though they were atomic
symbols.
2. Numbers are constants that evaluate to themselves. They do
not need to be quoted.
3. Numbers should not be used as variables or function names.
FLOATING-POINT NUMBERS
RULES:
1. A decimal point must be included but not as the first or last
character.
2. A plus sign or minus sign may precede the number. The plus
sign is not required.
3. Exponent indication is optional. The letter E followed by
the exponent to the base 10 is written directly after the number. The
exponent consists of one or two digits that may be proceeded by a plus or
minus sign.
4. Absolute values must lie between 2 to the 129 power and 2 to
the -128 power.
5. Significance is limited to 8 decimal digits.
6. Any possible ambiguity between the decimal point and the
point used it dot notation may be eliminated by putting space before and
after the LISP dot. This is not required when there is no ambiguity.
EX. 60.0
6.E1
6000.00E-01
0.6E+2
FIXED-POINT NUMBERS
There are not much to them. The just written as integers with an
optional sign.
EX. 29
-32700
ARITHMETIC FUNCTIONS AND PREDICATES
Arithmetic functions must be given numbers as arguments; otherwise it
will result in an error. The arguments may be any type of number. Both a
fixed-point number can be use with a floating-point number a the same time
as arguments. If all arguments in a function are fixed-point numbers, then
the result will be a fixed-point number. If at least one argument is a
floating-point number, then the values of the function will be a
floating-point number.
plus ::= "(""plus" x1 x2 ... xn")",
is a function of any number of arguments whose values is the
algebraic sum of the arguments.
difference ::= "(""difference" x y")",
has for its value the algebraic difference of its arguments.
minus ::= "(""minus" x")",
has for its value -x.
times ::= "(""times" x1 x2 ... xn")",
is a function of and number of arguments, whose value is the
product (with correct sign) of its arguments.
In many modern LISP interpretters the normal symbols (+,-, *, /) are used
as alternatives for (plus, minus, times, ...).
add1 ::= "(""add1" x ")",
has n + 1 for its value. The value is fixed-point or
floating-point, depending on the argument.
sub1 ::= "(""sub1" x ")",
has x - 1 for its value.
Again modern LISP permit "1+" and "1-" as alternatives.
max ::= "(""max" "("x1,x2")"")"
chooses the largest of its arguments for its value.
min ::= "(""min" "(x1,x2,..xN")"")"
chooses the smallest of its arguments for its value.
divide ::= "(""divide" "("x , y ")"")"
computes the quotient and the remainder of x and y.
float ::= "(" "float" x ")"
returns true if x is a floating-point number.
equal ::= "(""equal" x, y ")"
its value is true if the arguments are identical.
logor ::= "(""logor" "("x1,x2,..xN"")"
performs a logical OR on its arguments.
logand ::= "(""logand" "("x1,x2,..xN"")"
performs a logical AND on its arguments.
logxor ::= "(""logxor" "("x1,x2,..xN"")"
performs an exclusive OR.
leftshift ::= "(""leftshift""("x, n")"")"
The first argument is shifted left by the number of bits
specified by the second argument. If the second argument is negative, the
first argument will be shifted right.
SEMANTICS
NIL: nil and the empty list are completely equivalent. Theysatisfy the
equal predicates. NIL is used to implement FALSE in a Boolean expression or
predicate.
LISP has many predicates that test objects to see whether they belong to a
particular data type.
ATOM: is a predicate that tests its argument to see if it is anatom.
NUMBERP: tests to see if its argument is a numeric atom
SYMBOLP: tests its arguments to see in it is a symbol, a nonnumericatom.
LISTP: tests its argument to see if it is a list.
ZEROP: checks to see if its argument is a zero.
PLUSP: checks to see if its argument is positive.
MINUSP: checks to see if its argument is negative.
EVENP: checks to see if its argument is even.
ODDP: checks to see if its argument is odd.
<,>: expect arguments to be numbers. The predicate > tests them tosee that
they are in strictly descending order, while < checksto see that they are
in strictly ascending order.
=: (Modern lists) tests for numerical or general equality.
COND: has a template that calls for particularly peculiar
argumentevaluation. Example:
(COND (test 1 ) (consequent 1-1) )
(test 2 ) (consequent 2-1) )
.
.
(test m ) (consequent m-1) ))
LAMBDA: defines anonymous procedures.
Modern LISP systems provide many other functions:-
DEFUN: an acronym for define function.
CASE: checks the evaluated key form against the unevaluated keysusing EQL.
If the key is found, the corresponding clause istriggered and all of the
clause's consequents are evaluated.
PLUS:
1. LISP facilitates procedure abstraction and data abstraction.
2. LISP is a good language with which to build interpreters and
compilers for a variety of languages.
3. Once understood atoms are not too confusing to work with.
4. Strings con be manipulated easily.
5. The use of objects makes life in programming easier.
MINUS:
1. Too many parentheses have to be used. Makes it confusing to keep
track of them all.
2. The train of thought is different from normal human thinking.
3. The objects are great but, you have to know what variables are asked
for and how many.
4. Lambda notation does not allow you to attach a name to the
procedure it defines.
5. It is not possible to hide a data structure behind a set of functions.
INTERESTING:
1. One of the first LISP programs did calculus problems at the level
of university freshmen.
2. LISP is the language in which most research on representation is
done.
3. LISP-based programs are beginning to make user models by
analyzing what the user does.
4. The use of so many parentheses.
5. All functions.
6. Object oriented programming.