Software Development

🧩 15.02 Program design using structure charts

Another approach to modular design is to choose the sub-tasks and draw a structure chart showing how the modules relate. Each box is a module; each level is a refinement of the level above.

A structure chart also shows the interface between modules: the variables passed between them, called parameters (Section 14.10). A parameter supplying a value to a lower-level module is drawn as a downward arrow; one supplying a new value back to the module above is drawn as an upward arrow.

Averages Figure 15.03

The top box (level 0) names the module. It is refined into three level-1 sub-tasks. Number1 and Number2 come up from INPUT numbers, go down into Calculate average, and Average comes back up and is passed down to OUTPUT average. This parameter passing is the interface.

🔀 Selection and repetition in a structure chart

Structure charts can also show control information. The number-guessing game from Section 12.06 can be modularised like this:

The diamond is a condition that is either TRUE or FALSE, so one branch or the other is followed.

Figure 15.05 is the pyramid-drawing program from Worked Example 12.10. The semi-circular arrow means the modules underneath it are repeated; the label gives the loop condition.

🔴 Connect 4 Figure 15.06

Structure charts help programmers see how modules relate and how they interface, which matters more as the problem grows. Figure 15.06 is the chart for the Connect 4 program (Task 13.06). Two extra symbols:

• An arrow with a solid round end (●→) shows the value passed is a flag (a Boolean).
• A double-headed arrow (←○→) shows the variable's value is updated within the module.

📜 15.03 Deriving pseudocode from a structure chart

Back to the pyramid (Figure 15.05). In Worked Example 12.10 every variable was global. Now we use local variables and parameters, so each module is self-contained and a change to a variable cannot accidentally affect a value elsewhere.

The top-level module, Pyramid, calls four modules. Each call supplies its parameters in brackets after the module identifier:

MODULE Pyramid
    CALL SetValues(NumberOfSymbols, NumberOfSpaces, Symbol, MaxNumberOfSymbols)
    REPEAT
        CALL OutputSpaces(NumberOfSpaces)
        CALL OutputSymbols(NumberOfSymbols, Symbol)
        CALL AdjustValuesForNextRow(NumberOfSpaces, NumberOfSymbols)
    UNTIL NumberOfSymbols > MaxNumberOfSymbols
ENDMODULE

PROCEDURE SetValues(NumberOfSymbols, NumberOfSpaces, Symbol, MaxNumberOfSymbols)
    INPUT Symbol
    CALL InputMaxNumberOfSymbols(MaxNumberOfSymbols)
    NumberOfSpaces ← (MaxNumberOfSymbols - 1) / 2
    NumberOfSymbols ← 1
ENDPROCEDURE

PROCEDURE InputMaxNumberOfSymbols(MaxNumberOfSymbols)
    REPEAT
        INPUT MaxNumberOfSymbols
    UNTIL MaxNumberOfSymbols MOD 2 = 1
ENDPROCEDURE

PROCEDURE OutputSpaces(NumberOfSpaces)
    FOR Count ← 1 TO NumberOfSpaces
        OUTPUT Space      // without moving to next line
    NEXT Count
ENDPROCEDURE

PROCEDURE OutputSymbols(NumberOfSymbols, Symbol)
    FOR Count ← 1 TO NumberOfSymbols
        OUTPUT Symbol     // without moving to next line
    NEXT Count
    OUTPUT Newline        // move to the next line
ENDPROCEDURE

PROCEDURE AdjustValuesForNextRow(NumberOfSpaces, NumberOfSymbols)
    NumberOfSpaces ← NumberOfSpaces - 1
    NumberOfSymbols ← NumberOfSymbols + 2
ENDPROCEDURE

Note that a structure chart does not say how parameters are passed: by reference or by value. Here SetValues, InputMaxNumberOfSymbols and AdjustValuesForNextRow change their parameters, so those must be passed BYREF for the changes to reach Pyramid.

