Functions and Decomposition

from byubit import Bit

Decomposition

Decomposition means breaking a problem into smaller parts. It’s the “divide and conquer” strategy.

We did this with the “fix the tree” problem:

Get to the base of the trunk
Add the trunk

Most problems are solved using decomposition—we break the problem down into smaller, managable chunks.

Functions

A function is a block of code with a name.

Let’s say you write a block of code that performs the following steps:

Open the washing machine
Put the clothes in the machine
Put the detergent in the machine
Close the lid
Select the standard cycle
Push the big button

We’ll call this series of steps start_the_laundry.

Any time you want the computer to start your laundry, you don’t want to have to specify each step every single time.

You just want to say: “Hey Computer, start_the_laundry(), and the computer starts your laundry.

def start_the_laundry():
    print("I'm sorry")
    print("I can't do that for you. 😕")

start_the_laundry()

    I'm sorry
    I can't do that for you. 😕

start_the_laundry()
start_the_laundry()
start_the_laundry()

    I'm sorry
    I can't do that for you. 😕
    I'm sorry
    I can't do that for you. 😕
    I'm sorry
    I can't do that for you. 😕

Functions

Have a definition
Have a name
Take arguments or args
Can be documented
Have a body
May return a value
Have a scope

def create_salutation(name):
    """Return a salutation addressed to `name`"""
    return f"Hello {name}, it is very nice to meet you."

Very often (even most of the time), you want to provide information to your function.

Like bit.paint("green").

You want to pass information to your function. We call these arguments.

def say_it_twice(message):
    print(message)
    print(message)

say_it_twice("I love programming! 😄")

    I love programming! 😄
    I love programming! 😄

Can we do this with Bit?

🤔

Yes!

def paint_ahead(bit, color):
    while bit.front_clear():
        bit.move()
        bit.paint(color)

bit = Bit.new_world(5,5)
paint_ahead(bit, "green")
bit.draw()

bit.left()
paint_ahead(bit, "blue")
bit.draw()

bit.left()
paint_ahead(bit, "red")
bit.draw()

bit.left()
paint_ahead(bit, "blue")
bit.draw()

png

Function syntax

A function is defined with def.

Indentation matters! (Are you catching on to a theme here…?)

Function arguments go in the parentheses. You can use these arguments inside the body of the function.

To return a value from the function, use return.

Function scope

🔭

No, not that kind of scope.

Scope as in:

“That work item is not in scope”
“Is the ward activity in scope for this meeting, or will we talk about that next time?”

A function has a scope: the variables that the body of the function can use.

The function arguments are part of the function’s scope.

name = "Fulando"
print(name)

def create_salutation(name):
    """Return a salutation addressed to `name`"""
    return f"Hello {name}, it is very nice to meet you."

print(create_salutation("Joãzinho"))

# This statement is outside the function definition
# So, `name` is not the same as `name` in `create_salutation`
print(name)

    Fulando
    Hello Joãzinho, it is very nice to meet you.
    Fulando

It’s like the word “professor”.

From class to class, the same word “professor” (i.e. variable) has a specific meaning (i.e. value), but only in the scope of that class.

Outside that class, the meaning of the word “professor” could be something different.

For now, understand that for the body of a function to use something, you should pass that something as a function argument.

There are other ways for functions to use values besides their arguments, but let’s walk before we run.

Divide and Conquer

In CS, we can use functions to help us divide and conquer.

Maybe it’s obvious, but EVERYTHING in software is about decomposition.

For example, your web browser is MILLIONS of lines of code.

PNG images, urls, HTML, inline video, network packets, SSL encryption, DOM tree…

You can’t possibly keep track of all that in your head.

But a single function—sure, that’s managable.

Abstraction!

Using functions to decompose a problem is another form of abstraction.

For example, once we wrote the paint_row function, we could forget the details of move-and-paint and think in terms of coloring entire rows at once.

This is powerful!

How to call a function

To invoke or call a function, we use the function’s name, followed by the values for the functions arguments in parentheses.

def say_this_twice(message):
    print(message)
    print(message)

