Slide 1

Today: many basic examples, observations about loops, top-down decomposition

Announcments:

• Assignment 1 has been released
  • It is due Tuesday, June 28th, 11:59pm, PDT
  • You will complete a bunch of Bit programming problems
  • Some of them are challenging!
  • Come to LaIR or Office Hours, or post on Ed if you need help

Slide 2

Tricky Case: Double Move

Here is new problem in the "bit if" section - double move. The idea here is that bit paints the 2nd, 4th, etc. moved-to squares red, leaving the others white. This requires two moves within the loop.

> double-move (while + two moves in loop)

The code below is a good first try, but it generates a move error for certain world widths. Why? The first move is safe, but the second will make an error if the world is even width. Add an if-statement, so the second move and paint are only done when it is legal.

    while bit.front_clear():
        bit.move()
        bit.move()
        bit.paint('red')

Usually you run your code one case at a time, using the Run All option as a final check that all the cases work. In this case, Run All reveals that some cases have a problem with the above code.

The Falling Water problem in the puzzle section also demonstrates this issue.

> falling-water

Slide 3

Decomposition - Program and Functions

"Divide and Conquer" - a classic strategy, works very well with computer code

• "Decomposition" - touching on this topic today, more later
• Divide a program into functions
• One function for each sub-situation
• "Call" the right function when that situation appears
• This works well - a bit magical
  Write the function once
  Just call the function when we need that situation solved

Slide 4

Program Made of Functions

Our big picture - program made up of functions

Slide 5

Decomposition Strategy - Divide and Conquer

• Confronted with a giant code problem
  Looks impossible
• Divide into more manageable sub-problems
  aka "helper" functions
• Work on the smaller, helper functions, not so bad
• Mesh the functions together to solve the whole thing
• Divide and Conquer is a simple strategy
  It's also how all CS is done, like this is our one big strategy idea
• Today: decompose out a helper function

Slide 6

Big Picture - Browser Example

• Think about the code of a web browser
• PNG images, urls, HTML, inline video, network packets, SSL encryption, DOM tree, ...
• You cannot keep the code for all of that in your head
• It is millions of lines of code
• But you can imagine a function that solves one part of it
  render_png_image()
  check_ssl_keys()
• This is how CS works
• Decompose into Functions
• Work on each function separately

Slide 7

Functions - The Wizard of EarthSea

In the Wizard of EarthSea novels by Ursula Le Guin .. each thing in the world has its secret, true name. A magician calls a thing's true name, invoking that thing's power. Strangely, function calls work just like this - a function has a name and you call the function using its name, invoking its power.

Slide 8

How To Call a Function

We've seen def many times - defines a function. Recall that a function has a name and body lines of code, like this "go_west" function:

def go_west(bit):
    bit.left()
    bit.paint('blue')
    ...

To "call" a function means to go run its code, and there are two common ways it is done in Python. Which way a function is called is set by its author when the function is defined.

Slide 9

1. Call by noun.verb

For "object oriented" code, which is how bit is built, the function call is the noun.verb form, e.g. bit.left(). Here "left" is the name of the function. Your code will call bit functions like this, but your own functions will use the more common "def" form below.

Slide 10

2. Call by name

For a function with a regular def, like this:

def go_west(bit):
    bit.left()
    bit.paint('blue')
    ...

The function call is formed by the function's name with parenthesis after it, like this:

    ...
    go_west(bit)
    ...

Slide 11

What Does Function Call Do?

Say the program is running through some lines, which we'll call the "caller" lines. Then the run gets to the following function call line; what happens?

    # caller lines
    bit.right()
    go_west(bit)  # what does this do?
    bit.left()
    ...

What the go_west(bit) directs the computer to do: (a) go run the lines inside the "go_west" function, suspend running here in the caller. (b) When go_west() is done, return to this exact spot in the caller lines and continue running with the next line. In other words, the program runs one function at a time, and function-call jumps over to run that function.

Slide 12

Decomposition 1 - Fill World Blue

This example demonstrates bit code combined with divide-and-conquer decomposition. The program is decomposed into two functions.

> Fill Example

The whole program does this: bit starts at the upper left facing down. We want to fill the whole world with blue, like this

Program Before:

Program After:

Slide 13

1. - Decompose fill_row_blue() "helper" function

First we'll decompose out a fill_row_blue() function that just does 1 row.

This is a "helper" function - solves a smaller sub-problem.

fill_row_blue() Before (pre)

fill_row_blue After (post):

We could have you write the code for this one, but we're providing it today to get to the next part.

Run the fill_row_blue a few times, see what it does. (Case-1 in the menu is the fill_row_blue test case).

