Oleg Kiselyov: A Non-Traditional Compilers Course

The talk introduces a non-traditional Compilers course that I have been teaching for three years to upper-level undergraduates. The course covers overall the standard material, but in a unique fashion.

First of all, it is a practical course about compilers rather than parsing or automata theory or type theory.

The characteristic of the course is an iterative, incremental development: we start with the most trivial source language, develop the full compiler for it, and then keep extending the source language and the compiler in small steps, reusing the earlier work as much as possible. At each iteration, we build a complete end-to-end compiler producing runnable and testable executables (on x86-64 platform), for a (progressively larger) subset of the source language — which eventually becomes something like Pascal, or C with arbitrarily nested functions.

Another characteristic is the extensive use of tagless-final style, taking the full advantage of extensibility afforded by it. The extensibility here means reuse -- of type-checked and compiled artifacts from the previous increment -- rather than copy-paste. The compiler is hence structured as a stack of domain-specific languages, with parsing at the bottom and assembly at the top. The languages are extended by adding new operations here and there (and only occasionally by redirection). The talk gives a brief introduction to the tagless-final style.

Yet another feature is the attention given to names, or `variables’, and associating attributes to them. Our approach, which readily permits adding attributes at will and analyzing variable usage, may remind some of algebraic effects.

https://okmij.org/ftp/tagless-final/Compiler/index.html

Venue: ETH Zürich / Zentrum / HG F 33.1

Speaker: Prof. Oleg Kiselyov, Tohoku University, Japan

Oleg Kiselyov has been programming and doing research for 45 years, in various languages and in various organizations and companies. Further details about his interests and work can be found on his personal website https://okmij.org/ftp/