61a-final-study-guide.key
CS 61A Final Exam Study Guide – Page 1
Exceptions are raised with a raise statement.
raise
try:
The
If, during the course of executing the
that is not handled otherwise, and
car cdr-stream
Stored
explicitly
Evaluated
lazily
>>> try:
x = 1/0
except ZeroDivisionError as e:
print(‘handling a’, type(e))
x = 0
handling a
>>> x
0
A stream is a Scheme pair, but
the cdr is evaluated lazily
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
SELECT “abraham” AS parent, “barack” AS child UNION
SELECT “abraham” , “clinton” UNION
SELECT “delano” , “herbert” UNION
SELECT “fillmore” , “abraham” UNION
SELECT “fillmore” , “delano” UNION
SELECT “fillmore” , “grover” UNION
SELECT “eisenhower” , “fillmore”;
CREATE TABLE parents AS
SELECT [expression] AS [name], [expression] AS [name], … ;
CREATE TABLE dogs AS
SELECT “abraham” AS name, “long” AS fur UNION
SELECT “barack” , “short” UNION
SELECT “clinton” , “long” UNION
SELECT “delano” , “long” UNION
SELECT “eisenhower” , “short” UNION
SELECT “fillmore” , “curly” UNION
SELECT “grover” , “short” UNION
SELECT “herbert” , “curly”;
E
F
A D G
B C H
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;
First Second
barack clinton
abraham delano
abraham grover
delano grover
Latitude Longitude Name
38 122 Berkeley
42 71 Cambridge
45 93 Minneapolis
A table has columns and rows
A column
has a
name and
a type
A row has a value for each column
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;
kind legs weight
dog 4 20
cat 4 10
ferret 4 10
parrot 2 6
penguin 2 10
t-rex 2 12000
weight/
legs
count(*)
5 2
2 2
weight/legs=5
weight/legs=2
weight/legs=2
weight/legs=3
weight/legs=5
weight/legs=6000
(car (cons 1 nil)) -> 1
(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
(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)) 1 1 1 …
(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))) 2 3 …1
+ +
(define (map-stream f s)
(if (null? s)
nil
(cons-stream (f (car s))
(map-stream f
(cdr-stream s)))))
(define (filter-stream f s)
(if (null? s)
nil
(if (f (car s))
(cons-stream (car s)
(filter-stream f (cdr-stream s)))
(filter-stream f (cdr-stream s)))))
If the class of the exception inherits from
The
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;
SELECT [columns] FROM [table] WHERE [condition] ORDER BY [order];
n prime
2 1
3 1
5 1
7 1
scm> (list ‘quotient 10 2)
(quotient 10 2)
The built-in Scheme list data structure can represent combinations
scm> (eval (list ‘quotient 10 2))
5
(define-macro (twice expr)
(list ‘begin expr expr))
> (twice (print 2))
2
2
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
(begin (print 2) (print 2))
A macro is an operation performed on source code before evaluation
scm> (map (lambda (x) (* x x)) ‘(2 3))
(4 9)
scm> (for x ‘(2 3) (* x x))
(4 9)
(define-macro (for sym vals expr)
(list ‘map (list ‘lambda
(list sym)
expr) vals))
(define-macro (for sym vals expr)
`(map (lambda (,sym) ,expr) ,vals))
OR
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
(define (factorial n k)
(if (= n 0) k
(factorial (- n 1)
(* k n))))
(define (length s)
(if (null? s) 0
(+ 1 (length (cdr s)))))
(define (length-tail s)
(define (length-iter s n)
(if (null? s) n
(length-iter (cdr s) (+ 1 n)) ) )
(length-iter s 0) )
Recursive call is a tail call
Not a tail call
(define size 5) ; => size
(* 2 size) ; => 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 ((a size) (b (+ 1 2))) (* 2 a b)) ; => 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? 1 2) (null? nil) (= 3 4) (eq? 5 5)) ; => (#f #t #f #t)
(list (or #f #t) (or) (or 1 2)) ; => (#t #f 1)
(list (and #f #t) (and) (and 1 2)) ; => (#f #t 2)
(append ‘(1 2) ‘(3 4)) ; => (1 2 3 4)
(not (> 1 2)) ; => #t
(begin (define x (+ size 1)) (* x 2)) ; => 12
`(+ size (- ,size) ,(* 3 4)) ; => (+ size (- 5) 12)
;; 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))
;; 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)))
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
• Binding names: (define
• New procedures: (define (
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)
> (define pi 3.14)
> (* pi 2)
6.28
> (define (abs x)
(if (< x 0)
(- x)
x))
> (abs -3)
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?
> (define a 1)
> (define b 2)
> (list a b)
(1 2)
Quotation is used to refer to symbols directly in Lisp.
No sign of “a” and “b” in
the resulting value
> (list ‘a ‘b)
(a b)
> (list ‘a b)
(a 2)
Quotation can also be applied to combinations to form lists.
> (car ‘(a b c))
a
> (cdr ‘(a b c))
(b c)
Symbols are now values
Expression Trees
A basic interpreter has two parts: a parser and an evaluator
6
lines Parser expression Evaluator value
‘(+ 2 2)’ Pair(‘+’, Pair(2, Pair(2, nil))) 4
4
Pair(‘*’, Pair(Pair(‘+’, …)))
(* (+ 1 (- 23) (* 4 5.6)) 10)
printed as
‘(* (+ 1’
‘ (- 23)’
‘ (* 4 5.6))’
‘ 10)’
Lines forming
a Scheme
expression
A number or a Pair with an
operator as its first element
A number
scheme_reader.py scalc.py
Expression Trees
A basic interpreter has two parts: a parser and an evaluator
6
lines Parser expression Evaluator value
‘(+ 2 2)’ Pair(‘+’, Pair(2, Pair(2, nil))) 4
4
Pair(‘*’, Pair(Pair(‘+’, …)))
(* (+ 1 (- 23) (* 4 5.6)) 10)
printed as
‘(* (+ 1’
‘ (- 23)’
‘ (* 4 5.6))’
‘ 10)’
Lines forming
a Scheme
expression
A number or a Pair with an
operator as its first element
A number
scheme_reader.py scalc.py
A Scheme list is written as elements in parentheses:
(
Each
(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
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.
A Scheme list
‘(+ 1’
‘ (- 23)’
‘ (* 4 5.6))’
Lines Expression
A Parser takes a sequence of lines and returns an expression.
Lexical
analysis Tokens
Syntactic
analysis
‘(‘, ‘+’, 1
‘(‘, ‘-‘, 23, ‘)’
‘(‘, ‘*’, 4, 5.6, ‘)’, ‘)’
Pair(‘+’, Pair(1, …))
(+ 1 (- 23) (* 4 5.6))
printed as
• 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
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
Apply
Eval
Recursive calls:
• Eval(operator, operands) of call expressions
• Apply(procedure, arguments)
• Eval(sub-expressions) of special forms
Base cases:
• Primitive values (numbers)
• Look up values bound to symbols
Base cases:
• Built-in primitive procedures
Recursive calls:
• Eval(body) of user-defined procedures
Requires an
environment
for name
lookup
The structure
of the Scheme
interpreter
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))
1
Pair
2
Pair
nil[parent=g] s
[parent=g] s
[parent=g] s
g: Global frame
f LambdaProcedure instance [parent=g]
CS 61A Final Exam Study Guide – Page 2
Creates a new
environment each
time a user-
defined procedure
is applied
A basic interpreter has two parts: a parser and an evaluator.
>>> s = Pair(1, Pair(2, Pair(3, nil)))
>>> s
Pair(1, Pair(2, Pair(3, nil)))
>>> print(s)
(1 2 3)
class Pair:
“””A pair has two instance attributes:
first and rest.
rest must be a Pair or nil.
“””
def __init__(self, first, rest):
self.first = first
self.rest = rest
(* 3
(+ 4 5)
(* 6 7 8))
Calculator Expression Expression Tree
restfirst
*
restfirst
3
restfirst restfirst
nil
restfirst
+
restfirst
4
restfirst
5 nil
restfirst
*
restfirst
6
restfirst
7
restfirst
8 nil
Representation as Pairs
The Calculator language has primitive expressions and call expressions
* 3
+ 4 5 * 6 87
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.
Formulate a concise answer to the question what the function computes.
3) Work through examples that illustrate the function’s purpose.
4) Outline the function as a template.
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.
restfirst
1
restfirst
2
restfirst
3 nil