Annotating Deeply Embedded Languages

This is my master's thesis on extending deeply embedded languages* with additional information that can be used to add source mapping support and custom compiler instructions to existing embedded languages.

Abstract:

This thesis explores the idea of annotating deeply embedded languages with additional information. A common problem with deeply embedded languages is that there is no strong connection between an embedded program, the abstract syntax tree for that embedded program, and a compiled version of the program. By gathering source location information for embedded expressions using a novel implicit parameter-based approach and annotating the embedded program's AST with this information, it becomes possible to map the embedded program back to the original source code. This new information can be used to improve compiler diagnostics, and to provide better profiling and debugging experiences for the language. In addition, the idea of extending that approach by also annotating the language with instructions for the compiler as a way to allow the programmer to hand optimize parts of a program will be explored. Storing these instructions as annotations on the abstract syntax trees enables new optimization workflows without requiring any changes to the language itself. Finally, an implementation of this annotation system in an existing language is examined, and its consequences on the experience of using the language are evaluated.

Full PDF
Thesis defense presentation, presented by @tmcdonell at the Haskell Implementor's Workshop 2022

^{*An embedded language is a programming language whose programs are written inside of another language, called the host language. Evaluating a shallowly embedded program directly produces a result, while deep embeddings produce an Abstract Syntax Tree of the program instead. This AST can then be checked, optimized, and eventually interpreted or compiled to native code.}

Links

ICFP 2022
UU Theses Repository

Implementation source code

The implementation for the annotation system as implemented in Accelerate can be found in the GitHub repositories for the forked accelerate and the accelerate-llvm packages. The Data.Array.Accelerate.Annotations module in the accelerate fork contains a complete guide on how to migrate Accelerate libraries to the new annotated version of Accelerate. Take a look at the linear-accelerate fork for an example on how to do this.