1

Week5
Decomposition, Abstraction and
Functions

Reading:
▪ Chapter 4 of Guttag’s Book
2
Programming Exercise
• Write a script that finds the first 100 positive even integers, computes and
displays their sum.

3
Programming Exercise
• You have three identical prizes to give away and a pool of 30 finalists.
• The finalists are assigned numbers from 1 to 30.
• Write a program to randomly select the numbers of three finalists to
receive a prize.
• Make sure not to pick the same number twice.
• For example, picking finalists 3, 15, 29 would be valid but picking 3, 3, 31
would be invalid because finalist number 3 is listed twice and 31 is not a
valid finalist number.

4
Programming Exercise
• Write a script that displays the following triangle pattern
• Use for loops to generate the patterns. Display all asterisks (*) with a
single statement of the form print('*', end=‘’) which causes the
asterisks to display side by side.

5
Programming Exercise
• Write a script that displays the following triangle pattern
• Use for loops to generate the patterns. Display all asterisks (*) with a
single statement of the form print('*', end=‘’) which causes the
asterisks to display side by side.

6
Homework
• Write a script that displays the following triangle pattern
• Use for loops to generate the patterns. Display all asterisks (*) with a
single statement of the form print('*', end=‘’) which causes the
asterisks to display side by side.

7
How Do We Write Code?
• So far:

• covered language mechanisms (e.g., numbers, assignments,

input/output, comparisons, and looping constructs)

• know how to write different files for each computation

• each file is some piece of code

• each code is a sequence of instructions

8
Find Approximation to Square Root of x
if x < 0:
print('Does not exist')
else:
low = 0
high = max(1, x)
ans = (high + low)/2
while abs(ans**2 - x) >= epsilon:
if ans**2 < x:
low = ans
else:
high = ans
ans = (high + low)/2
print(ans, 'is close to square root of', x)
9
How Do We Write Code?
• Code lacks general utility:

• Want to reuse it? → Need to copy the code, possibly edit the variable
names, and paste it where we want it

• Cannot easily use this computation inside of some other, more complex,
computation

• Want to compute cube roots rather than square roots? → Have to edit the
code

10
Summing a Square Root and a Cube root
• Show code in Spyder

• The more code a program contains, the more chance something can go
wrong, and the harder the code is to maintain.

11
How Do We Write Code?
• Problems with this approach:

• Easy for small-scale problems

• Messy for larger problems

• Hard to keep track of details

• How do you know the right info is supplied to the right part of code

12
Good Programming
• More code not necessarily a good thing

• Measure good programmers by the amount of functionality

• Introduce functions

• Mechanism to achieve decomposition and abstraction

13
Example – Projector
• A projector is a black box
• don’t know how it works
• know the interface: input/output
• connect any electronic to it that can communicate with that input
• black box somehow converts image from input source to a wall,
magnifying it

• ABSTRACTION IDEA: do not need to know how projector works to use it

14
Example – Projector
• projecting large image for Olympics decomposed into separate tasks for
separate projectors

• each projector takes input and produces separate output

• all projectors work together to produce larger image

• DECOMPOSITION IDEA: different devices work together to achieve an

end goal

15
Let's Apply These
Concepts

TO PROGRAMMING!

16
Create Structure With Decomposition
• in projector example, separate devices
• in programming, divide code into modules
▪ are self-contained
▪ used to break up code
▪ intended to be reusable
▪ keep code organized
▪ keep code coherent

• this lecture, achieve decomposition with functions

• in a few weeks, achieve decomposition with classes

17
Suppress Details With Abstraction
• in projector example, instructions for how to use it are sufficient, no need
to know how to build one
• in programming, think of a piece of code as a black box
▪ cannot see details
▪ do not need to see details
▪ do not want to see details
▪ hide tedious coding details

• achieve abstraction with function specifications or docstrings

18
Functions
• Write reusable pieces/chunks of code, called functions

• functions are not run in a program until they are “called” or “invoked” in a
program

• function characteristics:
▪ has a name
▪ has parameters (0 or more)
▪ has a docstring (optional but recommended)
▪ has a body
▪ returns something

19
Function Definitions
• In Python each function definition is of the form

• def name of function (list of formal parameters):

body of function

