In this talk, Kiko will show how to build a compiler for an object-oriented language, using the functional language Haskell. The focus of the talk is the implementation of the type checker, but this design works well for developing static analysis tools, such as tracking uniqueness of variables to ensure data-race freedom. We will start with a simple type checker that accepts as input an abstract syntax tree and returns as output either an error or a typed abstract syntax tree. We will add more useful features with minimal changes to the initial implementation. Among these changes, I will try to cover some of the following features, starting with simple ones and moving to more complex cases: how to add backtraces, how to access a global environment, throw multiple errors, throw warnings, and how to leverage Haskell to statically prevent the use of the
non-annotated abstract syntax tree where one expects it to be typed. All of these examples exercise mathematical concepts such as monoids, functors, applicatives, monads, monad transformers, and data kinds (lifting types to kinds). Join me on this functional adventure.
This work was accepted as an experience report at the International Conference on Software Language Engineering, and we have a great software artefact as a companion to the paper. The artefact is easy to follow even for those who do not have too much experience with Haskell, and it has intermediate sections that ease-out some of the details of using data-kinds.
Software Artifact: https://www.plresearcher.com/files/monadic-typechecker/README.html