Lisp Notes
Lisp Notes
Lisp Notes
LISP = LISt Processing Originated w McCarthy 1959 Implemented Church's lambda-calculus recursive function theory Manipulation of symbolic information The initial Lisp was impractical no iteration Many versions: Franz, Mac, Inter, Common now the standard Guy Steele 1990: VERY useful reference.
12
First, Lisp is much more exible than most languages. Users have such total control over what goes on that if they do not like the syntax of the language, they may change it to suit themselves. Suppose that you do not like the method for de ning programs in, say, Fortran, can you do anything about it? Short of switching to another language the answer is clearly no. Indeed the very idea seems absurd. But not to Lisp users. Spector, 1995, PC. ...The second reason for choosing lisp is the way in which Lisp in oriented toward the manipulation of symbols as opposed to, say, numbers.Norvig, PoAIP, p. 25: What is it that sets Lisp apart from other languages? Why is it a good language for AI applications? There are at least seven important factors from Norvig: Built-in Support for Lists Automatic Storage Management Dynamic Typing First-Class Functions Uniform Syntax Interactive Environment Extensibility
13
Why Lisp?
Characteristics of Lisp
Interactive somewhat super cially, Recursive, Very simple syntax does automatic memory mgmt, variables not explicitly typed, may be interpreted or compiled. Oriented toward: 1 non-numeric symbol manipulation; 2 structure building and modi cation. Programs and data have same form Lisp is the defacto standard language in AI
14
In Lisp, ALL every expression returns a value; Some of those expressions also have side e ects.
| Fewer punctuation chars, only parens and white space. x=2+2 is one single symbol; need to insert spaces: x = 2 + 2 to separate the symbols. | Expressions delimited by parentheses. Semi colons are for comments.
15
Syntax of Lisp
| An atom is an S-expression: a symbol b non-symbol number, string, array; Examples: X, JOHN, SETQ, 7.2, "John" | A list is an S-expression: S-expr S-expr ; Examples: + 1 2, A B C | Note: case insensitive
:::
THAT'S ALL THERE IS TO THE SYNTAX!!! except for dot notation and special characters | we'll get to special chars later.
S-expression atom
symbol, number, string, character, array
list
(a b 3)
dotted pair
(3 . a) (a . (b . (3 . nil)))
Note: A list is a special case of a dotted pair where the last cell = NIL So, actually: an S-expression is either an atom or a dotted pair.
So A is an abbrev for A . NIL. Lists more commonly used than dotted pairs convenient. Note: nil . nil = . = . nil = 6= nil
16
17
Atoms:
atom turkey 1492 3turkeys *abc
Lists:
atom atom turkey atom 1492 ocean blue an-atom a list inside and more atoms a list containing 5 atoms a list containing 8 atoms and a list that contains 4 atoms a list containing a list containing a list of 11 atoms a list that ends with the null list not a list not a list not again
18
| Symbols like variables in most langs, have a value associated with them. Special: T, NIL | Normally write fcn as fa,b, ,n or in x a+b+ +n | In Lisp: put f inside left paren: f a b n
::: :::
By convention, we assume that when given a list to evaluate, the rst atom has a value associated with it which is the body of a function.
name of fn args | + 1 2 ! 3 | First elt of list is special: applied to rest of elts.
Evaluation of list: 1 eval each elt of list rst elt should return fcn body, rest return args; 2 apply fcn from 1st atom to rest. Important Note: use ' to indicate the S-expr stated" rather than the value of that S-expr. e.g., 'X returns X, whereas X returns the value stored in X. We'll run through what a sample session looks like in a minute.
19
Examples: | '2 ! 2 | 2!2 | 'John ! John | John ! ERROR: not a bound variable Quote: use ' to indicate the S-expression stated" rather than the value of that S-expression. Serves to BLOCK evaluation of following expression, returning it literally. Example: 'Pat Kim ! PAT KIM If we just had Pat Kim, it would consider Pat as a function and apply it to the value of the expression Kim.
Quote symbol
20
Sample Session
Fire up Lisp ...
+ 1 1 = 2 * 23 13 = 299 + 1 * 23 13 = 300 + * 2 2 - 10 9 = 5 * 2 2 2 2 = 16 sqrt * 2 2 2 2 = 4 = = 25 5 5 38 4 19 2
; Can abort out of this abort current ; computation and return to read-eval-print loop
21
It has a side
; length --
length append 'pat Kim list 'John Q Public 'Sandy = 4 ; Symbolic computations can be nested and ; mixed with numeric computations. ;;; Note: "list" puts elts into a list; doesn't merge them like "append" does. ;;; Note: Order of evaluation critical. ;;; Note: Parens MUST match -car l = A cdr l = B C D E first rest l = B cons 'q l = Q A B C D E ; MAIN CONSTRUCTOR used in Lisp. Eval args first.
; first l
; rest l
22
24
(CONS A B)
Adds one mem cell
(A . B)
Note: can have (CONS A NIL)-> (A)
same
(A B)
Note: can have (LIST A) -> (A)
(A B)
nil
(CONS X Y) = ((A) B)
25
The quote function inhibits the evaluation of its argument. It returns its argument literally. If the variable barney has the value 22, then:
Evaluating barney yields 22 Evaluating quote barney yields barney Evaluating car quote betty bambam yields betty
The single quote mark ' it is actually an apostrophe can be used as an abbreviation for quote ....
The rst element of a list be it an atom or another list is the car of the list.
car 'alphabet soup = alphabet car 'pickles beer alphabet soup = pickles beer car 'miro braque picasso leger = miro braque picasso
Everything except the rst element of a list is the cdr of the list.
cdr 'alphabet soup = soup cdr 'pickles beer alphabet soup = alphabet soup cdr 'miro braque picasso leger = leger
Given a complex S-expression, you can obtain any of its component S-expressions through some combination of car and cdr. cadr is the car of the cdr:
cadr 'old mcdonald had a farm = MCDONALD
cons 'woof 'bow wow = woof bow wow cons 'howl 'at the moon = howl at the moon
You get errors if you try to take the car or cdr of a non-nil atom
car 'foo = Error: Can't take CAR of FOO. cdr 'foo = Error: Can't take CDR of FOO.
You get funny dots" if you try to cons things onto non-lists
cons 'a 'b = A . B
Although dotted pairs" have their uses, we mostly won't use them beyond the rst problem set. That means that you're probably doing something wrong if you get dots in your answers.
setq is an exception to the normal evaluation rule; the rst argument is not evaluated. q = quote But setq cannot be used for generalized vars ! rplaced with setf. A generalized var refers to any place a ptr may be stored.
A 3 A 3 nil
"A has the value 3" "A has the value (3)"
Other places a ptr can be stored? car cdr of cons cell Asst ! replacing one ptr with another
(setf A (4)) (setf (car A) 4)
A 3 nil
A 3 nil 4
Can use an accessor such as CAR, CDR, FIRST, etc. "A has the value (4)"
nil
Symbol: indivisible atoms" actually have parts. Typically each atom is a table:
X
Name Value Function Prop List Package "X" (string -- not same as symbol) (if nothing here, atom is unbound) (function definition)
What does setf do? setf x 7 Changes value slot of X's table to point to 7 Can access slots: symbol-name 'reverse ! "reverse" symbol-function 'reverse ! compiled-fn reverse
8
Eval
EVAL = explicit evaluation. | + 3 5 ! evaluated w o user explicitly asking for eval'n | EVAL is applied by the system LISP = read-eval-print loop | Explicit eval = extra evaluation | Sort of the opposite of quote. Examples: Suppose setf x 'y, setf y 'z |x!y | eval x ! z | eval 'x ! y What is eval useful for? retrieving value of symbol whose name is not known until runtime: setf a 3 eval 'a ! 3 NOT REALLY A GOOD IDEA: Can use symbol-value; no reason to use eval. evaluating form that is constructed at runtime: eval list fn args ... eval list 'setf arg1 arg2 where arg1='x and arg2=3 evaluates setf x 3 Note: basically building a trivial function and running it on the y; in the old" days, this was considered the key" to Lisp's exibility NOT REALLY A GOOD IDEA: Use symbol-value again: setf symbol-value 'arg1 symbol-value 'arg2 But might be cases where don't have enough info; if the list 'setf x 3 is passed into a fn to be evaluated, then probably best thing to do is eval: 1 can't use funcall apply cause setf is macro; 2 don't know enough about the args w o extensive testing to be able to use or in this case not use symbol-value. But in general, we no longer need eval, really. Some people e.g., Norvig say you're doing something wrong if you use it. But you should know it is there, and that sometimes there's no choice. 9
Comments
10
Macro: setf x 1 Can test with macro-function x Special form: if test a b Can test with special-form x
Two others we'll learn about later: let, let* We'll initially concentrate on this rst type of form the function. We'll talk about macros in detail later.
11
Predicates
A Predicate is a function that is called to answer a yes-or-no question. A predicate returns boolean truth values T = true NIL = false T NIL special symbols; prede ned to have self as value. The atom t means true, and evaluates to itself. The atom NIL means false, and evaluates to itself. Predicates may return t for true, or they may return any other non-nil value. Predicates in Common Lisp take various forms, but often end with p.
12
Predicates continued
1. , numeric functions
3. atom x, null x, not x, listp x, consp x, numberp x, stringp x, arrayp x, vectorp x, characterp x, member x y :test test
Note: All conses are lists, but converse not true: consp nil ! nil Note: Member doesn't just return t or nil! 13
14
15
equalp is the most general see CLtL2 p. 103. And, or, and not allow the combination of predicates into complex predicates. EQ and EQUAL two most commonly used. EQ tests whether args eval to exact same Lisp obj EQUAL compares any two s-expressions lists, strings, etc. = used for numbers must be same number EQL: EQ or = EQUALP | same as EQUAL but disregards case for strings. Others: tree-equal, char-equal, string-equal, string=, char=
Note: these are all a special case of equal; Tree-equal tests whether two trees are equal except that the leaf nodes are expected to be symbol atoms not, eg., strings Note: can specify :TEST such as string=.
equalp T T T T T T nil
16
In reality, both pointers to A point to the SAME symbol i.e., the same exact mem location EQ: tests for memory location exactly | therefore, atoms only! LISP automatically makes sure that all refs to some symbol actually point to the UNIQUE point in mem that the symbol happens to be stored physically. This way, any info stored w it e.g., its value is accessible from every ref. Anytime LISP sees new symbol, it adds the symbol to its storehouse of known atoms.
17
18
Conditionals
IF: special form if = x 21 print 'blackjack WHEN: macro; has same form: when = x 21 print 'blackjack Di erence: IF has else part; should use if only when there is an else part ! if z 'not-empty 'empty z is a boolean | IF: most useful for 2-way fork where then else are each 1 expr | WHEN: used for 1-way fork then may be more than 1 expr What if more than 2-way fork? Use COND!
(cond (C1 ( E11 E21...)) (if C E1 E2) C
N Y
E11 E12...
E2
(when C E1 E2) C
Y
C1 E1 E2... Cn
E11 E12...
En1 En2...
COND: Powerful multiway branching construct; Arbitrary number of args called clauses Note: general form ! can have more than one action. Each clause is a list of s-exprs Example: Ci Ei1 Ei2 ... Eim. Value returned : Eim, where Ci is rst non-nil condition No more Ci or Ei's are evaluated. Convention for our class: last Ci is the constant T guaranteed to be non-nil. 19
Conditionals: Examples
cond x 'b y 'c t 'd
What if x = 'a? then returns b What if x = nil, y = t? then returns c What if x = nil y = nil? then returns d cond x setf x 1 + x 2 y setf y 2 + y 2 t setf x 0 setf y 0 What if x = t? then returns 3 What is x? x = 1 What if x = nil, y = t? then returns 4 What are x y? nil 2 What if x = nil y = nil? then returns 0 What are x y? 0 0
cond x setf x 1 + x 2 setf y 2 If x is nil, then it'll execute the last statement and return it. case expression match1 result11 result12 ... match2 result21 result22 ... ... matchn resultn1 resultn2 ...
Can also use OR and AND as conditional control constructs as we talked about earlier: and nil t t t, or t nil nil nil
20
The IF special form is a special case of COND: IF testform thenform elseform Evaluates testform. If the result is true, evaluates thenform and returns the result; if the result is nil, evaluates elseform and returns the result.
if 100 23 'sure-is 'sure-aint = SURE-IS if member 'bog 'blig blog bog bumper * 99 99 sqrt -1 = 9801 if member 'fog 'blig blog bog bumper * 99 99 sqrt -1 = c0 1
IF vs. COND
Note that the thenform and the elseform are both restricted to being single forms. In contrast, you can specify any number of forms in a cond clause:
setq temperature 8 = 8 cond temperature 32 print 'yowch -- it is cold! print 'i will play god and change that! setq temperature 78 t print 'well i guess it is not so bad print 'where do you think we are? hawaii? YOWCH -- IT IS COLD! I WILL PLAY GOD AND CHANGE THAT! = 78
21
If you want multiple forms in an IF you can use a PROGN: Evaluates each form in order, left to right. The values of all forms but the last are discarded; the value of the last form is returned.
if temperature 32 progn print 'yowch -- it is cold! print 'i will play god and change that! setq temperature 78 progn print 'well i guess it is not so bad print 'where do you think we are? hawaii? WELL I GUESS IT IS NOT SO BAD WHERE DO YOU THINK WE ARE? HAWAII? = WHERE DO YOU THINK WE ARE? HAWAII?
PROGN
22
23
De ning Functions
De ne Function = Defun" defun function-name parameter ... function-body Function name = symbol; parameters usually symbols. defun rst-name name rst name rst-name 'john q public ! JOHN
24
Here's a function that takes one argument and returns the argument plus 20:
defun add-20 n "returns n + 20" + n 20 = ADD-20 add-20 15 = 35
Note the use of a documentation string in the function above. The string is not obligatory and does not a ect the execution of the function, but it provides information about the function which can be accessed through the builtin functions documentation" and describe".
documentation 'add-20 'function = returns n + 20 describe 'add-20 = ADD-20 is a symbol. Its home package is USER. Its global function definition is Interpreted-Function ADD-20 FB0C26 ... Its source code is NAMED-LAMBDA ADD-20 N BLOCK ADD-20 + N 20 ... It has this function documentation: "returns n + 20" ...
The semicolon comment follows a convention: 1 Preface description of function with three semicolons; 2 Preface lines inside of a function with two semicolons; 3 Preface minor comments at end of line with two semicolons.
;;; The function TEST runs a demonstration. defun test "Runs a test of SOLVE-PROBLEM." setf x 'test-data ; Assign X some test data. ;; Call the main function. solve-problem x
25
Note: random" is a pseudo random number generator that takes a number and returns a value between zero inclusive and the number exclusive. Here's a function using COND that returns an atom indicating whether its argument is even or odd or not a number.
defun even-or-odd? n "returns 'even if n is even, 'odd if n is odd, and 'neither if n is not an in cond not integerp n 'neither evenp n 'even oddp n 'odd = EVEN-OR-ODD? even-or-odd? 24 = EVEN even-or-odd? 25 = ODD even-or-odd? 'swahili = NEITHER
26
Here's a function that takes two arguments and returns their sum:
defun my-sum n1 n2 "silly substitute for +" + n1 n2 = MY-SUM my-sum 99 100 = 199
27
defun double-cons one-thing another-thing "Returns the result of consing one-thing onto another-thing twic cons one-thing cons one-thing another-thing = DOUBLE-CONS double-cons 'hip 'hooray = HIP HIP HOORAY double-cons 1 nil = 1 1 double-cons 1 double-cons 1 nil = 1 1 1 1 defun quadruple-cons one-thing another-thing "Returns the result of consing one-thing onto another-thing 4x" double-cons one-thing double-cons one-thing another-thing = QUADRUPLE-CONS quadruple-cons 'um 'huh? = UM UM UM UM HUH?
28
defun run shoes print append 'i think i will take a trot in my list shoes setq shoes append 'old beat-up list shoes print append 'i think i will take a trot in my shoes = RUN run shoes I THINK I WILL TAKE A TROT IN MY NIKES I THINK I WILL TAKE A TROT IN MY OLD BEAT-UP NIKES = I THINK I WILL TAKE A TROT IN MY OLD BEAT-UP NIKES print 'foo = FOO defun run shoes ;; this version returns 'I RAN print append 'i think i will take a trot in my list shoes setq shoes append 'old beat-up list shoes print append 'i think i will take a trot in my shoes 'i ran = RUN run shoes I THINK I WILL TAKE A TROT IN MY NIKES I THINK I WILL TAKE A TROT IN MY OLD BEAT-UP NIKES = I RAN shoes = NIKES
29
30
defun random-elt choices "returns one element of the list of choices at random" nth random length choices choices = RANDOM-ELT random-elt animals = BUG random-elt animals = BIG-BUG
31
Taken from Chapter 2 of Norvig, PoAIP A Grammar for a miniscule Subset of English:
Sentence = Noun-Phrase + Verb-Phrase Noun-Phrase = Article + Noun Verb-Phrase = Verb + Noun-Phrase Article = the, a, ... Noun = man, ball, woman, table ... Verb = hit, took, saw, liked ... ;; The grammar can be used to generate sentences: To get a Sentence, append a Noun-Phrase and a Verb-Phrase To get a Noun-Phrase, append an Article and a Noun Choose "the" for the Article Choose "man" for the Noun The resulting Noun-Phrase is "the man" To get a Verb-Phrase, append a Verb and a Noun-Phrase Choose "hit" for the Verb etc. ;; The grammar can be used as the basis of the following ;; Lisp functions: defun sentence "generates and returns a sentence as a list of atoms" append noun-phrase verb-phrase = SENTENCE defun noun-phrase "generates and returns a noun-phrase as a list of atoms" append article noun = NOUN-PHRASE
Programming Example
32
33
34
35
Recursion
De ne length in terms of itself: the empty list has length 0 and any other list has a length which is one more than the length of the rest of the list.
defun length list cond null list 0 BASE t 1+ length cdr list RECURSION: leap of faith
Evaluation of recursive call: | Evaluate the argument cdr list | Bind it to list after old value is saved on stack. | Upon return, add 1 to result. Spiral of recursion: unwind when list = NIL
(length (a b c)) (length (b c))
(length (c))
(length ()) 0 1 2 3
36
Tail Recursion
Note: compiler has to allocate memory for each recursive call. But not true for all recursive calls! In rst def of length: add 1 after returning from recursive call. More e cient to write a tail-recursive" function: recursive call appears as the last thing the function does the tail
defun length list length-aux list 0
37
Here's a recursive function called lat?, that takes one argument and returns t if that argument is a list of atoms.
defun lat? l "Returns t if the argument is a list of atoms, nil otherwise" cond null l t atom car l lat? cdr l t nil = LAT? lat? 'remember the alamo = T lat? 'did you remember to floss? = NIL lat? long-list = T lat? 12 = Error: Can't take CAR of 12. While executing: LAT? Type Command-. to abort. See the Restarts menu item for further choices. 1 defun lat? l "Returns t if the argument is a list of atoms, nil otherwise" cond not listp l nil null l t atom car l lat? cdr l t nil = LAT? lat? 12 = NIL
38
The following member? function checks to see if its rst argument occurs in its second:
defun member? a lat "Returns t if a occurs in lat, nil otherwise" cond null lat nil t or equalp car lat a member? a cdr lat = MEMBER? setq five-colleges 'amherst umass hampshire smith mount-holyoke = AMHERST UMASS HAMPSHIRE SMITH MOUNT-HOLYOKE member? 'hampshire five-colleges = T member? 'oberlin five-colleges = NIL
39
Recall that Common Lisp includes a function called MEMBER that does a similar thing. Note, however, that it returns the matching cdr rather than t:
member 'hampshire five-colleges = HAMPSHIRE SMITH MOUNT-HOLYOKE member 'oberlin five-colleges = NIL
MEMBER
Note that MEMBER compares using EQ, not EQUALP. For example:
member 'nest 'a hornet in a hornet nest is to be avoided = NIL member? 'nest 'a hornet in a hornet nest is to be avoided = T
We can get MEMBER to match using equalp by providing a keyword argument details on this another day...
member 'nest 'a hornet in a hornet nest is to be avoided :test 'equalp = NEST IS TO BE AVOIDED
40
Wilensky Common Lispcraft p. 89: ...we have the following components to recursive programming: Breaking down the task at hand into a form that involves simpler versions of the same task. Specifying a way to combine the simpler versions of the task to solve the original problem. Identifying the "grounding" situations in which the task can be accomplished directly. Specifying checks for these grounding cases that will be examined before recursive steps are taken.
defun factorial n "returns the factorial of n" cond = n 1 1 t * n factorial - n 1 = FACTORIAL factorial 5 = 120 trace factorial = NIL factorial 5 Calling FACTORIAL 5 Calling FACTORIAL 4 Calling FACTORIAL 3 Calling FACTORIAL 2 Calling FACTORIAL 1 FACTORIAL returned 1 FACTORIAL returned 2 FACTORIAL returned 6 FACTORIAL returned 24 FACTORIAL returned 120 = 120
41
defun factorial n "returns the factorial of n" cond zerop n 1 t * n factorial - n 1 = FACTORIAL factorial 5 = 120
42
Sometimes iteration seems more natural. Common Lisp provides many iteration constructs.
DOTIMES var countform Macro resultform declaration * tag | statement * Executes forms countform times. On successive executions, var is bound to the integers between zero and countform. Upon completion, resultform is evaluated, and the value is returned. If resultform is omitted, the result is nil. dotimes n 20 'spumoni print n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 = SPUMONI
Iteration: DOTIMES
43
defun multi-cons one-thing another-thing n "Returns the result of consing one-thing onto another-thing n times" cond equalp n 0 another-thing t cons one-thing multi-cons one-thing another-thing - n 1 = MULTI-CONS multi-cons 'hip 'hooray 5 = HIP HIP HIP HIP HIP HOORAY
44
Iteration: DOLIST
DOLIST var listform Macro resultform declaration * tag | statement * Evaluates listform, which produces a list, and executes the body once for every element in the list. On each iteration, var is bound to successive elements of the list. Upon completion, resultform is evaluated, and the value is returned. If resultform is omitted, the result is nil. defun greet people "prints greetings for all of the people listed." dolist person people print append 'so nice to see you list person = GREET setq guests 'sally booboo mr-pajamas ms-potato-head = SALLY BOOBOO MR-PAJAMAS MS-POTATO-HEAD greet guests SO NICE TO SEE YOU SALLY SO NICE TO SEE YOU BOOBOO SO NICE TO SEE YOU MR-PAJAMAS SO NICE TO SEE YOU MS-POTATO-HEAD = NIL
45
'
Funny ' notation sharp-quote: maps name of function to function itself. Equivalent to FUNCTION. Always use this when using mapcar, apply, funcall, lambda expressions keywords e.g., :TEST. Note: only functions may be quoted not macros or special forms. More e cient; means something to compiler: go to compiled code, not through symbol to nd function defn. Analogous to quote. Use any time a function is specied. Mapcar: Expects an n-ary fn as 2st arg, followed by n lists. It applies the fn to the arg list obtained by collecting the rst elt of each list. | mapcar '1+ '5 10 7 ! 6 11 8 | mapcar function 1+ '5 10 7 ! 6 11 8 | mapcar 'cons 'a b c '1 2 3 ! A . 1 B . 2 C . 3 | mapcar 'print 'a b c ! A B C Note: last case also has side e ect of printing A, B, and C. Avoid consing up a whole new list by using Mapc: | mapc 'print 'a b c ! A B C This prints A, B, and C, but then returns the second arg, NOT a new list.
1
Apply: same idea, but don't need to know no. of args Eval: in general we can use funcall and apply.
*** Programmers who are used to other langs sometimes fail to see the point of lambda expressions. Why are they useful? 1 It's a pain to think up names and to clutter up a program with lots of functions that are only used very locally; 2 MORE IMPORTANT: can create new functions at run time. Note: cannot give a lambda expr to lisp to eval; lambda" not a function! But can use it as car of a list: lambda x + x x 2 ! 4. I don't use this though. Note: Defun is a macro that expands out to lambda; so there's really only one way to specify a fn, not two! symbol-function fn returns lambda expression.
3
The IF special form is a special case of COND: IF testform thenform elseform Evaluates testform. If the result is true, evaluates thenform and returns the result; if the result is nil, evaluates elseform and returns the result.
if 100 23 'sure-is 'sure-aint = SURE-IS if member 'bog 'blig blog bog bumper * 99 99 sqrt -1 = 9801 if member 'fog 'blig blog bog bumper * 99 99 sqrt -1 = c0 1
Note that the thenform and the elseform are both restricted to being single forms. In contrast, you can specify any number of forms in a cond clause:
setq temperature 8 = 8 cond temperature 32 print 'yowch -- it is cold! print 'i will play god and change that! setq temperature 78 t print 'well i guess it is not so bad print 'where do you think we are? hawaii? YOWCH -- IT IS COLD! I WILL PLAY GOD AND CHANGE THAT! = 78
If you want multiple forms in an IF you can use a PROGN: Evaluates each form in order, left to right. The values of all forms but the last are discarded; the value of the last form is returned.
if temperature 32 progn print 'yowch -- it is cold! print 'i will play god and change that! setq temperature 78 progn print 'well i guess it is not so bad print 'where do you think we are? hawaii? WELL I GUESS IT IS NOT SO BAD WHERE DO YOU THINK WE ARE? HAWAII? = WHERE DO YOU THINK WE ARE? HAWAII?
PROGN
defun random-elt choices "returns one element of the list of choices at random" nth random length choices choices = RANDOM-ELT random-elt animals = BUG random-elt animals = BIG-BUG
previous lecture Here's a recursive function called lat?, that takes one argument and returns t if that argument is a list of atoms.
defun lat? l "Returns t if the argument is a list of atoms, nil otherwise" cond null l t atom car l lat? cdr l t nil = LAT? lat? 'remember the alamo = T lat? 'did you remember to floss? = NIL lat? long-list = T lat? 12 = Error: Can't take CAR of 12. While executing: LAT? Type Command-. to abort. See the Restarts menu item for further choices. 1 defun lat? l "Returns t if the argument is a list of atoms, nil otherwise" cond not listp l nil null l t atom car l lat? cdr l t nil = LAT? lat? 12 = NIL
The following member? function checks to see if its rst argument occurs in its second:
defun member? a lat "Returns t if a occurs in lat, nil otherwise" cond null lat nil t or equalp car lat a member? a cdr lat = MEMBER? setq five-colleges 'amherst umass hampshire smith mount-holyoke = AMHERST UMASS HAMPSHIRE SMITH MOUNT-HOLYOKE member? 'hampshire five-colleges = T member? 'oberlin five-colleges = NIL
MEMBER
Recall that Common Lisp includes a function called MEMBER that does a similar thing. Note, however, that it returns the matching cdr rather than t:
member 'hampshire five-colleges = HAMPSHIRE SMITH MOUNT-HOLYOKE member 'oberlin five-colleges = NIL
Note that MEMBER compares using EQ, not EQUALP. For example:
member 'nest 'a hornet in a hornet nest is to be avoided = NIL member? 'nest 'a hornet in a hornet nest is to be avoided = T
previous lecture Wilensky Common Lispcraft p. 89: ...we have the following components to recursive programming: Breaking down the task at hand into a form that involves simpler versions of the same task. Specifying a way to combine the simpler versions of the task to solve the original problem. Identifying the "grounding" situations in which the task can be accomplished directly. Specifying checks for these grounding cases that will be examined before recursive steps are taken.
defun factorial n "returns the factorial of n" cond = n 1 1 t * n factorial - n 1 = FACTORIAL factorial 5 = 120 trace factorial = NIL factorial 5 Calling FACTORIAL 5 Calling FACTORIAL 4 Calling FACTORIAL 3 Calling FACTORIAL 2 Calling FACTORIAL 1 FACTORIAL returned 1 FACTORIAL returned 2 FACTORIAL returned 6 FACTORIAL returned 24 FACTORIAL returned 120 = 120
10
defun factorial n "returns the factorial of n" cond zerop n 1 t * n factorial - n 1 = FACTORIAL factorial 5 = 120
11
Sometimes iteration seems more natural. Common Lisp provides many iteration constructs. We talked about DOLIST last time. Another is DOTIMES.
DOTIMES var countform Macro resultform declaration * tag | statement * Executes forms countform times. On successive executions, var is bound to the integers between zero and countform. Upon completion, resultform is evaluated, and the value is returned. If resultform is omitted, the result is nil. dotimes n 20 'spumoni print n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 = SPUMONI
12
defun multi-cons one-thing another-thing n "Returns the result of consing one-thing onto another-thing n times" cond equalp n 0 another-thing t cons one-thing multi-cons one-thing another-thing - n 1 = MULTI-CONS multi-cons 'hip 'hooray 5 = HIP HIP HIP HIP HIP HOORAY
13
14
Global Variables
DEFVAR proclaims variable-name to be a special variable, optionally sets it to the value of initial-value, and returns variable-name. If initial-value is given, variable-name is initialized to the result of evaluating it unless variable-name already has a value. If initial-name is not used, it is not evaluated. The macro defvar only has an e ect the rst time it is called on a symbol. Documentation may be provided as a string.
DEFPARAMETER variable-name initial-value &optional documentation Macro
DEFPARAMETER proclaims variable-name to be a special variable, sets it to the value of evaluating initial-value, a form, and returns variable-name. Documentation may be provided as a string. Globals are conventionally written with surrounding * characters:
defvar *world-state* 'clear block-a on block-a table defparameter *depth-limit* 10 "The maximum depth to which we will search"
Note: Subsequent defvars for a previously defvar'd variable are ignored. Subsequent defparameters act as setq's.
15
Local Variables
LET creates a binding for each variable in parallel and evaluates forms in the resulting environment. Returns the value of the last form.
setq laadeedaa 'hihohiho = HIHOHIHO let laadeedaa 'feefifofum list laadeedaa laadeedaa laadeedaa = FEEFIFOFUM FEEFIFOFUM FEEFIFOFUM laadeedaa = HIHOHIHO
Note that the initializations in a LET are performed in parallel". You may not rely on the earlier ones being performed before the later ones. If you want sequential initialization behavior, use LET*:
let* foo 2 bar + foo 3 + foo bar = 7
17
Current activation record containing lexical vars pushed on stack; x bound to particular value, but symbol-value looks at global value, not value at top of the stack. IMPORTANT: Try not to overload programs w globals; use locals where possible.
18
Let*: is the same as Let except scope begins immediately. More formally: let* = let let ...
setf x 1 = 1 let x 5 y 1+ x print + x y = 7 ;; side effect 7 ;; value print x = 1 1 setf x 1 = 1 let* x 5 y 1+ x print + x y = 11 11 print x = 1 1
19
Lexical Closures
What does it mean to create a new function? Every time ' is evaluated, a fn is returned. But in previous examples, it is always the same fn that is returned e.g., the case given above for doubling arguments. Lexical closures are fns in which free variables have values from environment in which closure is PERFORMED, not APPLIED. | Evaluating a ' form PERFORMS a closure. | Using the result of this evaluation APPLIES the closure. A lexical closure is a box we can pick up and carry around with us; has its own local environment. A lexical closure is a function and its environment. Any function or lambda form de ned in a non-null lexical environment|that is, not at the top level|is actually a closure. What does free variable" mean? Example: variable n in lambda x ... n ... Normally: by lexical scoping rules, refers to value of global symbol taken at time the lambda expression is APPLIED: the value of n will be whatever the value of n is when this lambda expr is applied. Contrast: lexical closure; refers to value of that symbol taken at time the function is created i.e., when the closure is PERFORMED. The value PERSISTS between fn calls.
20
The existence of variables that are local to a fn but which persist between calls is useful for creating generators. A generator is a function that produces a sequence of related values.
defun make-even seed 'lambda nil setf seed + seed 2 = MAKE-EVEN
Lexical Closures
What is the free var above? SEED. It initially gets its value when the closure is performed:
setf even make-even 0 = Interpreted Closure xd275a6 funcall even = 2 funcall even = 4 ;; remembers!
21
Closures can be used in some powerful ways. The following gives us many of the advantages of global variables without the disadvantages.
let counter 0 defun new-id incf counter defun reset-id setq counter 0 = RESET-ID new-id = 1 new-id = 2 new-id = 3 reset-id = 0 new-id = 1 new-id = 2
We can also return closures from functions and then call them with FUNCALL or MAPCAR:
defun make-adder n 'lambda x + x n = MAKE-ADDER funcall make-adder 2 5 = 7 funcall make-adder 12 500 = 512 mapcar make-adder 3 '1 3 10 = 4 6 13
22
Note that adder n: PERFORMS the closure. What does adder 3 return?
adder 3 = Interpreted Closure xd275a6
This is a closure that REMEMBERS the value 3!!! n is set to 3 internally. Suppose Y is set to this result. We can now APPLY the closure:
funcall y 2 = 12 apply y '2 = 12 mapcar y '1 3 10 = 11 13 20
It is also possible to make closures that can be asked to change their state
defun make-adderb n ;; allows optional argument discussed next lecture 'lambda x &optional change if change setq n x + x n = MAKE-ADDERB setq addx make-adderb 1 = INTERPRETED-LEXICAL-CLOSURE x97AFE6 funcall addx 3 = 4 funcall addx 100 t = 100 funcall addx 3 = 103
23
24
;; alphanumeric ordering
Equality:
char=, char =, char , char =, char = not equal, char-equal upper lower allowed, char= distinguishes between them
25
Arrays: collection of int, char, sym, any s-exp Not strongly typed; can be mixed Dimensions:
0 1 2 0 1 2 3 --- start w ............ rows . . columns 0
26
AREF:
aref a 1 = X aref b 1 2 = 3
SETF:
setf aref a 1 2 = 2 ;; Returns 2; Array a becomes: 'x 2 x x x ;; For efficiency, can specify type: setf a make-array '1 :element-type 'integer = Simple-Vector T 1 FB0B9E setf a make-array '1 :element-type 'character
Some compilers can store the array more e ciently and create e cient code for accessing if it is typed.
27
Combines arrays and chars a string is a 1-d array vector of chars X = | a | b | c | ! "abc" shorthand char x 0 = a most appropriate aref x 0 = a elt x 0 = a least e cient: works on lists too How do we create a string?
make-string 7 :initial-element z = "zzzzzzz" string z = "z" string 'z = "z" string "z" = "z" format nil "~s" 'z ;; stream is nil just return value = "z"
Strings:
28
A sequence is: A 1-d array vector: a b c d A list: a b c d A string special case vector: a b c d = "abcd" Can perform certain types of ops on all sequences:
remove 'a 'a b c a :test 'eq = B C remove a "abc" :test 'char= = "bc" reverse 'a b c = C B A reverse "abc" = "cba" elt 'a b c a 1 = B
Sequences
Nth works on lists only not strings, vectors. Elt used for all sequences. If type is known, use: nth for lists aref for vectors arrays char for strings
29
Sequences continued
concatenate 'string "a" "b" = "ab" concatenate 'list 'a 'b = A B ;; Inefficient: Use append concatenate 'array a b c d e f = a b c d e f length "abc" = 3 length 'a b c = 3 length a b c = 3 subseq "abc" 2 3 = "c" subseq 'a b c 2 3 = C subseq a b c 2 3 = c
30
Suppose x = "abcd"
FIND: find
test
subseq x 1 = "bcd" ;; Often used with subseq subseq x position b x :test 'char= = "bcd"
REMOVE-IF: remove-if
FIND-IF: find-if
POSITION-IF: position-if
31
File is closed when "with" is exited. Note: read used w o arg means d t stream is *standardinput* the screen usually. So if you say read, it'll sit there until user types in. read-line stream is a variant of read: reads a whole line and returns a string. Can then use read-from-string.
setf n 0 setf x read-line stream "this is a line" = "this is a line" read-from-string x :start 5 = THIS = 5
Note: read-from-string returns two values atom and pointer of next char; we'll learn how to catch these values shortly. Note: This is NOT really correct! Need to specify two optional parameters ...
32
Note: If you have two modules, A, and B, where B depends on A, need to be careful about order of compilation and loading:
A macro defns
compile and load this first
B uses macros
then compile and load this
Taken from Chapter 2 of Norvig, PoAIP A Grammar for a miniscule Subset of English:
Sentence = Noun-Phrase + Verb-Phrase Noun-Phrase = Article + Noun Verb-Phrase = Verb + Noun-Phrase Article = the, a, ... Noun = man, ball, woman, table ... Verb = hit, took, saw, liked ...
;; The grammar can be used to generate sentences: To get a Sentence, append a Noun-Phrase and a Verb-Phrase To get a Noun-Phrase, append an Article and a Noun Choose "the" for the Article Choose "man" for the Noun The resulting Noun-Phrase is "the man" To get a Verb-Phrase, append a Verb and a Noun-Phrase Choose "hit" for the Verb etc. ;; The grammar can be used as the basis of the following ;; Lisp functions: defun sentence "generates and returns a sentence as a list of atoms" append noun-phrase verb-phrase = SENTENCE defun noun-phrase "generates and returns a noun-phrase as a list of atoms" append article noun = NOUN-PHRASE
34
35
36
37
Multiple Values
So far we've spoken of the value returned by a function." Historically: Lisp designed so that every fn returns a val. But sometimes we want more than one piece of info e.g., read-from-string. Rather than creating a list for multiple types of info, can return more than one value. Consider read-from-string. Suppose we want to catch" the two values:
x - "this is a string" read-from-string x nil nil :start 0 THIS 5
Note that this looks like a LET. Can use it to start out a function; close it o at the end. Now we can pluck out the tokens in the string:
x - "this is a string" n - 0 loop multiple-value-bind atom ptr read-from-string x nil nil :start n print atom setf n ptr when null atom return nil
Better to use FORMAT: format stream format-string E1 ... En The FORMAT function produces formatted output to character streams. It is very exible and has many options. The rst argument to FORMAT should be a stream. Use t for output to the listener. The second argument to FORMAT should be a string, which may or may not contain directives". Format is generally used either for side e ect or for value, but not both. If used for side e ect, the value is NIL.
If stream = t, then usually *standard-output* the screen . Can also specify another type of stream, like a le name. Directive: The tilde" character ~ is used to signal a directive.
~s
prints s-expr as is prints s-expr w o quotes slashes is a directive that starts a new line unconditionally
~a
~
is an iteration construct:
format t "~ ~a ~ " 'mary bill = MARY BILL ;; space at end.
~ ~a~^ ~
format t "~ ~a~^ ~ ." 'mary bill = MARY BILL ;; no space at end.
File is saved out when with" is exited. Value: specify nil for stream name returns a string; no side e ect:
format nil "~Here are 3 s-expressions: ~s, ~s, and ~s." 'a 'b c "de" = "Here are 3 s-expressions: A, B C, and "de"."
One of the simplest and most useful directives is ~, which means to output a newline character.
format t "~Bop bop~ shoo~ Bop bop shoo bob bop bop bam = NIL bob~ bop bop bam"
Even ~ has more options for example, a number between the ~ and the will cause that many newlines to be printed:
format t "jump down ~5 turn around." jump down
The second handiest format directive is ~a. This means go get the next lisp object from the argument list and print it here."
format t "~this is ~a, so ~a ~a ~a!" 'swell 'stomp 'and 'yell this is SWELL, so STOMP AND YELL! = NIL format t "~this is ~a, so ~a ~a ~a!" 'a list 4 "ever" 'tell this is A LIST, so 4 ever TELL! = NIL
There must be enough arguments in the call to format; extras will be ignored:
format t "~this is ~a, so ~a ~a ~a!" 'a list 4 "ever" Error: Missing argument format t "~this is ~a, so ~a ~a ~a!" 'a list 4 "ever" 'tell 'somebody this is A LIST, so 4 ever TELL! = NIL
See CLTL2 for many more variations. The power of FORMAT goes well beyond numeric formatting. Consider this example from Wilensky:
setq n 1 = 1 format t "~D boy~:P left" n 1 boy left = NIL setq n 2 = 2 format t "~D boy~:P left" n 2 boys left = NIL
The ~ and ~ directives can be used to perform iteration within a format string:
setq folks 'candy sandy wendy henry ben = CANDY SANDY WENDY HENRY BEN format t "It was a mess. ~ ~~A fell down,~ OUCH!" folks It was a mess. CANDY fell down, SANDY fell down, WENDY fell down, HENRY fell down, BEN fell down,OUCH! = NIL
There are format directives for case-conversion, tables, indirection, etc... See CLTL2 for details. Providing NIL as the rst argument to FORMAT causes the string to be RETURNED rather than printed.
progn setq my-string format nil "wowie zowie!" 'hmmm = HMMM my-string = "wowie zowie!"
Ordinary function de nitions specify some number of REQUIRED parameters; calls to these functions must pass exactly the correct number of arguments:
defun gimme-two the-first the-second list 'here-they-are the-first the-second = GIMME-TWO gimme-two 1 2 = HERE-THEY-ARE 1 2 gimme-two 1 Error: Too few arguments. gimme-two 1 2 3 Error: Too many arguments.
Function Parameters:
&optional
The rst enhancement that we'll look at is optional parameters. A function is speci ed to take optional parameters by putting &optional, followed by parameter names, in the parameter list.
defun shout stuff &optional more-stuff list 'hey 'you! '--- stuff more-stuff '! = SHOUT shout 'look 'out = HEY YOU! --- LOOK OUT ! shout 'look = HEY YOU! --- LOOK NIL ! defun shout stuff &optional more-stuff if more-stuff list 'hey 'you! '--- stuff more-stuff '! list 'hey 'you! '--- stuff '! = SHOUT shout 'look 'out = HEY YOU! --- LOOK OUT ! shout 'look = HEY YOU! --- LOOK !
10
continued If you don't want your optional parameter to default to nil, you can provide another default value:
&optional
defun shout stuff &optional more-stuff 'around list 'hey 'you! '--- stuff more-stuff '! = SHOUT shout 'look 'out = HEY YOU! --- LOOK OUT ! shout 'look = HEY YOU! --- LOOK AROUND !
Function Parameters:
11
continued You can also specify SUPPLIED-P variables with your optional parameters:
&optional
defun eat what &optional when 'supper when-supplied if and eq when 'supper when-supplied print 'supper is the default -- you could have left it out list 'you 'ate what 'at when = EAT eat 'gefilte-fish 'lunch = YOU ATE GEFILTE-FISH AT LUNCH eat 'gefilte-fish = YOU ATE GEFILTE-FISH AT SUPPER eat 'gefilte-fish 'supper SUPPER IS THE DEFAULT -- YOU COULD HAVE LEFT IT OUT = YOU ATE GEFILTE-FISH AT SUPPER
Function Parameters:
12
We can write functions that are even more exible by using &rest parameters. An &rest parameter gets bound to ALL remaining arguments in the function call.
defun eat first-food &rest more-foods format t "~you started with ~A" first-food dolist next-food more-foods format t "~and then you had ~A" next-food 'burp = EAT eat 'gefilte-fish you started with GEFILTE-FISH = BURP eat 'gefilte-fish 'horseradish you started with GEFILTE-FISH and then you had HORSERADISH = BURP eat 'gefilte-fish 'horseradish 'pickles you started with GEFILTE-FISH and then you had HORSERADISH and then you had PICKLES = BURP eat 'gefilte-fish 'horseradish 'pickles 'olives you started with GEFILTE-FISH and then you had HORSERADISH and then you had PICKLES and then you had OLIVES = BURP
Function Parameters:
&rest
13
Function Parameters:
&keyword
14
continued The nifty thing about keyword parameters is that you can specify any subset of a function's arguments, in any order:
&keyword
defun make-poem title &key subject 'flower location 'porch blaster 'torch covering 'snow format t "~~A, by Lulu Lispy" title format t "~--------------------------" format t "~'twas a stupendously beautiful ~A" subject format t "~upon my ~A-covered ~A" covering location format t "~such a lovely lovely ~A" subject format t "~I blasted it with my ~A." blaster = MAKE-POEM make-poem 'spring SPRING, by Lulu Lispy -------------------------'twas a stupendously beautiful FLOWER upon my SNOW-covered PORCH such a lovely lovely FLOWER I blasted it with my TORCH. = NIL make-poem 'spring :location 'veranda :blaster 'power-sander SPRING, by Lulu Lispy -------------------------'twas a stupendously beautiful FLOWER upon my SNOW-covered VERANDA such a lovely lovely FLOWER I blasted it with my POWER-SANDER. = NIL
Function Parameters:
15
Function Parameters:
&keyword
continued
make-poem 'spring :location 'veranda :blaster 'power-sander :subject 'pumpkin SPRING, by Lulu Lispy -------------------------'twas a stupendously beautiful PUMPKIN upon my SNOW-covered VERANDA such a lovely lovely PUMPKIN I blasted it with my POWER-SANDER. = NIL make-poem 'spring :subject 'space-alien :location 'veranda :blaster 'power-sander :covering 'glitter SPRING, by Lulu Lispy -------------------------'twas a stupendously beautiful SPACE-ALIEN upon my GLITTER-covered VERANDA such a lovely lovely SPACE-ALIEN I blasted it with my POWER-SANDER. = NIL
16
continued &keyword parameters can also be given SUPPLIED-P variables, and they may be combined with &optional and &rest parameters. Note that many built-in functions use &keyword parameters for optional features. For example, MEMBER has 3 keyword parameters: TEST, TEST-NOT, and KEY. It sounds funny to have a &keyword parameter called KEY, but that's just a coincidence. Here are some examples:
&keyword
member 'prune 'raisin prune cheese = PRUNE CHEESE defun young-version food case food raisin 'grape prune 'plum cheese 'milk = YOUNG-VERSION young-version 'prune = PLUM member 'plum 'raisin prune cheese = NIL member 'plum 'raisin prune cheese :key 'young-version = PRUNE CHEESE member 'green 'blue seagreen grass yellow teeth = NIL member 'green 'blue seagreen grass yellow teeth :key 'car = GREEN GRASS YELLOW TEETH
Function Parameters:
17
Function Parameters:
NOTE: TEST defaults to the function EQL. TEST-NOT is not as obvious, but it is sometimes handy:
member 4 '4 4 4 4 4 4 23 5 5 5 5 5 5 = 4 4 4 4 4 4 23 5 5 5 5 5 5 member 4 '4 4 4 4 4 4 23 5 5 5 5 5 5 :test-not 'eq = 23 5 5 5 5 5 5
18
Looping in Tanimoto is very simple dotimes, dolist, loop. dolist variable list optional-result body ...
defun length1 list let len 0 dolist element list incf len len ; start with LEN=0 ; and on each iteration ; increment LEN by 1 ; and return LEN
Looping Constructs
Most commonly used do macro. Note: we'll talk about LET next time.
do do* variable initial next ... exit-test result body ...
defun length3 list do len 0 + len 1 l list rest l null l len ; start with LEN=0, increment ; ... on each iteration ; until the end of the list
19
There are more complicated looping constructs than those described in Tanimoto, i.e., loop". Note: You should not be using loop in lieu of sequence operations. e.g., nding an elt in a list should be done with nd or nd-if, not loop or do. Note from last time: return x; will return out of a loop of any kind do, dolist, etc. with the value x. We'll look at this in a minute. Steele 84: loop body ... This is the old loop forever" loop. Tanimoto Steele 90: loop do body ... This is the more sophisticated loop macro that allows counting, summing, etc. Many di types of loop keywords." Example from page 60:
defun length6 list loop with len = 0 until null list for element = pop list do incf len finally return len ; ; ; ; ; start with LEN=0 and until end of list on each iteration increment LEN by 1 and return LEN
Loop
Can read Steele 90 for more details. Can also use COLLECT:
loop for i in 'bird 3 l horse when symbolp i collect i = bird horse
20
Defmacro
defmacro macro-name parameter ... body ... Compare: defun fn-name parameter ... body ... Similar structure, but a macro is di erent: the compiler expands macros into some other code. When do we use macros? When we want some nice" syntax that expands into uglier code that we don't care about looking at. 1 Decide what the nice" syntax is. 2 Decide what the ugly" code is. Why used? 1 E ciency: expanded in-line at compile time |More e cient than calling a fn at RT 2 Eval'n of args can be suppressed |Example: setf does not eval rst arg. 3 CT: can base expansion of macro on known arg vals
|setf
aref a 1 0: let* :g332 a :g331 0 excl::.inv-s-aref :g331 :g332 0
4 Shorthand: allows you to say things more concisely Evaln of macro: extra evaln step before standard form evaln takes place. Use macroexpand to see what a macro expands out to. Every time you de ne a macro, you are actually de ning a new language and writing a compiler for it! So don't take macros lightly.
21
| setf
a 1: setq a 1
Defmacro
Defmacro: 1 args bound to formals 2 macro's body eval'd produce new form 3 eval the new form at RT to produce nal value while test body ... loop unless test return nil body
Note: unless has intuitive meaning.
Expands to:
loop unless
How do we know when something is a macro? 1 Are args quoted? If not then probably macro, but not very reliable. 2 Macro-function 3 Macroexpand: if returns same thing, then not macro:
macroexpand 'cons 'a 'b: cons 'a 'b
22
DEFMACRO constructs a global macro de nition, binds it to symbol, marks symbol as a macro, and returns symbol. Defmacro is the macro equivalent of defun.
defvar *people-ages* 'sally 22 john 21 tina 56 eugene 43 wendy 11 sam 1 = *PEOPLE-AGES* defun get-age name &optional people-ages *people-ages* cond null people-ages nil eq name car car people-ages car cdr car people-ages t get-age name cdr people-ages = GET-AGE get-age 'tina = 56 get-age tina Error: Unbound variable: TINA defmacro age name list 'get-age list 'quote name = AGE age tina = 56 macroexpand 'age tina = GET-AGE 'TINA
23
Macros have more interesting applications. They are often used to extend the syntax of lisp.
defmacro while test &rest body append list 'do nil list list 'not test body = WHILE let n 1 while n 10 print n setq n + n 1 1 2 3 4 5 6 7 8 9 = NIL macroexpand-1 'while n 10 print n setq n + n 1 = DO NOT N 10 PRINT N SETQ N + N 1
24
Backquote Comma
Hardest part about de ning macro is building code that is the expansion of the macro. Have to use list, cons, append, etc. when writing a macro. Use backquote `: Gives more immediate way of building code. Handy in writing macros: acts just like quote except that any expression preceded by a comma is considered to be unquoted: setf name 'fred `I gave ,name about ,* 25 8 dollars becomes
i gave fred about 200 dollars
Backquote useful for other things not always used in macro: list list x where x = b c d can be speci ed as: `,x ! b c d. Other examples:
'spring forward fall back = SPRING FORWARD FALL BACK `spring forward fall back = SPRING FORWARD FALL BACK `spring forward fall back ,+ 100 265 times = SPRING FORWARD FALL BACK 365 TIMES 'spring forward fall back ,+ 100 265 times Error: Comma not inside backquote list 'spring 'forward 'fall 'back + 100 265 'times = SPRING FORWARD FALL BACK 365 TIMES defmacro mysetq a e `set quote ,a ,e mysetq x 3 ! set quote x 3 equiv to setq x 3
25
Commas, Comma-atsign
Commas can be nested deep within list structure:
setq name 'barney = BARNEY setq occupation 'bozo = BOZO append 'hello `mister ,name the ,occupation = HELLO MISTER BARNEY THE BOZO
COMMA-ATSIGN ,@ within a backquote splices" its list-valued result into the larger list: `a ,@x where x is b
c d ! a
b c d setq fudds-law 'if you push something hard enough it will fall over = IF YOU PUSH SOMETHING HARD ENOUGH IT WILL FALL OVER `in my youth i thought that ,@fudds-law -- but now i know better = IN MY YOUTH I THOUGHT THAT IF YOU PUSH SOMETHING HARD ENOUGH IT WILL FALL OVER -- BUT NOW I KNOW BETTER
26
Using the backquote, how would we rewrite WHILE without using LIST and LIST*? i.e., using ` and , and @?
defmacro while test &rest body `do not ,test ,@body
Cleaner Macros
The function MACROEXPAND-1 can be used to expand only one level of macro de nitions:
MACROEXPAND-1 form &optional environment Function
MACROEXPAND-1 returns the result of expanding form once within environment. In e ect, macroexpand simply calls macroexpand-1 repeatedly until no more expansion is possible.
27
Macro Tips
Note: have to be careful not to evaluate an expression more than once: Suppose element = cons 'a 'b? Don't want to evaluate this twice. Better to use LET:
`let elt ,element unless null elt print elt defmacro foo element `unless null ,element print ,element
PUSH is a macro:
So: push 'a x ! setq x cons 'a x Note: you can assume this macro is available in your homeworks. This is the most obvious way of inserting an elt at the front of a list.
28
More Macros
29
GENSYM creates and returns a unique uninterned symbol. If string-or-number is given, it will be used in the name of the new symbol.
30
31
More Macros
defmacro fortran operator &rest args case operator if cons 'arithmetic-if args do append 'do new-line-num args go cons 'go args = FORTRAN fortran if - x 3 * x 2 * x 100 * x x = 100 MACROEXPAND-1 'fortran if - x 3 * x 2 * x 100 * x x = ARITHMETIC-IF - X 3 * X 2 * X 100 * X X MACROEXPAND 'fortran if - x 3 * x 2 * x 100 * x x = LET :G304 - X 3 COND :G304 0 * X 2 = :G304 0 * X 100 T * X X
32
We can write a recursive version of macroexpand that expands all macro calls:
defun macroexpand* form if atom form form let expansion macroexpand form if consp expansion cons macroexpand* car expansion macroexpand* cdr expansion expansion = MACROEXPAND* macroexpand* 'cond x y 'x-higher x y 'x-lower t 'same = IF X Y PROGN 'X-HIGHER IF X Y PROGN 'X-LOWER IF T PROGN 'SAME NIL macroexpand 'cond x y 'x-higher x y 'x-lower t 'same = IF X Y PROGN 'X-HIGHER COND X Y 'X-LOWER T 'SAME
33
34
35
This section borrows from Paul Graham's ON LISP, Prentice Hall, 1994|THE book to read about lisp macros Here are some of the nifty things you can do with macros:
Argument transformation|e.g., the SETF macro, which picks apart its arguments before evaluation. Conditional evaluation of arguments|like IF, WHEN, COND, etc. Multiple evaluation of arguments|like DO, WHILE, etc. Use of the calling environment|a macro expansion replaces the macro call in the lexical scope of the call|hence it can use and change lexical bindings in ways that functions can't. For example, the behavior of the macro:
defmacro foo x `+ ,x y
depends on the binding of y where foo is called. Graham notes that This kind of lexical intercourse is usually viewed more as a source of contagion than a source of pleasure." Reduction of function call overheads|there is no overhead associated with macro calls. By runtime, the macro call has been replaced by its expansion. Computation at compile time|you can sometimes move a *lot* of computation to compile-time, reducing the runtime computation to a minimum. Integration with Lisp|sometimes you can write macros that transform problems, in a higher-level language of your own design, into simple Lisp. 36
37
Alists, Assoc
The matching functions in chapter 3 use an association list" ALIST for representing the associations of values with variables. ALIST: A list of lists in which each list is called an entry and the car of each entry is the key. In the book, each list is a dotted pair:
VAR1 . VAL1 VAR2 . VAL2 ...
Can use to build a table with or without dot: setf words 'one uno two dos three tres four cuatro ve cinco Use assoc to access: assoc 'one words :test 'eq ! one uno Allows you to index by key. Note, use :TEST. defun translate x second assoc x words :test 'eq translate 'one What is the result? ! uno
26
Can also use RASSOC to index by value rather than key, but the a-list must be stored as cons cells, not lists:
You might nd cons cells easier to work with as in the book.
27
Defstruct continued
Constructor, accessor, assignment automatically de ned when data structure is de ned.
DEFSTRUCT name-and-options doc-string slot-description * Macro
DEFSTRUCT de nes a new structure, according to name-andoptions, with slots described by the slot-descriptions.
defstruct elephant name color 'grey nose 'trunk isa 'mammal
ELEPHANT
Accessor:
WHITE
Assignment:
You COULD build complex data structures out of lists: I'll represent a PERSON as a list of name age shoe-size parents children where:
name is a list of atoms age is an integer shoe-size is an integer parents is a list of names children is a list of names
For example:
setq person-1 'betty byte 22 4 boopsie bytebarney byte bobby bytebelinda byte = BETTY BYTE 22 4 BOOPSIE BYTE BARNEY BYTE BOBBY BYTE BELINDA BYTE
We could also write a function with keyword arguments to make the construction of new PERSONs easier:
defun make-person &key name 'ordinary jo age 20 shoe-size 5 parents nil children nil "Returns a PERSON with the given attributes" list name age shoe-size parents children = MAKE-PERSON make-person :name 'consina cadarowitz = CONSINA CADAROWITZ 20 5 NIL NIL make-person :name 'consina cadarowitz :age 15 :parents 'candy carcharlie cdr = CONSINA CADAROWITZ 15 5 CANDY CAR CHARLIE CDR NIL
We could also write functions to DESTRUCTIVELY modify PERSONs. This requires the use of SETF:
defun set-person-name p new-name setf car p new-name = SET-PERSON-NAME set-person-name person-1 'boxcar willie = BOXCAR WILLIE person-1 = BOXCAR WILLIE 22 4 BOOPSIE BYTE BARNEY BYTE BOBBY BYTE BELINDA BYTE
Defstruct continued
This AUTOMATICALLY does the following: Creates a new data type called PERSON, which is a STRUCTURE with 5 SLOTS. De nes 5 new functions PERSON-NAME, PERSONAGE, PERSON-SHOE-SIZE, PERSON-PARENTS, and PERSON-CHILDREN, each of which takes a PERSON as its argument and returns the associated slot of that PERSON. De nes a predicate PERSON-P of one argument that is true if its argument is a PERSON. De nes a function MAKE-PERSON with 5 keyword arguments corresponding to the slots of PERSONs. Note: 1 Structures are not lists; 2 Structures may be destructively modi ed using SETF and the automatically de ned access functions; 3 DEFSTRUCT has many more features that we'll ignore for now.
6
Defstruct continued
setq person-2 make-person :name 'sally silicon = SPERSON :NAME SALLY SILICON :AGE 20 :SHOE-SIZE 5 :PARENTS NIL :CHILDREN NIL person-2 = SPERSON :NAME SALLY SILICON :AGE 20 :SHOE-SIZE 5 :PARENTS NIL :CHILDREN NIL person-name person-2 = SALLY SILICON person-shoe-size person-2 = 5 person-p person-2 = T person-p nil = NIL person-p person-1 = NIL person-2 = SPERSON :NAME SALLY SILICON :AGE 20 :SHOE-SIZE 5 :PARENTS NIL :CHILDREN NIL setf person-children person-2 'sam silicon = SAM SILICON person-2 = SPERSON :NAME SALLY SILICON :AGE 20 :SHOE-SIZE 5 :PARENTS NIL :CHILDREN SAM SILICON