Ulrich Schöpp, Computation by Interaction for Structuring Low-Level Languages
Computation by Interaction for Structuring Low-Level Languages
A successful approach in the semantics of programming languages is to model programs by interaction dialogues. While dialogues are most often considered as abstract mathematical objects, it has also been argued that they are useful for actual computation. Dialogues have been found useful especially for resource bounded computation, e.g. in Ghica's recent approach to hardware synthesis, or in joint work with Dal Lago on programming with sublinear space.
In this talk I will consider computation by interaction as an approach to organising and structuring low-level languages. The starting point is a simple way of constructing a basic interactive computation model from a low-level language by means of the Int-construction. Even for weak languages, the thus constructed model has interesting structure. It supports higher order functions and control effects, but also allows for fine-grained control of space usage. The model construction is not only related to game semantics, but it also turns out to be closely related to well-known methods of compiling with continuations and defunctionalization.