Structuring Languages as Object-Oriented Libraries

Pablo Inostroza Valdera

Promotors: prof.dr. P. Klint (UvA and CWI) and prof.dr. T. van der Storm (CWI and RUG)
Universiteit van Amsterdam
Date: 29 November, 2018
Thesis: PDF


The development of programming languages is challenging, as the typical language processing toolchain consists of different artifacts interacting with each other. The ideal scenario for engineering languages is one closer to traditional software engineering, where reuse, in the form of frameworks and libraries, has optimized development times.

However, in the case of the engineering of programming languages, there is a tension between admitting the evolution of the syntax of languages and at the same time the addition of new processors (or operations). In the literature of programming languages, this tension in terms of extensibility is concisely summarized in the Expression Problem.

Object Algebras solve the Expression Problem in the context of Object-Oriented programming, requiring only inheritance and parametric polymorphism from the host language. This thesis postulates that, given their advantages in terms of modularity and extensibility, Object Algebras are a suitable technique for structuring libraries of languages, with the goal of making reuse a central practice in the implementation of programming languages. The dissertation thus introduces applications of the Object Algebra pattern for implementing language libraries.

First, we introduce Recaf, a framework for creating extensions to Java. In Recaf, a combination of syntactic extensions (supported by a generic transformation) and semantic extensions (provided by an Object Algebra-based embedding) allows us to define libraries of Java dialects. Motivated by the challenge of improving the usability of transformation-based approaches such as Recaf, we propose String Origins, a technique to trace the results of program transformations back to their origins.

As another application of Object Algebras, inspired by libraries of semantic components, we introduce Modular Interpreters with Implicit Context Propagation. This technique is based on lifting Object Algebra-defined interpreters in order to implicitly propagate context, with the aim of composing modular language interpreters with different context requirements. These modular interpreters can be distributed as libraries of executable semantic specifications.

In Modular Interpreters with Implicit Context Propagation, context is represented using the side-effect facilities of the host language. The lack of explicit feature interaction between these effects complicates certain scenarios of composition. Motivated by this problem, we introduce JEff, a language that integrates Object Orientation with effects and handlers, as a first step towards an Object-Oriented language with effects, that could host effectful modular interpreters.

The results described in this dissertation show that Object Orientation, and Object Algebras in particular, provides a fertile foundation for the vision of library-based language development.