This tutorial series introduces Lightweight Modular Staging (LMS), a framework for runtime code generation in Scala.
Outline:
These docs are a collection of literate Scala files. Clone the GitHub repo:
git clone https://github.com/scala-lms/tutorials.git
Check the README.md file for prerequisites and start hacking!
Because it enables abstraction without regret: the key idea is to write very high-level and generic programs that generate specialized and extremely fast low-level code at runtime.
Programming abstractions that would usually be avoided in performance-sensitive code (objects, type classes, higher-order functions) can be used during generation without affecting performance of the generated code.
Because it is lightweight and modular: LMS is just a Scala library. With types, it distinguishes
expressions that are evaluated now (type T) vs later (type Rep[T]).
LMS comes with batteries included: it provides many optimizations such as common subexpression elimination out of the box, and it goes beyond purely generative approaches by providing an extensible intermediate representation that can be used to implement sophisticated domain-specific compiler pipelines.
At the same time LMS is hackable: since it is just a library, all aspects can be modified or extended to suit a particular purpose.
The following tutorials are available:
Getting Started
Rep[T] vs T
Shonan HMM Challenge
Sparse matrix vector multiplication
Selective unrolling and precomputation
Regular Expressions
From interpreters to compilers using staging
Ackermann's Function
From recursive functions to automata
Automatic specialization using staging
Automata-Based Regex Matcher
NFA to DFA conversion using staging
SQL Engine
Efficient data processing
Fast Fourier Transform (FFT)
Numeric kernels and rewriting optimizations
Sliding Stencil
Rearranging loop shapes
The material below has been extracted from Tiark's PhD thesis (PDF) and is still undergoing revision for the web.
Comments? Suggestions for improvement? View this file on GitHub.