Skip to content

TinyCompiler: a compiler in a week-end

Introduction

Have you ever wondered how a compiler works, but you never found courage to find out? Then this series of articles is for you. I have never had the chance to look under the hood either, but one week-end I have decided to to write a translator from the esoteric programming language wend (short for week-end), which I just invented myself, into regular GNU assembly. The goal is to keep the code as tiny as possible, 500-ish lines of python sounds great. The main repository lives on github (don't forget to check out other tiny* repositories in my profile).

Spoiler alert: I am currently working on a tinyoptimizer, a minimalist optimizing compiler.

So behold, here is a program that uses virtually all concepts in wend:

Fixed-point square root 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
main() {
    // square root of a fixed-point number
    // stored in a 32 bit integer variable, shift is the precision

    int sqrt(int n, int shift) {
        int x;
        int x_old;
        int n_one;

        if n > 2147483647/shift { // pay attention to potential overflows
            return 2 * sqrt(n / 4, shift);
        }
        x = shift; // initial guess 1.0, can do better, but oh well
        n_one = n * shift; // need to compensate for fixp division
        while true {
            x_old = x;
            x = (x + n_one / x) / 2;
            if abs(x - x_old) <= 1 {
                return x;
            }
        }
    }

    int abs(int x) {
        if x < 0 {
            return -x;
        } else {
            return x;
        }
    }

    // 25735 is approximately equal to pi * 8192;
    // expected value of the output is sqrt(pi) * 8192 approx 14519

    println sqrt(25735, 8192);
}

Since I am interested in a compiler, the language being implemented is of no importance. I am not trying to invent yet another C++ killer, that is not the point. Wend is a simple language similar to C or Java, but with far less features. Wend is strongly typed, with no pointers, arrays, closures, dynamic memory allocation, garbage collector or parallel computations. It supports nested functions and function overloading, a bare minimum for the first dive into compiler theory.

By the way, I have spent a lot more time on writing test programs than on the compiler itself :)

Graphics!

It is so dull to compute Fibonacci numbers, so here are more eyecandy examples for the compiler, check test-programs/gfx/*.wend files.

Mandelbrot set

Zero-player breakout game

Fire

Sunset race