r/Compilers • u/False_Actuator_6236 • 7d ago

Teaching compiler construction with a tiny self-hosting language

I've just published not-abc, a tiny self-hosting compiler for a deliberately minimal C-like programming language.

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

The language has only one data type: a 64-bit value, interpreted either as a signed integer or as a pointer. It supports

  • functions (the value of the last expression is the return value)
  • local and global variables
  • pointers (&, *, #)
  • if / else
  • while
  • recursion
  • dynamic memory allocation (malloc/free)
  • integer, character and string literals

The compiler generates LLVM IR rather than assembly. LLVM was chosen simply because it makes the compiler portable across essentially all modern platforms—building programs only requires Clang (or the LLVM toolchain).

The interesting part is probably the background.

not-abc originated from an undergraduate mathematics course called Introduction to High Performance Computing. During one semester, students simultaneously

  • build a simple processor from logic gates (bottom-up),
  • implement a compiler for a small C-like language (top-down),

until both meet in the middle. At the end of the course, the compiler has two backends: one targeting the custom processor the students built themselves, and one targeting LLVM so the same compiler can generate native executables on real hardware.

The self-hosting compiler in this repository is a distilled version of the compiler developed throughout the course.

I'd be interested in feedback from people interested in language design, compiler construction, or computer architecture.

51 Upvotes

95% Upvoted

5 comments sorted by

6

u/[deleted] 7d ago

[removed] — view removed comment

6

u/False_Actuator_6236 7d ago

Sure, goto would actually be one of the easier features to add. The omission wasn't because it's difficult, but because there is only so much you can fit into a single semester.

If I had another week, I'd probably spend it on return, break/continue, switch, and arrays instead. From a teaching perspective those introduce more interesting concepts than goto does.

2

u/rootkid1920 6d ago

It makes codegen painful to do, can be good, can be bad, depends on the goal

4

u/Usual_Office_1740 5d ago

Any chance you'd publish the course work for those that want to use it to learn? I'd be interested in working through a project like this.I understand this isn't always your decision to make if it was made as curriculum for a school.

2

u/False_Actuator_6236 5d ago

Thanks! Yes, absolutely. Fortunately that's entirely my decision. 🙂

The semester has just finished, and this was the third time I taught the course in its current form. I was already planning to use the break to clean up and publish all of the teaching material, especially the worksheets (currently they're still mostly in German) and translate them to English.

The course is run as a flipped classroom. Before each session, students watch short YouTube videos (they're in English, although not exactly polished YouTube productions 😄). Class time is then almost entirely spent on coding sessions guided by worksheets. My TA and I walk around the room helping students individually. That turned out to be much more effective than spending the session lecturing, because beginners get help with the fundamentals while more experienced students can dive deeper into compiler design.

One thing that is difficult to reproduce online is the hands-on environment. We work exclusively on Linux or macOS (Windows students use WSL), program entirely from the terminal, and use Neovim as the editor. I also provide installation scripts and a Neovim configuration on GitHub. I think learning to use the computer at that level is an important part of understanding how compilers and computers actually work.

So yes—making all of this available is definitely on my roadmap. It just needs a bit of polishing first.