Today I want to talk to you about the Carp compiler. After my last blog post spent some time on the front page of various internet forums and incited healthy and not so healthy discussions, my inbox was filled with requests for clarification. In general, people seem to be fairly interested in how the compiler works; miscommunication—possibly on my part—led to a confused picture of how it functions in some corners of the internet, so I would like to give you some general information about it.
A quick disclaimer before we start: I’m not the original author of the language, nor am I its principal maintainer. The pure fact that people read my blog post might have made them jump to conclusions; but I do not want to usurp anyone else’s work, and so here is a shout-out to the brilliant and kind-hearted Swede Erik Svedäng, who you can usually find on the Gitter channel, which is our primary means of communication these days. He is the author of Carp and the person I bug with my questions. If you are interested in learning more about Carp or just to hang around and chat, I suggest you go there.
Also, if this is too much for you that’s alright! I plan on writing more byte-sized updates from now on, but first I feel the need to get the overview out of the way. Everything is moving relatively quickly in Carpland at the moment, and what you’re about to read will probably require an update in the near future anyway.
Now for the main event: let’s talk about the compiler, from front to back.
The parser
The first stop in any compiler is the parser; Lisp parsers are
generally straightforward, and I don’t want to spend too much time on
its implementation. Because Haskell is the implementation language of
the compiler we use Parsec as our primary parser framework. This means
that we don’t go the more traditional route of using a
Bison/Yacc-compatible BNF grammar but rather use a parser combinator
framework. I generally prefer parser combinators, although admittedly
BNF grammars make for a nice specification of a language. Parsec spits
out an enriched AST—the regular AST is called Obj, the
extended version XObj—that stores a little bit of
additional information, such as where the node is coming from (line,
column, and file information), memory management info that we will talk
about later, and a unique identifier that we will need in the
emitter.
The only thing that I consider of note here is that the reader macros
@ and &, which you can read about in my
previous blog post, are defined in the parser. Carp does not have an
extensible reader macro system and is as such closer to Clojure than
Common Lisp.
The Eval module
This is where it gets a little icky. The single largest module in the
Carp codebase is the Eval module. It is around a thousand
lines of code, which isn’t terrible. It’s pretty long for a Haskell
module, but it’s not the largest I’ve seen. What’s bad about it is that
it does a lot of things and has no clear boundaries around its goals. A
nice way to put it would be that it’s “the heart of the compiler”, but
I’d argue that it’s just in dire need of a refactor.
Once invoked, it will perform a fold over the parsed source code in
AST form to generate and execute Commands. Commands are the concept that
makes Carp’s REPL so different1, more of a
view into the compiler than an interactive expression evaluator. There
are two commands that will be generated at this time:
ReplEval and ListOfCallbacks.
ReplEval is where it’s at, so I will start with
ListOfCallbacks. It is a simple data structure that holds a
list of commands that will be performed in sequence, enabling us to
chain shortcuts. You can see that in action when typing, for instance,
:bx at the REPL, which is a shorthand for writing
:b and :x in sequence, or (build)
and (run). It is thus just a convenient wrapper for us at
the REPL.
As you might have guessed at this point, this leaves
ReplEval with the thankless job of doing literally
everything else. It will be passed into the eval
function, which performs some of the things that you might expect an
interpreter to do, but some are suspiciously absent—this is just the
first pass after all, and we are not trying to interpret the source code
so much as to make it palatable for our backend.
ev(a|i)l
I’m not going to cover all the things that the evaluator is doing,
but I’ll try to give you a brief overview of a function-abomination that
is 450 lines of code long, and spends most of its time in various
case statements. That’s not quite as horrifying as
CPython’s infamous switch, but it’s bad enough for me to
rant—sorry Erik, but I know you feel similarly.
Disclaimer: this section is fairly mean to Carp. I love the language, but I try to be open about its current imperfect state. This is not a marketing campaign.
First, the evaluator will check what general flavour of
Obj it has received. If it’s a list, it will call the local
function evalList, which does most of the work. The other
two flavors it cares about are symbols and arrays, which get their own
special functions; if it receives something else, it will just parrot it
back to the caller; this is one of the REPL’s “features” that will
confuse you the first time you run it, and we should probably do
something about it.
If we have a symbol in front of us, evalSymbol will try
to look it up, and if it fails give you an error. If it succeeds, it
will return the value, but the REPL prints… nothing. Let’s try not to
think about that one too much. It makes sense if not used on the
top-level, where we actually might need bindings, for example in dynamic
functions—we’ll talk about those in the section about macro
evaluation.
Arrays are weird as well, at least on the top-level. They are
homogeneous by design, because, you know, they’re C arrays. If you work
on the REPL, however, the type checker will not take effect, so we can
do things such as writing [1 "hi" \2], and Carp won’t think
twice about it. That’s all well and good, except it really isn’t in the
REPL sense. For macros, again, this makes sense, as we will see
later.
Alright, I’ve put it off for long enough: it is time to talk about
evalList.
It uses two more data structures that we’ll need to cover to
understand much of what follows. The first is the environment
Env and the second the similar, but not quite the same,
type environment TypeEnv. The type environment registers
and saves types and is needed for type inference and checking. The
regular environment is used for values and functions.
Let’s quickly go through a few of the behaviours of the function,
just to give you an intuition for how it operates: if
evalList encounters a function or value definition, it will
expand macros in the form, try to infer its type, save the definition,
and move on. If it encounters a type definition, it will save this type
in its type environment and generate getters, setters, updaters,
str, and copy for this type and register those
as well. If it encounters external type or function definitions that are
implemented in C and exposed through register or
register-type, it will do the same as for regular values,
but take your definitions at face value and not try to check
anything2.
This should give you a little insight into how this function generally works; it is, however, also responsible for macro expansion and activating the type checker as needed. Let’s talk about both of those before entering the land of C.
Macro evaluation
First off the bad news: Carp’s macro system is not currently
hygienic 3. It also does not have any
gensym capabilities yet. Generally, it is a system of its
own, closer to Clojure than anything else, but with a few twists and
embellishments that aren’t found anywhere else, and some things that are
still sorely lacking.
There are two general concepts that macro evaluation has to deal
with: macros and dynamic functions. Macros are fairly straightforward:
they are simple rewrite rules that, given one or more forms as input,
return an output form. The magic happens in expand, where a
single form gets rewritten. I don’t want to dwell on this for too long,
just know that it calls eval whenever it finds a macro,
which calls apply, which calls eval again, and
it all makes sense in the end. The first call to eval will
defer work to apply, which takes care of generating a new
environment in which the parameter names are bound to the actual given
arguments, and it will call eval with the body and that
environment. This is akin to what an evaluation loop might do in an
interpreter when it encounters a function.
Dynamic functions are similar, but they actually evaluate their arguments before being applied. That simple idea makes them similar to normal functions and useful when applied recursively, and for proper metaprogramming. Macros are thus usually only useful for simple rewrites or as entry points to dynamic functions.
Type inference and checking
We’ve been working with a dynamically typed AST thus far, but this won’t do for compilation. Instead, we’re now going to infer our types, based on only the type information that we have from the standard functions and any annotations the user might have left behind. As I said before, this happens after macro evaluation, which means that macros know nothing about the types of the AST.
The type system relies on a simple unification solver to infer the missing types. Generic types are still valid at this point. The inference engine just annotates the objects it receives and, perhaps surprisingly, takes care of memory management information. It also returns any dependencies the inferred function might have from Concretization. If those last two tasks don’t make any sense to you, don’t worry, I’ll go over them in the following sections.
The annotation procedure relies entirely on generating and then
solving the contstraints. Generating constraints is simple, and it takes
all that we know from our function types. Let me give you a simple
example: given the statement (= a b), we know that the type
of a must be the same as b, because equality
checking doesn’t coerce its types in Carp; it is of type
(λ [a a] Bool). We will generate this constraint for our
solver. Should either one of the two variables be used in a non-generic
setting somewhere we can solve the constraints, and assign both of the
variables the same type—which in this particular case must happen during
initialization anyway. This simple yet powerful mechanism turns out to
be surprisingly useful.
Should the solver fail or find any typed
holes4, the engine will produce an error.
Otherwise the solver will produce a TypeMappings object,
which is just a mapping from generic to concrete types. The inference
engine then assigns those types to the values, and goes on to
Concretization and memory management.
Concretization
Concretization is a fairly large module again, but not nearly as big
as the evaluator. It will take care of emitting multiple versions of the
same polymorphic function with different concrete types, one for every
usage in our code. If you define a function sum that takes
a list of numbers and sums all of them, for instance, and then use them
with Double and Int types, it will both
generate the appropriate functions and symbols for the specialized code,
as well as change the code to use the specialized names instead.
This is where the generation of dependencies kicks in; dependencies are returned from type inference if additional specialized functions need to be generated.
This leads us to the last item on our list: memory management.
Memory management
The ManageMemory module is responsible for finding out
if and when any destructors/deleters are needed. Like the type
inference, concretizer, and evaluator, it is yet another tree walking
function5 .
Now, I haven’t actually worked on this module all that much yet either, so you’ll have to do with what I observed and what I found out by having Erik explain its magic to me. Pardon if this is not as instructive as you’d hope.
To find out where we need to add deleters we first need to figure out which variables pertain to which scope. To achieve this, we walk through the AST, doing something that Erik calls “abstract interpretation”. We take the set of variables that were defined before the scope and the set of variables that are defined at the end of the scope, and take the difference. This difference is what was created inside of the scope and needs to be deleted, so we add deleters for them—unless they’re unmanaged types, such as numbers, booleans, or characters.
There are three special cases we need to handle there, though: function calls, loops, and conditionals. Function calls take ownership of the variables passed into them, unless they were passed as references, and we can remove them from our set. And if they are being passed as references, we have to make sure they’re still in the set, otherwise it has been given away and we produce an error.
while loops are interesting because we visit their
conditions and bodies twice to simulate looping; this looks
algorithmically crude, but it seems to work
fine.6
Conditions were the most surprisingly complex to me, because they produce two interdependent scopes, one for each clause. Those need to be diffed to make sure that we clean up properly in all cases.
When we’ve found out what we need to delete where, we put this
information directly into our XObj for use by the
emitter—which brings me to our most fun section: we get to emit some
C!
Emitting C
While Erik would like the compiler to use an LLVM backend at one point, I personally am a fan of the C backend. This is partly because it emits fairly legible code and, all things considered, it is easier for me to read C than assembly or LLVM IR, and partly because it doesn’t lock us into the LLVM framework.7 But enough of the future, let’s talk about now!
The emitted C code is all put into one file called
out/main.c. This file is split into three acts, like any
good piece of dramaturgy: first come the types, a dramatis personae of
our play; then the declarations, like an overture, serving as an
exposition of what is about to happen; and then the definitions show us
what they got. All the file’s a stage, and all the definitions are mere
players. Let me talk about types and declarations first, and then we
will have a word about definitions.
Types & declarations
For both types and declarations, the process—and indeed the
function—we are using is the same: first we sort the bindings in the
environment, ranking them based on their dependencies, then we will
convert them to declarations. The only difference is what kind of
environment we are operating on. For declarations this will be the
regular environment Env, and for types the type environment
TypeEnv.
Sorting the bindings is relatively easy; all of the objects have a base score, which is a bit higher for modules than for values. Type definitions and aliases are ranked based on their dependency depth, i.e. how many other types they have references to internally and how those, in turn, score. We then sort them starting with the lowest and proceed to convert them to declarations.
There are some intricacies to the way how declarations are generated—we don’t generate anything for generic functions for instance, because we already specialized—, but the basic idea is that for regular definitions we generate function heads for functions and left hand sides of assignments for value definitions.
Types are a little more complex, because we generate both the struct
and the typedef at the same time. There, we will go through
the members one by one, get the type we inferred for it, convert it to
C, and mangle the name of the member. Generally, whenever we emit a Lisp
symbol in C, we will first mangle the name. Mangling is in this case
just a simple string replacement that will replace certain characters
that are not allowed in C symbols with their all-caps name, surrounded
by underscores. This means, for instance, that the omnipresent dash
- will become _MINUS_.
That is all there is to emitting declarations and types. Let’s move on to definitions!
Definitions
Emitting definitions is arguably the most important part of the compiler, and it makes sense that it’s thus also the most complex8 . Conceptually, the emitter is fairly simple: we take all the bindings in the environment, fold over them, weed out the ones that are not important to us, like external definitions and generic types, and emit the code for each binding.
In the following I will walk you through a few of the most important
pieces of machinery, but by no means all of them. A complete definition
can be found in the function toC of the Emit module.
One magic detail that makes this work is that the recursive emitter always returns the name of the variable it bound the last statement to, so that the callers know what was last assigned in case they need it.
Modules
Modules are conceptually simple: they just add another level of recursion, because they are their own environment and we thus have to do the whole process again.
Literals
Literals are also straightforward; most of the primitive literals we have can be compiled to C without any changes. The only literals that need some extra attention are strings and arrays.
For strings, we always emit two fresh variables and bind the string
literal of type char* and its reference of type
char** to those. This way we can have statically allocated
strings in our binary, in a straightforward way. It might not be the
best way going forward, but thus far has proved to be fairly
reliable.
Arrays are the most complex of the literals. This is due to two reasons: they are not just C arrays—I lied a little above—and they can contain any kind of statement in their definition.
Carp arrays are a two-member struct of data and length. When we emit an array literal, we first emit a literal struct initializer; that’s trivial because the length is known at compile time. We then go through the list of array contents and emit a statement that assigns the contents of the array at the index to the statement at that index.
(let [x [1 2 (+ 3 4)]]
;...
)That means that the array definition depicted in Figure 1 would compile to the C code depicted in Figure 2. In the end, it comes down to a fairly straightforward mechanism. The temporary variables reduce the legibility a little bit, but it’s still relatively easy to look at the compilate and see what’s happening.
Array _11 = {.len=3, .data=CARP_MALLOC(sizeof(int)*3)};
((int*)_11.data)[0] = 1;
((int*)_11.data)[1] = 2;
int _10 = Int__PLUS_(1, 2);
((int*)_11.data)[2] = _10;
Array__int x = _11;Symbols
The next item on our list is symbols. They are simple as well, because all we have to do is take their name and path—the path being the list of modules it is defined in—, mangle and concatenate everything, and we have a perfectly valid C symbol.
Control Flow
In Carp, the only control flow primitives baked into the language
proper are if and while. Both of these are
present in the language we are compiling to, so it shouldn’t be too hard
for us to translate from Carp to C.
In regards to if, we have the additional restriction
that it is always a two-branch form, due to the type checker. This makes
emitting easy and regular: we create a fresh variable, and append it to
the source code unless the type inference engine told us that the return
type of this if expression is Unit in
Carp-speak or void in C. We then visit the condition, and
assign it to a result variable—that is because the condition is less
restricted than in C, possibly resulting in multiple C statements—, put
the result variable into the head of the if, visit and
generate code for both clauses of the expression, and, if the return
type isn’t void, assign the return values of the clause
bodies to the fresh variable we created. This works because, as stated
above, visiting the body will tell us what we need to assign.
while is a little bit more complex; because the head
will possibly be executed multiple times, we put a declaration and
initialization at the top, like in the if, and then
reassign it at the bottom of the loop, running the same expression
again.
All of this requires a fair bit of machinery, but is in itself quite simple; as with most of the parts of the Carp compiler it can be a little tricky to keep it all in your head because it’s highly recursive.
Functions and Variables
You probably expect this to be the hairiest part of the emitter, but it is actually quite straightforward; it builds on the basic blocks we’ve already defined. Of course it is the most recursive, though.
Let’s start with function definitions. We first need to get the
declaration, but we already know how to do that from earlier; we then
visit the body, see whether our return type is void, and if
not, add a return statement that returns whatever our body did, again
using the name of the last variable that visit
returned.
After this surprisingly brief definition, let’s look at variables.
Normal def-style variables are easy: we have the type,
name, and assignment expression, so all we need to do is convert the
type to its C equivalent, mangle the name, and take the result of a
quick visit of the expression. Then we stick all of that in a row and we
have our value. Please note that this obviously is more restricted,
because it doesn’t support multiple statement assignments; this is
alright because defn is only used for top-level definitions
and C is equally limited in having expressions on the top level.
Our way of creating local variables is let. Carp’s
version of let is comparable to let* in Scheme, which means
that subsequent bindings can use prior bindings. That makes things
simple. All we truly need to do is create a bunch of bindings one after
the other inside a {} scope, visit the body of the
expression, and assign it to a fresh variable that we again created
prior, unless it is void, in which case we can skip that part.
It is amazing that these simple building blocks are all that we need to have definitions, but that’s how it is. In a few dozen paragraphs, I was able to describe the code emitter, skipping over some parts, but not shying away from telling you about the more complex parts either. I hope that I won’t ever stop being amazed by this.
Compiling C
Once we’ve arrived at a C file, we can compile it using one of the C
compilers on the target machine. Although Carp aims to support all C
compilers and doesn’t use any fancy or non-portable C
features8, its default compiler is
clang. Since early December, this can be changed by putting
(project-set! "compiler" "my-compiler") somewhere either
into the source or the compiling REPL session. My personal favorite
behavior would be if Carp honored the CC environment flag,
but that’s thus far not the case.
Carp produces a fat binary from a single C file, which means that, to
my knowledge, there is currently no mechanism to include another C
source file. Libraries can be linked to by adding a libflag
or cflag, also with the project-set! command.
Most binaries I personally produce have currently no dependencies except
libm, which Carp itself depends on, and only use
header-only C dependencies.
That means that, by default, Carp artifacts are more like Go’s fat binaries that include everything, but this is not the only way to do things. You could just link to all kinds of libraries willy-nilly if you wanted to; Carp gives you this kind of freedom. But I’d suggest only linking to libraries if it’s necessary, for instance if you wrap a big C library like OpenSSL; the default should always be largely self-contained binaries. But then again, that’s only because this is one of my favorite features of Go, and I’m biased. Carp is not, and you have the power to disagree.
Whatever the process, in the end a binary will be produced and land
in the out directory, conveniently named
a.out.
Fin
We talked about a lot of stuff today. While Carp certainly is a complex piece of machinery, it works most of its magic in a surprisingly straightforward and concise way. The whole compiler is just under 5000 lines of code long, and you can definitely read through it yourself if you want or need to. Its simplicity comes from both a relatively simple—meaner spirits than I might even call it limited—language design and the absence of—at this point surely premature—optimizations.
I hope I’ve whetted your appetite to jump into Carp, or even to look around its compiler internals. If you need advice or just want to chat, you can find all of us on Gitter; alternatively, Erik is on Twitter and my e-mail address should be floating around here somewhere!
See you around next time, when we talk about how to use Carp’s C interface!
Footnotes
1. Some on the internet would even go so far as to call it worse names, like “useless”, but I’d beg to differ. You’ll get a more familiar REPL soon enough.
2. While trusting the user to be correct when defining their type signatures can lead to errors at C compile time, and we try to minimize those, the alternative would be to parse the actual included C, and that sounds like an even more horrendous task to me. YMMV.
3. I would love to fix this when I’ve got both the time and the understanding of the current system that is required to build on top of it. I don’t think I’m quite there yet. Drop me a message if you want to team up!
4. Typed holes are a concept borrowed from other type-inferred languages. It enables the user to replace any statement with a special symbol. The constraint solver will then fail and tell you which type it inferred for the hole. This is useful when debugging type errors.
5. You’d think that all of this AST traversal makes for a slow compiler, but in my experience the Carp compiler is reasonably fast—then again, no huge projects exist to benchmark Carp’s performance at the time of writing.
6. For the people reading the code: there is an
interesting bit of fiddling to work around Haskell’s laziness in the
while branch of the walk function.
7. Also, I’ve found the Haskell bindings to LLVM unbearable, and I’m not alone: when I gave an introductory workshop into LLVM while at the Recurse Center, I told people that using it might not be the best idea. One of the people there did not heed my advice, and he emerged six weeks later, battle-hardened and weary.
8. Of course those properties aren’t always correlated, but very often I experience that the most important feature seems to have the most edge cases—or maybe that is just because I’ve thought about it more deeply than the rest.