Slide 14

Function Pre/Post Conditions

• We want to divide the whole program into functions
  Divide And Conquer!
• Careful about each functions boundaries, so they fit together
• Think about their pre/post conditions
• Pre - precondition of function
  state of world required before it runs
• Post - postcondition after it runs
  state of world promised after it's finished
• Pre/Post make the "contract" of function - what it does
  What it gets to assume when it is called
  What it promises to provide

Slide 15

Pre/Post - Why Do I Care?

• We are building a program of multiple functions
  This practice is huge productivity booster
• Need to make sure the functions mesh together
• Can we just call a function any old time?
• No - need to meet its pre conditions
• Suppose we want to call a() and then call b() - what's required?
• First check a() pre, make sure we have those conditions
• Then check the a() post, make adjustments to fit the b() pre

Slide 16

Look at fill_row_blue() Function

• Pre: bit is at left edge facing down
• Post: the horizontal row is all blue, bit is back at the exact start location and direction
• Convention: it's not required, but a post condition where bit returns to its original location is simple and easy to keep in mind, so we often do it that way.

def fill_row_blue(bit):
    bit.left()
    bit.paint('blue')
    while bit.front_clear():
        bit.move()
        bit.paint('blue')
    bit.right()
    bit.right()
    while bit.front_clear():
        bit.move()
    bit.left()

-Now comes the key, magic step for today. First, know what fill_row_blue() does exactly, pre/post.

Slide 17

Challenge: Write fill_world_blue()

• Now write the fill_world_blue() function to solve the whole world
• Make a drawing to guide thinking
• Mindful of pre/post conditions

Slide 18

2 Row Milestone

As an experiment write code to just solve the first 2 rows, without a loop. This is a test "milestone", working out that some things work, but without solving the whole thing.

Slide 19

1. How can I get the 1st row filled?

This can be done with 1 line of code. Think function-call.

Slide 20

2. How can I get the 2nd line filled?

Where is bit and with what facing after the code above?

Slide 21

fill_world_blue() Functions - A Great Deal!

• Replace the milestone code, solving the whole thing
• Key Idea: call fill_row_blue() to solve that sub-problem
• Like you're the boss - do what I say!
• Think about its pre/post conditions when calling
• Questions: how are you going to fill that first row? later rows?
• Sketch the state of the world to think about progress
• Try using "End State" checkbox to skip to end-state output

Slide 22

Decomposition 2: Cover

> Cover Example

Bit starts next to a block of solid squares (these are not "clear" for moving). Bit goes around the 4 sides clockwise, painting everything green.

Cover Before (pre):

cover_side() Helper After (post):

cover_square() After (post):

Slide 23

1. Run cover_side()

cover_side(bit): Move bit forward until the right side is clear. Color every square green. (demonstrates not left-clear test).

Run this code with case-1, see what it does. Study the code to see how it works, think about its pre/post (make a little drawing).

Slide 24

2. Challenge: write code for cover_square()

cover_square(bit): Bit begins atop the upper left corner, facing right. Paint all 4 sides green. End to the left of the original position, facing up.

Add code to paint the top and right sides. Key ideas:

• Call previously defined function to do work
• Must figure on its pre/post
• Trap: think about code inside cover_side()
• Correct: think only of its pre/post
• "Like A Boss" - just call the function, it jumps to your command!
• Start with top and right sides to get the idea
• Then add the other 2 sides
• The partial bit-output works as a sort of drawing to work out the needed pre/post

Slide 25

Top-Down Decomposition Strategy

• Top-Down Decomposition recipe:
• We have problem X to solve
• Thinking up the code for solve_x() function
• Q: what would be useful helper function here?
• Q: something I could call to solve a sub-part of the problem?
• These functions do not exist yet, we are trying to think them up
• What should be the pre and post conditions of the helper?
• e.g. say we think up a function called helper()
• 1. Outline the code for solve_x(), calling helper()
• 2. Now go implement the code for helper() too
• 3. Ideally, test helper() independently .. not doing that here

Slide 26

Decomposition 3: Hurdles Example

> Hurdles

Before

After

Slide 27

Top-Down Decomposition - Hurdles

• Do this as a top-down decomposition example
• Start with the top level function that solves the whole thing
  e.g. solve_hurdles() code below
• What helper function would be helpful?
• Write solve_1_hurdle() first
• Then write helpers for that
• Keep pre/post in mind as we go

Slide 28

solve_hurdles()

• solve_hurdles() function - the "top level" function
  solves the whole thing
• Its helper could be solve_1_hurdle()
  pre: facing up start of hurdle
  post: facing up start of next hurdle

