About ProGram Algebra

Program Algebra (PGA) is an algebraic framework for sequential programming. It is intended to contribute to a better understanding of sequential programming. A very simple program notation is used as basis for development of other program notations.

The syntax of program expressions in PGA is generated from a set of constants, the primitive instructions, and two composition mechanisms. The primitive instructions have as parameter a set of basic instructions. These basic instructions can be viewed as requests to an environment to provide some service. Upon execution, a basic instructions returns a boolean value.

Primitive instructions:

• a basic instruction: a
  After performing the basic instruction a execution continues with the next instruction.
• termination: !
  Execution stops.
• positive test: +a
  If the basic instruction a returns true, execution is continued with the next instruction. If it returns false, the next instruction is skipped.
• negative test: -a
  If the basic instruction a returns false, execution is continued with the next instruction. If it returns true, the next instruction is skipped.
• forward jump: #k
  The instruction itself and the following k - 1 instructions are skipped. If k is 0, a jump to the instruction itself is made.

Compositions:

• concatenation of X and Y: X;Y
• repetition of X: Xω

PGLA is a program notation for representing PGA expressions. For dealing with repetition, PGLA has an additional instruction.

• repeat: \\#n
  Here, n is a natural number greater than zero. A program text ending with this instruction will repeat its last n instructions, excluding the repeat instruction itself.

On top of PGLA, other program notation are designed, which can be mapped onto PGLA. Such a mapping towards PGLA is called a projection. Several projections to intermediate languages may be used to get the result that is needed. A mapping away from PGLA is called an embedding.

For more information, see the publications.