Build a programming language

What you are building

A language implementation reads source text and gives it a precise meaning. Use a host language that provides strings, lists, maps, and recursive functions. JavaScript or Python is enough for the complete project.

You will define the syntax and behaviour. That includes operator precedence: the parser must decide whether 2 + 3 * 4 means 2 + (3 * 4) or (2 + 3) * 4. Tests make each choice explicit.

Teal entries are build checks. The three magenta entries explain an implementation problem and link to the corresponding Language Engineering lesson.

Project milestones

1. List the stages needed to evaluate 2 + 3.

   Not the answer. The jobs. You found where one number ended and the next began, you saw which sign sat between them, and then you did the adding. Those three jobs are the three programs you are about to write and the whole build is them getting better at their work.

2. Turn a line of characters into a list of tokens.

   A token is one small piece of the text with a label on it. This is a number. This is a plus sign. This is a name. Feed in 12 + 3 and get three tokens back, with the spaces thrown away and the 12 arriving as one number rather than two separate digits. Print the list and read it.

3. Parse operator precedence correctly.

   Left to right: 2 and 3 make 5, and 5 fours are twenty. Every arithmetic teacher you have ever had says fourteen. Nothing in the token list settles it, because the tokens are identical whichever answer you want.

   What you need

   Operators take hold of their neighbours with different strengths, and that is called precedence. Times grabs the numbers either side of it before plus gets near them. You get it by writing the rules of your language down as a grammar: a short list of what a legal line may look like, with one rule per strength. Those rules turn a flat line into a shape, with the times sitting under the plus. The times is then finished before the plus can hand back an answer, and there are no special cases anywhere.

   step 4Write the rules that say which lines are legal step 6Make 2 + 3 * 4 come out fourteen, not twenty
4. Build and print an abstract syntax tree.

   A tree is drawn upside down. One box sits at the top, called the root, with lines running down to the boxes it holds. Those are its children, and each of them can hold more. For 2 + 3 * 4 the root is the plus. It holds a 2 on one side and the times on the other, and the times holds the 3 and the 4. Print it with indentation and check the shape by eye. If the times came out above the plus you would get twenty. You can see that before you run anything.

5. Evaluate the syntax tree.

   One function, one node at a time. A number node hands back its own number. A plus node asks each of its two children what they are worth and adds the two answers. It asks by calling itself, which is the whole trick, and the answers come back up the tree until the root is holding the only one left. Short. It is a working calculator.

6. Store and look up named values.

   One line saying that x stands for 4, the next line saying x * 3, and twelve comes out. The names and their values live in a table you carry with you as you walk the tree, and the usual word for that table is an environment. Then try the case you would rather avoid: use a name you never gave a value to, and make it say so instead of quietly answering nought.

7. Add conditional statements and loops.

   Two more kinds of node. An if node holds a test and a body. A while node holds the same two things, and runs the body again for as long as the test keeps answering true. That is the first time your walker visits the same node twice. Write a program in your own language that counts down from ten and stops on its own.

8. Implement function calls and returns.

   Call the same function twice and it goes wrong in one of two ways. The second call finds the first one's value for x still sitting in the table. Or it finishes and hands control back to where the first call was made from, not the second. One name shared between two calls, one place to come back to, and both of those are wrong.

   What you need

   Every call needs its own private space holding two things: the values it was called with, and where to carry on once it has finished. That space is a frame, and frames pile up, newest on top, and come off in the reverse order. Two calls make two frames, with two separate copies of everything. That is also what lets a function call itself without the two calls treading on each other.

   step 12Call a function, and watch the frames stack up
9. Run user-defined and recursive functions.

   Define a function in your language, call it with something, get an answer back. Then write the one that multiplies 5 by 4 by 3 by 2 by 1 by calling itself. Watch the frames go on and come off, and check that it says 120.

10. Compile repeated work to bytecode.

    On every pass through the body your walker asks what kind of node this is, where this name lives, and which child to visit first. Every one of those answers was settled when the tree was built, and not one of them changes between passes. Count the questions for a loop of ten, then for a loop of a thousand. The tree did not change and the asking went up with the count.

    What you need

    Answer the questions once, before anything runs, and write down what to do as a flat list of very small instructions. That list is called bytecode. Running it needs a far simpler machine than a tree walker. Every instruction takes its inputs from the top of a pile of values, and drops its answer back on the same pile. This is not a second project. It is the same tree, read once instead of once per pass.

    step 13Compile it once instead of walking the tree every time
11. Run a complete program on the bytecode machine.

    One command that reads a file, breaks it into tokens, builds the tree, compiles it and runs the instructions. Point it at something you actually want: a scorekeeper, a dice roller, a room you can walk around in. A program you wrote, in a language you wrote, giving the right answer. That is the build finished.

Review the language in four passes

Review the same implementation for expected behaviour, invalid input, execution cost, and internal checks.

Course links for each pass

Each of those three later passes has a step behind it, in the course about building things that keep working. Take them when you want them and not before.

1. Choosing inputs you would never have typed.
   Make it correct

   Your own examples are the ones you built the code to pass, so they find nothing. Carve the possible inputs into regions instead, where your code is supposed to behave the same way all through a region. Take one case from each region. Then take the boundary between two regions as well, because a boundary is where somebody wrote "greater than" and meant "greater than or equal to".

   step 4Choosing the cases that matter
2. Keeping the walker and the compiler side by side.
   Make it fast

   Write down the list of operations both of them offer, and what each operation promises, with nothing said about how it does it. That list is an interface. When both the walker and the compiled machine answer to the same one, the same program runs through either and the same tests check both. Choosing between them becomes a decision about speed rather than a rewrite.

   step 11One interface, two implementations
3. Catching a broken tree where it was built.
   Make it survive

   Your tree nodes quietly promise things about their own insides: a plus holds exactly two children, a name node holds a name that is not empty. That promise is the node's representation invariant, and nothing checks it unless you write the check. So write it: a small function that looks inside a node and answers true or false, run every time a node is made. It catches a bad node where it was built rather than five steps later inside the evaluator.

   step 9The tripwire inside the type

Related projects and courses

Reading text, working out what it means, and then doing it is not a trick reserved for programming languages. It is the same machinery under a search box that accepts price < 20, a spreadsheet formula, a configuration file and the query planner inside a database. Build a tokeniser, a parser and an evaluator by hand once, and none of those is a closed box any more. Nor is the compiler you use for your day job.

All builds or read Language Engineering straight through, which covers the same ground in the same order and goes considerably further, and Software Construction for the three later passes.