Teacher's note: the chart's label says "UNTIL NumberOfSymbols = MaxNumberOfSymbols", but the pseudocode tests >. Because NumberOfSymbols grows by 2 after the row is printed, testing = would stop one row early and miss the base. Trust the pseudocode.

MODULE Averages
    CALL InputNumbers(Number1, Number2)
    CALL CalculateAverage(Number1, Number2, Average)
    CALL OutputAverage(Average)
ENDMODULE

PROCEDURE InputNumbers(BYREF Number1 : REAL, BYREF Number2 : REAL)
    INPUT Number1
    INPUT Number2
ENDPROCEDURE

PROCEDURE CalculateAverage(BYVAL Number1 : REAL, BYVAL Number2 : REAL, BYREF Average : REAL)
    Average ← (Number1 + Number2) / 2
ENDPROCEDURE

PROCEDURE OutputAverage(BYVAL Average : REAL)
    OUTPUT "The average is ", Average
ENDPROCEDURE

MODULE NumberGuessingGame
    CALL GenerateSecretNumber(SecretNumber)
    CALL InputGuess(Guess)
    CALL OutputMessage(Guess, SecretNumber)
ENDMODULE

PROCEDURE GenerateSecretNumber(BYREF SecretNumber : INTEGER)
    SecretNumber ← INT(RAND(100)) + 1     // 1 to 100
ENDPROCEDURE

PROCEDURE InputGuess(BYREF Guess : INTEGER)
    OUTPUT "Guess a number: "
    INPUT Guess
ENDPROCEDURE

PROCEDURE OutputMessage(BYVAL Guess : INTEGER, BYVAL SecretNumber : INTEGER)
    IF Guess = SecretNumber
        THEN
            OUTPUT "Well done, you guessed it!"            // OUTPUT congratulation
        ELSE
            OUTPUT "Sorry, the number was ", SecretNumber  // OUTPUT consolation message
    ENDIF
ENDPROCEDURE

MODULE Connect4
    CALL InitialiseBoard(Board)                      // Board ↑
    CALL SetUpGame(ThisPlayer, GameFinished)         // ThisPlayer ↑, GameFinished ●↑
    WHILE NOT GameFinished
        CALL PlayerMakesMove(Board, ThisPlayer)      // Board ↕, ThisPlayer ↓
        CALL OutputBoard(Board)                      // Board ↓
        CALL CheckGameFinished(Board, ThisPlayer, GameFinished)
        IF NOT GameFinished
            THEN
                CALL SwapPlayer(ThisPlayer)          // ThisPlayer ↕
        ENDIF
    ENDWHILE
ENDMODULE

PROCEDURE PlayerMakesMove(BYREF Board : ARRAY, BYVAL ThisPlayer : CHAR)
    CALL PlayerChoosesColumn(Board, ColumnNumber)    // ColumnNumber ↑
    CALL FindFreeRow(Board, ColumnNumber, RowNumber) // RowNumber ↑
    Board[RowNumber, ColumnNumber] ← ThisPlayer
ENDPROCEDURE

🚦 15.04 Program design using state-transition diagrams

A computer system can be seen as a finite state machine (FSM). An FSM has a start state, and an input makes it change (transform) from one state to another. The information about the states can be set out in a state-transition table.

Table 15.01 State-transition table

• In state S1, input a causes no change of state; input b transforms S1 to S2.
• In state S2, input b causes no change; input a transforms S2 to S1.

A state-transition diagram describes the same behaviour. The start state has an arrow with a dot on its tail (●→). If the FSM has a final (halting) state, it is drawn as a double circle (S1 here).

If an input causes an output, the label has a vertical bar: input | output. In Figure 15.08, in state S1 the input b produces output c and moves the FSM to S2. An FSM with outputs is also called a Mealy machine.

🐞 15.05 Types of error

Why errors occur and how to find them

Software may not do what it should because:

