This is the homepage of the Computer Science for All courses by Professor Christoph Kirsch.
This is an introductory class on compiler construction for bachelor students in computer science. The goal of the class is to introduce basic principles of compilers for students to understand the design and implementation of programming languages. Seeing and actually understanding self-compilation is the overarching theme of the class, and the sentence the class earns is this: a compiler is a proof system for syntax and a constructor of semantics, and every semantic question it seems to answer is a chosen approximation.
After taking the class, students are able to understand the difference between syntax and semantics of a programming language, how syntax is specified and efficiently checked, how semantics is efficiently implemented through code generation, how a compiler that compiles itself is bootstrapped, and how a program becomes a formula that a solver can check within a bound.
Week 1 is the talk What is Selfie?. The lectures follow one axis, from the small to the vast to the countable to the uncountable, in six stations: I Size, II Notation, III Meaning, IV Cost, V Machines, VI Intelligence. Each lecture is an HTML deck with a PDF rendering next to it, and ends with a piece of music and, in the introductory class, two things to read. The decks are at selfie.cs.uni-salzburg.at/classes/cc.
| week | station | lecture | assignments |
|---|---|---|---|
| 1 | spine | What is Selfie? (pdf) | print-your-name |
| 2 | I, II | The Scanner (pdf) | hex-literal |
| 3 | II | The Parser (pdf) | |
| 4 | III | Symbols and Types (pdf) | bitwise-shift-compilation |
| 5 | II | Expressions (pdf) | bitwise-shift-execution |
| 6 | III | Statements (pdf) | bitwise-and-or-not, logical-and-or-not |
| 7 | III | Procedures (pdf) | for-loop, lazy-evaluation |
| 8 | III | Self-Compilation (pdf) | array-access |
| 9 | III | Optimisation and Rice (pdf) | array-allocation |
| 10 | IV | Semantics as a Formula (pdf) | array-multidimensional |
| 11 | IV | SAT (pdf) | struct-declaration |
| 12 | IV | Bounded Model Checking (pdf) | struct-execution, rotor-check |
| 13 | V | Generated Code (pdf) | |
| 14 | VI | What is a Compiler? (pdf) |
The class works by explaining the basic principles behind selfie, a software system written in a tiny subset of C called C* that implements a self-compiling compiler targeting a tiny subset of RISC-V machine code called RISC-U, a self-executing RISC-U emulator, and a self-hosting RISC-U hypervisor. Selfie also comes with rotor and bitme, a model generator and a bounded model checker that turn a RISC-U binary into a formula and ask a SAT or SMT solver whether any input reaches a bad state within a bound.
Selfie features an autograder for the compiler assignments, one or two per week as listed above, ending with rotor-check: generate the model of a program that exercises your own language extension and let bitme find the input that reaches a bad state, or the bound up to which none does.
The textbook is What is Intelligence? Discovering Unproven Truth; the Programming and Cost chapters are this class, and the Meaning chapter is its theory.
The class is organized as part of a series of Computer Science for All classes.