Crafting an Interpreter in C

Crafting an Interpreter in C

The second half of Crafting Interpreters implements a new interpreter in C. As a high school student I was gifted the canonical text on C, “The C Programming Language”, (nicknamed K&R after the authors Brian Kernighan and Dennis Ritchie). I bounced off of it pretty hard. It’s been a gratifying experience to take another shot at learning the language.

Resources for Learning C

Coming from Javascript or Python, Java is, in my opinion, pretty easy to understand. It’s a little verbose but the semantics were ultimately familiar¹. However with C there were a few fundamental language features used frequently in the book that required me to dedicate some attention to learning them before I could be productive writing C myself vs just copying code out of the book. I resorted to using good old fashioned books to brush up on those features and that’s what I would recommend if you’re in the same boat.

My primary recommendation is “Modern C” by Jens Gustedt. Best practices for C and indeed the language itself have evolved over the decades since K&R was written. “Modern C” is also organized into sections for people with different experience levels sometimes covering the same language concept more than once in more depth each time. I think it’s very well organized for someone who wants to try and grab the language features she needs as quickly as possible at exactly the level of depth she needs at the moment.

The most famous book about C is the aforementioned K&R. I do think that this book is a really fascinating document. You can learn a lot about the mindset the authors of C had when the wrote it. While it’s definitely worth reading, I don’t think this is the best book for learning C today. It’s a great supplement to “Modern C” and I’ve known a few people who love the teaching style in this book.

A Few Features and Concepts

Here’s a quick survey of some of the things I needed to look up to get productive working through the exercises and extending the codebase.

Pointers and Memory Allocation

This is where C deviates the most heavily from other languages. C gives you basically one type of usable collection: fixed sized arrays². Other types of collections like growable array lists and stacks are built on top of pointers and memory allocation. If you’re not familiar with these features you will probably want to dedicate some time to brushing up on this. “Modern C” and K&R both cover this in a lot of detail and I used both to improve my understanding.

The Stack and the Heap³

Learning C it can be helpful to understand a little terminology about two different ways C programs store their variables in memory: stack memory and heap memory. You don’t necessarily need to understand how they work in depth to use the language, but stack memory and heap memory are referenced frequently in teaching materials about C. When you implement C Lox you’ll actually see analogous concepts used to manage the data in Lox programs too.

Stack Memory

Variables that you declare in your functions have a fixed size and they go on the stack. Integers, fixed length strings and array, pointers to addresses. The compiler knows at compile time how much space each function call will need from the stack (except for variable-length arrays, which are outside the scope of this article).

Heap Memory

When you allocate memory with malloc or realloc that goes on the heap. The heap can grow as you ask for more and more memory. This is the memory you’re worried about when you’re learning about memory management in C and the memory that would most likely be responsible for memory leaks.

Function Pointers

In Javascript and Python you can store functions in variables and pass them around. The analogous feature in C is the function pointer. These are used pretty heavily in the parser code in cLox to delegate to different functions when different operators show up in expressions. I found the syntax a little odd so it’s worth reading more about them for that reason, but I think they’re otherwise pretty intuitive.