Jaro Reinders
Please Note
5 records found
1
Algebraic effects are a simple and modular approach to modelling effectful computations. They are commonly embedded in functional programming languages, where they provide a lightweight and powerful way of programming with effects. Such embeddings typically use host language functions to represent continuations of effectful operations. While host language functions allow for easy programming with effects, they also hinder programmers wishing to define custom optimizations for effectful programs. Specifically, we cannot, in general, know what precisely a host language function does from within the language. This paper presents a solution to this problem by embedding algebraic effects as intrinsically typed, De Bruijn-indexed syntax. Working in Agda, we demonstrate how this provides a safe-by-construction model of effectful computations, with support for optimizations that inspect and transform variable binding. We intend this to be the basis of a verified compiler that uses our notion of effects with variable binding as an intermediate representation.
Compilers transform a human readable source language into machine readable target language. Nanopass compilers simplify this approach by breaking up this transformation into small steps that are more understandable, maintainable, and extensible. We propose a semantics-driven variant of the nanopass compiler architecture exploring the use a effects and handlers to model the intermediate languages and the transformation passes, respectively. Our approach is fully typed and ensures that all cases in the compiler are covered. Additionally, by using an effect system we abstract over the control flow of the intermediate language making the compiler even more flexible. We apply this approach to a minimal compiler from a language with arithmetic and let-bound variables to a string of pretty printed X86 instructions. In the future, we hope to extend this work to compile a larger and more complicated language and we envision a formal verification framework from compilers written in this style.