程序代写代做代考 python CS1010S Programming Methodology

CS1010S Programming Methodology

Lecture 2
Functional Abstraction

20 Aug 2018

Expectations

Tutorial Allocation
Coursemology Survey

– Choose your preferred slots
– As many slots as possible
– Updated with number of classes

Recitation
Appeal on CORS

classes starts
on Thursday/Friday

Late Policy
• < 10 min: OK • < 30 min: -10% • < 12 hours: -20% • < 24 hours: -50% • > 24 hours: -100%

Ask early for extensions

Submission is Final
But please remember to click

Finalize Submission

Don’t Stress
But please do your

work
Try NOT to submit at 23:58

Operators
Assignment

a = 5

Equality testing

a == 5

Not equal

a != 5

Backslash \

Escape character

print(‘That’s’)
print(‘That\’s’)

#Comments
# this is not a hashtag!

print(“Good to go”)

#print(“Good to go”)

# whatever is after the # is ignored

if light == “red”: # Check state of light

What’s this?

from PIL import *
(Misison 0)

Python Imaging Library

Lecture
LT26

Recitation
Classroom

Tutorial Training
Coursemology

Mission
Coursemology

Tutorial
Classroom

Contest
Coursemology

Side Quest
Coursemology

Training
Coursemology

Forum
Coursemology

Forums
Post reflections for EXP

Trainings
Please don’t anyhow

hantam

Computational
Thinking

Fasten your
seatbelt

CS1010S Road Map

BASIC

INTERMEDIATE

ADVANCED

Functional
Abstraction

Higher-Order
Procedures

Recursion

Iteration

Wishful
Thinking

Order of
Growth

Data
Abstraction

List
Processing

Multiple
Representations

Object-Oriented
Programming

Memoization

Dynamic
Programming

Mutation &
State

Fundamental concepts of computer programming

Searching & Sorting

Functional Abstraction

WHAT
HOW
WHY

What is a function?

Inputs Function Output

Functions are nothing new

Find x?

𝑥 =
cos(𝜃)

𝑎

𝑥

𝑎
𝜃

function

input

Let’s start with something
easier

Question
How do we square a number?

The square function

def square(x):
return x * x

Define Name Input

Return Output

square(21)

square(2 + 5)

square(square(3))

441

49

81

Another function
def sum_of_squares(x, y):

return square(x) + square(y)

sum_of_squares(3, 4) 25

And another
from math import sqrt

def hypotenuse(a, b):

return sqrt(sum_of_squares(a, b))

hypotenuse(5, 12) 13

General Form
def ():


• name

– Symbol associated with the function

• formal parameters
– Names used in the body to refer to the arguments of the function

• body
– The statement(s) to be evaluated
– Has to be indented (standard is 4 spaces)

– Can return values as output

Black Box

Inputs Function Output

Don’t need to know how it works
Just know what it does

Black Box

𝑥 =
𝑎

cos(𝜃)

Do you know how cos work?

𝑥

𝑎
𝜃

Black Box

Inputs Function Output

As long as we know what it does,
we can use it. (the inputs

and output)

Return Type

Inputs Function Output

Output is returned with return
Return type can be None

Abstract Environment

Picture Language
(runes.py)

Also graphics.py + PyGif.py

Elements of Programming
1. Primitives

2. Means of Combination

3. Means of Abstraction

4. Controlling Logic

Primitives building block
show(rcross_bb)

Picture object

Primitives building block
show(corner_bb)

Primitives building block
show(sail_bb)

Primitives building block
show(nova_bb)

Primitives building block
show(heart_bb)

Applying operations
op(picture)

Example:
show(heart_bb)

function name input(s)

Fun with IDLE

Font matters

Primitive Operation
Rotating to the Right

clear_all()

show(quarter_turn_right(sail_bb))

pictureoperation

result is
another picture

Derived Operation
Rotating Upside Down

def turn_upside_down(pic):

return quarter_turn_right(

quarter_turn_right(pic))

clear_all()

show(turn_upside_down(sail_bb))

How about
Rotating to the Left?

def quarter_turn_left(pic):

return quarter_turn_right(

quarter_turn_upside_down(pic))

