Program Algebra and Coprogram Calculus

Abstract

On the basis of the program notation PGLD of program algebra, a program notation PGLDg (PGLD with goto's) is proposed with indirect absolute jumps. An indirect absolute jump, also called a goto instruction, instructs the agent executing a program to move to an occurrence of a label catch instruction. The semantics of PGLDg is determined by a projection back to PGLD. An interpretation of flow charts into PGLDg is given, thus demonstrating the expressive strength of PGLDg. PGLDg turns out to be a useful point of departure for further language extensions, the meaning of more involved languages being determined by a projection back to PGLDg. This semantic method (paradigm) is introduced as projection semantics. As an example a language extension of PGLDg with a conditional construct is discussed. Coprograms are introduced to model the working memory of a machine executing a program. Projection semantics as a paradigm must provide the possibility to translate a program into a PGLDg program together with an appropriate coprogram. A rigorous definition of coprograms is provided. Two modes of cooperation between programs and coprograms are introduced: `use' and `apply'. Coprograms give rise to a natural calculus, which is studied in some detail. The use of coprograms in projection semantics is exemplified in the case of a language extension with recursion.