CS计算机代考程序代写 scheme python data structure interpreter 61a-final-study-guide.key

61a-final-study-guide.key

CS 61A Final Exam Study Guide – Page 1

Exceptions are raised with a raise statement.
raise

must evaluate to a subclass of BaseException or an instance of one.

try:
except as :

The is executed first.
If, during the course of executing the
, an exception is raised
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 , then
The is executed, with bound to the exception.

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 can be a combination or atom (primitive).
(+ (* 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