clear_all()

show(quarter_turn_left(sail_bb))

Means of Combination
Stacking

clear_all()

show(stack(rcross_bb, sail_bb))

Multiple Stacking
clear_all()

show(stack(rcross_bb,

stack(rcross_bb,

sail_bb) )

Means of Combination
Placing Beside

def beside(pic1, pic2):

return quarter_turn_right(

stack(quarter_turn_left(pic2),

quarter_turn_left(pic1)))

A complex object
clear_all()

show(

stack(

beside(

quarter_turn_right(rcross_bb),

turn_upside_down(rcross_bb)),

beside(

rcross_bb,

quarter_turn_left(rcross_bb))))

Let’s give it a name
make_cross

stack(

beside(

quarter_turn_right(rcross_bb),

turn_upside_down(rcross_bb)),

beside(

rcross_bb,

quarter_turn_left(rcross_bb))))

stack(

beside(

quarter_turn_right(pic),

turn_upside_down(pic)),

beside(

pic,

quarter_turn_left(pic))))

def make_cross(pic):

return stack(

beside(

quarter_turn_right(pic),

turn_upside_down(pic)),

beside(

pic,

quarter_turn_left(pic))))

return vs show

Naming your objects
clear_all()

my_pic = make_cross(sail_bb)

show(my_pic)

my_pic_2 = make_cross(nova_bb)

show(my_pic_2)

Repeating the pattern
clear_all()

show(make_cross(make_cross(nova_bb)))

Repeating multiple times
clear_all()

def repeat_pattern(n, pat, pic):

if n == 0:

return pic

else:

return pat(repeat_pattern(n-1, pat, pic))

show(repeat_pattern(4, make_cross, nova_bb))

Qn: What does
repeat_pattern

return?recursion

Anonymous Functions
def square(x):

return x * x

foo = lambda x: x * x

foo(1)

foo(16)

input output

function

1
256

New Patterns
clear_all()

show(repeat_pattern(3,

lambda pic: beside(pic, pic),

nova_bb))

clear_all()

show(repeat_pattern(3,

lambda pic: stack(pic, pic),

nova_bb))

anonymous
function

Another nice pattern
clear_all()

show(repeat_pattern(4, make_cross, rcross_bb))

What about 3 rows?
clear_all()

show(stack_frac(1/3, rcross_bb, sail_bb))

clear_all()

show(stack_frac(1/3, rcross_bb,

stack(rcross_bb, rcross_bb)))

Repeating n times
def stackn(n, pic):

if n == 1:

return pic

else:

return stack_frac(1/n,

pic,

stackn(n-1, pic))

clear_all()

show(stackn(3, nova_bb))

clear_all()

show(stackn(5, nova_bb))

A rectangular quilting pattern
clear_all()

show(stackn(5, quarter_turn_right(

stackn(5, quarter_turn_left(nova_bb)))))

A rectangular quilting proc
def nxn(n, pic):

return stackn(n, quarter_turn_right(

stackn(n, quarter_turn_left(pic))))

clear_all()

show(nxn(3, make_cross(rcross_bb)))

After all this…

No idea how a picture
is represented

No idea how the
operations do their

work

Yet, we can build
complex pictures

This is
Functional Abstraction

We can make Sterograms!

Black Box

Inputs Function Output
Depth
Map

Sterogram
Generator

Sterogram

Functional Abstraction

Can’t see
stereograms?

Anaglyphs

And if you think this is
cool…

You ain’t seen nothing
yet!

What have we learnt?

WHAT
Functional Abstraction = Black-box

HOW
def and lambda

Functions are objects
(in Python)

WHY?
Help us manage

complexity

Allow us to focus on
high-level problem

solving

Creating 3D objects
We use greyscale to represent depth

– Black is nearest to you
is furthest away

means

Overlay Operation
clear_all()

show(overlay(sail_bb, rcross_bb))

Advanced Overlay Operation
clear_all()

show(overlay_frac(1/4, corner_bb, heart_bb))

Scaling
clear_all()

show(scale(1/2, heart_bb))

Recall
stereogram(scale(1/2, heart_bb))

