Frame VM: a virtual machine using scopes as frames

Chiel Bruin

In the paper ‘Scopes Describe Frames’ by Bach Poulsen et al. the scopes-as-frames paradigm was introduced. In this paradigm there is a correspondence between the scope graph of a program and its run-time memory layout. As an effect, static resolution paths in the scope graph correspond to dynamic memory access paths. Precisely this paradigm lies at the core of the Frame VM: A virtual machine that is being developed to both explore the correspondence between scopes and frames, and as a way to ease code generation for language designers.

Scopes in the scope graph contain declarations and are connected using links. In the same way, the main memory (heap) of the machine and its local variables are stored in data frames, where these frames contain slots and are connected by links.

One element that is not accounted for in the scopes-as-frames paradigm, is how control-flow is modeled in a language. For this, the Frame VM uses a variation on the conventional call stack. This stack consists of call frames linked using return addresses. In the VM, multiple return addresses are allowed, transforming the call stack to a call graph. This allows modeling control-flow in a way similar to CPS-semantics.

During the talk a number of examples will be discussed to explain both the correspondence between memory-layout and scope graphs, and the way control flow can be influenced to easily achieve (among others) exception handling and generator functions.

---

Previous: Simon Fowler | Exceptional Asynchronous Session Types: Session Types without Tiers
Next: Makoto Tatsuta | Brotherston's Conjecture: Equivalence of Inductive Definitions and Cyclic Proofs