< Retour au sommaire

Towards a solution to the expression problem for compilers: strongly typed nano-passes

Daniel Mercier le

Lieu: Salle 1073

Suivre en visio

Abstract

We present a new solution to the problem of (strongly) typing compiler passes when the source and destination language share multiple constructors. We are interested in approaches that limit the amount of boilerplate that needs to be (re)written for each language, while still maintaining a very strict typing discipline. Our solution uses well-known tools, but combine them in a novel way:

• the idea of nanopasses, in which each pass encodes a very limited transformation
• the use of ppx syntax extensions to express only the differences between a language and the next
• the traversal of the AST using top-down and bottom-up recursion schemes
• OCaml polymorphic variants, which are instrumental to precisely type our (non-recursive) transformation functions. We present our implementation of this approach in the context of the Ada frontend for the Infer analyzer, which as of today contains 28 passes. We will also discuss the various pitfalls we have encountered along the way, as well as possible improvements (in particular deforesting the combination of multiple passes).

Download slides