say_this_twice("I think I'm getting the hang of this")

It a function doesn’t declare any arguments, then you just use empty parentheses:

def say_something_intelligent():
    print("Line upon line, precept upon precept")

say_something_intelligent()

Programmers, being human beings, don’t like to say so many syllabals if they can help it.

arguments → args

parentheses → parens

Many of the examples I’ve shown use verbs as the function name: say_this_twice, etc.

Sometimes we refer to functions with a noun.verb pattern, like bit.move.

Eventually you will learn how to make functions that have a noun part and not just a verb part, but for now we’ll just use functions with a simple verb name.

Order of execution

If you were to follow these instructions:

Bake a cake
Make frosting
Frost the cake

You would start by baking the cake. This involves many steps (gather ingredients, mix batter, pour, insert in oven, etc.), and while you are performing those sub-steps, you pause your execution of the other steps in the instructions.

Once you’re done baking the cake, you move on to step 2, which again involves sub-steps, and so you wait to move on to step 3 until all the sub-steps of 2 are done.

Function calls are the same way. When you invoke a function, the execution at the call site pauses until after the function has finished.

The Big Picture - Functions Calling Functions!

def say_it_in_a_box(message):
    print("-"*len(message))
    print(message)
    print("-"*len(message))

def say_something_epic(name):
    say_it_in_a_box(f"I am {name}, and with functions I will rule the world!")
    print("Man, that was epic.")

def print_something():
    print("something!")

print_something()

    something!

me = "a professor"
say_something_epic(me)

    -----------------------------------------------------------
    I am a professor, and with functions I will rule the world!
    -----------------------------------------------------------
    Man, that was epic.

Sometimes the term helper function is used to describe a function that helps another do its job.

say_it_in_a_box would be an example of this.

Decomposition in Action

In the first examples, we’ll demonstrate a bottom-up approach to decomposition.

We’ll write the most specific functions first, and then build up from there.

An equally valid approach is to start with the more general function first, and then build down to more specialized functions.

You’ll probably use both strategies regularly.

Decomposition 1: Blue Ocean

# Before
# Notice the orientation of Bit!
Bit.load("blue-ocean-start.txt").draw()

png

# After
Bit.load("blue-ocean-finish.txt").draw()

png

Let’s start by defining a function that solves a small piece of this problem.

def fill_row_blue(bit):
    # Turn to face down the row
    bit.right()

    # Paint the row
    while bit.front_clear():
        bit.paint("blue")
        bit.move()

    bit.paint("blue")

    # Turn to face back
    bit.right()
    bit.right()

    # Go back
    while bit.front_clear():
        bit.move()

    # face back up
    bit.right()

bit = Bit.load("blue-ocean-start.txt")
fill_row_blue(bit)
bit.draw()

png

Pre and Post Conditions

When composing a solution from smaller pieces, it is essential to consider the pre-conditions and post-conditions of the samller parts.

This helps us to fit the parts together.

In the context of Bit, you might ask yourself:

When this function starts
- where is Bit in the grid?
- which direction is Bit facing?
When this function finishes
- where will Bit be?
- which direction will Bit be facing?

It will be very difficult to take the next step if you don’t know where the first step landed you.

The pre and post conditions of a function for a “contract” for that function.

What context do you promise to the function?

What results does the function promise to you?

This contract defines the abstraction the function represents.

You don’t have to care about how the function does the job, you just care that the function will work when you meet its starting expectations and do what it promised.

Example: Bake a cake

Oven contract:
- Pre-heat oven to 350 degrees
- Timer set for 30 minutes
- Stick cake batter in
- Get baked cake back
Pre conditions: oven assumes it is turned on and pre-heated and you have set the timer for 30 minutes
Invocation: you stick the cake batter in
Post conditions: you get a cake back.

I don’t care whether the oven uses electricity or gas, or even super-heated plasma fields, as long as it meets my expectations of what an “oven” is and does, i.e. that if I preheat it, set a timer, and insert batter, I’m going to get a cake at the end.