def is a reserved word that tells Python

def max_val(x, y): a function is about to be defined
if x > y:
return x
else:
return y

20
Function Definitions
• In Python each function definition is of the form

• def name of function (list of formal parameters):

body of function

max_val is the name to refer to the

def max_val(x, y):
function
if x > y:
return x
else: function names — all lowercase with
return y words separated by underscores

21
Function Definitions
• In Python each function definition is of the form

• def name of function (list of formal parameters):

body of function

The function body is any piece of Python

def max_val(x, y):
code
if x > y:
return x
else: return — a special statement, used
return y only within the body of a function

22
Function Definitions
• In Python each function definition is of the form

• def name of function (list of formal parameters):

body of function

def max_val(x, y): formal parameters of the function

if x > y:
return x
else:
return y

23
Function Definitions
• The formal parameters are bound (as in an assignment statement) to the
actual parameters (also called arguments) of the function invocation
(also referred to as a function call).

• max_val(3, 4)binds x to 3 and y to 4

• A function call is an expression, and like all expressions, it has a value.

• That value is returned by the invoked function.

24
Function Definitions
• The value of the expression max_val(3,4)*max_val(3,2) is 12,
because the first invocation of max_val returns the int 4 and the
second returns the int 3

25
The return statement
• Execution of a return statement terminates an invocation of the function

• There will be one warning if no return statement

• Python returns the value None, if no return given

• represents the absence of a value

26
Function Definitions

27
Function Definitions

28
Function Invocation
• When a function is called, sequence of events:

1. The expressions that make up the actual parameters are evaluated, and
the formal parameters of the function are bound to the resulting values.
▪ max_val(3+4, z) will bind the formal parameter x to 7 and the formal
parameter y to whatever value the variable z has

2. The point of execution (the next instruction to be executed) moves from

the point of invocation to the first statement in the body of the function

29
Function Invocation
3. The code in the body of the function is executed until either
▪ a return statement is encountered and the value of the expression following
the return becomes the value of the function invocation

▪ there are no more statements to execute, and the function returns None

4. The value of the invocation is the returned value

5. The point of execution is transferred back to the code immediately
following the invocation

30
Lambda Abstraction
• Parameters allow programmers to write code that accesses not specific
objects, but instead whatever objects the caller of the function chooses to
use as actual parameters

31
A Function for Finding Roots
def find_root(x, power, epsilon):
if x < 0 and power%2 == 0:
return None #Negative number has no even-powered roots
low = min(-1, x)
high = max(1, x)
ans = (high + low)/2
while abs(ans**power - x) >= epsilon:
if ans**power < x:
low = ans
else:
high = ans
ans = (high + low)/2
32
return ans
Test Functions
• Pay big dividends

• Save a programmer from the tedious and error-prone task of visually

inspecting each output and checking it for correctness

• Beat sitting at a keyboard and typing test cases into the shell over and
over during debugging the process of finding out why a program does not
work, and then fixing it

33
A Test Function for Finding Roots
def test_find_root(x_vals, powers, epsilons):
for x in x_vals:
for p in powers:
for e in epsilons:
result = find_root(x, p, e)
if result == None:
val = 'No root exists'
else:
val = 'Okay'
if abs(result**p - x) > e:
val = 'Bad'
print(f'x = {x}, power = {p}, epsilon = {e}: {val}')
34
A Test Function for Finding Roots
x_vals = (0.25, 8, -8)
powers = (1, 2, 3)
epsilons = (0.1, 0.001, 1)
test_find_root(x_vals, powers, epsilons)

• Three tuples (i.e., sequences of values) of length three, one call checks 27
combinations of parameters.

35
Keyword Arguments and Default Values
• Two ways that formal parameters get bound to actual parameters:

• Positional — the most common method — the first formal parameter is

bound to the first actual parameter, the second formal to the second
actual, etc.

• Keyword arguments — formals are bound to actuals using the name of

the formal parameter

36
Keyword Arguments and Default Values
def print_name(first_name, last_name, reverse):
if reverse:
print(last_name + ', ' + first_name)
else:
print(first_name, last_name)

• The function print_name assumes that first_name and last_name

are strings and that reverse is a Boolean.

