Posts in this category

Sun, 25 Apr 2010

You are good enough!

Permanent link

Have you ever tried writing a compiler?

Most programmers haven't. Most programmers think that writing a compiler is hard. Or even some deep magic for which you need some kind of advanced wizardry that you only obtain by hacking twenty years on a compiler already, or so.

It's not.

Writing a feature complete compiler for a full fledged programming language is quite some work. But writing a simple compiler isn't. And contributing to an existing compiler isn't either.

I'd like to point you to Jack Crenshaw's tutorial series Let's Build a Compiler. It's rather old, and outdated by many standards, and not all that well formatted and so on, but it really teaches you the basics of how to parse a program, and then interpret it, or compile it down to assembler.

But mostly it shows you that compiler writing is no black magic at all. It's just like writing any other kind of program: Once you've got the gist of how compilers can work, it's mostly a matter of actually implementing things. And if some features seem hard to implement, there's plenty of literature that you can read on that particular topic.

(Mr. Chrenshaw's tutorial inspired me to write a toy interpreter in Perl for a nearly usable, Turing complete programming language. Math::Expression::Evaluator is a side product of writing that interpreter).

Contributing to an existing compiler is even easier. The overall architecture already exists, and typically you need to only modify small parts to add a feature.

I want to illustrate this by a feature that Solomon Foster, Jonathan Worthington and I added to Rakudo in a nice piece of collaboration.

The Feature

Perl 6 has the reduction meta operator. It takes an infix operator, and applies it to a list. Here a few examples:

# normal form
# same as 1 + 2 + 3 + 4
my $sum = [+] 1, 2, 3, 4;

# triangle form:
# same as
# my @sub-sums = 1, 1 + 2, 1 + 2 +3 , 1 + 2 + 3 + 4
my @sub-sums = [\+] 1, 2, 3, 4;

# right-associative operators are reduced right to left:
# infix:<**> is exponentiation
# same as 2 ** (3 ** 4)
say [**] 2, 3, 4

# chained operators are AND'ed together:
# same as  1 <= 2 && 2 <= 3 && 3 <= 4
my $sorted = [<=] 1, 2, 3, 4;

Status Quo

When we started our work, only the first, simplest version was implemented, i.e. reduction of a left associative, non-chaining infix operator.

What we did

Solomon started with a basic implementation of the reduction logic. You'll notice that it's written in Perl 6, so no knowledge of scary low level languages required.

In a series of small patches Solomon and I generalized and improved the logic step by step, and Jonathan wired the parser to the reduction logic.

All of these patches were written in Perl 6 code, and only the last one required more than a trivial amount of guts knowledge.

The actual reduction method is no piece of magic. It ended up a bit lengthy because it needs to consider several different variations of the reduction feature. It's just an ordinary function that you would typically find in a perl module.


If you know a bit of Perl 6, you can contribute to Rakudo today. Many built-in features can be desugared to ordinary library functions under the hood. If implement the logic, somebody can tell you how to wire up it with the rest of the compiler, or even do it for you.

You are good enough. Ordinary programmers can do it, no wizardry required.

(The same actually holds true for most projects that look scary from the outside. In my experience it's just very important that the community is friendly and helpful.)

(With apologies to mst).

[/perl-6] Permanent link