CS 61A Final Exam Study Guide – Page 1
Exceptions are raised with a raise statement. raise
(define size 5) ; => size
(*2size);=> 10
(if (> size 0) size (- size)) ; => 5
(cond ((> size 0) size) ((= size 0) 0) (else (- size))) ; => 5 ((lambda (x y) (+ x y size)) size (+ 1 2)) ; => 13 (let((asize)(b(+12)))(*2ab));=> 30
(map (lambda (x) (+ x size)) (quote (2 3 4))) ; => (7 8 9)
(filter odd? (quote (2 3 4))) ; => (3)
(list (cons 1 nil) size ‘size) ; => ((1) 5 size) (list(equal?12)(null?nil)(=34)(eq?55));=> (#f#t#f#t) (list(or#f#t)(or)(or12));=> (#t#f1)
(list (and #f #t) (and) (and 1 2)) ; => (#f #t 2) (append'(12)'(34));=> (1234)
(not(>12));=> #t
(begin (define x (+ size 1)) (* x 2)) ; => 12 `(+size(-,size),(*34));=> (+size(-5)12)
try:
except
The
If, during the course of executing the
If the class of the exception inherits from
>>> try:
x = 1/0
except ZeroDivisionError as e: print(‘handling a’, type(e)) x=0
handling a
>>> x 0
(cdr (cons 1 nil)) -> ()
(cons 1 (cons (/ 1 0) nil)) -> ERROR
(car (cons-stream 1 nil)) -> 1 (cdr-stream (cons-stream 1 nil)) -> () (car
(cons-stream 1 (cons-stream (/ 1 0) nil))) -> 1 (cdr-stream
(cons-stream 1 (cons-stream (/ 1 0) nil))) -> ERROR
car
Stored explicitly
1 1… +
2 3…
f s)
cdr-stream
Evaluated lazily
;; Return a copy of s reversed.
(define (reverse s) (define (iter s r)
(if (null? s) r (iter (cdr s)
(cons (car s) r)))) (iter s nil))
A table has columns and rows
A row has a value for each column
SELECT [expression] AS [name], [expression] AS [name], … ;
SELECT [columns] FROM [table] WHERE [condition] ORDER BY [order];
A stream is a Scheme pair, but the cdr is evaluated lazily
;; Apply fn to each element of s.
(define (map fn s)
(define (map-reverse s m)
(if (null? s) m (map-reverse
(cdr s)
(cons (fn (car s)) m)))) (reverse (map-reverse s nil)))
(define (range-stream a b) (if (>= a b)
nil
(cons-stream a (range-stream (+ a 1) b)))) (define lots (range-stream 1 10000000000000000000)) scm> (car lots)
1
scm> (car (cdr-stream lots))
2
scm> (car (cdr-stream (cdr-stream lots)))
3
(define ones (cons-stream 1 ones))
(define (add-streams s t) (cons-stream (+ (car s) (car t))
(add-streams (cdr-stream s) (cdr-stream t))))
(define ints (cons-stream 1 (add-streams ones ints)))
A column has a name and a type
Latitude
Longitude
Name
38
122
Berkeley
42
71
Cambridge
45
93
Minneapolis
1 +
1
CREATE TABLE parents AS
SELECT “abraham” AS parent, “barack” AS child
UNION
UNION E UNION
UNION
UNION
UNION F
(define (map-stream f s) (if (null? s)
nil
(cons-stream (f (car s))
(map-stream f (cdr-stream s)))))
(define (filter-stream (if (null? s)
nil
(if (f (car s))
SELECT “abraham” SELECT “delano” SELECT “fillmore” SELECT “fillmore” SELECT “fillmore” SELECT “eisenhower”
, “clinton” , “herbert” , “abraham” , “delano”
, “grover”
, “fillmore”;
(car s) (filter-stream f (cdr-stream s)))))
(cons-stream
(filter-stream f (cdr-stream s)))
CREATE TABLE dogs AS
SELECT “abraham” AS name, “long” AS fur
SELECT “barack” SELECT “clinton” SELECT “delano” SELECT “eisenhower” SELECT “fillmore” SELECT “grover” SELECT “herbert”
, “short” , “long” , “long” , “short” , “curly” , “short” , “curly”;
UNION UNION UNION UNION UNION UNION UNION
ADG
The built-in Scheme list data structure can represent combinations scm> (list ‘quotient 10 2) scm> (eval (list ‘quotient 10 2))
(quotient 10 2) 5
A macro is an operation performed on source code before evaluation
B
C
H
First
Second
barack
clinton
abraham
delano
abraham
grover
delano
grover
(define-macro (twice expr) (list ‘begin expr expr))
> (twice (print 2))
2
2 (begin (print 2) (print 2))
SELECT a.child AS first, b.child AS second
FROM parents AS a, parents AS b
WHERE a.parent = b.parent AND a.child < b.child;
Evaluation procedure of a macro call expression:
• Evaluate the operator sub-expression, which evaluates to a macro • Call the macro procedure on the operand expressions
• Evaluate the expression returned from the macro procedure
scm> (map (lambda (x) (* x x)) ‘(2 3)) scm> (for x ‘(2 3) (* x x)) (4 9) (4 9)
(define-macro (for sym vals expr) OR (define-macro (for sym vals expr)
The number of groups is the number of unique values of an expression A having clause filters the set of groups that are aggregated
select weight/legs, count(*) from animals
group by weight/legs
having count(*)>1; weight/legs=5
weight/legs=2 weight/legs=2 weight/legs=3 weight/legs=5 weight/legs=6000
CREATE TABLE ints(n UNIQUE, prime DEFAULT 1); INSERT INTO ints VALUES (2, 1), (3, 1);
INSERT INTO ints(n) VALUES (4), (5), (6), (7), (8); UPDATE ints SET prime=0 WHERE n > 2 AND n % 2 = 0; DELETE FROM ints WHERE prime=0;
The way in which names are looked up in Scheme and Python is called lexical scope (or static scope).
Lexical scope: The parent of a frame is the environment in which a procedure was defined. (lambda …)
Dynamic scope: The parent of a frame is the environment in which a procedure was called. (mu …)
> (define f (mu (x) (+ x y)))
> (define g (lambda (x y) (f (+ x x)))) > (g 3 7)
13
kind
legs
weight
dog
4
20
cat
4
10
ferret
4
10
parrot
2
6
penguin
2
10
t-rex
2
12000
(list ‘map (list ‘lambda (list sym)
expr) vals))
`(map (lambda (,sym) ,expr) ,vals))
weight/ legs
count(*)
5
2
2
2
A procedure call that has not yet returned is active. Some procedure calls are tail calls. A Scheme interpreter should support an unbounded number of active tail calls.
A tail call is a call expression in a tail context, which are:
• The last body expression in a lambda expression
• Expressions 2 & 3 (consequent & alternative) in a tail context if • All non-predicate sub-expressions in a tail context cond
• The last sub-expression in a tail context and, or, begin, or let
n
prime
2
1
3
1
5
1
7
1
(define (factorial n k) (if (= n 0) k
(factorial (- n 1)
(* k n))))
(define (length-tail s) (define (length-iter s n)
(define (length s) (if (null? s) 0
(+ 1 (length (cdr s))))) Not a tail call
Recursive call is a tail call
(if (null? s) n
(length-iter (cdr s) (+ 1 n)) ) )
(length-iter s 0) )
Expression Trees
CS 61A Final Exam Study Guide – Page 2
Scheme programs consist of expressions, which can be:
• Primitive expressions: 2, 3.3, true, +, quotient, … • Combinations: (quotient 10 2), (not true), …
Numbers are self-evaluating; symbols are bound to values. Call expressions have an operator and 0 or more operands.
A combination that is not a call expression is a special form: • If expression: (if
• New procedures: (define (
A basic interpreter has two parts: a parser and an evaluator
A basic interpreter has two parts: a parser and an evaluator scheme_reader.py scalc.py
> (define a 1) > (define b 2) > (list a b) (1 2)
No sign of “a” and “b” in the resulting value
Syntactic analysis identifies the hierarchical structure of an expression, which may be nested.
Each call to scheme_read consumes the input tokens for exactly one expression.
Base case: symbols and numbers
Recursive call: scheme_read sub-expressions and combine them
A basic interpreter has two parts: a parser and an evaluator.
> (define pi 3.14) > (* pi 2)
6.28
> (define (abs x) (if (< x 0)
(- x)
x)) > (abs -3)
3
lines lines
‘(+ 2 2)’ ‘(+ 2 2)’
‘(* (+ 1′
”(* (+(1-’23)’
” ((*- 4235).’6))’ ” 10)'(* 4 5.6))’
‘ 10)’
expression expression
Pair(‘+’, Pair(2, Pair(2, nil))) Pair(‘+’, Pair(2, Pair(2, nil)))
Pair(‘*’, Pair(Pair(‘+’, …))) Pair(‘*’, Ppariirn(tPeadiars(‘+’, …))) (* (+ 1 (p-ri2nt3e)d (as* 4 5.6)) 10)
(* (+ 1 (- 23) (* 4 5.6)) 10)
value value
4 4
4 4
Evaluator Evaluator
Lines forming
A number or a Pair with an
operator as its first element A number or a Pair with an
operator as its first element
A number A number
a Scheme Lines forming
eaxpSrcehsesmieon
scheme_reader.py
scalc.py
Parser Parser
Lambda expressions evaluate to anonymous procedures. (lambda (
Two equivalent expressions:
(define (plus4 x) (+ x 4))
(define plus4 (lambda (x) (+ x 4)))
An operator can be a combination too:
((lambda (x y z) (+ x y (square z))) 1 2 3)
In the late 1950s, computer scientists used confusing names. • cons: Two-argument procedure that creates a pair
• car: Procedure that returns the first element of a pair • cdr: Procedure that returns the second element of a pair • nil: The empty list
They also used a non-obvious notation for linked lists.
• A (linked) Scheme list is a pair in which the second element is
nil or a Scheme list.
• Scheme lists are written as space-separated combinations.
• A dotted list has an arbitrary value for the second element of the
last pair. Dotted lists may not be well-formed lists.
> (define x (cons 1 nil)) >x
(1)
> (car x)
1
> (cdr x)
()
> (cons 1 (cons 2 (cons 3 (cons 4 nil)))) (1 2 3 4)
Symbols normally refer to values; how do we refer to symbols?
expression
A Scheme list is written as elements in parentheses:
(
Each
The task of parsing a language involves coercing a string representation of an expression to the expression itself. Parsers must validate that expressions are well-formed.
6 6
A Parser takes a sequence of lines and returns an expression.
Lines
‘(+ 1’
‘ (- 23)’
‘ (* 4 5.6))’
Tokens
‘(‘, ‘+’, 1
‘(‘, ‘-‘, 23, ‘)’
‘(‘, ‘*’, 4, 5.6, ‘)’, ‘)’
Expression
Pair(‘+’, Pair(1, …))
printed as
(+ 1 (- 23) (* 4 5.6))
Lexical analysis
Syntactic analysis
• Iterative process
• Checks for malformed tokens • Determines types of tokens • Processes one line at a time
• Tree-recursive process • Balances parentheses
• Returns tree structure • Processes multiple lines
Quotation is used to refer to symbols directly in Lisp.
Base cases:
• Primitive values (numbers)
• Look up values bound to symbols
Eval
The structure of the Scheme interpreter
Creates a new environment each time a user- defined procedure is applied
Apply
> (list ‘a ‘b) (a b)
> (list ‘a b) (a 2)
Symbols are now values
Quotation can also be applied to combinations to form lists.
Recursive calls:
• Eval(operator, operands) of call expressions • Apply(procedure, arguments)
• Eval(sub-expressions) of special forms
> (car ‘(a b c)) a
> (cdr ‘(a b c)) (b c)
class Pair:
“””A pair has two instance attributes:
first and rest.
rest must be a Pair or nil. “””
Requires an environment for name lookup
Base cases:
• Built-in primitive procedures
Recursive calls:
def
__init__(self, first, rest): self.first = first
self.rest = rest
To apply a user-defined procedure, create a new frame in which formal parameters are bound to argument values, whose parent is the env of the procedure, then evaluate the body of the procedure in the environment that starts with this new frame.
(define (f s) (if (null? s) ‘(3) (cons (car s) (f (cdr s))))) (f (list 1 2))
>>> s =
>>> s Pair(1,
>>> print(s) (1 2 3)
Pair(1, Pair(2, Pair(3, nil))) Pair(2, Pair(3, nil)))
• Eval(body) of user-defined procedures
first
1
rest
first
2
rest
first
3
rest
nil
g: Global frame f
[parent=g] s [parent=g] s [parent=g] s
The Calculator language has primitive expressions and call expressions
Calculator Expression Expression Tree
(* 3
(+ 4 5)
(*678)) *3
+ 4 5 * 6 7 8
Representation as Pairs
LambdaProcedure instance [parent=g]
Pair Pair
1 2 nil
How to Design Functions:
1) Identify the information that must be represented and how it is
represented. Illustrate with examples.
2) State what kind of data the desired function consumes and produces.
5) Fill in the gaps in the function template. Exploit the purpose
statement and the examples.
6) Convert examples into tests and ensure that the function passes them.
Formulate a concise answer to the question what the function computes.
first
first
*
rest
3
rest
first
rest
first
rest
nil
3) Work through examples that illustrate the function’s purpose.
4) Outline the function as a template.
first
*
rest
first
6
rest
first
7
rest
first
8
rest
nil
first
+
rest
first
4
rest
first
5
rest
nil