Implementation, Integration, and Application of Embedded Domain-Specific Languages

PhD Dissertation, University of Utah. December 2021.

abstract

Domain-specific languages (DSLs) provide features such as notations, semantics, abstractions, and more that help programmers solve domain problems in more direct, correct, or flexible ways than using a general-purpose language. Embedded DSLs expand on the benefits of DSLs by providing an easier path to implementation, as well as better interoperability with a host language and other DSLs embedded into the same host. However, embedded DSLs present additional challenges for implementation, integration, and application.

This dissertation addresses various challenges of embedded DSLs. We address parsing embedded domain-specific notations with a novel parsing algorithm. Our parsing algorithm admits arbitrary, ambiguous, left-recursive, procedural parsers, advancing the state of the art for expressive parsing. We address host language and DSL integration with the example of an embedded shell language. This shell language demonstrates design for tight integration, allowing smooth growth from interactions to programs. We address DSL application with the example of a DSL for creating random program generators. This DSL allows fuzzers for programming language implementations to be created quickly and with low effort.