Translating Fundamental Program Structures to Assembly
Flow Charting
In the 1960s, programmers tended to write what we today call spaghetti
code: code with an obscure flow of control, in which branches tended
to be both from and to places in the code that were convenient
regardless of the effect on the overall flow of the program. ``Flow
charting'' was developed as a means of trying to visualize the flow of
a program.
The first presentation of "fundamental forms" in programming was in a
paper by Boehm and Jacopini in Communications of the ACM,
titled "Flow Diagrams, Turing Machines, and Languages with only Two
Formation Rules", in 1966. This was a purely theoretical
contribution, with no application to practical programming. However,
Dijkstra then observed that programming solely in terms of these
fundamental forms resulted in better code (more readable, easier to
maintain); he made the case that programming should be limited to
these forms in a letter to CACM titled "GOTO Considered
Harmful", published in 1968.
There was quite a language of flow charting; we are only
interested in two symbols: the process and the decision.
- Process
-
|
A process is simply a sequence of events with a single entry
point and a single exit point. The simplest process is a single
instruction.
|
- Decision
-
|
A decision is just what the name implies: a decision is made as
to whether there should be a branch in the flow of control.
|
Fundamental Forms
When structured programming was a new programming methodology
(late 1960s), it was observed that any algorithm can be
described by using nested sequences of just three fundamental forms
defined in terms of processes and sequences. Each of these forms is
itself a process. The forms are:
- Sequence
-
|
A sequence is a series of processes with no branches between
them.
|
- If-Then-Else
-
|
An if-then-else is a decision and two sub-sequences. Either of
the sub-sequences may be empty.
|
- While
-
|
The While is a condition and a sequence; the sequence is
executed over and over again while the condition remains true.
|
Using the languages in common use at the time, writing structured code
required quite a bit of discipline on the part of the programmer.
Using modern languages, the mechanics of writing structured code are
taken care of for you, since the sort of nested control structures
provided by modern procedural languages reflect these fundamental
forms (as well as extensions such as break
and
continue
statements, and C do-while
and
switch
statements).
An historical aside to mention here is that one of the reasons
programmers gave at the time for objecting to structured programming
was that they felt that they could better optimize their code if they
had the freedom to write spaghetti code. Today, compilers can
optimize code better than people can, and are best able to work with
structured code.
We can translate a program written in a high level language into
assembly code by recognizing the fundamental forms that are present in
the code, and translating them into assembly code. Some examples of
the details of how to do this are in The
Joy of coding