Last time on the intermediate-language series, we have discussed the static single assignment form of programs. As a very quick reminder, the main goal of SSA is to make both control flow and data flow of a program (or rather, of a single function within a program) as explicit as possible. Of course, this within the constraints of realistic compilers.

We have also discussed the role of φ instructions and how it might be better to instead make the data flow along control-flow edges explicit, in effect making all variables local to basic blocks (as opposed to functions). This would perhaps reduce our rather nasty φ problem (of course, we can't completely solve this problem, since it is, in a very real sense, a manifestation of a deep intrinsic property of programs… while φ instructions definitely have an ‘accidental complexity’ component, that is far from the whole story).

As a starting point today, let me revisit a data flow diagram from last week:

What we have here is, in essence, a state transformer: take the local state of the function, do some computations and spit out a new local state. Now the shape of that state is clearly not fixed: on the output, there are more variables than on the input. What we are doing is an implicit optimisation: we only consider live variables to be part of the state. Of course we could add y to the inputs and simply never use it (it is, after all, clearly dead when we enter this basic block).

But this isn't really too important: even if we try very hard to remove all dead variables from the state as soon as possible, we are still going to need those ‘pass-through lanes’ (like the one for c in the picture). If we look at this from the perspective of types, passing through those live variables has a real cost – they show up in the type signatures of our basic blocks.

When we connect two such blocks with an edge, we must match up each output variable of the first with an input variable of the latter: in other words, we must respect the types of those basic blocks. We have made the data flow very explicit, but we have lost all traces of composability – basic blocks carry a great deal of their context in their type signatures.

You might recall that back in the beginning of this series, I have claimed that functions are good at composition. And we don't even have to squint very hard to see a clear correspondence between our basic blocks, with their inputs and outputs, and the functions they compute. So can we learn something from functions to make our basic blocks more composable?

If you are familiar with functional programming, you might be aware that there are two ‘styles’ of function composition: pointed and point-free. So far, we have been engaged in using the pointed style, where arguments get names. At a first blush, naming all those pass-through arguments is what landed us in trouble in the first place, so perhaps we could make the point-free style work in our favour?

Well, I am glad you have asked. Point-free function composition gives rise to what is often called row polymorphism but not on records (the original context for row polymorphism), but on a stack. Before we delve into that, a quick aside: you might be wondering why don't we simply apply row polymorphism in its original cast, on records with named fields, especially since our state with named local variables looks an awful lot like a record (with named fields). The problem we run into is that in this arrangement, the names are equated with the identity of the variables and that lands us in square one, where variables are local to functions (all basic blocks must agree on the identity of variables).

So let's go back to stacks and consider what happens if we treat our basic blocks not as state transformers but as stack transformers. That is, a basic block takes some values off the top of an input stack, does some computation on them, and returns an output stack with results pushed on top of an unchanged prefix (that's how we will call the part of the stack that the input stack transformer does not examine). Notably, it does not matter what was in the prefix, since the transformer did not even look at it. In other words, we could say that the stack transformer is prefix polymorphic.

With that in mind, let's look at that data flow diagram again, but rearranged slightly to make it work as a stack transformer:

It's really the same picture, except it's now easier to visualise the input and output columns as stacks, and the effect of the transformer as pushing y' on top of this stack (i.e. the output stack is bigger than the input stack). Let's look at a variant where a and b are no longer alive after the block:

Here, the output stack is smaller than the input stack. However, in both cases, we can stack any number of ‘pass-through lanes’ below the interesting part of the diagram for free, by simply not examining the prefix. We are basically pattern-matching on the top of the stack and passing the unmatched part through.

This seems as good a place to stop as any. Next time, we will look at actually representing bigger chunks of a program as compositions (or circuits) of these stack transformers, and perhaps touch on stack signatures (an exceedingly simple type system) and linearity (in the sense of linear types). Further down the line, we want to deal with representing (addressable) memory – what LLVM represents using load and store instructions – and then we'll perhaps be ready to translate some programs into this form and see how it works out (or doesn't) in practice.