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:

    “It seems to me that upbringings have themes. The parents set the theme, either explicitly or implicitly, and the children pick it up, sometimes accurately and sometimes not so accurately.... The theme may be “Our family has a distinguished heritage that you must live up to” or “No matter what happens, we are fortunate to be together in this lovely corner of the earth” or “We have worked hard so that you can have the opportunities we didn’t have.””
    —Calvin Trillin (20th century)