Gems : language modularization, semantically

Abstract

Great efforts are needed to create new programming languages, and to maintain and improve existing ones, since it requires both knowledge about language design and implementation, and knowledge about specific domains. Therefore, it is a desire to modularize languages as components and share common features among different languages, including syntax and semantics. Most current tools towards this goal, including many extensible compilers and language workbenches, depend on metaprogramming and code generation. They achieve only syntactic modularity by allowing users to write code separately. Semantic modularity, which requires the components to be modularly type-checked and separately compiled, is not fully available.

A part of the language modularization issue is abstracted by the expression problem, which requires a recursive datatype (abstract syntax tree, AST) to be extended with both new operations (semantics) and new data variants (abstract syntax structures), while retaining semantic modularity. However, some solutions to the expression problem exist only on paper and practical tools and experiments are missing. Furthermore, the expression problem only focuses on operations that consume such extensible ASTs, while operations that produce ASTs are neglected, such as parsing, the bridge between concrete and abstract syntax.

In the thesis, we present our work on modularizing the whole pipeline of languages. We build a Scala framework called Gems (Language Modularization, Semantically), which consists of two parts: a set of techniques to modularize languages, and a metaprogramming library for practical development. Semantic modularity is guaranteed in every aspect: parsing, abstract syntax, semantics (operations on ASTs). We use techniques of type-safe modular parsing, and modular external visitors with some enhancements. Gems only requires features that have strong theoretical background in object-oriented programming, including higher-order generics, type variance, and multiple inheritance. Scala-specific features such as case classes are not needed. Moreover, Gems does not rely on metaprogramming to achieve modularity, but only uses it to generate local boilerplate code. To evaluate its utility, we conduct a case study by implementing interpreters of the first 18 languages in book Types and Programming Languages, and compare with a non-modular implementation.