An Automata-Theoretic Model of Idealized Algol (with Brian Dunphy,
ICALP 2012, July 2012)
In this paper, we present a new model of class-based Algol-like programming
languages inspired by automata-theoretic concepts. The model may be seen as
a variant of the "object-based" model previously proposed by Reddy, where
objects are described by their observable behaviour in terms of events. At
the same time, it also reflects the intuitions behind state-based models
studied by Reynolds, Oles, Tennent and O'Hearn where the effect of commands
is described by state transformations. The idea is to view stores as
automata, capturing not only their states but also the allowed state
transformations. In this fashion, we are able to combine both the
state-based and event-based views of objects. We illustrate the efficacy of
the model by proving several test equivalences and discuss its connections
to the previous models.
[Extended abstract |
Full paper
]