Jackson Structured Programming

From Wikipedia, the free encyclopedia

Jackson Structured Programming or JSP is a method for structured programming based on correspondences between data stream structure and program structure. The method is closely related in concept to creating a parser for a regular expression that describes the data stream structure, but tries to build a program structure that matches more than one data stream and provides guidance and techniques to compensate the limited lookahead and the clashes between the structures of the different data streams.

JSP was originally developed in the 1970s by IT consultant Michael A. Jackson and documented in his 1975 book Principles of Program Design. Jackson's aim was to improve the general standard of COBOL programming, but the method is still useful when coding with modern programming languages such as C and Perl. And while JSP was originally geared towards writing batch-style file processing programs, its principles are still useful when programming in the small, below the level where object-oriented methods become important.

Jackson Structured Programming was seen by many as related to Warnier Structured Programming, but the latter method focused almost exclusively on the structure of the output stream.

As a method of programming, JSP is more straightforward than other structured methods, avoiding the leaps of intuition needed to successfully program using, say, top-down decomposition. And although it imposes a structure upon a program which improves its modifiability and maintainability, the structure is rather different from the type of structure advocated by Wirth, Dijkstra, et al.

1 The method
2 A worked example
3 See also
4 External links

[edit] The method

JSP uses semi-formal steps to capture the existing structure of a program's inputs and outputs in the structure of the program itself.

The intent is to create programs which are easy to modify over their lifetime. Jackson's major insight was that requirement changes are usually minor tweaks to the existing structures. For a program constructed using JSP, the inputs, the outputs, and the internal structures of the program all match, so small changes to the inputs and outputs should translate into small changes to the program.

JSP structures programs in terms of four component types:

fundamental operations
sequences
iterations
selections

The method begins by describing a program's inputs in terms of the four fundamental component types. It then goes on to describe the program's outputs in the same way. Each input and output is modelled as a separate Data Structure Diagram (DSD). To make JSP work for compute-intensive applications, such as digital signal processing (DSP) it is also necessary to draw algorithm structure diagrams -- something not envisioned by Jackson himself.

The input and output structures are then unified or merged into a final program structure, known as a Program Structure Diagram (PSD). This step may involve the addition of a small amount of high level control structure to marry up the inputs and outputs. Some programs process all the input before doing any output, whilst others read in one record, write one record and iterate. Such approaches have to be captured in the PSD.

The PSD, which is language neutral, is then implemented in a programming language. JSP is geared towards procedural languages which are not OO, such as Fortran, Pascal, Cobol, PL/1 and C. To a large degree JSP is not helpful for OO languages and declarative languages.

JSP uses a diagramming notation to describe the structure of inputs, outputs and programs, with diagram elements for each of the fundamental component types.

A simple operation is drawn as a box.

An operation

A sequence of operations is represented by boxes connected with lines. In the example below, operation A consists of the sequence of operations B, C and D.

A box labeled 'A' connected to three boxes below it labeled 'B', 'C' and 'D'

A sequence

An iteration is again represented with joined boxes. In addition the iterated operation has a star in the top right corner of its box. In the example below, operation A consists of an iteration of zero or more invocations of operation B.

A box labeled 'A' connected to a box labeled 'B' below it with a star in the top right corner

An iteration

Selection is similar to a sequence, but with a circle drawn in the top right hand corner of each optional operation. In the example, operation A consists of one and only one of operations B, C or D.

A box labeled 'A' connected to three boxes below it labeled 'B', 'C' and 'D' each with a circle in the top right hand corner

A selection

[edit] A worked example

As an example, here is how a programmer would design and code a run length encoder using JSP.

A run length encoder is a program which takes as its input a stream of bytes. It outputs a stream of pairs consisting of a byte along with a count of the byte's consecutive occurrences. Run length encoders are often used for crudely compressing bitmaps.

With JSP, the first step is to describe the structure of a program's inputs. A run length encoder has only one input, a stream of bytes which can be viewed as zero or more runs. Each run consists of one or more bytes of the same value. This is represented by the following JSP diagram.

The run length encoder input

The second step is to describe the structure of the output. The run length encoder output can be described as zero or more pairs, each pair consisting of a byte and its count. In this example, the count will also be a byte.

The run length encoder output

The next step is to describe the correspondences between the operations in the input and output structures.

The correspondences between the run length encoders inputs and its outputs

It is at this stage that the astute programmer may encounter a structure clash, in which there is no obvious correspondence between the input and output structures. If a structure clash is found, it is usually resolved by splitting the program into two parts, using an intermediate data structure to provide a common structural framework with which the two program parts can communicate. The two programs parts are often implemented as processes or coroutines.

In this example, there is no structure clash, so the two structures can be merged to give the final program structure.

The run length encoder program structure

At this stage the program can be fleshed out by hanging various primitive operations off the elements of the structure. Primitives which suggest themselves are

read a byte
remember byte
set counter to zero
increment counter
output remembered byte
output counter

The iterations also have to be fleshed out. They need conditions added. Suitable conditions would be

while there are more bytes
while there are more bytes and this byte is the same as the run's first byte and the count will still fit in a byte

If we put all this together, we can convert the diagram and the primitive operations into C, maintaining a one-to-one correspondence between the code and the operations and structure of the program design diagram.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    int c;

    /* This assumes there's at least one char to get.  Otherwise... */
    c = getchar();
    while (c != EOF) {
        int count = 1;

        int first_byte = c;

        c = getchar();

        while (c != EOF && c == first_byte && count < 255) {
            count++;
            c = getchar();
        }

        putchar(first_byte);
        putchar(count);
    }
    return EXIT_SUCCESS;
}