• The programmer made a coding mistake
• the requirements specification was not drawn up correctly
• the software designer made a design error
• the user interface is poorly designed and the user makes mistakes
• the computer hardware fails.

If the end user finds the error, that is bad for the developer's reputation, so software must be tested before release. Research shows that the earlier an error is found, the cheaper it is to fix, so testing goes on throughout development. The purpose of testing is to discover errors. As the Dutch computer scientist Edsger Dijkstra put it, testing can show the presence of bugs, but never their absence.

Syntax errors are the easy ones: the compiler or interpreter finds them and usually gives a hint. Many editors flag them as you type. A program that compiles successfully has no syntax errors left. With an interpreter that is not true: only statements about to be executed are syntax-checked, so an untested program may still hide syntax errors (Chapter 8, Section 8.05; Chapter 20, Section 20.06).

Figure 15.11: the compiler stops when it first notices the error, and the error is often on the previous line, because it cannot tell until it reaches the next line and finds an unexpected keyword.

Much harder to find are logic errors and run-time errors. A run-time error happens when execution comes to an unexpected halt ("crash") or goes into an infinite loop and "freezes".

Both can only be found by careful testing. They may appear only in certain circumstances: a program that crashes every time is obviously wrong, but one that works for months until one data set makes it fail is much harder to catch, sometimes only after serious consequences.

🧪 15.06 Testing methods

Stub testing Figure 15.12

You may want to test a user interface before all its facilities exist. Write a stub for each procedure: a body containing only an output statement that confirms the call was made. Each menu option then calls its stub.

Black-box testing

The programmer can see the code (white-box testing, below). A program should also be tested by people who cannot see the code and do not know how it was written. They read the specification, devise test data, work out the expected results, run the program and record the actual results. The program is a "black box". Test data usually includes normal, extreme/boundary and erroneous/abnormal values.

Where actual and expected results differ, there is a problem. Black-box testing shows that there is an error; debugging software or dry-running is then used to find the lines that need correcting (Section 15.08).

White-box testing

To check that the code itself works, choose test data that checks every path through it.

✍️ Dry-running an algorithm

A good way to check that an algorithm works is to dry-run it with a trace table and different test data, also called a walk through. You write down the current contents of every variable and condition at each step.

These testing methods are used early in development, for example as individual modules are written. Sometimes programmers use them on their own code; larger organisations employ separate software testers.

Integration, alpha, acceptance and beta testing

Software is often many modules written by different programmers. Each may pass its own tests, but once they are joined, the whole program must be tested: integration testing, usually done incrementally (add one module, test again, then add the next).

Before release, in-house testers carry out alpha testing. Bespoke software (written for a specific customer) is then handed over, and the customer checks it meets their requirements: acceptance testing, usually part of hand-over; when it passes, the customer signs off the software.

Software for general sale has no single customer, so after alpha testing a version is released to a limited audience of beta testers, who use it in their own environments and report problems back so the software house can fix them: beta testing.

🗺️ 15.07 Test strategy, test plans and test data

During the design stage, a testing strategy must be worked out so the software is tested rigorously from the very beginning. Decide which testing methods suit the project and produce a carefully designed test plan.

Large programs cannot be tested exhaustively, but systematic testing should find as many errors as possible. First an outline test plan, for example:

• flow of control: does the user get appropriate choices, and does the chosen option go to the correct module?
• validation of input: has all data been entered into the system correctly?
• do loops and decisions perform correctly?
• Is data saved into the correct files?
• does the system produce the correct results?

The outline is then turned into a detailed test plan. To carry out the tests we choose test data: unlike real, live data, it is chosen specifically to test different possibilities.

Table 15.07 Types of test data

How to prevent errors

The best way to get a program that works is to prevent errors in the first place. A major cause of errors is poor requirements analysis, so understand the problem and what the user wants or needs. Use:

