Game semantics for an object-oriented language
View/ Open
Date
2009Author
Wolverson, Nicholas
Metadata
Abstract
This thesis investigates the relationship between object-oriented programming
languages and game models of computation. These are intuitively well matched:
an object encapsulates some internal state and presents some behaviour to the
world via its publicly visible methods, while a strategy for some game represents
the possible interactions of a program with its environment.
We work with a simple and well-understood game model. Rather than tailoring
our model to match some existing programming language, we view the
simplicity of our semantic setting as a virtue, and try to find the appropriate
language corresponding to the model.
We define a class-based, stateful object-oriented language, and give a heapbased
operational semantics and an interpretation in our game model. At the
heart of this interpretation lies a novel semantic treatment of the phenomenon
of data abstraction. The model closely guides the design of our language, which
enjoys an intermediate level of expressivity between that of first-order and general
higher-order store.
The agreement between the operational and game interpretations is verified
by a soundness proof. This involves the development of specialised techniques
and a detailed analysis of the relationship between the concrete and abstract
views. We also show that definability and full abstraction hold at certain types
of arbitrary rank, but are problematic at other types.
We conclude by briefly discussing an extended language with a control operator,
along with other extensions leading to a possible core for a more realistic
programming language.