def solve_hurdles(filename):
    """
    Solve the sequence of hurdles.
    Start facing north at the first hurdle.
    Finish facing north at the end.
    (provided)
    """
    while bit.front_clear():
        solve_1_hurdle(bit)

Slide 29

solve_1_hurdle()

Helper function - solve one hurdle. If we had this, solve_hurdles would be easy. Just doing one hurdle is not so intimidating. Divide and conquer!

What helper functions would be useful here? Make observation about the 4 moves that make up a hurdle.

• Now focus on writing solve_1_hurdle()
• What are its pre/post conditions?
• What helpers would be useful in here?
• There are 4 moves, 2 moves of one type (A), 2 moves of a second type (B)
• Write a helper function for each move type
• helper a: go_wall_right() - go while wall to right
• helper b: go_until_blocked() - go until wall in front
• Running a hurdle looks somewhat like a, a, b, b
  With some turn/moves in between
• Figure out pre/post for these
• Write solve_1_hurdle() code calling them
• Then need to go write the helpers
• Divide and conquer theme: isolate a sub problem, write code for just that part

Here is a sketch, working out that there are two sub-problem types

Here is the solve_1_hurdle() code - sketching that we have go_wall_right() and go_until_blocked() helpers. Can write this before we write the helpers. Think about pre/post for each.

def solve_1_hurdle(bit):
    """
    Solve one hurdle, painting all squares green.
    Start facing up at the hurdle's left edge.
    End facing up at the start of the next hurdle.
    """
    go_wall_right(bit)
    bit.right()
    bit.move()
    go_wall_right(bit)
    bit.right()
    go_until_blocked(bit)
    bit.left()
    go_until_blocked(bit)
    bit.left()

Slide 30

Power Move: Delegation and Knowing Things

• Knowledge is Power, so they say
• Calling a helper function is like delegation
• Call it, do not think about its internal detail
• Say I call a wash_dishes() function
• I want the post condition: dishes are cleaned and not broken
• Do I care if the hand drying is counter clockwise?
• Do I care if they stand here or there?
• Do I care which lights are on?
• In CS these are called the "details" of the computation
• We care about the post condition
• Not knowing the details is power
• See in this example, calling helper functions
• Work the pre/post, keep your mind clear of the details

Slide 31

Write Two More Helpers

Now write two more helpers. Here we see the importance of the pre/post to mesh the functions together. (For lecture demo, may just use prepared versions of these.)

def go_wall_right(bit):
    """
    Move bit forward so long as there
    is a wall to the right. Paint
    all squares green. Leave bit with the
    original facing.
    """
    bit.paint('green')
    while not bit.right_clear():
        bit.move()
        bit.paint('green')


def go_until_blocked(bit):
    """
    Move bit forward until blocked.
    Painting all squares green.
    Leave bit with the original facing.
    """
    bit.paint('green')
    while bit.front_clear():
        bit.move()
        bit.paint('green')

Slide 32

Run It

When all the helpers are built, we can try running it on a few worlds. Switch to a small font so you can see all the code at once, watch the run jump around. Go, Bit go!

Some other points to clean up, if we have time.

Slide 33

Helpers At Top - Convention

There is a convention to put the smallest, helper functions first in a file. The larger functions that call them down below. This is just a habit; Python code will work with the functions in any order. Placing the helpers first does have a kind of logic — looking at solve_1_hurdle(), the functions it uses are defined above it, not after.

Slide 34

solve_1_hurdle() Helpers + Triple Quote

At the top of each function is a description of what the function does within triple-quote marks - we'll start writing these from now on. This is a Python convention known as "Pydoc" for each function. The description is just a summary of the pre/post in words.

Slide 35

Run vs. Helper Tests

Previously we had separate testing for each helper which is ideal, and we will do that again in CS106A. In this case, we just run the whole thing and see if it works without the benefit of helper tests.

Slide 36

Coding Style 1.0 - Tactics

CS106A doe not just teach coding. It has always taught how to write clean code with good style. Your section leader will talk with you about the correctness of code, but also pointers for good style.

All the code we show you will follow PEP8, so just picking up the style tactic that way is the easiest.

Python Guide - click on the Style section, we'll pick out a few things today (for hw1), re-visit it for the rest later.

• Today:
• indent 4 spaces after the colon (:), for def/while/if etc.
  See all our examples
• 1 space between elements
  e.g. 1 + 2 * 3
• We prefer single quote mark for strings like 'red'
• The word pass in Python means is a placeholder that does nothing
  Often pass in the code marks the place where you add code
  Remove the pass when you put your code in, it's just a placeholder