Lisp 1 structures and functions

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
展开查看详情

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