Programming musings

Before getting into the task of coding one should sit down and think clearly not only about the objectives, but also about what we have achieved so far and what are the problems that the current ECL codebase faced and solved.

So, first of all, how does ECL compile and execute code right now? We have a redundant architecutre, with two compilers: one that transforms lisp code into bytecodes and another one that uses C as a backend. The first one is barely a single pass compiler: code is macroexpanded and, once expressed with a subset of Common Lisp, it can be directly translated into a set of bytecodes that match the structure of that language. While extremely simple, the development from scratch of such compiler taught this guy some lessons

• Common Lisp can be translated into a very simple subset of the language
• Simple also means robust.
• Even if the target language is simple, it can be difficult to perform serious optimizations.
• There is no need to have a full featured, extremely fast compiler to bootstrap ECL.

The second compiler, the lisp to C translator, has a longer story. It dates back to the days of Kyoto Common Lisp and thus it has a larger code legacy. With time, different layers of complexity were added to this compiler, which has always been a two pass process:

• Macroexpand and translate into a tree of expression objects.
• Process that tree and produce C code.

Again, nothing too complicated goes on. All optimizations have to be very simple because the internal representation is a mess. We distinguish between macroexpansion-time optimizations, where we can change the structure of the Common Lisp code depending on what we know about variables, arguments, declarations, etc, and optimizations performed when the C code is emitted, such as using the C data types for unboxing objects and making faster operations.

Wow, nothing fancy at all! Where are all those dead code elimination passes, type inference, inlining, etc? Well, they are more or less there, but only in a very minimalistic form. Inlining happens at macroexpansion time: when a function is called once, we compile again but inlining the lisp code; type inference happens as we perform the first pass, but it cannot keep different types along different code branches; we cannot really detect unused variables, and other useful optimizations, etc. And nevertheless things get done. The use of a C backend has a lot to do: the C compiler may sometimes perform optimizations that we did not think about or were too complicated.

So let’s take a breath. I am not telling you that you should stop using ECL right now. Of course not! ECL is more than compiled code and bytecodes, it is a very useful library implementing the whole of Common Lisp and more, plus it is the most portable Common Lisp around!

The goal is thus not to abandon all code and move on. What we want is to build a compiler from scratch, but which uses the same library, the same two backends, but is more savy, knows more about the structure of the code and thus will produce better code for us. We should learn the lessons above and aim for something like this:

• A first pass that translates Common Lisp into an even more minimalistic language.
• A second pass that discovers the structure of the code and creates the code flow graph.
• Multiple passes that optimize over the two previous elements.
• A pass that transforms our simple language into a Static Single Assignment language.
• A type inferencer that runs over that SSA languange.
• Different optimizers for useful operations (+, -, COS, CHAR, etc) also operating on that language.
• Further passes for code analysis, dead code elimination, precomputation of values, etc.
• A pass that does register allocation so that we do not have to keep all variables in closures.
• ….

The result should be a robust compiler that targets an abstract and very simple language that can be retargetted to either bytecodes or to C. In particular, the fact that we have SSA and a code flow graph means we can perform type inference much better and discover when a variable may be unboxed, or when a variable takes different types along different code paths. And the register allocation phase means we can optimize the bytecodes, which would now be able to store variables in a register array without consing further memory, etc, etc.

In general the architecture will be more robust because we can add more optimization passes as we learn more about the compilation process itself, but the language is kept simple at all times. We will even reach a point where we have to automatically get rid of all optimizations, keeping only the Lisp -> SSA -> bytecodes phase to bootstrap ECL itself.

There is a rather nice point that I mentioned before and which is that we do not need a sophisticated target language. Common Lisp is really simple, it just has a large library If we take the current bytecodes compiler and strip all bytecodes which are there to optimize and make the code run faster, we will notice that only the following is needed

• Constant values.
• Local variables.
• Assignment to variables.
• Function calls that use variables and assign output to some variables.
• A function prologue and epilogue that parse function arguments.
• A conditional and an unconditional jump statements.
• A named catch point for nonlocal jumps.

Anything else can be implemented using function calls. Global variables and constants? Create functions that read and write to a global lookup table. Closures? Implement them as a list of values. UNWIND-PROTECT, CATCH, BLOCK, TAGBODY can be modeled using the last two items. And so on and so forth.

In the next post I will elaborate more on this subject, introducing the first version of the language that we implement, together with the first data structures.