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.