l-calculus Back to this:
SUCC := λnfx.f (n f x)
This function takes how many 3
arguments?
What are the formal arguments?
n,f,x notnfx
1
l-calculus
λx. a b how many formal arguments? 1 (λx.ab)(abc) Whatisreturned? ab
Why?
The formal argument is not used in the function. Like:
(defun strange (x) (+ 1 2))
2
12
Given this:
0 := λf.λx.x λfx.x
1 := λf.λx.f x λfx. f (x)
SUCC := λnfx.f (n f x) How do you do SUCC 1?
3
The Q is similar to, given:
(defun simple (x) (+ 1 x))
How do you call simple?
(simple 5)
You call the fn by supplying an arg.
4
34
0 := λf.λx.x λfx.x
1 := λf.λx.f x λfx. f (x)
SUCC := λnfx.f (n f x)
arg
Succ 1 = λnfx.f(n f x) (λfx. f(x)) = λfx.f( (λfx. f(x)) f x)
= λfx.f( (λx. f(x)) x) = λfx.f(f(x))
fn
5
SUCC := λnfx.f (n f x) Succ 1 = λnfx.f(n f x) (λfx. f(x))
= λfx.f(f(x))
So, here we have a function that computes a value. Each step is precisely determined that when executed will give you the answer in a finite number of steps i.e an effective procedure
6
56
1
LISP itself
LISP is like a virtual computer. It has:
A list = Memory
An eval function = CPU/State table
What else is missing?
Machine codes = basic instructions for driving the computer
7
LISP itself
The “machine” codes for LISP are the basic instructions needed for manipulating lists + a couple of other basic functions.
What basic functions do we need?
8
78
Basic functions in LISP
For accessing elements in a list:
Car, cdr, first, second, caadr, cdadr
(a b c d e f g)
a car/first (bcdefg) cdr/rest
car/cdr: two basic instructions for access
9
Basic functions in LISP
For accessing elements in a list:
Car, cdr, first, second, caadr, cdadr
(a b c (d e) f g)
c caddr/third
e (cadr (cadddr
max 4
10
9 10
(car (a b) (c d))
(rest ‘(a b) ‘(b c))
(cadr (a (b c)) error (cadar ‘(((a ‘b)))) nil (cdddr ‘(a))
error
error
nil
11
Confusing brackets?
1) (caaar ‘((() x (r s) t))) (caaar ‘( ))
(caar ‘(nil x (r s) t))) (car ‘())
2) (cdddr ‘((() x (r s) t))) (cdddr ‘( ))
(cddr nil) (cdr nil)
()
Think of a complex list as a blob!
12
()
11 12
2
Basic functions in LISP
For constructing new lists:
cons Put something in a list
list Put everything in a list
append Combine lists into a single list
13
(cons (a b) (c d)) (cons ‘(a b) ‘(b c)) (cons ‘a (b c)) (cons ‘a ‘b)
error
((a b) b c) error (a.b)
(a.b) is known as a dotted pair
14
13 14
(list ‘(a b) ‘(c d))
(append ‘(a b) ‘(b c))
(list ‘a ‘(b c))
(cons ‘a ‘(b c)) (append ‘a ‘(b c))
((a b) (c d))
(a b b c) (a (b c))
(a b c) error
15
LISP Data Structure
(a b c) (d e) abc de
(cons ‘(a b c) ‘(d e))
abcde
16
15 16
LISP Data Structure
What happens when you (cons ‘a ‘e)?
e:
What does this stand for?
a:
e
a
(cons ‘a ‘e)?
a
a
(a)
e
You get a dotted pair
17
Basic functions in LISP
Other standard functions:
setf (for assigning values) defun
T (or anything nonNIL), Nil cond, when, if, unless equal, =
listp, numberp, atom, evenp, oddp and, or, not
member, reverse, null, length
18
17 18
3
1) (atom nil)
2) (null nil) T
T Nil is a funny thing in LISP. The reason (1)
returns T is because atom returns T if it is not a consed cell.
So, what is a consed cell?
In other words, nil is represented as NIL (i.e. a symbol) although we write () which makes it look like a list.
Nil is not represented as: but as symbol NIL
19
(numberp x) (evenp x) (oddp x) (listp x) (atom x)
What is odd about this list?
Atom is not defined as atomp even though it is a predicate – this is due to historical reason.
20
19 20
21 22
9) (and(or(=33)(=23))(=45)) 10) (or (3 + 3) ‘(= 3 3))
nil error
11) (or (+ 3 3) ‘(= 3 3)) 6
12) (or ‘(= 3 3) (3 + 3)) (= 3 3)
(why not error?)
OR evaluates until a predicate returns T whereas AND evaluates until a predicate returns NIL – lazy evaluation
21
13) Return f in ((a b) (c d) (e f))
(last ‘ ) ((e f)) returns the
a list
Rewrite the above using reverse instead of last: (cadar (reverse ‘ ))
What about: (last (last ‘ ))? ((e f))
last element (cadar (last ‘ )) f in the list as
22
Conditional Statements
(cond (predicate1 s1 s2 s3…sn) (predicate2 s1 s2 s3…sn)
::
(predicaten s1 s2 s3…sn))
23
Example:
(defun simple (x)
(cond ((oddp x) (1+ x))
((evenp x) (* x x))))
(defun simple (x)
(cond ((oddp x) (1+ x))
(t (* x x))))
24
23 24
4
Use “if” if there are only two options:
(defun simple (x)
(cond ((oddp x) (1+ x))
(t (* x x)))) (defun simple (x)
(if (oddp x) (1+ x) (* x x))) But, you don’t need to.
25
Write a function, FUN, that given a number will do the following. If it is 1, returns “one”, if it is 2 returns “two”, else returns “toobig”.
(defun fun (x)
(cond ((= x 1) ‘one)
((= x 2) ‘two) (t ‘toobig)))
26
25 26
Write a function, my-sum, that given a list of numbers, will return its sum.
(defun my-sum (L) (cond ((null L) 0)
(t (+ (car L) (my-sum (cdr L))))))
27
Write a function odd-L which given a list of numbers will identify all the odd numbers in it.
Ø (odd-L ‘(1 2 3 4 5)) (t nil t nil t)
Ø (odd-L ‘(1)) (t)
(defun odd-L (L)
(cond ((oddp (car L)) (cons T (odd-L (cdr L))))
(t (cons NIL (odd-L (cdr L))))))
28
27 28
Write a function odd-L which given a list of numbers will return all the odd numbers in it.
Ø (odd-L ‘(1 2 3 4 5)) (1 3 5)
Ø (odd-L ‘(1)) (1)
(defun odd-L (L)
(cond ((oddp (car L))
(cons (car L) (odd-L (cdr L)))) (t (cons NIL (odd-L (cdr L))))))
29
Write a function oddlist which given a list will return all the odd numbers in it.
Ø (oddlist ‘(1 2 b (c 3) d)) (1)
Ø (oddlist ‘(2 (5 7) 8)) ()
30
29 30
5
Write a function oddlist which given a list will return all the odd numbers in it.
(defun oddlist (L) (Cond ((null L) nil)
((and (numberp (car L)) (oddp (car L))) (cons (car L) (oddlist (cdr L))))
(t (oddlist (cdr L)))))
31
LISPWorks
When using LISPWorks, you can open a new file and type in your functions.
To transfer a function to the listener, you need to evaluate it. Go to “buffers”, type compile or evaluate. This evaluates all functions in your file.
To evaluate just one function, select your function by moving your cursor to the end of the function and go to “definitions” and press evaluate.
32
31 32
Tracing functions
>(trace fac) (fac)
>(fac 2) >(untrace fac)
CL-USER 4 > (fac 2) 0 FAC > …
>> N : 2
1 FAC > …
>> N : 1
2 FAC > …
>> N : 0 2 FAC < ...
<< VALUE-0 : 1 1 FAC < ...
<< VALUE-0 : 1 0 FAC < ...
<< VALUE-0 : 2 2
33
LISPWorks
LISPWorks allows you to do one “horrible” thing:
please put back the lovely brackets!
CL-USER 1 > + 1 2 3
CL-USER 2 > cons ‘a ‘(b c) (A B C)
CL-USER 3 >
34
33 34
6