Designing a program is a mixture of creativity and rigorous thinking.
Write down as precisely as we can what the program should do. What are the inputs and outputs? How do the outputs relate to the inputs? This description is called an informal specification. We call it informal because it is written in English. Formal specifications are written in a mathematical notation.
To make the specification clear, come up with examples of what the program does in particular cases. The examples should stress the program: use it in boundary conditions and in the most unexpected ways we can imagine.
To find out what programming techniques we will need, a good way is to use the interactive interface to experiment with program fragments. The idea is to write small operations that we think might be needed for the program. We use the operations that the system already provides as a basis. This step gives us a clearer view of what the program's structure should be.
Structure and Coding
At this point we can lay out the program's structure. We make a rough outline of the operations needed to calculate the outputs from the inputs and how they fit together. We then fill in the blanks by writing the actual program code. The operations should be simple: each operation should do just one thing. To improve the structure we can group related operations in modules.
Testing and Reasoning
Now that we have a program, we must verify that it does the right thing. We try it on a series of test cases, including the examples we came up with before. We correct errors until the program works well. We can also reason about the program and its complexity, using the formal semantics for parts that are not clear. Testing and reasoning are complementary: it is important to do both to get a high quality program.
Judging the Quality
The final point is to step back and judge the design's quality. There are many factors involved in quality:
- Does the design solve the right problem?
- Is it correct?
- Is it efficient?
- Is it maintainable?
- Is it extensible?
- Is it simple?