Stepwise refinement - Levels of abstraction

The next process is what is called stepwise refinement or decomposition. Rather than leaving step 1 as “walk to paper”, we need to be more clear than this. So, to break this step down with stepwise refinement, we could say…

1. Walk to paper.
1a. Walk to wall
1b. turn right
1c. move
1d. turn left

As this program is relatively simple, I think it can be left at just the one breakdown. However, more complicated programs will require that steps 1a, 1b, 1c, 1d and 1e are decomposed several times.

For step 2 “pick it up”, the assignment says we can assume there will always be a paper there. To be on the safe side, we might want to have a bit more detail here and put checks in place such as using an if statement to check if a paper is present. Also, we could look here at pre-conditions and post-conditions. We need to know where Karel will be after step 1 and where he needs to be to start step 3. In the breakdown of “walk to paper” I decided to leave Karel at the inside of the door facing out… so a pre-condition is that Karel needs to make 1 move to the paper. A post-condition I will set is for Karel is that he has returned to inside the house facing west which means we need to remember that as a pre-condition for step 3… returning to the start.

Breaking down part 2:

2. Pick it up
2a. Move to paper
2b. Check if paper available
2c. pick up paper
2d. turn around
2e. move (leave facing west)

Now we know that Karel is in the house, facing west we can break down step 3 as follows:

3. Return back to the start
3a. move to wall
3b. turn right
3c. move to wall

I decided to tackle point 3 a different way. Instead of sending Karel back to the couch the same way he came in… along the top and right wall. I decided to make him simply continue west till he hits the wall, then turn right and then move to the top wall.

Levels of Abstraction: Levels of abstraction was originally described by Dijkstra as a bottom-up design technique. In Dijkstra’s system each level of abstraction is composed of a group of related functions, some of which are externally visible and some of which are internal to the level. Internal functions are hidden from other levels; they can only be invoked by functions on the same level. The internal functions are used to perform tasks common to the work being performed on that level of abstraction. Each level of abstraction performs a set of services for the functions on the next higher level of abstraction.

Example

Problem: Print the count and average of a sequence of positive integers

• Initial Solution: 
1. Initialize data
2. Get data
3. Calculate results
4. Output results


• Refinement:
1. Initialize data
2. get data
• 2.1 loop
• 2.2     get integer x
• 2.3     exit when x < 1
• 2.4     process x
3. Calculate results
• 3.1 avg = sum / count
4. Output results

• Further refinement (of step 2.4):
• 2.4.1 increase count by 1
• 2.4.2 increase sum by x


• Process of refinement is complete when all steps can be easily programmed