Lowkey is an educational language, interpreter, and compiler that novice programmers can incrementally write from scratch, step by step!

The goal is to iteratively write a compiler from scratch for a simple statically typed language, with visible progress and feedback ^{1 2}. Each step aims to be 30 minutes or less. You may use any systems programming language you want, as long as it allows you to low-level access to memory and empowers you to build arbitrary data structures ³.

Lowkey is loosely based on the Odin programming language and is meant to only implement those language features that are common to most programming languages.

To get started, open step-001.md and complete the task.

The compiler will be implemented incrementally, step by step, in 30 minute sitdown sessions. Each step will have a suite of test files to pass. Each step will start with a copy of the source code from the previous step (a la Handmade Hero).

• step-001.md : Create a Hello, world! program in your chosen language.
• step-002.md : Create a tokenize() function and have it find the starting byte positions of words in a sentence.
• step-003.md : Have tokenize() return a dynamic array of Tokens with token type, start byte, and length. Check that start byte and length produce the expected values from the source text.
• step-004.md : Add line number, column number, and token index to the Token struct, as well as some debugging output.
• step-005.md : Tokenize variables (my_var_1), multi-digit integer constants (1_337), and the assignment operator (:=)
• step-006.md : Return a list of TokenizationError structs from tokenize() whenever an invalid integer is encountered during tokenization.
• step-007.md : Create a executable that will act as a REPL (read execute print loop) - i.e. an interactive prompt.
• step-008.md : In the REPL, print nice-looking error messages from the error list returned by tokenize().
• step-009.md : Build a simple intepreter by creating an execute() function to "execute" tokens and return the final state.
• step-010.md : In the REPL, add a state command to print out the program state.
• step-XXX.md : Add a source command to print out the current source text that has been accumulated.

• step-XXX.md : Create a parse() function that takes in a token list and outputs a simple AST with naive precedence.
• step-XXX.md : Build a simple tree-walk interpreter in REPL mode.
• step-XXX.md : Parse -7234 + 3 and create an actual Abstract Syntax Tree (AST) instead of a list of nodes; AST creation visualization.
• step-XXX.md : Create a simple Lowkey runtime executable with an internal function called lowkey_main_temp() that returns a single constant number 42, and print out that value.
• step-XXX.md : Create an assembly file for your given architecture and create a global function called lowkey_main that simply returns a constant number 43. In the Lowkey runtime executable, replace lowkey_main_temp() with lowkey_main(). Finally, include the assembly file into the build, and verify that the runner prints out 43.
• step-XXX.md : Take the single token output for 7234 and create an assembly file that returns that value, and see the runner print it out.
• step-XXX.md : Tokenize -7234 (tokenize a unary operation).
• step-XXX.md : Tokenize -7234 + 3 (tokenize a binary operation; skip whitespace).
• step-XXX.md : Take AST for -7234 + 3 and generate an add assembly instruction. Then, have that add result be returned instead of a constant number, and make sure it prints.
• step-XXX.md : Tokenize and parse return -7234 + 3, so the return asm is explicitly generated based on AST instead of implicitly generated.
• step-XXX.md : Tokenize and parse the function lowkey_main :: proc() -> int { return -7234 + 3 }, and don't implicitly generate any more asm.
• step-XXX.md : Tokenize, parse, and generate - as either a binary operation or unary operation.
• step-XXX.md : Tokenize, parse, and generate more binary operations: *, /.
• step-XXX.md : Parse 1 + 2 * 3 + 4 with proper precedence, according to Jonathan Blow's technique.
• step-XXX.md : Tokenize and parse () for explicit precedence ((1 + 2) * (3 + 4)).

• step-XXX.md : Tokenize, parse, and generate local variables of type int (s64).
• step-XXX.md : Tokenize, parse, and generate local variables of type uint (u64).
• step-XXX.md : Tokenize, parse, and generate local variables of type float (f64).
• step-XXX.md : Tokenize, parse, and generate local variables of type bool.
• step-XXX.md : Emit parse errors when values of incorrect types are used together.
• step-XXX.md : Tokenize, parse, and generate ==, !=, <, <=, >, >=.
• step-XXX.md : Tokenize, parse, and generate if <condition> {}.
• step-XXX.md : Tokenize, parse, and generate for {}.
• step-XXX.md : Tokenize, parse, and generate for <condition> {}.
• step-XXX.md : Tokenize, parse, and generate continue.
• step-XXX.md : Tokenize, parse, and generate break.
• step-XXX.md : Tokenize, parse, and generate add_ints :: proc(a: int, b: int) -> int { return a + b } called by lowkey_main()
• step-XXX.md : Write a program to solve some kind of puzzle, to prove that our little language works so far!
• step-XXX.md : Tokenize, parse, and generate structs.
• step-XXX.md : Tokenize, parse, and generate global variables.
• step-XXX.md : Tokenize, parse, and generate casting: int(<val>), float(<val>), uint(<val>)
• step-XXX.md : Tokenize, parse, and generate an int pointer type and variable: ^int and &.
• step-XXX.md : Tokenize, parse, and generate dereferencing an int pointer: int^.
• step-XXX.md : Tokenize, parse, and generate assigning to a dereferenced int pointer: int^ = <val>.
• step-XXX.md : Tokenize, parse, and generate raw unions.
• step-XXX.md : Tokenize, parse, and generate enumerated unions/tagged unions.
• step-XXX.md : Tokenize, parse, and generate a switch statement. (needed? I might want to skip this, since you can use ifs)
• step-XXX.md : In the REPL, record command history and make up arrow cycle through entries.
• step-XXX.md : In the REPL, make ctrl-r search through the command history.

