Composable Compilers: Evolution toward a Practical Reality

Other Titles


The ability to add new features to programming languages is essential for language design experimentation and domain-specific developments, but implementing and maintaining small language extensions in traditional compilers remain a challenge. General-purpose programming languages do not have desired mechanisms to integrate small, independently developed extensions into a working programming language. At the same time, domain-specific languages that support such integration struggle to gain popularity in the programming language community. More language mechanisms and tools are needed as a middle ground so that a broader range of programmers can implement, maintain, and combine compilers for individual language features more easily. At the heart of compiler construction, new design patterns are proposed to allow compilers to be extended in a modular way and to be merged with little effort. These design patterns, implementable in a mainstream programming language, encode dynamic relationships between node types in abstract syntax trees (ASTs) so that inheritance in object-oriented programming still works over the course of language evolution. A new AST representation lets a single AST be viewed as different programs for different languages. Compiler passes are language-neutral, making translations reusable and composable. At the front end, engineering language syntax can be a painstaking process, especially when individual language syntaxes start to interact. Automatic parser generators, albeit a powerful tool to parse complex grammars, are unhelpful when grammars are faulty, as reports of parsing conflicts do not explain these faults. To improve debugging experience, a semi-decision procedure is added to an LALR parser generator to give compact counterexamples illustrating why the grammar in question is ambiguous. For unambiguous grammars that cause parsing conflicts, a different kind of counterexample is constructed to aid removal of conflicts. At the back end, translation passes in compilers require extracting components of AST nodes. Pattern matching, an important feature in functional languages, is a prime candidate for this task. However, data abstraction and extensibility, two concepts central to object-oriented languages, are in conflict with pattern matching. A new language design based on modal abstraction reconciles static, modular reasoning about exhaustiveness in pattern matching with data abstraction.

Journal / Series

Volume & Issue



Date Issued




ambiguous grammars and parsing; compilers; Computer science; pattern matching and data abstraction; programming language evolution; extensibility and composability


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Myers, Andrew C.

Committee Co-Chair

Committee Member

Kozen, Dexter Campbell
Constable, Robert Lee

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Attribution-ShareAlike 2.0 Generic


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record