2008/10/07 by Bergstra, Jan A., Ponse, Alban
#D.3.1 #F.3.2 #FOS: Computer and information sciences #Programming Languages (cs.PL)
paper · doi:10.48550/arxiv.0810.1151
A program is a finite piece of data that produces a (possibly infinite) sequence of primitive instructions. From scratch we develop a linear notation for sequential, imperative programs, using a familiar class of primitive instructions and so-called repeat instructions, a particular type of control instructions. The resulting mathematical structure is a semigroup. We relate this set of programs to program algebra (PGA) and show that a particular subsemigroup is a carrier for PGA by providing axioms for single-pass congruence, structural congruence, and thread extraction. This subsemigroup characterizes periodic single-pass instruction sequences and provides a direct basis for PGA's toolset.