Student Projects

Bernard Sufrin

November 2022

Modeless Structure Editing

Oege de Moor and I wrote a paper called Modeless Structure Editing for Tony Hoare’s retirement symposium. What we had in mind was a family of modeless editors whose underlying model of the document being edited is akin to its abstract syntax tree. It’s clear what this means if the document represents, for example, a program in a programming language or a proof in a proof calculus; but we conjecture that structured prose documents will also be amenable to this approach to a useful extent.

Editing an abstract syntax tree model does not mean that one must necessarily work with a “tree-shaped” view of the document.

The benefits of editing an abstract syntax tree model include:

Such an approach has the potential to yield dividends in performance and simplicity of implementation of incremental semantic checks, code-generation, etc.

The first phase of this project will construct (in Scala) a prototype structure editing toolkit implementing the model explained in this paper. Subsequent phases will provide one or two case studies in its use. The architecture of an editor that could use such a document model already exists – in the shape of our AppleRed editor, whose document model is (in principle) “pluggable”, and that currently uses a linear model (document as a sequence of lines of text). What will be needed is to construct a new “plugin” conforming to the AppleRed document model interface, and to adapt and generalise that interface where necessary.

Concurrent and Distributed Programming

CSO-F – Communicating Scala Objects with Fibres

The Scala language is a powerful object oriented language, with a type system, that is much more flexible and expressive than Java’s. Scala’s compilers translate into code for the Java Virtual machine. It is particularly convenient to embed new programming constructs in Scala; and this has yielded many domain-specific extensions.

In 2008 we designed and implemented a concurrency-specific extension1 in the style of OCCAM/CSP called Communicating Scala Objects (CSO) (See this paper2). The extended language has been used in a variety of applications as well as for teaching the principles of channel-based concurrent programming.

The present CSO implementation maps each running process to a (kernel) thread – usually taken from a thread-pool. But kernel threads – even when pooled – are heavyweight entitites, and their multiplexing across the resources of a real machine places an artificial upper bound (a few thousand) on the number of active processes within a program. This, in turn, hampers the realisation of powerful programs as “scrutable concurrent compositions of components”, and likewise the realisations of components themselves. Removal of the scaleability limit imposed by the thread-per-running-process constraint promises much: both in expressive power and the realization of potential performance on multicore machines.

Present JVM approaches to concurrency sacrifice either expressive power (for example Futures) or simplicity of incorporation in existing programs (for example Actors). The popularity of the Go language shows that the channel-based approach is accessible to large numbers of practitioners.

The time is more than ripe for a reimplementation of CSO using a lighter-weight implementation scheme for active processes. Project LOOM has provided an implementation of Fibres that may well do the trick.

The aim of this project is to explore the use of Fibres to implement running CSO processes. Some of present CSO implementation should be reusable: in particular the channel implementations and much of the instrumentation to support debugging and diagnosis.

Projects based on Go

CHOP: Composable Higher-Order Processes

The Go language runtime system has deservedly gained a reputation for efficiency and scaleability across architectures with numbers of processors ranging from one to hundreds. But the Go language itself leaves something to be desired by those who seek higher level ways of directly realizing systems as concurrent compositions of well-specified components communicating by means of channels.

The goal of this project is to define a concurrent language that, like Go, encourages inter-module information sharing by channel communication (in contrast to encouraging the implementation of intermodule communication by memory sharing). Like Communicating Scala Objects, which was modelled, to a certain extent, on OCCAM 3, it should incorporate robust language constructs for concurrent composition, alternation, and termination of composites.

CHOP programming should have something of the flavour of CSO programming, but its design should be semantically conservative – in the sense that it should be possible for programs in CHOP to be simply translateable into efficient Go programs. Recent developments in the Go type system may make this easier than would have been possible earlier in the language’s development.

We have done some preliminary development of a Go library that supports CSO-like parallel composition, and CSO-like termination of networks of connected components using the propagation of channel closures.

Gobol: dynamically-typed, prototype-based, object oriented language

The goal of this project is to reimplement, in Go, an interpreter (or compiler+virtual machine) for a concurrent programming language based on the prototype-based object-oriented language Obol.

  1. At the time we called it, more prosaically, a “library”.↩︎