Most problems can be solved by adding a level of indirection. But indirection does not come for free – it has a high cost in performance!

When performance matters, programmers pick C over high-level alternatives. The drawbacks are well known: buggy systems, security vulnerabilities, poor programmer productivity, etc.

An alternative approach is generative programming: writing expressive high-level programs that generate fast low-level code at runtime. While there are successful program generators for key libraries (BLAS, FFT), generative programming has remained somewhat of a black art.

This tutorial provides a step-by-step introduction to the open-source LMS (Lightweight Modular Staging) framework, which brings runtime code generation and compilation to Scala programs.

As an example of serious systems-level programming, we will build, within this 90 minute tutorial, a SQL query engine that outperforms existing database systems and consists of just about 500 lines of high-level Scala code.

Along the way, we will discuss powerful generative programming patterns such as mixed-stage (static/dynamic) data structures and mechanically turning interpreters into compilers through staging (e.g. for SQL queries or regular expressions).