CS 61A Final Exam Fall 2020 Study Guide – Page 1
Exceptions are raised with a raise statement. raise
try:
The
If, during the course of executing the
If the class of the exception inherits from
The built-in Scheme list data structure can represent combinations
(define size 5) ; => size
(*2size);=> 10
(if(>size0)size(-size));=> 5
(cond ((> size 0) size) ((= size 0) 0) (else (- size))) ; => 5 ((lambda(xy)(+xysize))size(+12));=> 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)
scm> (list ‘quotient 10 2) (quotient 10 2)
scm> (eval (list ‘quotient 10 2)) 5
(list (and #f #t) (and) (and 1 2)) ; => (#f #t 2) (append'(12)'(34));=> (1234) (not(>12));=> #t (begin(definex(+size1))(*x2));=> 12 `(+size(-,size),(*34));=> (+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))
A table has columns and rows
A row has a value for each column
;; 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)))
There are two ways to quote an expression
Quote: ‘(a b) => (a b) Quasiquote: `(a b) => (a b)
They are different because parts of a quasiquoted expression can be unquoted with ,
(define b 4)
Quote: ‘(a ,(+ b 1)) => (a (unquote (+ b 1)) Quasiquote: `(a ,(+ b 1)) => (a 5)
Quasiquotation is particularly convenient for generating Scheme expressions:
(define (make-add-procedure n) `(lambda (d) (+ d ,n))) (make-add-procedure 2) => (lambda (d) (+ d 2))
; Sum the squares of even numbers less than 10, starting with 2 ;x=2
A column has a name and a type
Latitude Longitude Name
38
122
Berkeley
42
71
Cambridge
45
93
Minneapolis
; total
; while
; total = total + x
; x=x+1
; RESULT: 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
(begin
(define (f x total)
(if (< (* x x) 50)
(f (+ x 1) (+ total x)) total))
(f 1 0))
(define (sum-while starting-x while-condition add-to-total update-x)
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;
= 0
x * x < 50:
>>> try:
x = 1/0
except ZeroDivisionError as e: print(‘handling a’, type(e)) x=0
handling a
0
SELECT [expression] AS [name], [expression] AS [name], … ;
SELECT [columns] FROM [table] WHERE [condition] ORDER BY [order];
CREATE TABLE parents AS
SELECT “abraham” AS parent, “barack” AS child
UNION
UNION E UNION
UNION
UNION
UNION F
; ; ; ; ;
total while
= total + x=x+2
RESULT: 2 * 2 + 4 *
SELECT “abraham” SELECT “delano” SELECT “fillmore” SELECT “fillmore” SELECT “fillmore” SELECT “eisenhower”
, “clinton” , “herbert” , “abraham” , “delano”
, “grover”
, “fillmore”;
= 0
x < total
10:
(begin
(define (f x total)
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 BCH
x*x
4 + 6 * 6 + 8 * 8 = 120
CREATE TABLE dogs AS
SELECT "abraham" AS name, "long" AS fur
(if (< x 10)
(f (+ x 2) (+ total (* x x))) total))
(f 2 0))
; Sum the numbers whose squares are less than 50, starting with 1 ;x=1
First
Second
barack
clinton
abraham
delano
abraham
grover
delano
grover
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
kind legs
weight
dog
4
20
cat
4
10
ferret
4
10
parrot
2
6
penguin
2
10
t-rex
2
12000
weight/ count(*) legs
5
2
2
2
; (eval (sum-while 2 ;(eval(sum-while1 `(begin
(define (f x total) (if ,while-condition
'(< x 10) '(* x x) '(<(*xx)50)'x
'(+ x 2))) => 120 ‘(+x1))) => 28
having count(*)>1; weight/legs=5
weight/legs=2 weight/legs=2 weight/legs=3 weight/legs=5 weight/legs=6000
(f ,update-x (+ total ,add-to-total))
total))
(f ,starting-x 0)))
Optional content removed
CS 61A Final Exam Fall 2020 Study Guide – Page 2
scheme_reader.py scalc.py
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 (
> (define pi 3.14) > (* pi 2)
6.28
> (define (abs x) (if (< x 0)
(- x)
x)) > (abs -3)
3
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
(+ (* 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.
6 6
> (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
Expression Trees
A basic interpreter has two parts: a parser and an evaluator A basic interpreter has two parts: a parser and an evaluator
A basic interpreter has two parts: a parser and an evaluator.
A Parser takes a sequence of lines and returns an expression.
Lines
‘(+ 1’
‘ (- 23)’
‘ (*45.6))’
Tokens
‘(‘, ‘+’, 1
‘(‘, ‘-‘, 23, ‘)’ ‘(‘,’*’,4,5.6,’)’,’)’
Expression
Pair(‘+’, Pair(1, …))
printed as
(+1(-23)(*45.6))
• 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.
> (car ‘(a b c)) a
> (cdr ‘(a b c)) (b c)
(car (cons 1 nil)) -> 1
(cdr (cons 1 nil)) -> ()
(cdr (cons 1 (cons 2 nil))) -> (2)
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
>>> s = Pair(1, Pair(2, Pair(3, nil))) >>> s
Pair(1, Pair(2, Pair(3, nil)))
>>> print(s)
(1 2 3)
Base cases:
• Primitive values (numbers)
• Look up values bound to symbols
Eval The structure of the Scheme
> (list ‘a ‘b) (a b)
> (list ‘a b) (a 2)
interpreter
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
Creates a new environment each time a user- defined procedure is applied
Apply
Requires an environment for name lookup
Base cases:
• Built-in primitive procedures
Recursive calls:
• Eval(body) of user-defined procedures
first rest
1
first rest
2
first rest
3 nil
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))
LambdaProcedure instance [parent=g]
Pair Pair
1 2 nil
1) Identify the information that must be represented and how it is
2) State what kind of data the desired function consumes and produces.
5) Fill in the gaps in the function template. Exploit the purpose
6) Convert examples into tests and ensure that the function passes them.
The Calculator language has primitive expressions and call expressions
Calculator Expression Expression Tree
(* 3
(+ 4 5)
(*678)) *3 +45*678
Representation as Pairs
first rest first rest first rest first rest
*3 nil
first rest
*
first rest first rest
+ 4
first rest
6
first rest
5 nil
first rest
7
first rest
8 nil
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
scheme_reader.py
scalc.py
Parser Parser
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
Lexical analysis
g: Global frame f
[parent=g] s
[parent=g] s
[parent=g] s
How to Design Functions:
represented. Illustrate with examples.
Formulate a concise answer to the question what the function computes.
Syntactic analysis
3) Work through examples that illustrate the function’s purpose.
4) Outline the function as a template.
statement and the examples.