Function
Depth
Map

Sterogram
Generator

Sterogram

Managing Complexity

Computers will follow
orders precisely

Abstractions

What makes a good abstraction?

Problem Solution
Primitives

Abstractions
Invented to make

the task easier

Good Abstraction
1. Makes it more natural to think about tasks

and subtasks

Example

House Bricks

Walls

Rooms

Bricks

Divide and
Conquer

Programming

Program Primitives

Primitives

Functions Divide and
Conquer

Good Abstraction
1. Makes it more natural to think about tasks

and subtasks

2. Makes programs easier to understand

Compare:

def hypotenuse(a, b):

return sqrt((a*a) + (b*b))

Versus:

def hypotenuse(a, b):

return sqrt(sum_of_squares(a, b))

def sum_of_squares(x, y):

return square(x) + square(y)

def square(x):

return x * x

Good Abstraction
1. Makes it more natural to think about tasks

and subtasks

2. Makes programs easier to understand

3. Captures common patterns

stack(

beside(

quarter_turn_right(rcross_bb),

turn_upside_down(rcross_bb)),

beside(

rcross_bb,

quarter_turn_left(rcross_bb))))

stack(

beside(

quarter_turn_right(pic),

turn_upside_down(pic)),

beside(

pic,

quarter_turn_left(pic))))

def make_cross(pic):

return stack(

beside(

quarter_turn_right(pic),

turn_upside_down(pic)),

beside(

pic,

quarter_turn_left(pic))))

Allows Code Reuse

Good Abstraction
1. Makes it more natural to think about tasks

and subtasks

2. Makes programs easier to understand

3. Captures common patterns

4. Allows for code reuse
• Function square used in sum_of_squares.

• square can also be used in calculating area of circle.

Another Example
Function to calculate area of circle given the radius

pi = 3.14159

def circle_area_from_radius(r):
return pi * square(r)

given the diameter:

def circle_area_from_diameter(d):
return circle_area_from_radius(d/2)

Good Abstraction
1. Makes it more natural to think about tasks

and subtasks

2. Makes programs easier to understand

3. Captures common patterns

4. Allows for code reuse

5. Hides irrelevant details Water molecule
represented as 3 balls

Ok for some chemical analyses,
inadequate for others.

Depth
Map

Function
Stereogram
Generator

Stereogram

Function that was provided

Good Abstraction

1. Makes it more natural to think about tasks
and subtasks

2. Makes programs easier to understand

3. Captures common patterns

4. Allows for code reuse

5. Hides irrelevant details

6. Separates specification from implementation

Recap
Functional Abstraction

=

Black Box

No need to know how a car works to drive it!

Functional Abstraction
Separates specification from implementation

Specification: WHAT

Implementation: HOW

Example
def square(x):

return x * x

def square(x):
return exp(double(log(x)))

def double(x): return x + x

To think about

Why would we want to
implement a function in

different ways?

Good Abstraction
1. Makes it more natural to think about tasks

and subtasks
2. Makes programs easier to understand
3. Captures common patterns
4. Allows for code reuse
5. Hides irrelevant details
6. Separates specification from implementation
7. Makes debugging (fixing errors) easier

Good Abstraction
Where is the bug?

def hypotenuse(a, b):
return sqrt(sum_of_squares(a, b))

def sum_of_squares(x, y):
return square(x) + square(y)

def square(x): return x + x

def hypotenuse(a, b):
return sqrt((a + a) * (b + b))

Variable Scope

Variable Scope
x = 10

def square(x): return x * x

def double(x): return x + x

def addx(y): return y + x

square(20)

square(x)

addx(5)
Which x ?

Variable Scope

def square(x):

return x * x

formal parameter

body

A function definition binds its formal parameters.

i.e. the formal parameters are visible only inside the
definition (body), not outside.

Variable Scope

def square(x):

return x * x

formal parameter

body

• Formal parameters are bound variables.

• The region where a variable is visible is called the
scope of the variable.

• Any variable that is not bound is free.

Variable Scope
x = 10

def square(x):

return x * x

def double(x):

return x + x

def addx(y):

return y + x

x is bound

x is bound

