On classes of program schemata

We define the following classes of program schemata: P = class of schemes using a finite number of simple variables PA = class of schemes using simple and subscripted variables (arrays) PR = class of schemes allowing recursive functions PL = class of schemes allowing labels as values Pm = class of schemes allowing a finite number of special markers as values Ppds = class of schemes using pushdown stores With these, we can also discuss for example PAm, the class of schemes allowing arrays, and special markers as values; and PAL the class of schemes allowing arrays, and labels as values. We argue that PA, PR, and PL faithfully represent mechanisms of subscripting, recursion, and labels as values, that are present in many "real" programming languages. We show that P ⊂ PR ⊂ PA ≡ PAm ≡ PAL ≡ Ppdsm. Each of the inclusions and equivalences is effective, except for the equivalences concerning PA. For example, given a scheme in PAm an equivalent scheme in PA exists, but we also prove that you cannot (in general) construct it. We conjecture that PAL, PAm, and Ppdsm are indeed "universal".