The Craft Of Coding

CPP 29-Feb Designing Programs

Posted by Pete Sun, 28 Feb 2016 21:41:00 GMT

For a small enough task, it is possible to start writing code immediately. This is not necessarily the best plan, but it can be feasible.For larger tasks when the program is going to be more complex, just jumping into coding is going to lead to problems.

Understanding the problem

Crazy as it may seem, no matter how clear a problem statement may look on first reading, there is going to be some complexity that is not immediately obvious. So it always pays to spend some time Exploring the Requirements, initially by just asking questions, but more usefully by generating examples that the program should and should not be able to handle.

Consider the case of a simple command line calculator, that takes the input calculation, builds a bracketed expression and then prints the result…

Calc>1+2
Expression : (1+2)=3
Calc>1+(2*3)
Expression : (1+(2*3))=7
Calc>1+2*3
Expression : ((1+2)*3)=9
Calc>
  1. What do we think we understand about the requirements?
  2. What is unclear/under-specified?
  3. What restrictions do we want to put on the program to make it easier to implement?

Using Examples to Explore Requirements

Once you have an idea about the what the program is supposed to do you can test out that idea by working through an example. If you think that operator precedence needs to be taken into account, you can create examples where this would matter and work through these examples with the people requesting the program.

Note. You will need to write down each of these examples with expected output for use as test cases that you can use to test the program (after it is written) to validate whether it implements the requirements correctly. To do this successfully you will need examples of inputs that the program is not expected to be able to process.

Design is Iterative and Incremental

Whenever you have a design idea, you can use the examples you have collected to check if the proposed mechanism will work for the examples. In most cases this will cause you to refine or rework your design ideas. The benefit of revising the design at this stage is that it is much simpler to revise your design before you have committed any time to writing code, since once code has been written you will find yourself very reluctant to delete that code and start again on a new idea.

Conceptually most programs are very similar, they have three stages that are repeated indefinitely:

  1. Input – collecting the data from users or devices using some mechanism
  2. Processing – manipulating the inputs in some way, often in combination with stored data
  3. Output – resenting the results of the processing to users (or sending it off to another device)

Historically there have been two ways of designing programs, Top Down and Bottom Up, both of which have merits, these days most people use a mixture of the two.

Top Down Design

From your understanding of the problem, write down three to seven high level steps that could be used to make the program do what it is supposed to do. For each of these high level steps,

  1. Identify the expected inputs to this step.
  2. Identify the information that this step needs to remember.
  3. Specify the outputs from this step.

An obvious check at this stage is to make sure that the inputs to a downstream step are produced by a prior step in the sequence.

Once the consistency of these steps has been confirmed, then the next part of the process is stepwise refinement, where each high level step is further decomposed into three to seven sub-steps, where we can repeat the process of identifying the inputs, stored data and outputs.

The theory behind this is that after several passes of this stepwise refinement, each sub-sub-sub-step is well enough defined for it to be easy to implement in code. All these sub parts should then naturally fit together and as a whole work to deliver the desired functionality.

Bottom Up Design

Starting with low level components that are known to work (or you know how to build), the program is incrementally built up from a very small beginning. In this approach, the complete program always works, even if the implementation is incomplete and only some inputs can be handled correctly.

The program can be continually tested with a wider variety of inputs as the functionality is built up.

The theory behind this is is that the developers can be making progress on the parts of the problem that they know how to build while in the background they can think about ways of implementing the more complex, less understood parts. All parts always work together because the program can always be tested to ensure that it works as a whole.

Design is Hard

Although as simplified prescriptions, both Top Down and Bottom Up design look workable, in practice, neither works all that well by itself. Top Down is good for getting the big picture, but Bottom Up experience is always needed or you can end up with a box labelled the magic happens here that nobody knows how to implement. Knowing the availability of well tested components is also key to success with top down design, so that the design steps can be steered to the needs of the existing components. After all, if you need a way to distribute multiple documents rapidly, email, or webserver coupled with a instant message sending a URL is a known solution rather than trying to design all the low level steps.

Tasks for the week

  1. Document your understanding of the requirements for the command line calculator.
  2. Document any questions you have about the requirements.
  3. Document your example inputs for the calculator, together with your expected outputs. These need to be in text files with no extraneous characters, so eventually you can run your program with the input file and then compare to the expected output file

    calc < inputs.txt > outputs.txt

inputs.txt

1+2
1/2

expected.txt

Calc>Expression : (1+2)=3
Calc>Expression : (1/2)=0.5
Calc>

© Pete McBreen 2016 Things are not as they seem. They are what they are. — Terry Pratchett (Thief of Time)