y is bound, x is free

Example
pi = 3.14169

def circle_area_from_radius(r):
pi = 22/7 #local pi
return pi * square(r)

Which pi?

Block Structure
def hypotenuse(a, b):

def sum_of_squares():
return square(a) + square(b)

return math.sqrt(sum_of_squares())

The variables a and b in sum_of_squares refer to the formal
parameters of hypotenuse.

Hides irrelevant details (sum_of_squares) from the user of
hypotenuse.

Wishful Thinking

WHAT
Top-down design approach:

Pretend you have whatever you
need

WHY
Easier to think with in the goal

in mind

Analogy
Suppose you are to build a house.

Where do you start?

Individual
bricks

Building plan

Example
Suppose you want to compute hypotenuse

def hypotenuse(a, b):

return sqrt(sum_of_squares(a, b))

def sum_of_squares(x, y):

return square(x) + square(y)

def square(x):

return x * x

a

b

?

Another Example
Comfort Delgro, the largest taxi operator in Singapore, determines the

taxi fare based on distance traveled as follows:

• For the first kilometre or less: $2.40

• Every 200 metres thereafter or less up to 10 km: $0.10

• Every 150 metres thereafter or less after 10 km: $0.10

Problem:
Write a Python function that

computes the taxi fare from distance
travelled.

How do we start?

Formulate the problem

Needs a name

Pick an appropriate name

(not foo)

Function

Formulate the problem

Taxi Faredistance fare

• Results should be
unambiguous

• What other abstractions
may be useful?

• Ask the same questions for
each abstraction.

• What data do
you need?
(be thorough)

• Where would
you get it?
(argument/
computed?)

How can the result be
computed from data?

1. Try simple examples

2. Strategize step by step

3. Write it down and refine

Solution

• What to call the function?

• What data are required?

• Where to get the data?

• What is the result?

taxi_fare

distance

function argument

fare

How can the result be computed
from data?

• e.g. #1: distance = 800 m, fare = $2.40

• e.g. #2: distance = 3,300 m
fare = $2.40 + 2300/200 × $0.10

= $3.60

• e.g. #3: distance = 14,500 m
fare = $2.40 + 9000/200 × $0.10 + 4500/150 × $0.10 = $9.90

Pseudocode
Case 1: distance <= 1000 fare = $2.40 Case 2: 1000 < distance <= 10,000 fare = $2.40 + $0.10 * (distance – 1000)/200 Case 3: distance > 10,000
fare = $6.90 + $0.10 * (distance – 10,000)/150)

Note: the Python function ceil rounds up its
argument. math.ceil(1.5) = 2

What’s this?

Solution
def taxi_fare(distance): # distance in metres

if distance <= 1000: return 2.4 elif distance <= 10000: return 2.4 + (0.10 * ceil((distance – 1000) / 200)) else: return 6.9 + (0.10 * ceil((distance – 10000) / 150)) # check: taxi_fare(3300) = 3.6 Can we improve this solution? Coping with Change What if… 1. the starting fare increases? 2. stage distance changes? 3. increment amount changes? Avoid Magic Numbers It is a terrible idea to hardcode numbers (magic numbers): - Hard to make changes in future Define abstractions to hide them! Solution v2 def taxi_fare(distance): # distance in metres if distance <= stage1: return start_fare elif distance <= stage2: return start_fare + (increment * ceil((distance - stage1) / block1)) else: return taxi_fare(stage2) + (increment * ceil((distance - stage2) / block2)) stage1 = 1000 stage2 = 10000 start_fare = 2.4 increment = 0.1 block1 = 200 block2 = 150 recursive call in 2018 def taxi_fare(distance): # distance in metres if distance <= stage1: return start_fare elif distance <= stage2: return start_fare + (increment * ceil((distance - stage1) / block1)) else: return taxi_fare(stage2) + (increment * ceil((distance - stage2) / block2)) stage1 = 1000 stage2 = 10000 start_fare = 3.7 increment = 0.22 block1 = 400 block2 = 350 Summary • Functional Abstraction • Good Abstractions • Variable Scoping • Wishful Thinking Recitation Thursday/Friday