Shunting functions and branches 🚂

Oh boy, these last few weeks working on Credence have been tough.

Recall that in my previous post, I spoke about breaking down the AST into a queue of operators and operands. This algorithm has a name, the Shunting Yard algorithm, similar to a shunting yard of tracks and locomotives.

For the most part, it worked great — until I encountered functions and function arguments — the algorithm appeared to fall apart. The shunting yard algorithm was created initially for arithmetic operators, more or less; fortunately, however, it can be extended:

In general, the algorithm turns expressions in infix notation into reverse polish notation:

2 3 add   →  add(2,3)
2 3 4 add mul  →  mul(2, add(3,4))

How could we properly convert functions and their arguments while keeping operator precedence and associativity? The answer - drum roll 🥁 - treat functions themselves as operators that accept k arity as operands:

x y f 2  →  f(x, y)

Here we have a function operator f with an arity of 2 and pop the operands x and y off the operand stack. Let's take a look at extending this further for function arguments:

x j 1 y f 2  →  f(j(x), y)

We see that our function operator j takes one operand that we pop off and push the result back into the stack. Next, we see that f has an arity of 2 operands, so we pop off the j call and y and use these as arguments, and we're done!

For branches, I had to put away my conductor hat and design a proper branching state machine. Seriously, I'll be dreaming about stacks for weeks ...

Here's the class definition in case you'd like to take a look for yourself. The ITA algorithm works by breaking down function definitions into "statement blocks" and then using recursive descent on the statement types.

When we encounter a branching statement, we add a label to the stack for the block and increment the "level." Here are the branch types:

constexpr auto BRANCH_STATEMENTS = { "if", "while", "case" };

Of course, we must note that a branch may include another branch (a nested if, or nested loops within an if, etc.). As we continue our recursive descent, each time we encounter a branch statement, we increment the level and push a new label onto the stack, using this label to continue execution. When we're done with the block, we pop the label off the stack.

It took me about a week to finish an algorithm I was happy with, and by the time I was done, my (imaginary) beard was halfway to the floor, Haha.

One final note, I'm very happy with the outcome of ITA and probably won't be using another IR. The next (and final) step will be translating into target machine code. I've previously discussed SSA, sea of nodes, and other methods used in compilers like LLVM. However, now I know personally that these are very academic in nature and not necessary for a language as simple as B, given my optimization goals.

Let your problem statement choose the tools, not the other way around!