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.

Att implementera ett programmeringsspråk är en omfattande utmaning. Detta är särskilt relevant för domänspecifika språk, där implementationsarbetet är än mer disproportionerligt gentemot den allmänna nyttan. Å andra sidan kan ett domänspecifikt språk ge stora produktivitetsvinster inom dess avsedda domän. För att uppnå sådan potential med en rimlig mängd arbete krävs bättre implementationsmetoder. Som väl är så tenderar implementationstekniska framsteg för domänspecifika språk även gynna generella programmeringsspråk och vice versa; denna avhandling är således relevant för båda.

Allmänt tenderar programmering att åstadkomma ökad produktivitet via abstraktion; något som avgränsar implementationsdetaljer till någon liten del av ett program eller utelämnar dem helt och hållet. Denna avhandling arbetar med abstraktioner inom tre områden: återanvändning av implementationsarbete mellan flera programspråksimplementationer, tvetydighet i programspråkssyntax, och automatisering av implementationsval för datastrukturer.

Inom det första området introducerar vi syncons, små användardefinierade språkkonstruktioner som beskriver syntax, namnbindningssemantik, och körsemantik. Den sistnämnda ges i form av makroexpansion till ett annat språk, som även det definieras m.h.a syncons. Ett språk konstrueras sedan genom att återanvända syncons från tidigare språk och konstruera nya i mån av behov.

Inom det andra området ger vi en formell definition av lösbar tvetydighet, vilket innebär att en programmerare kan skriva om ett tvetydigt program till en entydig form. Klassen språk där alla tvetydigheter är lösbara är strikt större än klassen entydiga språk, vilket ökar designfrihet; en språkdesigner behöver inte göra godtyckliga val för att åstadkomma en entydig grammatik, vilket typiskt sett krävs av moderna parsningsmetoder. Detta är användbart i ett flertal situationer; i denna avhandling fokuserar vi på tre fall: syntaktisk sammansättning, intuitiva grammatiker, och nya språkkonstruktioner som saknar allmänt kända konventioner. Vi tillhandahåller två metoder som stödjer lösbar tvetydighet: en som utökar kontextfria grammatiker och använder sig egen parser, och en som kan användas i en mer konventionell parser. Den förstnämnda är mer uttrycksfull, men språk definierade i den andra innehåller enbart lösbara tvetydigheter, vilket vi bevisar i Coq. Båda tillhandahåller en automatisk metod som finner alla entydiga former av tvetydiga program.

Inom det tredje området tillhandahåller vi en design där en användare kan definiera nya abstrakta typer, konkreta representationer, abstrakta operationer, och konkreta operationsimplementationer på ett utbyggbart sätt. Exempelvis kan nya bibliotek lägga till representationer, operationer, och operationsimplementationer till tidigare definierade abstrakta typer. Vi stödjer också representationsbyten, där en abstrakt typ kan använda olika representationer i olika delar av ett program. Vi tillhandahåller också en uppsättning automatiska lösare som väljer implementationer, antingen genom att prioritera optimalitet eller snabb analysis, plus en möjlighet att återanvända en tidigare lösning, även om programet ändrats något sedan dess.

Sammantaget bidrar denna avhandling till att ge större kontroll över abstraktionsnivåer i programmeringsspråk och deras implementationer, dels genom att höja abstraktionsnivån där det är fördelaktigt, men också genom att kräva detaljer och specificitet där det är önskvärt.