Compiler Club

Interpreter, Going Open, and Milestones

2009-09-13T17:01:00.003-04:00

As I mentioned in my previous post, I've made my compiler available on github: jdfrens/hobbes. I haven't officially put a license on it yet, but it'll be a "don't blame me for bad things, yet give me credit if you use it".

I thought it would be interesting to start working on a interpreter as well. I've written many interpreters the last couple of years (since "Programming Languages" had been my course), but getting it to coexist with my compiler might be interesting. I'm also curious what re-use I might find in my code. (The interpreter could be used for constant folding.) Plus, I want to see how well CIAT can deal with two different sets of processors. (Short answer: quite well! More on this later.)

Finally, I'm trying out Pivotal Tracker to keep track of the stories for my interpreter and compiler. I'm thinking that I might post summaries for each true iteration there (i.e., once a week). I'll have to have another post on how I've abused the term "iteration" here in the past.

Long time, no post!

2009-09-11T16:42:00.003-04:00

Since my life has settled down into merely "finding a job" (since I completed "frantically packing and moving"), I thought it would be a good idea to resurrect some of my old projects to keep and improve my programming skills. I've picked up some new ideas for interpreting and compiling since I posted last (nine months ago), so this blog gets resurrected along with my NRHC.

I accomplished two things today: I finished iteration #5 for the NRHC, and I moved my code to github! Check out my hobbes repository. Soon I'll post a blog entry about iteration #5.

NRHC Story #4: Multiplication

2008-12-27T17:00:00.000-05:00

User Story

A Hobbes program can be a single multiplication of integers or command-line arguments.

Analysis

My NRHC compiler could already add two integers, so adding the ability to multiply two numbers should be pretty easy. Just make the addition-generating code more generic, right?

Implementation

Mostly right. In terms of generating PIR code, yes, all I had to do was make the code a bit more generic. I was surprised, though, that the additional token type MULTIPLY complicated the back end. It felt to me like I was worrying about this extra token type more often than I should have to.

Now, granted, I'm using ASTs like (+ 1 2) and (* 3 4). I don't have generic OP ASTs: (OP + 1 2) and (OP * 3 4). I suspect that this would make my code just a little bit simpler. However, I'm sure I'll be better off moving to a tree intermediate representation.

My next story will be to allow any number of additions and multiplications. But first, I'm going to refactor my code to use TIRs in the back end. I'll say more about TIRs in a future entry.

CIAT version 0.3.0

2008-12-26T15:40:00.001-05:00

I released CIAT 0.3.0 today; it is almost all internal and API changes.

The only output change is displaying standard error messages from a Java-implemented compiler. This is useful (necessary even) for debugging.

The input format didn't change at all.

The biggest internal change is to make each processor responsible for its own processing. (A processor is something like "a compiler implemented in Java" or "the Parrot Virtual Machine".) Each processor is also responsible for reporting whatever it finds important, like source code, compiled code, generated code, execution, error messages, etc. As I expected, this led to some code duplication, but for the time being I'm okay with that. Eventually, I suspect the duplicated code will end up in a Ruby module for a mix-in.

I feel a lot better about the design, and as I add new features, I'll be trimming away the duplicated code and unnecessary abstractions I have now.

A Parsing DSL in Ruby

2008-11-02T19:32:00.002-05:00

I watched about half of a video about a parsing library written in Ruby, entitled (appropriately enough) Grammar: A BNF-like Ruby DSL for Parsing (project on RubyForge). It seems kind of interesting, but it lacks a certain elegance. I'd argue that ANTLR is a bit more elegant, but as I understand it Parsec for Haskell is sheer elegance.

NRHC Story #3: command-line arguments (again, again!)

2008-10-30T16:23:00.003-04:00

So I'm done with Story #3 (started here and continued here). Fixing my "problems" from the last time were not as difficult as I had at first anticipated. (This is most evident since I'm posting this final follow-up the same afternoon!)

Implementation (again)

The Parser. I had to tweak the parser so that ARGV references could appear in an addition expression. The trick here was that I couldn't just make the addition expression recursive since that would allow addition expressions in addition expressions. I don't have a story for that feature yet, and there are too many other issues (associativity for one) that come up, so I couldn't easily add it.

