Modularity beyond compositionality

Abstract

Modern software becomes increasingly complex and rapid-evolving. The cost of developing and maintaining software systems is extremely high. To reduce the engineering effort involved in developing and maintaining software systems, modularity plays an important role. A modular way to develop software will subdivide a software system into a bunch of smaller components. Each of those components can then be of a manageable size, can be developed in parallel with isolated functionality assigned to specific programmers. The components should be extensible so that new functionality can be added easily without affecting other existing components. However, such a modular extensible style of component-based software development is not widely applicable in practice due to inadequate support from the modularization techniques in programming languages. This thesis aims at investigating techniques on programming languages that support modular extensible software development from three perspectives: plain design patterns, metaprogramming-based design patterns, and novel language designs. Plain design patterns can be directly applied in existing programming languages. Existing languages have an advantage that programmers are already familiar with, allowing a wider application of the modularization technique without a steep learning curve. With the help of metaprogramming, the boilerplate code associated with the design patterns can be automated. However, existing languages are sometimes too restrictive in terms of syntax and semantics, which might not be expressive or concise enough for certain cases. For such cases, new programming languages (features) suit better.

The first part of the thesis focuses on plain design patterns. We connect shallow embeddings to Object-Oriented Programming (OOP) via procedural abstraction. We argue that common OOP mechanisms increase the modularity and reuse of shallow EDSLs. We make our arguments by using Gibbons and Wu’s examples, where procedural abstraction is used in Haskell to model a simple shallow EDSL. We recode that EDSL in Scala and with an improved OO-inspired Haskell encoding. We further illustrate our approach with a case study on refactoring a deep external SQL query processor to make it more modular, shallow, and embedded.

The second part of the thesis turns to metaprogramming-based design patterns. We present Castor, a Scala framework for programming with extensible, generative visitors. Castor has several advantages over previous approaches including its support for pattern matching, type-safe interpreters, imperative style visitors, and graphs. The applicability of Castor is shown by several examples and two case studies on modularizing interpreters from the “Types and Programming Languages” book and UML activity diagrams.

The last part of the thesis is on novel language designs. We propose a programming style called Compositional Programming. We introduce four key concepts for Composi- tional Programming: compositional interfaces, compositional traits, method patterns, and nested trait composition. Altogether these concepts allow us to naturally solve challenges such as the Expression Problem, model attribute-grammar-like programs, and generally deal with modular programs with complex dependencies. We present a language design, called CP, which is proved to be type-safe, together with several examples and three case studies.