Stepwise Refinement
Stepwise Refinement by Functional
Decomposition
- Stepwise refinement: design a problem solution by
- stating the solution at a high level
- refining steps of the solution into simpler steps
- repeating step 2, until steps are simple enough to execute
- Decompose based on function of each step
- Makes heavy use of pseudocode
Example
- Problem: Print the count and average of a sequence of positive
integers
- Initial Solution:
- Initialize data
- Get data
- Calculate results
- Output results
- Refinement:
- Initialize data
- get data
- 2.1 loop
- 2.2 get integer x
- 2.3 exit when x < 1
- 2.4 process x
- Calculate results
- 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
Application to Module Design
- Same technique can be used to decompose a system into modules
- Begin with main module
- Break a module into submodules
- Repeat step 2 until modules are small and easily written
- Use stepwise refinement on individual modules
Module Design Goal
- According to David Parsons (and others) a good design should
- Maximize Cohesion
- Minimize Coupling
- Cohesion: Procedure have one well defined task
- Coupling: Don't access global data or data from another module
- 324 Students: Does this sound familiar?
Structure chart
- Modules
- Parameters and return values
- logical
- data
- If and loop
Example
- Update customer master file with transaction records
Top Down and Bottom Up
- Note that the example above is a top down solution
- Top down: solve a problem by breaking a solution into smaller
and smaller parts
- Bottom up: solve a problem by joining simpler functions to make
more and more complex functions
- Most people use a combination of top down and bottom up
Top Down vs Bottom Up
- Advantages of top down
- Relatively easy
- Defer implementation details (put in bottom modules)
- Top down testing
- Disadvantages of top down
- Hard to identify top functions (is there a simple function at
the top?)
- No natural hierarchy
- Bottom up strength
- Identifies system utilities that can be reused
- Bottom up weakness
- Hard to do entire system from bottom up