Zicc has been a long running project of mine. The first commit on the GitHub repo goes back all the way to 2023, and that was like the third rewrite.

Even the name changed multiple times. From ic4 “IntCode C CrossCompiler” when I believed I would be able to write a self-hosting C compiler, to iccc “IntCode C Compiler” when I realized Intcode was less a programming language and more an instruction set, to the final zicc “Zanna IntCode Compiler” when I gave up on self-hosting and decided that a working compiler was enough.

The reason for those false starts are multiple, and plague many, many of my projects. First of all, I like a clean slate. This is the inevitable reality of the Pareto principle: the first few percent of the work are the most satisfying, as they swat down large parts of the wanted result.

Then there is the lack of accountability. No one saw what I was doing, and that gave rise to next to no stakes in not reaching the end. Projects that I actually use like dices had only a couple of restart, usually due to technical choices at the start that revealed themselves being less than optimal.

The hard part

When I started ic4, I wrote the vm, then an assembler, then half a parser, then left. iccc had a parser, and some code generation, and then stop. zicc is where I finally conquered my road block: the type system.

Who knows me knows I love type systems. They are great part of a talk that was not given by me, and will probably take form of a blog post here at some point. So, of course, the type system must be as over-engineered as possible!

Putting the int in Intcode

Let’s start easy. Of course, there is int. Duh, Intcode. One cell, one int. Easy, right?

Integers can be negative: 1101,100,-1,4,0 is a valid program (find 100 + -1, store the result in position 4).

Well, then it’s signed…. signed what? 32-bits? 64-bits? What’s the spec saying? Ah yes, no spec. Day 9 to the rescue:

The computer should have support for large numbers. Some instructions near the beginning of the BOOST program will verify this capability.

Shite… well, this will be a problem for another day.

Pointers: why I left C

Wanna know why I left the idea of a C compile alone? Because pointers. Intcode has two way of pointing to memory - absolute, and relative to a register called the Relative Base Register.

If the register is used to signal the top of the stack, this naturally maps to two kinds of pointers: pointers to static variable, and pointers to variables on the stack. Even worse, there is no way to access the value of RBR directly, making converting between the two pointers impossible.

Others less interesting stuff

Arrays of specified length, unknown type for pointer to unknown, function types, composite types.

Composite types in particular cover both unions and structs (and the anonymous nesting) by being a map to type and offset.

The type table

The problem: types are recursive, and checking one against the other is gonna be slow. I don’t want that. So, a type table is born: an array with all types connected to a numeric id (and keeping names while it’s at it).

This table upholds a magnificent lie: that all types have an u64 connected, and that two types are equal iff the two ids are equal.

How? Some smart way of mashing all bits inside the eight bytes?

Yep. It assigned the ids as it goes. Want to know what is the id of &[int;3]? It is… umm… five. Always was, always will be.

This holds as long as the types are not recursive. Then, you end up in a problem that is the only reason why I learnt Prolog, after months of getting totally destroyed by it.

I’ll implement it again, trust me, but for now I am good with only non-recursive types, guaranteed by having to give the id of the types you are using to define your type to have its id.

So?

This is the current state. Stay tuned to see how I fail again at code generation. But the easy part of the hard part is done, and I’ll not get back on it until at least a file compiles and run. Maybe this time it’s the right time.