• tried and tested design techniques, such as structured programming or object-oriented design
• conventions such as identifier tables, data structures and standard algorithms
• tried and tested modules or objects from program libraries.

🔧 15.08 Corrective maintenance

Programs don't wear out or need lubricating like machines. Corrective maintenance is the work needed when a program does not work correctly because of a logic error or a run-time error. Some errors only show up after a long time, under rare circumstances: a part of the program that is seldom used, or data that occasionally includes extreme values. Earlier corrective maintenance can also introduce new errors.

When a problem is reported, the programmer finds the cause of the bug with debugging software or a trace table (Section 15.06).

INPUT BinaryString
StringLength ← Length(BinaryString)
FOR i ← 1 TO StringLength
    Bit ← BinaryString[i]
    BitValue ← IntegerValue(Bit)   // convert string to integer
    DenaryValue ← DenaryValue + 2 + BitValue
NEXT i

INPUT BinaryString
StringLength ← Length(BinaryString)
DenaryValue ← 0
FOR i ← 1 TO StringLength
    Bit ← BinaryString[i]
    BitValue ← IntegerValue(Bit)
    DenaryValue ← DenaryValue * 2 + BitValue
NEXT i
OUTPUT DenaryValue

🧭 15.09 Adaptive maintenance

Programs are often changed so they can do things they were not originally designed to do. The Connect 4 game (Worked Example 13.03) lets two players, O and X, play each other. An amended version could make one player the computer, so one person can play against it.

PROCEDURE ComputerChoosesColumn(BYREF Board : ARRAY, BYREF ColumnNumber : INTEGER)
    // 1. Win if possible
    FOR Col ← 1 TO 7
        IF ColumnHasSpace(Board, Col) AND MoveWins(Board, Col, 'X')
            THEN
                ColumnNumber ← Col
                RETURN
        ENDIF
    NEXT Col
    // 2. Block the opponent's winning move
    FOR Col ← 1 TO 7
        IF ColumnHasSpace(Board, Col) AND MoveWins(Board, Col, 'O')
            THEN
                ColumnNumber ← Col
                RETURN
        ENDIF
    NEXT Col
    // 3. Otherwise prefer the centre, else any column with space
    IF ColumnHasSpace(Board, 4)
        THEN
            ColumnNumber ← 4
        ELSE
            REPEAT
                ColumnNumber ← INT(RAND(7)) + 1
            UNTIL ColumnHasSpace(Board, ColumnNumber)
    ENDIF
ENDPROCEDURE

✨ 15.10 Perfective maintenance

The program works, but there is still room to improve it. For example, it might run faster if file handling changed from sequential access to direct access.

FUNCTION GetPositiveNumber
    DECLARE n : INTEGER
    OUTPUT "Enter a positive number: "
    INPUT n
    RETURN n
ENDFUNCTION
// main program
REPEAT
    Number1 ← GetPositiveNumber
    IF Number1 <= 0
      THEN
        OUTPUT "Not a positive number: "
    ENDIF
UNTIL Number1 > 0
REPEAT
    Number2 ← GetPositiveNumber
    IF Number2 <= 0
      THEN
        OUTPUT "Not a positive number: "
    ENDIF
UNTIL Number2 > 0

FUNCTION GetPositiveNumber() RETURNS INTEGER
    DECLARE n : INTEGER
    OUTPUT "Enter a positive number: "
    INPUT n
    WHILE n <= 0
        OUTPUT "Not a positive number. Enter a positive number: "
        INPUT n
    ENDWHILE
    RETURN n
ENDFUNCTION

// main program
Number1 ← GetPositiveNumber()
Number2 ← GetPositiveNumber()

📌 Summary

