Transcript (1) ((a))

LISP Data Types
Functional Programming
Academic Year 2005-2006
Alessandro Cimatti
[email protected]
LISP: basic data types
• Everything is a symbolic expression
• Symbolic expressions can be
– Atoms
• Numbers
• Symbols
– Lists
• Atom: a sequence of characters beginning with a
letter, digit or special character other than “(“ or
“)”.
– numbers, variable names, etc.
– Examples
• 2, 30, fibo, this-is-an-atom
Recognizers
> (atom 'a)
T
> (atom 12)
T
>(atom '(12 23))
NIL
> (numberp 'a)
NIL
> (numberp 12)
T
> (symbolp 'a)
T
> (symbolp 12)
NIL
Basic Math
• Predicates:
–
–
–
–
–
–
(zerop number)
(plusp number)
(oddp integer)
(evenp integer)
(integerp atom)
(floatp atom):
returns true if the argument is zero/positive number/etc.; nil, otherwise.
• Comparison:
–
–
–
–
–
–
–
(= number more-numbers)
(/= number more-numbers)
(< number more-numbers)
(> number more-numbers)
(<= number more-numbers)
(>= number more-numbers)
(<= 1 3 5 7)  T; (< 1 3 3 5)  Nil;
Basic Math
• Arithmetic Operations:
–
–
–
–
–
–
(+ numbers)
(- number rest-numbers)
(* numbers)
(/ number rest-numbers)
(1+ number)
(1- number)
• Examples
–
–
–
–
–
–
–
–
(1+ 24)  25
(1- 24)  23
(+ 2 5 6)  13
(+ ) = 0
(/ 3 4 5)  3/20
(/ -3) = -1/3
(* )  1
(+ (* 2 3) (/ 2 5))  32/5
More Math
•
•
•
•
(max 1 2 3 4 5)  5
(min 1 2 3 -4)  -4
(exp number) = enumber
(expt base power) = basepower
– (exp 2)  7.389
– (expt 2 3)  23 = 8;
• (log number optional base) = logbase number;
– (log 8 2)  3; (log 3)  1.09;
• (abs number)
– (abs -5)  5
• (signum number) returns -1, 0 or 1 if the number is negative, zero or
positive, respectively
• (sqrt number);
• (isqrt number) returns the greater inter less than equal to the exact
positive square-root of the number
• (round number)
• (floor number)
• (ceiling number)
• (truncate number)
Symbolic Expressions
• Everything is an S-expression (Symbolicexpression).
• S-expression = ATOM | LIST
• List:
– a collection of S-expression enclosed by parentheses
– a sequence of items.
– Examples
• (1 apple 200 3.14),
• ((peach (orange)) 3.14 (apricot) apple)
– List is treated as function calls
• first item as the name of a function.
– Example
• (append ’(a b) ’(c d))  (a b c d)
NIL
• NIL is a special S-expression
• It is both an atom and a list.
• It represents the empty list
– can also be written as ()
• It represents falsity
– anything else is considered to be true
– T is the default value used for true
• Examples
(not
(not
(not
(and
(and
nil) = t
t) = nil
‘p) = nil
‘p ‘q nil ‘r) = nil
‘p ‘q ‘r) = r
The List ADT
• A list is either
– The empty list ()
• or
– The list obtained by adding an element to a list
• The Abstract Data type:
–
–
–
–
()
cons
first
rest
:
->
: <elem> x <list> ->
:
<list> ->
:
<list> ->
<list>
<list>
<elem>
<list>
Lists: examples
• The empty list
– NIL, also written ( )
• One element lists
–
–
–
–
(a)
(1)
((a))
(())
• Two element lists
– (a 1)
– (a b)
– (a (1))
Operators
• atom: returns true if the argument is an atom; nil otherwise.
– (atom ’(a b))  nil
– (atom ’a)  T
• null: returns true if the argument is nil, nil otherwise.
– (null ’(a b))  nil;
– (null ’())  T
(null ’a)  nil
• first, rest:
– (first ’(a b))  a
– (rest ’(a b))  (b)
• second, third, .., nth:
– (second ’(a b))  b
– (nth 3 ’(a b c d))  c
On Quoting
• Lists are treated as function calls
• When given a list, the interpreter attempts to evaluate the 1st term as
the name of a function
• The other terms are evaluated using the previously given rules, the
results of their evaluations are passed as parameters.
• The quote operator prevents the interpreter from trying to evaluate an
s-expression.
> (setq a 5)
5
> (+ 6 (* 3 a))
21
> (list (quote (+ 2 a)) 1 3)
((+ 2 a) 1 3)
> (list ‘(+ 2 a) 1 3)
((+ 2 a) 1 3)
Eval
• Quote returns an atom or a list preventing its evaluation.
> (setq a ‘b)
b
> (setq b ‘c)
c
• Eval: is the inverse of the quote operator
> (+ 3 6)
9
> (eval ’(+ 3 6))
9
> (eval ’a)
b
> (eval a)
c
> (eval ’b)
c
> (eval b)
Error: the variable c is unbound
Operators
• length: number of elements in a list
– (length ’(a b c))  3
• cons: append an atom and a list
– (cons ’a ’(b c d))  (a b c d)
– (cons ’(a) ’(b c d))  ((a) b c d)
• first: return the first element of a list
– (first ’(a b c))  a
• rest: return the list without the first element
– (rest ’(a b c))  (b c)
• basic properties
– (first (cons x y)) = x
– (rest (cons x y)) = y
Operators
• list: creates a list out of atoms and lists
– (list
– (list
– (list
 (a
’a
’a
’a
(1
’b ’c)  (a b c)
’((b) c))  (a ((b) c))
’(1 2) ’((b c) (3 4)))
2) ((b c)(3 4)))
– (list 1 2 (* 3 4))  (1 2 12)
(* 3 4) gets evaluated!
Basics: list
• append: append two lists
> (append ’(a
(a b c d)
> (append ’(a
(a b a b c d)
> (append ’(a
(a b c d)
> (append ’()
()
b) ’(c d))
b) ’(a b) ’(c d))
b) ’() ’(c d))
’() ’())
Basics: list
• member: takes two arguments to search for
and a list to search for it in, then returns the
item if it finds it and everything after it in the
list
> (member 3 ’((1 2) 3 4 5))
(3 4 5)
> (member 2 ’((1 2) 3 4 5)
nil
Binding
• You can bind variable anywhere in a program with the let or let*
special forms to create a local context.
– let and let*: lexical scope (local context)
• (let ( <list of local vars> ) <body> )
• (let ((a 20) b (c 30)) <body> )
– With let*, values from previous variables can be used to define new
value.
• (let* ((a 20) (b (* 2 a)) c) <body> )
–
>
3
>
8
>
3
>
5
>
3
Examples
(let ((a 2)) (+ a 1))
(let ((a 2) (b 4) (c 0)) (* a b))
(setq c 3)
(let ((c 5)) c)
c
Lexical scope
• Return value according to the lexical scope where
it’s defined.
> (setq reg 5)
5
> (defun check-reg () reg)
CHECK-REG
> (check-reg)
5
> (let ((reg 6))
(check-reg))
5
Dynamic scope
• Defvar can be used to define a special variable
that is dynamically scoped.
> (defvar *sp* 3)
*sp*
> (defun check-sp () *sp*)
CHECK-SP
> (check-sp)
3
> (let ((*sp* 4)) (check-sp))
4
> *sp*
3
> (let ((x 23)) (check-sp))
3
Conditional Predicates
• Predicates
–
–
–
–
–
–
–
Returns either T or Nil.
numberp, listp, symbolp, zerop, etc.
atom:
test if an s-expression is an atom.
null:
tests for nil.
equal: test if the values are the same.
eq:
test if the memory locations are the same.
typep: takes two parameters of an element to test and
a type to test it for
• e.g.) (typep 6 ’number)
– Logical operators: and, or, not
• Nil or the empty list is considered to be false, everything else
is true.
• (and 1 2)  2
• (and () 2)  nil
Control structure
• if statement
– (if condition Body1-when-true Body2-when-false)
> (if (< 3 5) (+ 2 3) (* 2 3))
5
• cond statement
– (cond ((testp1) body1)
((testp2) body2)
....
(t (default-body))
> (cond ((> 1 2) (+ 2 3))
((< 2 3) (* 2 3))
(t
10))
6
Length
(defun length (l)
(if (null l) 0
(+ 1 (length (rest l)))))
length
> (length ‘(a b c))
(+ 1 (length ‘(b c)))
(+ 1 (+ 1 (length ‘(c))))
(+ 1 (+ 1 (+ 1 (length ‘()))))
(+ 1 (+ 1 (+ 1 0))
...
(+ 1 2)
3
Iterative Length
> (defun length (l) (length-iter l 0))
length
> (defun length-iter (l cnt)
(if (null l) cnt
(length-iter (rest l) (+ 1 cnt)))
length-iter
> (length ‘(a b c))
(length-iter ‘(a b c) 0)
(length-iter ‘(b c) 1)
(length-iter ‘(c) 2)
(length-iter ‘() 3)
3
Append
(defun append (l1 l2)
(if (null l1) l2
(cons
(first l1)
(append (rest l1) l2)))))
Running Append
> (append ‘(1 2) ‘(3 4 5))
(cons 1 (append ‘(2) ‘(3 4 5)))
(cons 1 (cons 2 (append ‘() ‘(3 4 5)))
(cons 1 (cons 2 ‘(3 4 5)))
(cons 1 ‘(2 3 4 5))
(1 2 3 4 5)
Reverse
(defun reverse (l)
(if (null l) l
(append
(reverse (rest l))
(list (first l)))))
Running reverse
> (reverse ‘(a b c))
(append (reverse ‘(b c)) ‘(a))
(append (append (reverse ‘(c)) ‘(b)) ‘(a))
(append (append (append () ‘(c)) ‘(b)) ‘(a))
(append (append ‘(c) ‘(b)) ‘(a))
(append (cons ‘c ‘(b)) ‘(a))
(append ‘(c b) ‘(a))
(cons ‘c (append ‘(b) ‘(a)))
(cons ‘c (cons ‘b ‘(a)))
(cons ‘c ‘(b a))
(c b a)
; Notice something wrong?
; We traverse the lists too many times!!!
Iteration vs Linear Recursion
• We have seen this happen with numbers
• The return value of the caller function is
the return value of the called function
• No need to “wait on stack” for called
function to return
• Iteration can be optimized during
compilation
Reverse Iterative
(defun reverse (l)
(reverse-iter l ()))
(defun reverse-iter (l acc)
(if (null l) acc
(reverse-iter (rest l) (cons (first l) acc))))
(reverse-iter
(reverse-iter
(reverse-iter
(reverse-iter
‘(c b a)
‘(a b c) nil)
‘(b c) (cons ‘a nil))
‘(c) (cons ‘b ‘(a)))
‘() (cons ‘c ‘(b a)))
Append Iterative
(defun append (l1 l2) (append-iter l1 l2 ()))
(defun append-iter (l1 l2 acc)
(if (null l1)
(if (null acc) l2
(append-iter l1 (cons (first acc) l2) (rest acc))
(append-iter (rest l1) l2 (cons (first l1) acc)))))
> (append-iter ‘(a b) ‘(c d e) ‘())
(append-iter ‘(b) ‘(c d e) ‘(a))
(append-iter ‘() ‘(c d e) ‘(b a))
(append-iter ‘() ‘(b c d e) ‘(a))
(append-iter ‘() ‘(a b c d e) ‘())
(a b c d e)
The Cons ADT
•
A cons is either
–
•
Or
–
•
<atom>:
->
cons : <sexp> x <sexp> ->
car
:
<cons> ->
cdr
:
<cons> ->
<sexp>
<cons>
<sexp>
<sexp>
Basic properties
–
–
•
The list obtained by consing two elements
The Abstract Data Type:
–
–
–
–
•
The empty list ()
(car (cons x y)) = x
(cdr (cons x y)) = y
Compare with lists: the second element of the last cons of a list is always nil
> (cons 1 2)
(1 . 2)
> (list 1 2)
(1 2)
> (cons 1 (cons 2 nil))
(1 2)
Conses
• cons: takes two s-expressions and returns a list
whose car is the 1st item and whose cdr is the 2nd item.
i.e. insert the 1st item into the list of 2nd item.
– (cons ’a ’(b c))  (a b c)
– (cons ’(a) ’(b c))  ((a) b c)
• car: returns 1st element (atom or list)
– (car ’(a (b d)))  a
– (car ’((a b) c))  (a b)
• cdr: returns the rest of a list except the 1st element of a
list
– (cdr ’(a (b c)))  ((b c))
– (cadr ’((a b) c))  (c)
• Combinations are possible: cXXXXr where X=(a|r)
– (cadr ’(a (b c))) == (car (cdr ’(a (b c))))
 (b c)
Dot notation
• A dot is used to represents a cons with infix
notation
• The printer will try to avoid printing dots explicitly
turning them into list notation:
> ’(1 . 2)
(1 . 2)
> ’(1 . nil)
(1)
> ’(1 . (2 . 3))
’(1 2 . 3)
> ’((1 . 2) . (3 . 4))
’((1 . 2) 3 . 4)
Counting the atoms
> (defun cnt-atom (l)
(cond ((null l) 0)
; nil
((atom l) 1)
; not a cons
(t (+ (cnt-atom (car l))
(cnt-atom (cdr l))
)
)
)
)
cnt-atom
> (cnt-atom '(a (b c) d (e f (g h))))
8
> (cnt-atom '(a (b . c) d (e f (g . h))))
8
Flattening a tree
(defun flat (x)
(cond ((null x) x)
((atom x) (list x))
(t (append (flat (car x))
(flat (cdr x))))))
f
>(flat '(1 2 3 4))
(1 2 3 4)
>(flat '(1 (2 3) 4))
(1 2 3 4)
>(flat '(2 . 3))
(2 3)
>(flat '(() 1 (1 (2 4) (5 . 3))))
(1 1 2 4 5 3)
Flattening a tree
(defun flat1 (x)
(cond ((atom x) (list x))
(t (append (flat1 (car x))
(flat1 (cdr x))))))
f
>(flat1 '(1 2 3 4))
(1 2 3 4 NIL)
>(flat1 '(1 (2 3) 4))
(1 2 3 NIL 4 NIL)
>(flat1 '(2 . 3))
(2 3)
>(flat1 '(() 1 (1 (2 4) (5 . 3))))
(NIL 1 1 2 4 NIL 5 3 NIL)
Flattening a tree
(defun flat2 (x)
(cond ((null x) x)
((atom x) (list x))
((null (car x)) (cons nil (flat2 (cdr x))))
(t (append (flat2 (car x))
(flat2 (cdr x))))))
f
>(f '(1 2 3 4))
(1 2 3 4)
>(f '(1 (2 3) 4))
(1 2 3 4)
>(f '(2 . 3))
(2 3)
>(f '(() 1 (1 (2 4) (5 . 3))))
(NIL 1 1 2 4 5 3)