On Classes of Program Schemata
Robert L. Constable, David Gries · SIAM Journal on Computing · 1972
We define the following classes of program schemata: ${\text{P}} = $ class of schemes using a finite number of simple variables; ${\text{P}}_{\text{A}} = $ class of schemes using simple and subscripted variables (arrays); ${\text{P}}_{{\text{Ae}}} = $ class of schemes in ${\text{P}}_{\text{A}} = $, with the addition of an equality test on subscript values; ${\text{P}}_{\text{R}} = $ class of schemes allowing recursive functions; ${\text{P}}_{\text{L}} = $ class of schemes allowing labels as values; ${\text{P}}_{\text{M}} = $ class of schemes allowing a finite number of special markers as values; ${\text{P}}_{{\text{pds}}} = $ class of schemes using pushdown stores. With these, we can also discuss, for example, ${\text{P}}_{{\text{AM}}} $, the class of schemes allowing arrays, and special markers as values ; and ${\text{P}}_{{\text{AL}}} $, the class of schemes allowing arrays, and labels as values. We argue that ${\text{P}}_{\text{A}}$, ${\text{P}}_{\text{R}}$, and ${\text{P}}_{\text{L}}$ faithfully represent mechanisms of subscripting, recursion, and labels as values, that are present in many “real” programming languages. We show that \[ {\text{P}} < {\text{P}}_{\text{R}} < {\text{P}}_{\text{A}} \equiv {\text{P}}_{{\text{AM}}} \equiv {\text{P}}_{{\text{pdsM}}} \equiv {\text{P}}_{{\text{Ae}}} \equiv {\text{EF}}, \] where EF is Strong’s class of effective functionals, assuming total functions and predicates. The inclusions ${\text{P}} < {\text{P}}_{\text{R}} < {\text{P}}_{\text{A}} $ and equivalences ${\text{P}}_{{\text{AL}}} \equiv {\text{P}}_{{\text{AM}}} \equiv {\text{P}}_{{\text{pdsM}}} \equiv {\text{P}}_{{\text{Ae}}} $ are effective. For example, given a program scheme in ${\text{P}}_{{\text{AM}}} $ we can construct an equivalent one in ${\text{P}}_{{\text{AL}}} $. However, we show that for any scheme in ${\text{P}}_{{\text{AM}}} $ an equivalent ${\text{P}}_{\text{A}} $ scheme exists, but also prove it cannot (in general) be constructed! We conjecture that ${\text{P}}_{{\text{A}}} $, ${\text{P}}_{{\text{AL}}} $, and equivalent classes are indeed “universal.” The above results assume that the uninterpreted functions and predicates are total. We discuss the problems which arise when they are partial. We define the class of multischemes and outline the relationship between the class ${\text{P}}_{{\text{Ae}}} $, multischemes, and Strong’s nondeterministic and deterministic effective functionals.