Parallel program schemata: A mathematical model for parallel computation

In this paper we report some results of a study on the range of possible structure of programming languages. The main emphasis is on the range of graphical ("topological" or flowchart) and syntactic structure. For the sake of simplicity and precision we rather severely limit the "semantic structure" of the languages--we restrict ourselves to command (instruction) languages for Turing machines. As we show, this apparently strong limitation imposes very little restriction on the graphical and syntactic structure. The bulk of the paper consists of the presentation of six Turing machine languages. These languages serve to illustrate the range of possible structure and, more important, they allow us to establish the range of a number of structural parameters. All the languages are universal in the sense that in each one we can program every computable function. However, they differ greatly in syntax, graphical structure, ease of compilation (assembly), and in the type of machine, if any, which can operate directly in the language. In brief, we present languages with finite-state, context-free and more complex syntax; languages with "conventional" graphical structure, with block structure and only one transfer per block, with only nested transfers (nested loops), with transfers only to the immediately neighboring instructions, and with only one transfer per program.