Lisp 1 structures and functions

1 .First Lecture on Introductory Lisp 

2 .John McCarthy • Pioneer in AI – Formalize common-sense reasoning • Also – Proposed timesharing – Mathematical theory – …. • Lisp stems from interest in symbolic computation (math, logic) 

3 . Language speeds ww.bagley.org/~doug/shoutout: Completely Random and Arbitrary Point System 

4 . Why Lisp? • Because it’s the most widely used AI programming language • Because AI researchers and theoreticians like using it • Because it’s good for writing production software (Graham article) • Because it’s got lots of features other languages don’t • Because you can write new programs and extend old programs really, really quickly in Lisp 

5 .• Lisp stands for “LISt Process” – Invented by John McCarthy (1958) – Simple data structure (atoms and lists) – Heavy use of recursion – Interpretive language • Variations – Frantz Lisp (80’s) – Common Lisp (de facto industrial standard) • Common Lisp at gl.umbc.edu and sunserver1.csee.umbc.edu – command line: clisp – main site: http://clisp.sourceforge.net/ – help site: http://www.apl.jhu.edu/~hall/lisp.html – tutorial site: http://grimpeur.tamu.edu/~colin/lp/node10.html 

6 .1. Valid objects (S-expressions) Atoms: numbers: (real 1.0, integer 1) symbols: a consecutive sequence of characters (no space) e.g., a, x, price-of-beef. two special symbols: T and NIL for logical true and false. strings: a sequence of characters bounded by double quotes e.g., "this is red". (Note: LISP is case insensitive) Lists: a list of atoms and/or lists, bounded by "(" and ")“, e.g., (a b c), (a (b c)) top elements of a list example: top elements of list (a b c) are a, b, and c top elements of list (a (b c)) are a and (b c) nil: empty list, same as (). 

7 .2. Function calls • also a list • use prefix notation: (function-name arg1 ... argn) • returns function value for the given list of arguments • functions are either provided by Lisp function library or defined by the user. • Examples: >(+ 1 3 5) 9 >(/ 3 5) 3/5 >(/ 3.0 5) 0.59999999999999998 >(sqrt 4) 2 

8 . • Sqrt • + • * 5 

9 .• exit • quote = ` 

10 .• load 

11 .• Atoms • numeric • fractions • floating point • literal atoms • Boolean values • other symbols • strings 

12 .) • Lists • NIL = () 

13 .• Function calls • evaluation of functions 

14 .• setf more general than setq • binding 

15 .3. Evaluation of S-expression 1) Evaluate an atom. • numerical and string atoms evaluate to themselves; • symbols evaluate to their values if they are assigned values, return Error, otherwise; • the values of T and NIL are themselves. 2) Evaluate a list - evaluate every top element of the list as follows, unless explicitly forbidden: • the first element is always a function name; evaluating it means to call the function body; • each of the rest elements will then be evaluated, and their values returned as the arguments for the function. • Examples >(+ (/ 3 5) 4) >(+ (sqrt 4) 4.0) >(sqrt x) 23/5 6.0 Error: The variable X is unbound. 

16 .3) To assign a value to a symbol (setq, set, setf) >(setq x 3.0) >x 3.0 3.0 • setq is a special form of function (with two arguments); • the first argument is a symbol which will not be evaluated; • the second argument is a S-expression, which will be evaluated; • the value of the second argument is assigned to be the value of the first argument >(setq y x) >y >(+ x y) 3.0 3.0 6.0 ; the value of x is assigned as the value of y • to forbid evaluation of a symbol (quote or ‘) 

17 . >(quote x) >'x >(setq z 'x) x x x >(+ x z) Error: X is not of type NUMBER ... •. to force an evaluation, using function "eval" >(+ x (eval z)) 6.0 Two more assignment functions: eval (set x y) ; assign the value of y to the value of x. x is evaluated ; first and whose value must be a symbol ; "setq" is a combination of "set" and "quote" (setf x y) ; similar to but more general than "setq" in that x can be ; something other than a symbol. setf 

18 .• first • rest • function nesting 

19 .• car • cdr • cadr • caddr • nthcdr • butlast • cons • append 

20 .• length • reverse • last • list 

21 .• Basic expression evaluation 

22 . 2) Predicates (a special function which returns NIL if the predicate is false, T or anything other than NIL, otherwise) =, >, <, >=, <= for numerical values; predicates equal, eq, for others (symbols, lists, etc.) x=3 >(< x y) >(= x y) >(equal ‘x ‘y) >(equal ‘a (car L)) NIL T NIL T y=3 L=(a b) tests if x is a atom >(atom x) >(atom L) >(atom (car L)) T NIL T tests if x is a list >(listp x) >(listp L) NIL T also numberp, symbolp, null >(numberp ‘x) >(numberp x) >(symbolp ‘x) >(symbolp x) NIL T T NIL 

23 .• Basic storage handling 

24 . >(null L) >(null NIL) >(null x) NIL T NIL 3) Set operations ( a list can be viewed as a set whose members are the top elements of the list) >(member 'b L) ; test if symbol b is a member (a top element) of L (B C) ; if yes, returns the sublist of L starting at the ; first occurrence of symbol b >(member ‘b (cons 'b L)) (B A B C) >(member x L) Set NIL ; if no, returns NIL operations >(union L1 L2) ; returns the union of the two lists >(intersection L1 L2) ; returns the intersection of the two lists >(set-difference L1 L2) ; returns the difference of the two lists 

25 .• defun 

26 .• Data structures • assoc 

27 . • make-array • aref • defstruct 0 1 2 3 0 (a b c d) 2 3 4 3 “this” 5 6 7 #\c 8 9 10 1 2 4 Changed to 12 

28 .• Dotted pairs 

29 .• Dotted pairs