Content deleted Content added
added a new final section on JSP and object-oriented design |
m run on sentence |
||
| (27 intermediate revisions by 23 users not shown) | |||
Line 1:
{{Short description|Computer programming method}}
[[Image:JSP RLE output1.png|thumb|240px|Example of a JSP diagram.]]
'''Jackson structured programming''' ('''JSP''') is a method for [[structured programming]] developed by British software
JSP describes structures (of both data and programs) using three basic structures
== Introduction ==
[[Michael A. Jackson (computer scientist)|Michael A. Jackson]] originally developed JSP in the 1970s. He documented the system in his 1975 book ''Principles of Program Design''.<ref name="PoPD"
Jackson Structured Programming was similar to [[Warnier/Orr Diagrams|Warnier/Orr structured programming]]<ref>{{Citation | first = JD | last = Warnier | year = 1974 | title = Logical Construction of Programs | publisher = Van Nostrand Reinhold | place = NY}}</ref><ref>{{Citation | first = KT | last = Orr | year = 1980 | contribution = Structured programming in the 1980s | title = Proceedings of the ACM 1980 Annual Conference | publisher = ACM Press | place = New York, NY | pages = 323–26 | doi = 10.1145/800176.809987 | isbn = 978-0897910286 | s2cid = 26834496 }}</ref> although JSP considered both input and output data structures while the Warnier/Orr method focused almost exclusively on the structure of the output stream.
▲Jackson Structured Programming was similar to [[Warnier/Orr Diagrams|Warnier/Orr structured programming]]<ref>{{Citation | first = JD | last = Warnier | year = 1974 | title = Logical Construction of Programs | publisher = Van Nostrand Reinhold | place = NY}}</ref><ref>{{Citation | first = KT | last = Orr | year = 1980 | contribution = Structured programming in the 1980s | title = Proceedings of the ACM 1980 Annual Conference | publisher = ACM Press | place = New York, NY | pages = 323–26 | doi = 10.1145/800176.809987 | isbn = 978-0897910286 }}</ref> although JSP considered both input and output data structures while the Warnier/Orr method focused almost exclusively on the structure of the output stream.
== Motivation for the method ==
At the time that JSP was developed, most programs were batch COBOL programs that processed sequential files stored on tape. A typical program read through its input file as a sequence of records, so that all programs had the same structure— a single main loop that processed all of the records in the file, one at a time. Jackson asserted that this program structure was almost always wrong, and encouraged programmers to look for more complex data structures. In Chapter 3 of ''Principles of Program Design''<ref name="PoPD"/> Jackson presents two versions of a program, one designed using JSP, the other using the traditional single-loop structure. Here is his example, translated from COBOL into Java. The purpose of these two programs is to recognize groups of repeated records (lines) in a sorted file, and to produce an output file listing each record and the number of times that it occurs in the file.
Here is the traditional, single-loop version of the program.
<syntaxhighlight lang="java">
Line 40 ⟶ 42:
line = in.readLine();
// begin outer loop: process 1 group
while (line != null) {
numberOfLinesInGroup = 0;
String firstLineOfGroup = line;
// begin inner loop: process 1 record in the group
while (line != null && line.equals(firstLineOfGroup)) {
numberOfLinesInGroup++;
Line 54 ⟶ 56:
</syntaxhighlight>
Jackson criticises the traditional single-loop version for failing to process the structure of the input file (
== The basic method ==
Line 68 ⟶ 70:
* 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|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, which focus on internal data structures rather than input and output ones.
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.
Line 78 ⟶ 80:
A simple operation is drawn as a box.
A sequence of operations is represented by boxes connected with lines. In the example below,
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,
Selection is similar to a sequence, but with a circle drawn in the top right hand corner of each optional operation. In the example,
==A worked example==
As an example, here is how a JSP programmer would design and code a [[Run-length encoding|run length encoder]]. A run length encoder is a program whose input is a stream of bytes which can be viewed as occurring in ''runs'', where a run consists of one or more occurrences of bytes of the same value. The output of the program is a stream of byte pairs, where each byte pair is a compressed description of a run. In each pair, the first byte is the value of the repeated byte in a run and the second byte is a number indicating the number of times that that value was repeated in the run. For example, a run of eight occurrences of the letter "A" in the input stream ("AAAAAAAA") would produce "A8" as a byte pair in the output stream. Run length encoders are often used for crudely compressing bitmaps.
The second step is to describe the output data structure, which in this case consists of zero or more iterations of byte pairs.
▲<center>[[Image:JSP RLE input.png]]<br>The run length encoder input</center>
The next step is to describe the correspondences between the
▲<center>[[Image:JSP RLE output1.png]]<br>The run length encoder output</center>
{{center|[[Image:JSP RLE correspondence.png]]}}
▲The next step is to describe the correspondences between the operations in the input and output structures.
The next step is to use the correspondences between the two data structures to create a program structure that is capable of processing the input data structure and producing the output data structure. (Sometimes this isn't possible. See the discussion of ''structure clashes'', below.)
{{center|[[Image:JSP RLE program.png]]}}
Once the program structure is finished, the programmer creates a list of the computational operations that the program must perform, and the program structure diagram is fleshed out by hanging those operations off of the appropriate structural components.
# read a byte
# remember byte
Line 125 ⟶ 122:
# output counter
Also, at this stage conditions on iterations (loops) and selections (if-then-else or case statements) are listed and added to the program structure diagram.
# 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
Once the diagram is finished, it can be translated into whatever programming language is being used. Here is a translation into C.
<syntaxhighlight lang="c">
Line 139 ⟶ 136:
{
int c;
int first_byte;
int count;
c = getchar(); /* get first byte */
while (c != EOF) {
first_byte = c;
c = getchar(); /* get next byte */▼
▲ c = getchar();
/* process the succeeding bytes in the run */
while (c != EOF && c == first_byte && count < 255) {
/* process one byte of the same value */
count++;
c = getchar(); /* get next byte */
}
Line 161:
== Techniques for handling difficult design problems ==
In ''Principles of Program Design'' Jackson recognized situations that posed specific kinds of design problems, and provided techniques for handling them.
One of these situations is a case in which a program processes two input files, rather than one. In 1975, one of the standard "wicked problems" was how to design a transaction-processing program. In such a program, a sequential file of update records is run against a sequential master file, producing an updated master file as output. (For example, at night a bank would run a batch program that would update the balances in its customers' accounts based on records of the deposits and withdrawals that they had made that day.) ''Principles of Program Design'' provided a standard solution for that problem, along with an explanation of the logic behind the design.
Another kind of problem involved what Jackson called "recognition difficulties" and today we would call parsing problems. The basic JSP design technique was supplemented by POSIT and QUIT operations to allow the design of what we would now call a [[backtracking]] parser.
JSP also recognized three situations that are called "structure clashes"— a boundary clash, an ordering clash, and an interleaving clash— and provided techniques for dealing with them. In
== JSP and object-oriented design ==
JSP was developed long before object-oriented technologies became available. It and its successor method [[Jackson system development|JSD]] do not treat what now would be called "objects" as collections of more or less independent methods. Instead, following the work of [[C. A. R. Hoare]], JSP and JSD describe software objects as [[coroutine|co-routines]].<ref>{{Citation | first = R | last = Wieringa | title = A survey of structured and object-oriented software specification methods and techniques | journal =
== See also ==
* [[Jackson
* [[Warnier/Orr diagram
== References ==
Line 181:
== External links ==
{{Commons category|Jackson Structured Programming}}
* [http://www.sabretech.co.uk/pages/thought.html A free graphical JSP Editor written in
* [https://www.his.se/en/about-us/staff/henrik.engstrom/jsp-editor/ A JSP editor]
* [http://www.jacksonworkbench.co.uk/stevefergspages/jackson_methods/index.html A brief history of the Jackson methods]
| |||