not-abc: a tiny self-hosting compiler used for teaching

[michaellehn]

Hi,
I thought this project might be of interest to some people here.

I teach high-performance computing to mathematics students at Ulm University. One of the things I wanted students to understand is what actually happens between source code and the machine, without turning the course into a full compiler construction course.

For that purpose I developed a small C-like language called ABC and a compiler for it. Later I wondered how small I could make a compiler that is still powerful enough to compile itself. That became not-abc:

https://github.com/michael-lehn/not-abc

It supports functions, local and global variables, pointers, if/else, while loops, recursion and dynamic memory. The compiler itself is written in not-abc and generates LLVM IR.

The point isn't really to create yet another programming language. I wanted the complete compiler to be small enough that students can understand the whole path from source code to generated code, while still getting to the point where self-hosting becomes real rather than something they only read about.

I'm currently rewriting more of the teaching material from German into English. I'd be very interested in meeting people here who are working on similar small compilers, languages or teaching projects, or simply find this kind of thing interesting. Feedback and discussion would be very welcome.

The ABC compiler and language used for this are available here:
https://github.com/michael-lehn/abc-llvm

[thewrongchristian]

I teach high-performance computing to mathematics students at Ulm University. One of the things I wanted students to understand is what actually happens between source code and the machine, without turning the course into a full compiler construction course.

For that purpose I developed a small C-like language called ABC and a compiler for it. Later I wondered how small I could make a compiler that is still powerful enough to compile itself. That became not-abc:

https://github.com/michael-lehn/not-abc

I think this is pretty neat!

I always wondered how the likes of Thomson and Ritche created the B then C programming languages, bootstrapping from implementations that don't even provide structures (I can't imagine doing anything complex in Fortran!).

I have a couple of questions/suggestions:

- Is the source in examples/not-abc.abc the source that produced the top level not-abc.ll?
- There is no LICENSE file in the repository, so it's not clear under what license the compiler is available.

[Alexey1994]

I prefer programming with wires using a Richards controller; it’s much closer to reality than typing in abstract bytes.

[sandras]

I'd be very interested in meeting people here who are working on similar small compilers, languages or teaching projects, or simply find this kind of thing interesting. Feedback and discussion would be very welcome.

I have written a variant of Forth, which, eventually, I would like to make self-hosting. It does compile the threaded-code portion of itself for now.

[michaellehn]

I teach high-performance computing to mathematics students at Ulm University. One of the things I wanted students to understand is what actually happens between source code and the machine, without turning the course into a full compiler construction course.

For that purpose I developed a small C-like language called ABC and a compiler for it. Later I wondered how small I could make a compiler that is still powerful enough to compile itself. That became not-abc:

https://github.com/michael-lehn/not-abc

I think this is pretty neat!

I always wondered how the likes of Thomson and Ritche created the B then C programming languages, bootstrapping from implementations that don't even provide structures (I can't imagine doing anything complex in Fortran!).

I have a couple of questions/suggestions:

- Is the source in examples/not-abc.abc the source that produced the top level not-abc.ll?
- There is no LICENSE file in the repository, so it's not clear under what license the compiler is available.

Thanks! And thanks for pointing out the missing license — I simply hadn't thought about that. I'll add one.

Regarding the bootstrapping process, there is a little bit of history behind examples/not-abc.abc.

During the course, the students wrote a not-abc compiler in ABC over the course of the semester. The reference implementation is the one in the `not-abc` subdirectory of the ABC repository:

https://github.com/michael-lehn/abc-llv ... in/not-abc

(Some students actually added a few features of their own. Like array declarations.)

That compiler has two backends: one for the ULM Architecture (Ulm Lecture Machine), the small machine we use in the course, and one generating LLVM IR. The separation is deliberately very simple. gen.hdr describes the interface to the code generator, and there are two implementations:

- gen_simple.abc generates assembly for the ULM Architecture. This is the backend the students implemented.
- gen_llvm.abc generates LLVM IR. I hacked that together in an afternoon at the end of the semester, after the idea occurred to me during the last week of the course.

The Makefile therefore builds two compiler executables, not-abc_simple and not-abc_llvm.

The examples/not-abc.abc file in the not-abc repository came afterwards. I took all the .abc source files of the compiler and manually reduced them to the much more primitive not-abc language.

For example, I replaced enum constants with integer literals. Struct member accesses such as `foo.x` and `foo.y` become something like *(&foo + 0) and *(&foo + 8 ) if the members have offsets 0 and 8.

It certainly doesn't make the source prettier, but with (Neo)Vim and a few suitable macros it is mostly mechanical work. The smaller factorial.abc and especially list.abc examples perhaps give a better impression of what programming in such a primitive language looks like.

Converting the compiler itself this way took me roughly one morning.

And that finally gives you the bootstrap:

1. Use not-abc_llvm (which is itself written in ABC) to compile examples/not-abc.abc into not-abc-v0.ll.
2. Use clang to turn not-abc-v0.ll into the executable not-abc-v0.

At that point the compiler is bootstrapped.

For self-hosting, use not-abc-v0 to compile examples/not-abc.abc again, producing not-abc-v1.ll.

not-abc-v1.ll is identical to not-abc-v0.ll.

So yes: examples/not-abc.abc is the source from which the top-level not-abc.ll ultimately comes.

And thanks again for mentioning the license. That was simply an oversight on my part. I'll add a license file.

[michaellehn]

I prefer programming with wires using a Richards controller; it’s much closer to reality than typing in abstract bytes.

Fair point Although there aren't any wires you can actually touch, we do go one step further down:
https://github.com/michael-lehn/ulm-on-ice
The ULM CPU used in the course is implemented from logic gates and runs on an FPGA. So at least the abstract bytes eventually turn into actual signals somewhere.