See the reference-implementation for example code for all the steps, written in Odin. Please don't look at this unless you get stuck and have already looked at the hints in that step's readme.

I recommend watching these videos by Brian Will to get a sense for what is common between most programming languages:

• Every Programming Language in 15 Minutes

• Every programming language in (another) 15 minutes: data types

See the Lowkey language overview (WIP!) for more information about Lowkey.

I have a few opinionated suggestions for you, before you get started:

• Don't use AI! This is for your own learning, so do it the old fashioned way.

• Start off implementing all your code in a single file, and resist the initial urge to organize things into multiple files.

  • There may come a time when you will want to make some natural splits as it becomes obvious, but remember that each split is not free - each one adds friction to your code. That can be good once you know the shape of the problem you are trying to solve! But until you get a sense of the full picture, 'premature program organization' can instead slow you down dramatically because you are more worried about how to split things perfectly than you are about writing the code, solving the problem, and doing the thing. So just do the thing!

  • For more on this, see Clean Code : Horrible Performance | Full Interview @ 39:24 and Semantic Compression.

• Write your code in a procedural style. What this means is that you want to think in terms of Plain Old Data (POD) objects and the functions that operate on them, not in terms of objects as self-aware beings that act. Ditch Object Oriented Programming (OOP).

  • For more on this, see CppCon 2014: Mike Acton "Data-Oriented Design and C++" from 12:24 - 25:29 and Object-Oriented Programming is Bad by Brian Will.

• Don't use object/class methods! Just use boring, old functions. So instead of something like this (in C++):

  tokenizer.parse(token_stream);

  Do this:

  tokenizer_parse(&tokenizer_state, token_stream);

  • The thing I dislike about methods on objects is that it's a lie. To the CPU, there is no such thing as a self-contained object that has code and data bundled together. Code actually lives in one spot, while the data lives in another, and the CPU even caches them separately at the lowest level of the memory hierarchy.

  • It's a subtle shift in thinking, but I think it's important, especially coming from higher-level languages that only deal with objects, methods, and closures.

  • To remember what functions work on what data objects, you can do a naming convention like object_action() and make the first argument a pointer to the data object (this is all that methods do under the hood).

  • For a more in-depth discussion on this, see How I Program C by Eskil Steinberg from 38:40 - 41:05 and Why does Odin not have any methods?.

• "Code like a 15 year old with 30 years of experience."

• If you are looking for a good programming language to use that is fast, powerful, and nudges you towards all the things I've mentioned above, give Odin a try! It's a C alternative that is a joy to program in.

  • Start with Introduction to the Odin Programming Language by Karl Zylinski.

• Crafting Interpreters by Robert Nystrom (Chapter 2 is a great introduction!)

• Discussion: Making Programming Language Parsers, etc by Jonathan Blow and Casey Muratori (the first 25 minutes or so is a great introduction to how to go about doing tokenization and parsing)

• Discussion with Casey Muratori about how easy precedence is... by Jonathan Blow and Casey Muratori

• Compiler Construction by Niklaus Wirth

• An Incremental Approach to Compiler Construction by Abdulaziz Ghuloum

• Zig Tokenizer and Zig Parser by Mitchell Hashimoto

• Lexing by Thorsten Ball

• Blaise by Ginger Bill. It's an educational compiler implementation to teach people how to make a compiler from scratch and all of the minimal stages to produce an executable.

• Chibicc by Rui Ueyama - Write a C compiler from scratch, incrementally.

• Real-time Operating Systems by Dr. James Archibald - Through a series of labs, incrementally write your own custom "YAK" RTOS from scratch in C and 8086 assembly and run it on the class 8086 emulator.

• Computer Enhance by Casey Muratori (15$/mo subscription) - Learn 8086 assembly and incrementally implement a complete 8086 emulator from scratch in part 1; learn how the CPU works from the perspective of a programmer in the other parts.

• Writing an OS in Rust by Phil Opperman and Intermezzos by Steve Klabnik - Write the very beginnings of your own x64 OS in Rust

• Handmade Hero by Casey Murator - Write a computer game from scratch, in 1 hour sessions (the consensus is to follow along for the first 30 days, and then as needed after that).