selfie

An educational software system of a tiny self-compiling C compiler, a tiny self-executing MIPS emulator, and a tiny self-hosting MIPS hypervisor.

View the Project on GitHub

Selfie is a project of the Computational Systems Group at the Department of Computer Sciences of the University of Salzburg in Austria.

The Selfie Project provides an educational platform for teaching undergraduate and graduate students the design and implementation of programming languages and runtime systems. The focus is on the construction of compilers, libraries, operating systems, and even virtual machine monitors. The common theme is to identify and resolve self-reference in systems code which is seen as the key challenge when teaching systems engineering, hence the name.

There is a free book in early draft form called Selfie: Computer Science for Everyone using selfie even more ambitiously reaching out to everyone with an interest in learning about computer science.

Selfie is a fully self-referential 7k-line C implementation of:

  1. a self-compiling compiler called starc that compiles a tiny but powerful subset of C called C Star (C*) to a tiny but powerful subset of MIPS32 called MIPSter,
  2. a self-executing emulator called mipster that executes MIPSter code including itself when compiled with starc,
  3. a self-hosting hypervisor called hypster which is based on a tiny microkernel implemented in mipster and provides MIPSter virtual machines that can host all of selfie, that is, starc, mipster, and hypster itself, and
  4. a tiny C* library called libcstar utilized by selfie.

Selfie is kept minimal for simplicity and implemented in a single file. There is a simple linker, disassembler, profiler, and debugger as well as minimal operating system support in the form of MIPS32 o32 system calls built into the emulator.

C* is a tiny Turing-complete subset of C that includes dereferencing (the * operator) but excludes composite data types, bitwise and Boolean operators, and many other features. There are only signed 32-bit integers and 32-bit pointers as well as character and string literals. This choice turns out to be helpful for students to understand the true role of composite data types such as arrays and records. Bitwise operations are implemented in libcstar using signed integer arithmetics helping students gain true understanding of two’s complement. C* is supposed to be close to the minimum necessary for implementing a self-compiling, single-pass, recursive-descent compiler. C* can be taught in around two weeks of classes depending on student background.

The compiler can readily be extended to compile features missing in C* and to improve performance of the generated code. The compiler generates MIPSter executables that can directly be executed by the emulator or written to a file in a simple, custom-defined format. Support of standard MIPS32 ELF binaries should be easy but remains future work.

MIPSter is a tiny Turing-complete subset of the MIPS32 instruction set. It only features arithmetic, memory, and control-flow instructions but neither bitwise nor byte-level instructions. MIPSter can be properly explained in a single week of classes.

The emulator implements minimal operating system support that is meant to be extended by students, first as part of the emulator, and then ported to run on top of it, similar to an actual operating system or virtual machine monitor. The fact that the emulator can execute itself helps exposing the self-referential nature of that challenge. In fact, selfie goes one step further by implementing microkernel functionality as part of the emulator and a hypervisor that can run as part of the emulator, on top of the emulator, and even on top of itself, all with the same code.

Selfie is the result of many years of teaching systems engineering. The design of the compiler is inspired by the Oberon compiler of Professor Niklaus Wirth from ETH Zurich. The design of the selfie microkernel is inspired by microkernels of Professor Jochen Liedtke from University of Karlsruhe.