Computational Chains and the Simplification of Computer Programs

Abstract

In the synthesis of switching circuits, a formal representation of the function to be realized by the circuit is first established and simplified as much as possible. Only then is construction of the circuit undertaken. It is argued that an analogous strategy should be followed in the synthesis of digital computer programs: the function to be realized by a program should first be established in a suitable formalism; the resulting formal expression should then be simplified as much as possible; only at this point should translation into the final ``machine'' program be undertaken. In the light of this discussion, the simplification of a certain type of elementary program, containing no branching or internal modification, is considered in detail. It is argued that the analysis of this type of program, whose formalization is called a ``computational chain,'' is a prerequisite to the analysis of more general programs. A system of notation is developed, and rules are given for minimizing the temporary storage requirements associated with a computational chain, for eliminating vacuous and redundant parts, and for forming combinations of chains.