How to Design a Program?

Designing a program is a mixture of creativity and rigorous thinking. 

Informal Specification 

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.

Examples

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.

Exploration

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?

Simplicity is especially important, since it makes many of the other factors easier to achieve. If a design is complex, the best we can say is that it is not yet in its definitive form. Next to simplicity is completeness, that is, the design has all the functionality it needs, so that it can be used as a building block.

When coming up with examples it can be clear that the specification has to be changed. The most important step is testing. It closes the loop: it gives feedback from the coding step back to the specification step.