Jackson Structured Programming - A Worked Example

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

  1. read a byte
  2. remember byte
  3. set counter to zero
  4. increment counter
  5. output remembered byte
  6. output counter

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

  1. while there are more bytes
  2. 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 #include int main(int argc, char *argv) { char c; c = getchar; while (c != EOF) { char count = 1; char first_byte = c; c = getchar; while (c != EOF && c == first_byte && count < 255) { count++; c = getchar; } putchar(first_byte); putchar(count); } return EXIT_SUCCESS; }

Read more about this topic:  Jackson Structured Programming

Famous quotes containing the word worked:

    “The two most far-reaching critical theories at the beginning of the latest phase of industrial society were those of Marx and Freud. Marx showed the moving powers and the conflicts in the social-historical process. Freud aimed at the critical uncovering of the inner conflicts. Both worked for the liberation of man, even though Marx’s concept was more comprehensive and less time-bound than Freud’s.”
    —Erich Fromm (1900–1980)