Stepwise refinement
Stepwise refinement refers to the progressive refinement in small steps of a program specification into a program. Sometimes, it is called top-down design.
The term stepwise refinement was used first in the paper titled Program Development by Stepwise Refinement by Niklaus Wirth, the author of the programming language Pascal and other major contributions to software design and software engineering, in the Communications of the ACM, Vol. 14 (4), 1971, pp. 221-227.
Wirth said, "It is here considered as a sequence of design decisions concerning the decomposition of tasks into subtasks and of data into data structures."
We use the term here mainly to describe the development of a method from its specification. We will see small steps, like breaking a high-level statement into a sequence of statements, introducing a local variable, translating an English statement into Java, and introducing a method.
1. Changing time formats
We develop a function to translate a time of day from 24-hour format into conventional AM-PM format. Three important kinds of stepwise refinement are used: Implementing a task as a sequence of 3 subtasks, making a refinement into a case analysis instead of directly into Java, and using the mañana principle. The video is 6 minutes long. Read it here. times.pdf.
2. Anglicizing an integer
Anglicize means to adapt (a foreign word, name, or phrase) to English usage. According to the Merriam-Webster online dictionary, the first known use of the word was in 1710. Here, we develop a method to anglicize integers ---to turn integers like 1710 into words: one thousand seven hundred ten. It's amazing how stepwise refinement results in a simple method, and the development incorporates recursion in a natural way. The video 8.2 minutes long. Read it here: anglicize.pdf
3. Evaluating an expression
We develop a method that evaluates and returns the value of expressions like these: " 52 + 71 -1 -652 ". Two important techniques are used (1) structure a loop to reflect the structure of the data that it processes. (2) mañana principle. The video is 4:51 minutes long. Read it here: eval.pdf
4. Edgar Allan Poe and "The Raven"
"The Raven" is a famous poem by Edgar Allan Poe. Poe also wrote an essay titled "The "Philosophy of Composition", in which he describes how he developed "The Raven". It is pure top-down design / stepwise refinement! Click the image to the left to watch our account of it, with Paul Gries reading parts of the poem. Click for The Raven and the essay:
In these videos, you have seen stepwise refinement being used in several ways:
1. Implementing a task as a sequence of tasks.
2. Refining a difficult problem into two steps rather than one: first giving a case analysis, then translating into Java.
3. Using the mañana principle: seeing the need for a method, stubbing it in and writing calls on it, and then later (tomorrow, mañana) writing the method body.
4. Alternating testing with development: after each step of development, test that the development was correct.
5. Introducing a local variable for efficiency purposes.
6. Breaking a development into several pieces. For example, figuring out how to deal with the integer 234 without worrying about anglizing it (produce 234/100, " hundred", and 234%100) and then figure out how to anglicize 234/100 and 234%100.
7. Structuring a loop to reflect the structure of the data it processes.
8. Separation of concerns: A key point is to focus on one thing at a time and handle it properly. The phrase separation of concerns was coined by Edsger Dijkstra.