But this lead me down an interesting and good path. A literal integer and an ARGV reference are both simple expressions. It's simple expressions that can appear in an addition expression. So a little bit of refactoring, and the grammar was whipped into shape.

Code Generation. Not much had to change with code generation. I was already putting the value of an ARGV reference into a PIR register, the only trick was getting rid of extra argv declarations. As I described in my previous post, I need this directive in my PIR code when I want to use command-line arguments:

.param pmc argv

Originally, this directive was spit out each time there was an ARGV reference, and it was spit out just before each ARGV reference. So I'd end up with code like this:

.param pmc argv
$I0 = argv[1]
.param pmc argv
$I1 = argv[2]

The first change I made was to make a separate pass on the AST to generate the directive (and in the future any other directives for a function prolog). So I had this:

.param pmc argv
.param pmc argv
$I0 = argv[1]
$I1 = argv[2]

My idea at this point was to leave the extra directive in the code from this phase of the compiler. It's not necessary for me to clean this up (or prevent it) right away; that would be giving the code generator too much responsibility.

Linear-Code Analysis. I broke out the linear-code analysis into a separate phase from the actual writing-code phase, and I suspect this will become an official linear-code analysis and optimization module.

So far, my linear-code analysis and processing consists of inserting tabs when needed and removing unnecessarily duplicated instructions. I've taken the approach that duplicated instructions are by default acceptable (e.g., two instructions that increment $I0). So I remove instructions that I know should not be duplicated, and so far that's just the argv directive.

Other Observations

I'm quite surprised that I haven't felt a burning need to switch to a tree intermediate representation, just processing from the ANTLR AST I get back from the parser. I'm certain, though, that one more language structure that requires a new case in one of my switch statements will put me over the edge. However, I think my next phase might be to add multiplication to the mix. This should not require a switch to a TIR.

I also discovered a slight annoyance with CIAT. Somewhat at the last minute when releasing v0.2.0, I tweaked the way it handles standard error, by dumping it into a file. Unfortunately, this means the standard error does not appear on the console, and I have no reference to it in the report.

NRHC Story #3: command-line arguments (again)

2008-10-30T11:18:00.005-04:00

I write this blog entry while I work on this story. If you need to refresh your memory about Story #3, check the analysis post.

I've decided to roughly time my process for this implementation. However, I have many distractions: several of my students are going through mock interviews today, and I have to be on hand to handle fires; other students email me with questions and requests (like getting access to a subversion repository); and I'm trying to rip three versions of The Wall to my computer today. And I'm writing this blog post as I go (although I'm not counting those minutes).

The Implementation

The Lexer. I started with the lexer. To fully parse ARGV[1], I figured I could do it all in the lexer or break it apart in the lexer and parse out integer in the parser. Doing everything in the lexer seems simpler since it's done in one place, but in thinking about it some more, I realized that it puts too much responsibility on the lexer, making it more complicated. It doesn't hurt that this will mostly be handled by the parser anyway in the future!

So I needed to recognize ARGV, [, and ]. (The compiler already recognizes integers.) With a fair number of interruptions and distractions, this took me 40 elapsed minutes. It was probably more like 10 or 15 minutes of real work.

The Parser. So here's a surprise. I did too much work for the lexer. I finished the parser in about 10 minutes, and I didn't need to use the new tokens from my lexer. This suffices in ANTLR:

expression : 'ARGV[' INTEGER ']' -> ^(ARGV INTEGER)

I don't need the ARGV for any reason after the parsing, so why bother to recognize it separately? I did however, create a temporary AST type named "ARGV" as seen in the rewrite rule.

So I took out the changes in my lexer, and I do the work in the parser. I know it will change later, but since I'm not sure how that will play out, I'll toss what I did now.

Compilation. According to the clock, this took me around 40 minutes or so, but part of that time was spent talking to a delusional Packers fan about football. (For the record, anyone not a Bears fan is, by definition, delusional.)

A couple things struck me while working on this. First, my compiler is working with the raw ASTs from ANTLR. They're not the nicest structures to work with since they're so generalized. More importantly, they don't lead to good OO code at all; it's all switch statements. The thing is, I'm not sure when I should switch over to my "tree intermediate representation" that I've cooked over the last few years. These TIR objects implement the visitor pattern, so the various compiler algorithms are nicely implemented in an OO way.

