Search

We present a new abstract machine, called DCESH, which describes the execution of higher-order programs running in distributed architectures. DCESH implements a generalised form of Remote Procedure Call that supports calling higher-order functions across node boundaries, without sending actual code. Our starting point is a variant of the SECD machine that we call the CES machine, which implements reduction for untyped call-by-value PCF. We successively add the features that we need for distributed execution and show the correctness of each addition. First we add heaps, forming the CESH machine, which provides features necessary for more efficient execution, and show that there is a bisimulation between the CES and the CESH machine. Then we construct a two-level operational semantics, where the high level is a network of communicating machines, and the low level is given by local machine transitions. Using these networks, we arrive at our final system, the distributed CESH machine (DCESH). We show that there is a bisimulation relation also between the CESH machine and the DCESH machine. All the technical results have been formalised and proved correct in Agda, and a prototype compiler has been developed.

We define new abstract machines for game semantics which correspond to networks of conventional computers, and can be used as an intermediate representation for compilation targeting distributed systems. This is achieved in two steps. First we introduce the HRAM, a Heap and Register Abstract Machine, an abstraction of a conventional computer, which can be structured into HRAM nets, an abstract point-to-point network model. HRAMs are multi-threaded and subsume communication by tokens (cf. IAM) or jumps. Game Abstract Machines (GAM), are HRAMs with additional structure at the interface level, but no special operational capabilities. We show that GAMs cannot be naively composed, but composition must be mediated using appropriate HRAM combinators. HRAMs are flexible enough to allow the representation of game models for languages with state (non-innocent games) or concurrency (non-alternating games). We illustrate the potential of this technique by implementing a toy distributed compiler for ICA, a higher-order programming language with shared state concurrency, thus significantly extending our previous distributed PCF compiler. We show that compilation is sound and memory-safe, i.e. no (distributed or local) garbage collection is necessary.