When the execution of an abstraction fails to fulfill the contract, you have a bug.

Whenever your code does something unexpected, it is because some piece is not true to the intended abstraction.

👆🏼

When your code isn’t working right, don’t just through in nots and bit.move()s in random places and hope that fixes things.

Review your abstractions: what are the contracts you have created within your code?

Does each piece accurately fulfill its contract?

Draw pictures!

Use comments or docstrings to clarify your expectations.

def fill_row_blue(bit):
    """Fill an entire row with blue paint
    Expect:
    - bit is facing up
    Should:
    - fill the full row to the right blue
    - not crash at the end of the row
    - return to the beginning of the row
    - end in the same orientation that it started
    """

    # Turn to face down the row
    bit.right()

    # Paint current square
    bit.paint("blue")

    # Fill in the rest of the row
    while bit.front_clear():
        bit.move()
        bit.paint("blue")

    # Now go back
    bit.left()
    bit.left()
    while bit.front_clear():
        bit.move()

    # Re-orient Bit
    bit.right()

Challenge: write `fill_world_blue`

Make a drawing to guide your thinking
Be mindful of the abstraction contracts: the pre/post conditions of each step

Two-row Milestone

Write code to fill just the first two rows.

See how the steps fit together. What is the “glue” that holds the pieces together?

How do I get the first row filled?

This is a single line of code. Think function call.

How can I get the second row filled?

After the first line of code completes, what will the state of the Bit world be?

What do I need to do from there to get the second line filled?

I’ll want to use fill_row_blue again–where does Bit need to be to make that work?

What do I need to do to get from the end of line 1 to the next call to fill_row_blue?

Build the loop

After the second row is filled, where will Bit be?

What do I need to do from there to be ready to fill the next row?

How will I know when to stop?

The Iteration Pattern

I have a problem that can be solved by doing the same thing repeatedly.

I have a condition that tells me that I’m done iterating.

while <I'm not done>:
    <Do the step>

Fill the Ocean

Write it in PyCharm

def fill_the_ocean(bit):
    """Fill the grid with blue
    Expect:
    - Bit is facing up
    Should:
    - Fill the whole grid blue
    """
    fill_row_blue(bit)
    while bit.front_clear():
        bit.move()
        fill_row_blue(bit)

bit = Bit.load("blue-ocean-start.txt")
fill_the_ocean(bit)
bit.draw()

png

👏🏽 👍🏻 💪🏻 🎉

The Power of Abstraction

The process of decomposition is the process of creating abstractions that work together to solve a bigger problem.

You can think: I can solve a small problem. If I’m clear about the pre and post conditions of that small solution, then I can glue it together with other small solutions to create a bigger solution.

I can do this over and over until the primary problem is solved.

Did I Just See the Iteration Pattern?

Step: solve a small piece of the problem and put it together with other small pieces

Am I done?: is the primary problem solved?

Not Just About Code

The power of abstraction and decomposition is not just about code.

This is life.

Do you have a big problem that feels overwhelming? Break it down.

Keep breaking it down until the piece seems managable.

Understand how the pieces fit back together.

Start solving small problems until the big problem is solved.

As you develop your skills at breaking down big problems into well-defined, useful abstractions that fit together into a full solution, your ability to do great things increases.

Heavenly Father will use you to accomplish His great work.

The Plan of Salvation

while <Not yet perfected>:
    Repent daily
    Rely upon the merits of Jesus Christ
    Receive His grace line upon line

Functions and Decomposition

Decomposition

Functions

Functions

Function syntax

Function scope

Divide and Conquer

Abstraction!

How to call a function

Order of execution

The Big Picture - Functions Calling Functions!

Decomposition in Action

Decomposition 1: Blue Ocean

Pre and Post Conditions

Challenge: write fill_world_blue

Two-row Milestone

How do I get the first row filled?

How can I get the second row filled?

Build the loop

The Iteration Pattern

Fill the Ocean

The Power of Abstraction

Did I Just See the Iteration Pattern?

Not Just About Code

The Plan of Salvation

Challenge: write `fill_world_blue`