Second, command-line arguments in PIR (that's "Parrot Intermediate Representation") required a compiler directive:

.param pmc argv

The thing is, this should be necessary only once in a PIR subroutine. I'm not sure what the Parrot interpreter will do if I include it more than once. In an addition expression, ARGV[0] + ARGV[1], it matters! I could always include the directive, but that would mean changing all of my previous acceptance tests. I balk at that not because of the work involved (ten minutes, tops) but because it suggests I should be looking for a different solution. So I need to figure a way to add that directive zero or one times as necessary. This is going to require more thought.

And this brings me to the third thing that I've discovered: I'm implementing only half the story! I can use a command-line argument only in place of a single integer; I cannot use them in an addition expression! Ooops.

I had to go back to see how I had phrased Story #3, and it does, in fact, promise the use of a command-line argument in place of any literal integer.

There is this tension in writing a story between making it too trivial and too much. Story #3 is the right size in any practical situation. However, it does not mean I need to implement the whole story. So this is a good place for me to break and to close out this blog entry. I'll finish the rest of Story #3 and post a summary of the results.

CIAT version 0.2.0

2008-10-27T17:25:00.004-04:00

I have been sort-of working on my compiler, just not on the compiler itself. As I described in my last post, oh so long ago, I'm trying to add command-line arguments. Unfortunately, my acceptance-testing framework CIAT (pronounced "dog") did not handle command-line arguments. To get command-line arguments to work, CIAT would have to be reworked at a few levels.

Fortunately, I know the guy in charge of the project (myself!), and it just meant pestering him in between other obligations.

So that's mostly what I've worked on for the past month. CIAT itself is written in Ruby, and I got sidetracked by cleaning up some of the HTML-generating code. But I have a system that will handle (optional) command-line arguments!

I haven't though much about the actual implementation of command-line arguments in Hobbes, so it'll be interesting to see how long it takes me to get back up to speed and finish the story.

NRHC Story #3: command-line arguments

2008-09-02T13:25:00.004-04:00

User Story

A Hobbes program can refer to command-line arguments in place of a literal integer. The syntax is array-like: ARGV[i], where i is an integer. Command-line arguments are assumed to be integers.

Analysis

As I mentioned in my writeup of Story #2, it bothers me that a constant folder might satisfy that story better. I want to write a constant folder, but I also want to be required to generate interesting PIR code.

To force the issue, I need some way to get outside information into the running program. I could have gone with file or keyboard input, but I hate keyboard input, and I have no love for file input. It also seems like a lot to pull into Hobbes at this point. Grabbing input from command-line arguments is fairly easy to do in PIR, and it extends the language very simply at this point.

My first thought was to use a syntax like $0, $1, $2 to refer to specific command-line arguments. This feels a little too much like bash or Perl to me, and it's not the syntax that I'll use eventually. In talking about this story with my Compiler Club cohorts, we brainstormed that it might be useful to start using the ultimate syntax right now: ARGV[0], ARGV[1], ARGV[2]. There are two reasons why I like this:

I won't have to change acceptance tests later on.
It won't be a difficult thing to do in the compiler right now.

If it was harder to implement, then my first reason wouldn't matter at all. I love having my cake and eating it, too!

If this goes well, I suspect Story #4 will be to add print() as special syntax. Using the print() function will be required eventually, and it would be useful to get used to this syntax and to upgrade my acceptance tests sooner rather than later.

YAGNI ANTLR?

2008-09-01T19:32:00.003-04:00

As soon as I posted my last entry, I feared I was a little too coy or defensive about using ANTLR. There is a part of me that thinks I jumped to ANTLR too soon.

YAGNI!

That's what I hear when I go to sleep at night. Well, maybe only when I write these blog posts about using ANTLR.

"You Ain't Gonna Need It" (YAGNI) is about implementing the simplest thing that will work. If you don't need it now, don't use or implement it.

When I was searching for a good reference for "YAGNI", I came across this essay from "Uncle Bob" Martin. He describes how they developed FitNesse for months without writing pages to disk; everything ran in memory! They just didn't need the write-pages-to-disk feature right away.

A fairly good argument could be made for delaying ANTLR in my compiler, although maybe not as good as the pages-in-memory argument for FitNesse. The FitNesse developers got a great "page storage" interface, but there's already a natural interface between the front end and back end of a compiler. If this natural interface didn't already exist, I'd consider this a strong argument in favor of delaying ANTLR.

There's a consideration of expertise. I already know ANTLR, and I know it better than I know regular expressions in Java. ANTLR wins.

There's a consideration of code size. If I were to go truly with the simplest thing that could work, the plain Java version could be done with a StringTokenizer and a regular expression. However, you'd lose most (if not all) of the interface between the front and back ends. The stronger you try to make that interface, the more code you have to write for the plain Java version. ANTLR provides the interface, and it's really not that much code at all.

So, I won't say it's completely obvious that ANTLR is the right step to take this soon, but it's also not obvious that ANTLR should be delayed.

NRHC Story #2: integer or addition

2008-09-01T18:20:00.004-04:00

I just can't start working on Story #3 when I "have" to get caught up writing these blog entries...

User Story

A program of the form n+m is a valid Hobbes program, for integers n and m. The PIR code should perform the addition and print the result.

Analysis

One of the lessons I've learned about iterative development is that the stories should be small. For some reason, I had the idea that "story" equals "iteration" when it came to compiler writing, but that's very, very wrong. So while you might like to get all arithmetic implemented in one iteration, you should not write that up as one story.

Having erred that way in the past, I might be going in the other direction now, making the story too small. However, I don't (for now at least) see "too small" as an error. It just means writing more stories. Tentatively, I see these stories (in a mostly strict order):

Implement addition of only two integers
Implement multiplication
Implement subtraction, division, modulus, exponentiation, and other binary operators
Implement two-operator expressions without precedence and with only left associativity
Implement multiple-operator expressions
Implement precedence
Implement right associativity (for exponentiation)

We'll revisit this list as I implement the other stories.

One really cool thing about breaking them down this small, I can implement other features in between. For example, Story #3 is implementing command-line arguments. That will bring extra considerations for this story as well as the other arithmetic stories.

Implementation

The front end now benefits from a parser. Previously, a Hobbes program could only be a single integer, so a lexer was fine (assume that the lexer spits out an integer token). But now there's an alternative (integer or integer addition), and this can be implemented in an ANTLR parser quite easily.

Since I started using a parser, my acceptance tests started complaining about a newline at the end of the input. (This is a slight drawback of CIAT: all files end with a newline.) So I also had to add the ability to ignore whitespace to my lexer.

As for the back end, the front end will give me an ANTLR abstract syntax tree which is a pretty plain data structure. I do a switch over that type of the AST and spit out the appropriate PIR code.

In between the first and second stories, I tweaked the way I collect, store, and print PIR instructions. In the compiler itself, I don't want to have to worry about all of the PIR formatting rules with tabs and newlines. Here's an example of a complete program:

.sub main
 $I0 = 100
 $I1 = -36
 $I0 += $I1
 print $I0
 print "\n"
.end

The . directives are not indented; the executable code is indented. From what I can tell, the difference is that initial ., so that's what I follow for indentation.

Actually, there's a serious temptation at this stage to write a constant folder. Since the two values in an addition expression are going to be constants, why doesn't my compiler do the addition for me? This would be perfectly acceptable for this story, appropriately following YAGNI. However, Story #3 will request command-line arguments; the general code will have to be generated then at least some of the time, and the constant folder will be of less use. I might implement a constant folder as Story #4; I haven't decided yet.

NRHC Story #1: a single integer

2008-09-01T16:48:00.004-04:00

User Story

A valid Hobbes program consists of a single integer (positive or negative). The compiler should generate a PIR program which, when executed, the single integer will be printed to standard output.

Analysis and Implementation

In the future, I plan to post something before I start a story and after I complete it. Many things change along the way. But since I'm getting ready to start Story #3, I'll do just this one post for Story #1.

There's a tempting option for this story: write a single Java program that reads from System.in and writes to System.out to satisfy the story. (I should at least try this sometime.) Instead, I pulled in ANTLR right away to use its regular expressions to recognize valid integers. This also let me start unit testing with my own ANTLR Testing library.

I had to write a very minimal parser in ANTLR so that it could figure out some follow sets. But I only used the lexer in the back end: read the integer from ANTLR, and print PIR code to display that number.

I've toyed around with PASM (the assembly-level version of Parrot code) in the past, but it appears the Parrot people are more interested in PIR, which works at a slightly higher level. It's still a linear code, but you get to use your own variable names (not have to worry about registers), the syntax for declaring and calling procedures is greatly simplified, and conditional branching is done with a readable if...goto... statement.

This story actually took me quite a lot of time because I spent so much time working on a framework for writing acceptance tests. I use FitNesse for my No Latte interpreter. No Latte, as a language for writing web pages, is very sensitive to whitespace, and FitNesse tends to trim whitespace off your input and output. Also, FitNesse's format is a bit annoying for multi-line input. Hence, CIAT (pronounced "dog") was born. With a lot of help from Mark, we got a 0.1.0 version out that works quite well.

Lessons Learned

Most of the lessons I learned on this iteration were learned on CIAT. Most importantly, I had to figure out how to write acceptance tests for an acceptance tester!

As for my Hobbes compiler, there wasn't anything particularly surprising to me on this iteration. The front end was a rather simple lexer. The back end assumed that the front end gave it an integer token which it turned into four or five lines of PIR code.

The NoRecess Hobbes Compiler

2008-08-30T20:26:00.002-04:00

My Compiler

I'm calling my compiler the "NoRecess Hobbes Compiler". "NoRecess" is a moniker I picked up years ago when I was in college. I even bought up the domain for my website: NoRecess.

"Hobbes" is the name of the language I'll be compiling. It's based on the Tiger language from Andrew Appel's compiler books. It looks and works a bit like ML.

My Approach

Agile.

I'm tempted to leave it just at that, but I want to highlight two things.

First, I believe strongly in test-first development. I believe strongly in acceptance testing. In short, I believe in TATFT ("Test All The Freakin' Time", video NSFW!).

Second, over the last few years, I've come to appreciate incremental development in educational settings. A former student and I tried this very thing and wrote a paper about it. It's become clear to me that the real key is to work with really small iterations.

Technologies

I'm using Java and Eclipse to implement my compiler. The front end is being implemented with ANTLR.

For unit testing, I'm using JUnit and my own ANTLR Testing.

For acceptance testing, I've used FitNesse in the past for both compilers and interpreters, and the biggest problem I've had is in whitespace processing. Programs are usually multi-line affairs, and it's annoying entering them into FitNesse tables. Even worse, FitNesse strips the initial and trailing whitespace, and many times indentation matters a lot!

So I wrote my own acceptance tester: CIAT ("Compiler and Interpreter Acceptance Tester", pronounced "dog"). So far I'm really liking the way it's evolving.

Welcome!

2008-08-30T20:11:00.003-04:00

As you might guess from the title of this blog, it's focused on compilers. I am one of those strange software developers who is utterly fascinated by interpeters and compilers. Two former students convinced me to start an informal compiler course (it took all of ten seconds). The result is that we've met for a couple weeks this summer, and we've made decent progress (considering that all but me are full-time employees in the summer).

The purpose of this blog is to record some of the interesting compiler things we stumble upon. I plan to record the iterations I go through building my compiler. I suspect most of us will post interesting links.

Compiler Club

Interpreter, Going Open, and Milestones

Long time, no post!

NRHC Story #4: Multiplication

User Story

Analysis

Implementation

Next Story

CIAT version 0.3.0

A Parsing DSL in Ruby

NRHC Story #3: command-line arguments (again, again!)

Implementation (again)

Other Observations

NRHC Story #3: command-line arguments (again)

The Implementation

CIAT version 0.2.0

NRHC Story #3: command-line arguments

User Story

Analysis

YAGNI ANTLR?

NRHC Story #2: integer or addition

User Story

Analysis

Implementation

NRHC Story #1: a single integer

User Story

Analysis and Implementation

Lessons Learned

The NoRecess Hobbes Compiler

My Compiler

My Approach

Technologies

Welcome!