CS计算机代考程序代写 61a-mt1-study-guide.key

61a-mt1-study-guide.key

CS 61A Midterm 1 Study Guide – Page 1

208
mul(add(2, mul(4, 6)), add(3, 5))

add(2, mul(4, 6))
26mul

add 2
mul(4, 6)

mul 4 6

24

add(3, 5)

add 3 5

8

-2
2

-2
None

abs(number):

print(…):

display “-2”

2, 10
1024

pow(x, y):

Pure Functions

Non-Pure Functions

A name evaluates to
the value bound to
that name in the
earliest frame of
the current
environment in which
that name is found.

Defining:

Call expression:

square( x ):

return mul(x, x)

>>> def

square(2+2)

Calling/Applying: square( x ):

return mul(x, x)

Def
statement

Formal parameter

Body

Return
expression

(return statement)

operand: 2+2
argument: 4

operator: square
function: func square(x)

Intrinsic name

4

16
Argument

Return value

:



:


…


Compound statement

Suite

Clause

Each clause is considered in order.
1.Evaluate the header’s expression.
2.If it is a true value, execute the suite, then skip the
remaining clauses in the statement.

1. Evaluate the header’s expression.
2. If it is a true value, execute the (whole) suite, then
return to step 1.

Execution rule for while statements:

Execution rule for def statements:

Execution rule for assignment statements:

Evaluation rule for call expressions:

Execution rule for conditional statements: hof.py Page 2

return total

def identity(k):
return k

def cube(k):
return pow(k, 3)

def summation(n, term):
“””Sum the first n terms of a sequence.

>>> summation(5, cube)
225
“””
total, k = 0, 1
while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 � 3) / (k * 4 � 1) # Local function definitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3)
>>> add_three(4)
7
“””
def adder(k):
return k + n
return adder

def compose1(f, g):
“””Return a function that composes f and g.

f, g �� functions of a single argument
“””
def h(x):
return f(g(x))
return h

@main
def run():
interact()

Function of a single
argument (not called term)

A formal parameter that
will be bound to a function

The function bound to term
gets called here

The cube function is passed
as an argument value

0 + 13 + 23 + 33 + 43 + 55

Higher-order function: A function that takes a function as an
argument value or returns a function as a return value

Nested def statements: Functions defined within other
function bodies are bound to names in the local frame

Evaluation rule for or expressions:

Evaluation rule for and expressions:

Evaluation rule for not expressions:

Applying user-defined functions:

1.Evaluate the operator and operand subexpressions.
2.Apply the function that is the value of the operator
subexpression to the arguments that are the values of the
operand subexpressions.

1.Create a new local frame with the same parent as the
function that was applied.

2.Bind the arguments to the function’s formal parameter
names in that frame.

3.Execute the body of the function in the environment
beginning at that frame.

1.Create a new function value with the specified name,
formal parameters, and function body.

2.Its parent is the first frame of the current environment.
3.Bind the name of the function to the function value in the
first frame of the current environment.

1.Evaluate the expression(s) on the right of the equal sign.
2.Simultaneously bind the names on the left to those values,
in the first frame of the current environment.

1.Evaluate the subexpression .
2.If the result is a false value v, then the expression
evaluates to v.

3.Otherwise, the expression evaluates to the value of the
subexpression .

1.Evaluate ; The value is True if the result is a false
value, and False otherwise.

A name is bound to a value

In a frame, there is at most
one binding per name

Statements and expressions
Red arrow points to next line.

Gray arrow points to the line
just executed

Frames (right):Code (left):

Import statement

Assignment statement

Name Value

Binding

Local frame

Intrinsic name of
function called

Formal parameter
bound to
argument

Return value is

not a binding!

Built-in function

User-defined
function

2

1

“y” is
not found

“y” is
not found

Error

def abs_value(x):

if x > 0:
return x
elif x == 0:
return 0
else:
return -x

1 statement,
3 clauses,

3 headers,
3 suites,
2 boolean

contexts

•An environment is a
sequence of frames

•An environment for a
non-nested function
(no def within def)
consists of one local
frame, followed by the
global frame

2

1

1

2

1

B
A B

A

A call expression and the body
of the function being called
are evaluated in different
environments

1.Evaluate the subexpression .
2.If the result is a true value v, then the expression
evaluates to v.

3.Otherwise, the expression evaluates to the value of the
subexpression .

def fib(n):
“””Compute the nth Fibonacci number, for N >= 1.”””
pred, curr = 0, 1 # Zeroth and first Fibonacci numbers
k = 1 # curr is the kth Fibonacci number
while k < n: pred, curr = curr, pred + curr k = k + 1 return curr def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3)
>>> add_three(4)
7
“””
def adder(k):
return k + n
return adder

CS 61A Midterm 1 Study Guide – Page 2

A function that returns a function

A local
def statement

The name add_three is
bound to a function

Can refer to names in
the enclosing function

square = lambda x,y: x * y

that returns the value of “x * y”
with formal parameters x and y

A function

Must be a single expression

square = lambda x: x * x def square(x): return x * xVS
• Both create a function with the same domain, range, and behavior.

• Both functions have as their parent the environment in which they
were defined.

• Both bind that function to the name square.

• Only the def statement gives the function an intrinsic name.

•Every user-defined function has
a parent frame (often global)

•The parent of a function is the
frame in which it was defined

•Every local frame has a parent
frame (often global)

•The parent of a frame is the
parent of the function called

Evaluates to a function.

No “return” keyword!

When a function is defined:
1. Create a function value: func ()
2. Its parent is the current frame.



3. Bind to the function value in the current frame

(which is the first frame of the current environment).

When a function is called:
1. Add a local frame, titled with the of the function being

called.
2. Copy the parent of the function to the local frame: [parent=

the local frame.

2

1

3

Nested
def

A function’s signature
has all the information
to create a local frame

Return value of make_adder is an
argument to compose1

from operator import floordiv, mod
def divide_exact(n, d):
“””Return the quotient and remainder of dividing N by D.

>>> q, r = divide_exact(2012, 10)
>>> q
201
>>> r
2
“””
return floordiv(n, d), mod(n, d)

Two return values,
separated by commas

Multiple assignment

to two names

>>> min(2, 1, 4, 3)
1
>>> max(2, 1, 4, 3)
4
>>> abs(-2)
2
>>> pow(2, 3)
8
>>> len(‘word’)
4
>>> round(1.75)
2
>>> print(1, 2)
1 2

>>> 2 + 3
5
>>> 2 * 3
6
>>> 2 ** 3
8
>>> 5 / 3
1.6666666666666667
>>> 5 // 3
1
>>> 5 % 3
2
>>> print(print(1))
1
None

def search(f):
“””Return the smallest non-negative
integer x for which f(x) is a true value.
“””
x = 0
while True:
if f(x):
return x
x += 1

def is_three(x):
“””Return whether x is three.

>>> search(is_three)
3
“””
return x == 3

def inverse(f):
“””Return a function g(y) that returns
x such that f(x) == y.

>>> sqrt = inverse(lambda x: x * x)
>>> sqrt(16)
4
“””
return lambda y: search(lambda x: f(x)==y)

Printed output:
1
4
9

from operator import add, mul

def curry2(f):
“””Curry a two-argument function.

>>> m = curry2(add)
>>> add_three = m(3)
>>> add_three(4)
7
>>> m(2)(1)
3
“””
def g(x):
def h(y):
return f(x, y)
return h
return g