Abstraction, Composition, and Resolvable Ambiguity in Programming Language Implementation
Time: Tue 2024-10-08 13.00
Location: Ka-Sal A (Östen Mäkitalo), Kistagången 16, Kista
Video link: https://kth-se.zoom.us/j/66561560361
Language: English
Subject area: Computer Science
Doctoral student: Viktor Palmkvist , Programvaruteknik och datorsystem, SCS
Opponent: Associate Professor Jeremy Yallop, University of Cambridge
Supervisor: David Broman, Programvaruteknik och datorsystem, SCS; Associate Professor Philipp Haller, Teoretisk datalogi, TCS; Assistant Professor Elias Castegren, Division of Computing Science, Department of Information Technology, Uppsala University
QC 20240916
Abstract
Implementing a programming language is a significant undertaking. This is especially problematic for domain-specific languages, whose limited general applicability skews the effort-to-benefit ratio further. On the other hand, a domain-specific language can be very beneficial indeed for a problem in its intended domain. To realize this potential we require more effective implementation approaches. Of course, the technical requirements of a domain-specific language overlap significantly with those of a general purpose language, thus advances for one tend to benefit the other as well.
Programming in general tends to increase productivity through abstraction, various means of either relegating implementation details to more limited portions of a program or omitting them altogether. This dissertation explores abstraction in three areas: reusing work between language implementations, ambiguity in programming language syntax, and automatic representation selection for high-level data structures.
In the first area we provide syncons, short for syntactical construct, where each syncon is a user-defined language construct that includes syntax, binding semantics, and run-time semantics. The run-time semantics are given in terms of macro expansion to another language, which in turn is also defined using syncons. A language is constructed by defining whatever new syncons are required and reusing others from previous languages.
In the second area we formally define resolvable ambiguity, an ambiguity that can be resolved by a programmer by editing an ambiguous program. The class of resolvable languages is larger than the class of unambiguous languages, which gives greater design freedom. For example, a designer need not make arbitrary choices in their grammar to satisfy the needs of most modern parsing methods. This thesis focuses on three cases for resolvable ambiguity: syntactic composition, intuitive grammars, and new language constructs for which no syntactic conventions yet exist. We provide two approaches using resolvable ambiguity; one extending context-free grammars and using its own parser, and one meant for embedding in a conventional parser. The former is more expressive, while the latter admits a proof that all ambiguities are resolvable, which we provide, mechanized in Coq. Both can automatically compute all resolutions of an ambiguity.
In the third area we present an approach where new abstract types, representations, operations, and operation implementations can be introduced by a user in an extensible fashion, e.g., new libraries can add representations, operations, and operation implementations to previously defined abstract types. We also support representation switching, where an abstract type can be represented differently throughout lifetime. We complement the design with a set of solvers prioritizing optimality or quick analysis, and also support transferring a previous solution, even in the presence of minor program changes.
Overall, these contributions allow greater control over the level of abstraction in programming languages as well as their implementations, raising it where beneficial, and enforcing greater specificity where desirable.