Program schemes

Historical introduction

From Ong 2015:

Much studied in the 1970s, program schemes are a program calculus that separates control structure and operations on data, thus providing a framework for investigating the descriptive power of control structures and program transformation. The idea of program schemes can be traced back to the pioneering 1960 paper of Ianov 50, which inspired early work in the cateogry-theoretic and algebraic semantics of program schemes and related formalisms 35, 89, fixpoint theory and induction principles 78, and the question of decidability of equivalence of program schemes 80, 67. There is a large literature (for example 32, 72, 24, 23, 44) throughout the 1970s on the semantics of program schemes, using a variety of approaches including operational, denotational, algebraic and automata-theoretic. In the late 1970s, Indermark, Damm and others 27, 29, 28, 38, 39 studied program schemes that are constrained by a family of simple types, as generators of hierarchies of word and tree languages. For a survey of the early work, see Courcelle’s handbook article 21.

References

Program schemes originated in

Y. I. Ianov, "The logical schemes of algorithms," Problems of Cybernetics, vol. 1, pp. 82–140, 1960.

A handbook article reference:

Courcelle, Bruno. 1990. ‘Recursive Applicative Program Schemes’. In Formal Models and Semantics, 459–92. Handbook of Theoretical Computer Science 2. Elsevier. https://doi.org/10.1016/B978-0-444-88074-1.50014-7.

@incollection{courcelle_1990,
	series = {Handbook of {Theoretical} {Computer} {Science}},
	title = {Recursive {Applicative} {Program} {Schemes}},
	isbn = {978-0-444-88074-1},
	number = {2},
	booktitle = {Formal {Models} and {Semantics}},
	publisher = {Elsevier},
	author = {Courcelle, Bruno},
	year = {1990},
	doi = {10.1016/B978-0-444-88074-1.50014-7},
	pages = {459--492},
}

The historical intro comes from a LICS 2015 invited talk by Luke Ong:

Ong, Luke. 2015. ‘Higher-Order Model Checking: An Overview’. In 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 1–15. Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.9.

@inproceedings{ong_2015,
	address = {Kyoto, Japan},
	title = {Higher-{Order} {Model} {Checking}: {An} {Overview}},
	doi = {10.1109/LICS.2015.9},
	booktitle = {2015 30th {Annual} {ACM}/{IEEE} {Symposium} on {Logic} in {Computer} {Science} ({LICS})},
	publisher = {IEEE},
	author = {Ong, Luke},
	year = {2015},
	pages = {1--15},
}