Controlling control: functional language design and implementation
The design and implementation of functional languages is a problem that has been tackled from many perspectives. Generally, one starts with a formal specification of the semantics, after which this is used to derive an implementation of the language (e.g., an interpreter). The usual (operational) approaches to giving semantics are small-step, big-step and definitional interpreters, the last one capturing both a formal specification of the language and an actual implementation. However, the presentation of a functional language should aim to use a mixture of these (e.g., provide a small-step semantics, and then implement a definitional interpreter). This becomes a problem when languages with more complex control mechanisms such as exception handling and concurrency are considered, because the mentioned approaches generally do not scale well. In this talk, we present a unified view of semantics and implementation, that scales well with the complexity of the language, whilst still giving one the ability to reason about it. We first present a simple and powerful way to specify small-step operational semantics using evaluation contexts, which allow us to succinctly capture complex control mechanisms. We then show how the idea of evaluation contexts is tightly linked to delimited continuations. Furthermore, delimited continuations can then be use to implement a definitional interpreter, which is both concise and highly extensible. To achieve this, we make use of various control operators and employ multi-prompt delimited continuations. Finally, we explore how the delimited continuation approach relates to other similar (in spirit) approaches of implementing interpreters, such as effects-and-handlers and monadic reflection.