37
Keyword Arguments and Default Values
• Each of the following is an equivalent invocation of print_name:

• print_name('Olga', 'Puchmajerova', False)

• print_name('Olga', 'Puchmajerova', reverse = False)
• print_name('Olga', last_name = 'Puchmajerova', reverse
= False)
• print_name(last_name = 'Puchmajerova', first_name =
'Olga’, reverse = False)

38
Keyword Arguments and Default Values
• Though the keyword arguments can appear in any order in the list of
actual parameters, it is not legal to follow a keyword argument with a non-
keyword argument.

• An error message would be produced by

print_name('Olga', last_name = 'Puchmajerova', False)

39
Keyword Arguments and Default Values
• Keyword arguments are commonly used in conjunction with default
parameter values.

def print_name(first_name, last_name, reverse = False):

if reverse:
print(last_name + ', ' + first_name)
else:
print(first_name, last_name)

40
Keyword Arguments and Default Values
• Default values allow programmers to call a function with fewer than the
specified number of arguments.

print_name('Olga', 'Puchmajerova')
print_name('Olga', 'Puchmajerova', True)
print_name('Olga', 'Puchmajerova', reverse = True)

will print

Olga Puchmajerova
Puchmajerova, Olga
Puchmajerova, Olga

41
Keyword Arguments and Default Values
• Using keyword arguments reduces the risk of unintentionally binding an
actual parameter to the wrong formal parameter.

• The line of code leaves no ambiguity about the intent of the programmer
who wrote it.

• This is useful because calling a function with the right arguments

in the wrong order is a common blunder.

print_name(last_name = 'Puchmajerova', first_name =

'Olga’)

42
Variable Number of Arguments
• Python has several built-in functions that operate on a variable number of
arguments.

• Both are legal (and evaluate to what you think they do).

min(6,4)
min(3,4,1,6)

• Python makes it easy for programmers to define their own functions that
accept a variable number of arguments.

43
Variable Number of Arguments
• The unpacking operator * allows a function to accept a variable number
of positional arguments.
def mean(*args):
# Assumes at least one argument and all arguments are
numbers and Returns the mean of the arguments
tot = 0
for a in args:
tot += a
return tot/len(args)

• The name following the * in the argument list need not be args. It can be
any name.

44
Programming Exercise
• Implement a radians function that returns the radian equivalent of a
degree.

• Use the following formula:

rad = degrees * pi/180

• Use this function to print a chart showing the radian equivalent of all
degrees ranging from 1° to 180°.
• Use two digits of precision for the results.

45
Scoping
def f( x ):
y = 1
x = x + y Function Definition
print('x =', x)
return x
x = 3
y = 2
z = f( x ) Main program code
print('z =', z) • Initializes variables
print('x =', x) • Makes a function call
print('y =', y) • Assigns a return of
function to variable z

46
Scoping
def f( x ): formal parameter
y = 1
x = x + y Function Definition
print('x =', x)
return x
x = 3
y = 2
z = f( x ) actual parameter Main program code
print('z =', z) • Initializes variables
print('x =', x) • Makes a function call
print('y =', y) • Assigns a return of
function to variable z

47
Scoping
def f( x ): formal parameter
y = 1
x = x + y Function Definition
print('x =', x)
return x
x = 3
y = 2
z = f( x ) actual parameter Main program code
print('z =', z) • Initializes variables
print('x =', x) • Makes a function call
print('y =', y) • Assigns a return of
function to variable z
• When run, what will the code print?
48
Scoping
x = 4
z = 4
x = 3
y = 2

49
Scoping
def f( x ): • At the call of f, the formal
y = 1 parameter x is locally bound to the
x = x + y value of the actual parameter x in
print('x =', x) the function body of f
return x
x = 3
y = 2 • The actual and formal parameters
z = f( x ) have the same name, but they are
print('z =', z) not the same variable
print('x =', x)
print('y =', y)

50
Scoping
def f( x ): • Each function defines a new name
y = 1 space, also called a scope
x = x + y
print('x =', x)
return x • The formal parameter x and the
x = 3 local variable y that are used in f
y = 2 exist only within the scope of the
z = f( x ) definition of f
print('z =', z)
print('x =', x)
print('y =', y)

51
Scoping
def f( x ): • The statement x = x + y within
y = 1
the function body binds the local
x = x + y x to 4.
print('x =', x)
return x
x = 3 • The assignments in f have no
y = 2 effect on the bindings of the names
z = f( x ) x and y that exist outside the
print('z =', z) scope of f.
print('x =', x)
print('y =', y)

52
How to think about Scoping?
1. At the top level, i.e., the level of the shell, a symbol table keeps track of
all names defined at that level and their current bindings

2. When a function is called, a new symbol table (called a stack frame) is

created. This table keeps track of all names defined within the function
(including the formal parameters) and their current bindings. If a function is
called from within the function body, yet another stack frame is created.

3. When the function completes, its stack frame goes away

53
Variable Scope

54
Variable Scope

55
Variable Scope

56
Variable Scope

57
Variable Scope

58
Scoping
• In Python, one can always determine the scope of a name by looking at
the program text

• This is called static or lexical scoping.

59
Example Illustrating Scope Rules
def f(x): x = 3
def g(): z = f(x)
x = 'abc'
print('x =', x)
print('x =', x)
print('z =', z)
def h():
z = x
z()
print('z =', z)
x = x + 1
print('x =', x)
h()
g()
print('x =', x)
return g 60
History of the Stack Frames Associated
with the Code
• The first column contains the set of
names known outside the body of
the function f
▪ the variables x and z, and
▪ the function name f

• The first assignment statement

binds x to 3.

61
History of the Stack Frames Associated
with the Code
• The assignment statement z =
f(x) first evaluates the expression
f(x) by invoking the function f
with the value to which x is bound.

• When f is entered, a stack frame

is created (see column 2)

62
History of the Stack Frames Associated
with the Code
• The names in the stack frame are:
▪ formal parameter x, not the x in
the calling context
▪ g, and h

• The variables g and h are bound to

objects of type function.

63
History of the Stack Frames Associated
with the Code
• When h is invoked from within f,
another stack frame (column 3)

• It contains only the local variable z

64
History of the Stack Frames Associated
with the Code
• Why does it not also contain x?

• A name is added to the scope

associated with a function only if

▪ a name is a formal parameter of

the function or

▪ a variable bound to an object

within the body of the function

65
History of the Stack Frames Associated
with the Code
• In h, x occurs on the right-hand
side of an assignment statement

• x is not bound to an object

anywhere in the function body of
h, the interpreter will search the
stack frame associated with the
scope within which h is defined
i.e., stack frame of f

66
History of the Stack Frames Associated
with the Code
• If x is found, the value to which it is
bound is used.

• If x was not found there, an error

message is produced

67
History of the Stack Frames Associated
with the Code
• When h returns, the stack frame
associated with it goes away i.e.,
popped off the top of the stack
(see column 4)

• Frames are never removed from

the middle of the stack

• This “last in first out” (LIFO)

behavior is referred to as a stack

68
A Helpful Analogy
• A helpful analogy is to think of
a stack of books

• You can remove only the top

book

• Also, you can add a new book

on the top

69
History of the Stack Frames Associated
with the Code
• The function g is now invoked

• A stack frame containing g's local

variable x is added ( see column 5)

70
History of the Stack Frames Associated
with the Code
• When g returns, that frame is
popped (column 6).

71
History of the Stack Frames Associated
with the Code
• When f returns, the stack
frame containing the names
associated with f is popped,
getting us back to the
original stack frame
(column 7)

72
Example Illustrating Scope Rules
• What does the code print?

73
Example Illustrating Scope Rules
• When f returns, even though the variable g no longer exists, the object of
type function to which that name was once bound still exists

• z is bound to the value returned by f, and the function call z() is used to
invoke the function that was bound to the name g within f — even though
the name g is not known outside the context of f

74
Example Illustrating Scope Rules
• What does the code print?

x = 4
z = 4
x = abc
x = 4
x = 3
z = <function f.<locals>.g at 0x1092a7510>
x = abc

On my system
z = <function f.<locals>.g at 0x0000024138442040>

75
Example Illustrating Scope Rules
def f(): • What does the code print?
print(x)
def g():
print(x)
x = 1
x = 3
f()
x = 3
g()

76
Example Illustrating Scope Rules
def f(): • Prints 3 when f is invoked
print(x)
def g():
print(x) • Prints an error message when print
x = 1
x = 3 statement in g is encountered
f()
x = 3
g() • UnboundLocalError: local
variable 'x' referenced
before assignment

77
Example Illustrating Scope Rules
def f(): • The assignment statement
print(x) following the print statement
def g():
print(x) causes x to be local to g.
x = 1
x = 3
f() • Since x is local to g, it has no
x = 3 value when the print statement
g() is executed

78
Example Illustrating Scope Rules
def f(): • If an object is bound to a name
print(x) anywhere in the function body
def g(): (even if it occurs in an expression
print(x)
before it appears as the left-hand
x = 1
x = 3 side of an assignment), it is treated
f() as local to that function
x = 3
g()

79
Example Illustrating Scope Rules
• inside a function, can access a variable defined outside

• inside a function, cannot modify a variable defined outside — can using

global variables, but is disapproved of

80
Example Illustrating Scope Rules

81
Functions
• Functions provide decomposition and abstraction

• Decomposition creates structure. It allows us to break a program into

parts that are reasonably self-contained and that may be reused in
different settings.

• Abstraction hides detail. It allows us to use a piece of code as if it were a

black box — something whose interior details we cannot see, don't need to
see, and shouldn't even want to see

82
Using Functions to Modularize Code
• As we implement more complicated functionality, it is convenient to split
functions into multiple functions, each of which does one simple thing

83
Using Functions to Modularize Code
def find_root_bounds(x, power):
"""x a float, power a positive int return low, high such that
low**power <=x and high**power >= x"""

low = min(-1, x)
high = max(1, x)
return low, high

84
Using Functions to Modularize Code
def bisection_solve(x, power, epsilon, low, high):
"""x, epsilon, low, high are floats epsilon > 0 low <= high and
there is an ans between low and high s.t. ans**power is within
epsilon of x returns ans s.t. ans**power within epsilon of x"""
ans = (high + low)/2
while abs(ans**power - x) >= epsilon:
if ans**power < x:
low = ans
else:
high = ans
ans = (high + low)/2
return ans 85
Using Functions to Modularize Code
def find_root(x, power, epsilon):
"""Assumes x and epsilon int or float, power an int,
epsilon > 0 & power >= 1 Returns float y such that y**power is
within epsilon of x. If such a float does not exist, it returns
None"""
if x < 0 and power%2 == 0:
return None #Negative number has no even-powered roots
low, high = find_root_bounds(x, power)
return bisection_solve(x, power, epsilon, low, high)

86
Using Functions to Modularize Code
• Is this version of find_root easier to understand than the original
monolithic implementation?

• Probably not!

• A good rule of thumb: if a function fits comfortably on a single page, it

probably doesn't need to be subdivided to be easily understood

87
Functions as Objects
• In Python, functions are first-class objects

• can be treated like objects of any other type, e.g., int or list

• have types, e.g., type(abs) → 'builtin_function_or_method’

• can appear in expressions, e.g., as the right-hand side of an assignment

statement or as an argument to a function; they can be returned by
functions etc.

88
Functions as Objects
• Using functions as arguments allows a style of coding called higher-order
programming

• Allows to write functions that are more generally useful

89
Functions as Arguments

90
Functions as Arguments

91
Functions as Arguments

92
Functions as Arguments

93
Methods, Oversimplified
• Methods are function-like objects — can be called with parameters, and
can return values

• If s is a string, the find method can be used to find the index of the first
occurrence of a substring in s
▪ If s was 'abcbc', s.find('bc') would return 1

• Attempting to treat find as a function, e.g., invoking find(s,'bc'),

produces the error message NameError: name 'find' is not
defined

94
Programming Exercise
• Implement a fahrenheit function that returns the Fahrenheit equivalent
of a Celsius temperature. Use the following formula:

F = (9 / 5) * C + 32

• Use this function to print a table showing the Fahrenheit equivalents of all
Celsius temperatures in the range 0 – 100 degrees.

• Use one digit of precision for the results

95
Programming Exercise
• Calculate the product of a series of integers that are passed to the function
product, which receives an arbitrary argument list.

• Test your function with several calls, each with a different number of
arguments

96