https://inst.eecs.berkeley.edu/~cs61a/sp17/
- LISP
- Everything is an expression
- 不再有语句和表达式的区别
- Every expression is either a single value or a list
- Single values are things like numbers and strings and hash tables。
- The list part, however, is a big deal.
- In a language like Python, the list is one data type within the language
- But in Lisps, the list is more like an organizing principle for everything that happens.
- yes, you can use the list as a data type.
- But a function call is also a list.
- Functional programming.
- functions avoid two habits common in other languages: data mutation and relying on state.
- Everything is an expression
- atoms
- The classical atoms:
- Numbers: integer, floating-point, complex, rational.
- Symbols.
- Booleans:
#t,#f. - The empty list:
() - Procedures (functions).
- Some newer-fangled, mutable atoms:
- Vectors: Python lists.
- Strings
- Characters: Like Python 1-element strings
- The classical atoms:
- pairs
- Pairs are like two-element Python lists , where the elements are (recursively) Scheme values.
- Lisp最早是被设计来处理符号数据(如公式)。这些符号通常递归的被定义( an exp = op + subexps ).
- the notion of a symbol:
- Essentially a constant string
- Two symbols with the same “spelling” (string) are by default the same object (but usually, case is ignored).
- The main operation on symbols is equality.
- e.g.
a bumblebee numb3rs * + / wide-ranging !?@*!!
- e.g.
- The Scheme notation for the pair
- (V1 . V2)
- Lists are so prevalent that there is a standard abbreviation:
| Abbreviation | Means |
|---|---|
| (V ) | (V . ()) |
| (V1 V2 · · · Vn) | (V1 . (V2 . (· · · (Vn . ())))) |
| (V1 V2 · · · Vn−1 . Vn) | (V1 . (V2 . (· · · (Vn−1 . Vn)))) |
- one can build practically any data structure out of pair
- In Scheme, the main one is the (linked) list
- Scheme expressions and programs are instances of Lisp data structures (“Scheme programs are Scheme data”).
- At the bottom, numerals, booleans, characters, and strings are expressions that stand for themselves.
- Most lists (aka forms) stand for function calls:
(OP E1 · · · En)
- Since programs are data, we have a problem:
- How do we say, eg., “Set the variable x to the three-element list (+ 1 2)”
- without it meaning “Set the variable x to the value 3?”
- In English, we call this a use vs. mention distinction
- For this, we need a special form -- a construct that does not simply evaluate its operands.
(quote E)yields E itself as the value, without evaluating it as a Scheme expression:(quote (+ 1 2))=>(+ 1 2)
- 简化版本
'(xxx)'
(quote E)is a sample of special form : an exception to the general rule for evaluting functional forms- A few other special forms also have meanings that generally do not involve simply evaluating their operands:
(if (> x y) x y) ; like python A if X else B(and (integer?) (> x y) (< x z)) ; like python and(or (not (integer? x)) (< x L) (> x U)) ; Like Python ’or’(lambda (x y) (/ (* x x) y)) ; Like Python lambda , yields function(define pi 3.14159265359) ; Definition(define (f x) (* x x)) ; Function Definition(set! x 3) ; Assignment ("set bang")
- the fancy traditional Lisp conditional form:
cond- cond: chains a series of tests to select a result
- suport
else, but a cond-clause that starts with else must be the last cond-clause.
- suport
- cond: chains a series of tests to select a result
scm> (define x 5)
scm> (cond ((< x 1) ’small)
((< x 3) ’medium)
((< x 5) ’large)
(#t ’big))
big- which is the Lisp version of Python’s
"small" if x < 1 else "medium" if x < 3 else "large" if x < 5 else "big"- When evaluated as a program, a symbol acts like a variable name.
- Variables are bound in environments, just as in Python, although the syntax differs.
- To define a new symbol, either use it as a parameter name (later), or use the “define” special form:
- This (re)defines the symbols in the current environment.
(define pi 3.1415926)
(define pi**2 (* pi pi))- To assign a new value to an existing binding, use the set! special form:
(set! pi 3)- pi must be defined (not like Python).
- Function evaluation is just like Python
- To create a new function, we use the lambda special form:
scm> ( (lambda (x y) (+ (* x x) (* y y))) 3 4)
25
scm> (define fib
(lambda (n) (if (< n 2) n (+ (fib (- n 2)) (fib (- n 1))))))
scm> (fib 5)
5- 把一个lambda 赋给一个 symbol 太常见了，这么写略繁琐
scm> (define (fib n)
(if (< n 2) n (+ (fib (- n 2)) (fib (- n 1)))))scm> (/ 5 2)
2.5
scm> (quotient 5 2)
2
scm> (< 2 4 8) ; chain compare like python
#t
(integer? 5)
#t- Pairs (and therefore lists) have a basic constructor and accessors
- cons : constructor
- car : Contents of the Address part of Register number
- cdr : Contents of the Decrement part of Register number,
- cpr : Contents of the Prefix part of Register number
- ctr : Contents of the Tag part of Register number
- cadr :
- cadar : ...
- between the first letter ('c') and the last ('r'),
- a 'a' means "the car of" and a 'd' means "the cdr of".
- so
- cadr is "the car of the cdr",
- cddr is the cdr of the cdr,
- cadar is the "car of the cdr of the car" (thus the parameter has to be a list of list),
scm> (cons 1 2)
(1 . 2)
scm> (cons 'a (cons 'b '()))
(a b)
scm> (define L (a b c)) ; define won'e evaluate oprands
scm> (car L)
a
scm> (cdr L)
(b c)
(cadr L) ; (car (cdr L))
b
scm> (cdddr L) ; (cdr (cdr (cdr L)))
()- And one that is especially for lists:
scm> (list (+ 1 2) 'a 4)
(3 a 4)- we can use the quote form to construct a malformed list
scm> '(1 2 3)
(1 2 3)
scm> '(1 . (2 . (3)))
(1 2 3)
scm> '(1 . (2 . 3))
(1 2 . 3) ; malformed !scm> (null? nil)
True
scm> (append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
scm> (cons '(1 2 3) '(4 5 6))
((1 2 3) 4 5 6)
scm> (list '(1 2 3) '(4 5 6))
((1 2 3) (4 5 6))
scm> (length '(1 2 3 4 5))
5- Sometimes, you’d like to introduce local variables or named constants
- The let special form does this:
scm> (define x 17)
scm> (let ((x 5)
(y (+ x 2)))
(+ x y))
24- This is a derived form, equivalent to:
- 想象 let 是在给你定义参数
scm> ((lambda (x y) (+ x y)) 5 (+ x 2))- TODO, 为什么 最后加法x 的值是17 ？
- In Scheme, tail-recursive functions must work like iterations
(define (sum init L)
(if (null? L) init
(sum (+ init (car L)) (cdr L))))- tail recursions . From the reference manual:
- Implementations of Scheme must be properly tail-recursive.
- Procedure calls that occur in certain syntactic contexts called tail contexts are tail calls.
- Scheme implementation is properly tail-recursive if it supports an unbounded number of [simultaneously] active tail calls
- First, let’s define what that means
- Basically, an expression is in a tail context , if
- it is evaluated last in a function body (函数中最后一个求值
- and provides the value of a call to that function. (并为该函数提供了一个返回值))
- A function is tail-recursive if
- all function calls , in its body , that can result in a recursive call on that same function , are in tail contexts.
- In effect, Scheme turns recursive calls of such functions into iterations instead of simply returning
- by replacing those calls with one of the function’s tail-context expressions
- This decreases the memory , devoted to keeping track of which functions are running and who called them , to a constant.
- The “bases” are
- (lambda (ARGUMENTS) EXPR1 EXPR2 ... EXPRn)
- (define (NAME ARGMENTS) EXPR1 EXPR2 ... EXPRn)
- If an expression is in a tail context, then certain parts of it become tail contexts all by themselves
(define (prime? x)
"True iff X is prime."
)(define (prime? x)
"True iff X is prime."
(cond ((< x 2) #f)
((= x 2) #t)
(#t ?)) ; ? is undefined
)(define (prime? x)
"True iff X is prime."
(define (no-factor? k lim)
"LIM has no divisors >= K and < LIM."
)
(cond ((< x 2) #f)
((= x 2) #t)
(#t (no-factor? 2
(floor (+ (sqrt x) 2)))))
)(define (prime? x)
"True iff X is prime."
(define (no-factor? k lim)
"LIM has no divisors >= K and < LIM."
(cond ((>= k lim) #t)
((= (remainder x k) 0) #f)
(#t ?)))
(cond ((< x 2) #f)
((= x 2) #t)
(#t (no-factor? 2
(floor (+ (sqrt x) 2)))))
)(define (prime? x)
"True iff X is prime."
(define (no-factor? k lim)
"LIM has no divisors >= K and < LIM."
(cond ((>= k lim) #t)
((= (remainder x k) 0) #f)
(#t (no-factor? (+ k 1) lim))))
(cond ((< x 2) #f)
((= x 2) #t)
(#t (no-factor? 2
(floor (+ (sqrt x) 2)))))
)- On several occasions, we’ve computed the length of a linked list like this:
;; The length of list L
(define (length L)
(if (eqv? L '()) ; Alternative: (null? L)
0
(+ 1 (length (cdr L)))))-
but this is not tail recursive. How do we make it so?
-
Try a helper method:
;; The length of list L
(define (length L)
(define (length+ n R)
"The length of R plus N."
(if (null? R) n
(length+ (+ n 1) (cdr R))))
(length+ 0 L))- The functions
assq,assv, andassocclassically serve the purpose of Python dictionaries - An association list is a list of key/value pairs. The pyhton dictionary
{1:5, 3:6, 0:2}might be represented( (1 . 5) (3 . 6) (0 . 2) )
- The
assxfunctions access this list, returning the pair whose car matches a key argument. - The difference between the methods is that
assqcompares usingeq?(Pythonis).assvuseseqv?(which is like Python==on numbers and likeisotherwise).assocusesequal?(does “deep” comparison of lists).
;; The first item in L whose car is eqv? to key, or #f if none.
(define (assv key L)
(cond ((null? L) #f)
((eqv? key (caar L)) (car L))
(else (assv key (cdr L))))
);; Assumes f is a two-argument function and L is a list.
;; If L is (x1 x2...xn), the result of applying f n-1 times
;; to give (f (f (... (f x1 x2) x3) x4) ...).
;; If L is empty, returns f with no arguments.
;; [Simply Scheme version.]
;; >>> (reduce + ’(1 2 3 4)) ===> 10
;; >>> (reduce + ’()) ===> 0(define (reduce f L)
)(define (reduce f L)
(cond ((null? L) (f)) ; Odd case with no items
((null? (cdr L)) (car L)) ; One item
(else (reduce f (cons (f (car L) (cadr L)) (cddr L))))
)
)(define (reduce f L)
(define (reduce-tail accum R)
(cond ((null? R) accum)
(else (reduce-tail (f accum (car R)) (cdr R)))
)
)
(if (null? L) (f) ;; Special case
(reduce-tail (car L) (cdr L)))
)naive solution
(define (map2 f L)
(if (null? L) '()
(cons (f (car L)) (map2 f (cdr L)))))- NOT tail-recursive
- Need to pass along the partial results and add to them
- Problem:
consadds to the front of a list, so we end up with a reverse of what we want
(define (map2 f L)
;; The result of prepending the reverse of (map rest) to
;; the list partial-result
(define (map+ partial-result rest)
(if (null? rest) partial-result
(map+ (cons (f (car rest)) partial-result) (cdr rest))
))
(reverse2 (map+ '() L)))- What about reverse
- Actually, we can use the very problem that
conscreates to solve it! - That is, consing items from a list from left to right results in a reversed list:
(define (reverse2 L)
(define (reverse+ partial-result rest)
(if (null? rest) partial-result
(reverse+ (cons (car rest) partial-result) (cdr rest))
) )
(reverse+ '() L)
)- Consider the problem of shuffling together two lists, L1 and L2.
- The result consists of the first item of L1, then the first of L2, then the second of L1, etc.
- until one or the other list has no more values.
(define (shuffle L1 L2)
(define (shuffle+ reversed-result L1 L2)
(if ?))
(shuffle+ '() L1 L2))(define (shuffle L1 L2)
(define (shuffle+ reversed-result L1 L2)
(if (null? L1) (reverse reversed-result)
?))
(shuffle+ '() L1 L2))(define (shuffle L1 L2)
(define (shuffle+ reversed-result L1 L2)
(if (null? L1) (reverse reversed-result)
(shuffle+ (cons (car L1) reversed-result) L2 (cdr L1))
))
(shuffle+ '() L1 L2))