• The program development cycle has the stages analysis, design, coding, testing and maintenance.
• Structure charts are graphical representations of the modular structure of a solution.
• A structure chart shows the interface between modules: the parameters passed between the calling module and the module called.
• Structure charts show selection (a module called only under certain conditions) and repetition (modules called repeatedly).
• A state-transition diagram is another way of documenting an algorithm.
• Testing strategies include stub testing, black-box testing, white-box testing, integration testing, alpha and beta testing, and acceptance testing.
• Logic errors and run-time errors can be located and corrected by dry-running an algorithm or using a trace table.
• Corrective maintenance fixes bugs that come to light while the program is in use.
• Adaptive maintenance alters the algorithm and data structures in response to required changes.
• Perfective maintenance enhances performance or maintainability.

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my mark-scheme-style points, not official mark schemes.

1 Consider this function:

FUNCTION Binary(Number : INTEGER) RETURNS STRING
    DECLARE BinaryString : STRING
    DECLARE PlaceValue : INTEGER
    BinaryString ← ''            // empty string
    PlaceValue ← 8
    REPEAT
        IF Number >= PlaceValue
          THEN
            BinaryString ← BinaryString & '1'   // concatenates two strings
            Number ← Number - PlaceValue
          ELSE
            BinaryString ← BinaryString & '0'
        ENDIF
        PlaceValue ← PlaceValue DIV 2
    UNTIL Number = 0
    RETURN BinaryString
ENDFUNCTION

2 A procedure to output a row in a tally chart:

PROCEDURE OutputTallyRow(NumberToDraw : INTEGER)
    IF Count > 0
      THEN
        FOR Count ← 1 TO NumberToDraw
            IF (Count MOD 5) = 0
              THEN
                OUTPUT('\')    // every 5th bar slants the other way
              ELSE
                OUTPUT('/')
            ENDIF
        NEXT Count
    ENDIF
    OUTPUT NewLine             // move to next row
ENDPROCEDURE

3 A random number generator is to be tested to see whether all numbers from 1 to 20 are generated equally often. In structured English:

Initialise a tally for the numbers 1 to 20
Repeatedly generate numbers in range 1 to 20
For each number generated, increment the relevant count
Calculate how often each number should be generated (expected frequency)
Output expected frequency
Output the list of numbers as a table with actual frequency

CONSTANT NumberOfTests = 1000
DECLARE Tally : ARRAY[1:20] OF INTEGER
DECLARE RandomNumber : INTEGER

MODULE RandomNumberTally
    CALL InitialiseTally(Tally)
    FOR Test ← 1 TO NumberOfTests                  // 1000 times
        CALL GenerateRandomNumber(RandomNumber)
        CALL UpdateTally(RandomNumber, Tally)
    NEXT Test
    CALL OutputTally(Tally)
ENDMODULE

PROCEDURE InitialiseTally(BYREF Tally : ARRAY)
    FOR i ← 1 TO 20
        Tally[i] ← 0
    NEXT i
ENDPROCEDURE

PROCEDURE GenerateRandomNumber(BYREF RandomNumber : INTEGER)
    RandomNumber ← INT(RAND(20)) + 1                 // 1 to 20
ENDPROCEDURE

PROCEDURE UpdateTally(BYVAL RandomNumber : INTEGER, BYREF Tally : ARRAY)
    Tally[RandomNumber] ← Tally[RandomNumber] + 1
ENDPROCEDURE

PROCEDURE OutputTally(BYVAL Tally : ARRAY)
    DECLARE ExpectedFrequency : INTEGER
    ExpectedFrequency ← NumberOfTests DIV 20
    OUTPUT "Expected frequency: ", ExpectedFrequency
    OUTPUT "Number   Actual frequency"
    FOR i ← 1 TO 20
        OUTPUT i, "        ", Tally[i]
    NEXT i
ENDPROCEDURE

4 A car park has a barrier at the exit. It starts lowered. To exit, the driver inserts a coin; the barrier raises and lets the car out, then lowers after the car has passed. In an emergency, staff can open the barrier with a remote control; it stays open until the remote control lowers it again. The three states are lowered, raised and open: