Memory Management in PIRC

Introduction

PIRC is a new implementation of the PIR language, and currently under heavy construction. While the code is documented, it does not provide an easy overview of implementation issues and design decisions. In order to solve this documentation gap, I'm writing these design decisions in a series of parrotblog.org articles. This very short article discusses the memory management of PIRC. 

The current PIR compiler, IMCC, has had a lot of memory leaks, most of which have been solved by now. Although conceptually manual memory management through malloc() and free() is very simple and straightforward, things become ugly once you loose overview of when datastructures go out of scope, and as a result you forget to free the memory. In PIRC a different approach is taken.

Note that instead of using malloc() and free() directly, you should use mem_sys_allocate() and mem_sys_free(), respectively, which are provided by Parrot.

Cheater!

PIRC parses the PASM or PIR input, builds a data structure, and generates a Parrot Byte Code file (a so-called Packfile). (at the moment of writing, the PBC is not generated yet, but work is underway to fix this; might take a while, though). The data structures that are created represent the PASM or PIR program being parsed, and as such can be considered an Abstract Syntax Tree.

As these data structures are used throughout the compilation phase, PIRC can cheat with memory management. Instead of freeing the memory of the data structures by manually calling mem_sys_free(), PIRC keeps track of all allocated memory blocks. Only when PIRC is done with the bytecode generation will it release all resources. This is fine, because the data structures are needed up to the end anyway, so memory is not occupied longer than necessary.

Poor Man's Garbage Collector

Whenever PIRC needs memory, a block of memory is allocated through Parrot's memory allocation function, mem_sys_allocate() (or a variant, which zeroes out all bytes). Before returning a pointer to the allocated block of memory, however, PIRC stores a pointer to the block of memory as well (in a list), and only then is the pointer to the block returned.

When PIRC is done with compiling, it will go through the list of memory pointers, and release the memory pointed to by each of the pointers. In a sense, you could consider this a garbage collector, except that there's no reuse of memory (but there's no need to anyway).

"Wait a minute," you might say, where are these pointers stored then? Well, of course, these pointers are stored in an extensible list, as we don't know the number of pointers to store beforehand. Surely the list cannot be allocated and store a pointer to itself.  This is fine, because the problem of keeping track of memory is now isolated to a single point in the program. The nodes in the list of allocated memory pointers are allocated directly through Parrot's memory functions. When all stored pointers are mem_sys_free()d, we only have to remember to mem_sys_free() these nodes. 

In this way, there's no need to worry about when pointers should be freed: it's done automatically, as long as PIRC allocates its memory through its built-in memory management system.

List of Pointers

Obviously, we don't want to create a new node for each pointer to store. Instead, a node can store a number of pointers, currently set to 512. So, after allocating memory for 512 times, a new node is created. This number of 512 was decided upon after some experimentation, but might prove too low for real world PIR input. As it's #define'd, it's easy to change, though.

Summary

In this very short article, I described how PIRC does its memory management. PIRC cheats a bit, by storing each pointer to an allocated block of memory in a special list. Once PIRC is done with compiling, all these pointers are passed to mem_sys_free(), Parrot's free() function (one by one, obviously). This way, you don't have to worry about when to free the memory in PIRC.

Parsing heredocs with PIRC

Introduction

The PIR language allows you to write so-called heredocs, as known from Perl (and I believe the idea was stolen from some older languages). If you're not a Perl programmer (like me), you might wonder what the heck I'm talking about. So, let's start with a simple example (using PIR syntax):

$S0 = <<'CODE'

This is a heredoc string

over

multiple 

lines

CODE

So, using the special <<"CODE" is stored in register $S0. So, the string stored in $S0 is:

"\nThis is a heredoc string\nover\nmultiple\nlines\n"

Want to see for yourself? 

cd compilers/pirc

make

export LD_LIBRARY_PATH=../../blib/lib

./pirc <file>

Not too difficult, eh? Well... you're right, until you use multiple heredocs in, for instance, subroutine arguments. Many Parrot tests use Perl scripts to specify the input (code) and the expected output. That's done like this:

pir_output_is(<<'CODE', <<'OUTPUT');

.sub main

   say 42

.end

CODE

42

OUTPUT

PIR also allows multiple ("nested" if you want, but they're not symmetrically nested; a better word would be "overlapping") heredocs. The current PIR compiler (IMCC) cannot handle this, but the new PIR compiler (currently still under development) PIRC, can. In an attempt to maximize the "truck number" of PIRC (which is currently estimated to be 1), I'm trying to do as much documentation of PIRC as possible. In this article, I'll be discussing how heredoc parsing is done in PIRC.

Single heredoc parsing

Let's start out simple with a single heredoc string. The heredoc preprocessor is implemented in the file compilers/pirc/new/hdocprep.l. Yes, that's right, that's not a C file, but a Lex specification file. Using Lex (and it's probably Flex that you'll be running, a faster implementation of Lex), the .l file is converted into a C file.

Now, for this discussion I'll assume that you know a bit about using Flex. A particular (advanced) feature of Flex-generated scanners (or "lexer" if you want) is the use of states. Using states you can implement several scanners in a single specification. Based on the state that the lexer is in, it'll recognize a subset of the rules. If no rule is specified, then the built-in, default INITIAL state is assumed. States can be pushed and popped of a stack, also managed by the generated C file. Whenever a new state is pushed onto the stack, that becomes the active state, and all rules that are specific to that state will become active. Once the state is popped of the stack, the rules fall out of scope again, and the state at the top of the stack (after popping) will become active.

So, the trick that's used is, as soon as the heredoc marker is read (e.g. <<'CODE'), we enter a new state, which will read the input line by line. All rules of the previous state are no longer active, so strings such as "<<'OUTPUT'" won't be matched, but instead are stored in a string buffer. After reading each line, it will check whether the heredoc end marker was read. As soon as the end marker is read, the heredoc scanning state will be popped, and scanning will continue in the initial state.

Single heredoc strings as subroutine arguments

Consider the following PIR line:

foo(<<'CODE', 42, 'hi')

After reading <<'CODE', the scanner will continue scanning in the heredoc state. However, the rest of the line, containing ", 42, 'hi')" should be stored somewhere, as this is not part of the heredoc.  So, the "rest of the line" is scanned, stored in a buffer, and then the heredoc scanning can start. After reading the end marker of heredoc, the scanned heredoc is printed to the output, after which the "rest of the line" can be scanned. Not so hard, eh?

Scanning multiple heredocs

Things get more interesting when you need to scan input like the following:

foo(<<'CODE', 42, <<'OUTPUT', 'hi')

.sub main

 say 42

.end

CODE

42

OUTPUT

Scanning the first heredoc string works fine; the "rest of the line" is then:

", 42, <<'OUTPUT', 'hi')"

After scanning the first heredoc, we tell the lexer to start retrieving the next characters from the "rest of the line" buffer. When scanning this line buffer, we'll encounter the <<'OUTPUT' marker, which indicates another heredoc string. At this point, we need to re-save the "rest of the line", which will contain:

, 'hi')

At this point, we need to continue scanning from the input file, after the point we left off after scanning the first heredoc. So, off we go, again switching input buffers in the lexer, so that the contents of the second heredoc string are scanned. Again, scanning line by line, checking for the heredoc end marker. Again, once we find the end marker, we'll switch back to the "rest of line" buffer, and finish scanning that string. Once we read EOF on the line buffer, again we switch back to the input file, and the rest of the file is scanned as if nothing happened.

Heredoc preprocessing

The heredoc handling is implemented as a separate pass over the input file. This was done to keep the complexity of the lexer manageable. Although this does result in more I/O operations, having better readable code is, IMHO anyway, a more important goal than presumably faster code, that is hard to maintain. Currently, the output of the heredoc preprocessor is written to a temporary file, of which the PIR lexer is reading.

Including files

The PIR language has a C-preprocessor-like #include directive, spelled as ".include". Logically, it's part of the macro layer, as the include directive is replaced by the contents of the specified file. However, as an included file may contain heredoc strings as well, the whole invocation scheme of the PIR compiler becomes more complex, as that included file must be handled by the heredoc preprocessor as well. 

So, PIRC cheats a bit. Instead of implementing the .include directive in the macro layer, it is moved "forward" to the heredoc preprocessor. This way, the heredoc preprocessor converts all heredoc strings into normal strings (a process I like to call "flattening the string", as the multi-line string is now flat, meaning it's a one-line string), and stores the contents of all included files into the temporary file. PIRC's normal lexer only ever sees one single input file, and does not need to handle the .include directive.

Summary

This article discusses the implementation of the heredoc preprocessor. PIRC allows you to use multiple heredoc strings in a single PIR statement, which introduces some complexity to the lexer. For that reason, heredocs are processed in a separate pass over the input. Besides handling heredocs, the .include directive is handled in the heredoc preprocessor as well, to make life a bit easier for myself.

Register allocation in a PIR compiler

Introduction

As some of you may know, I have been working on a new implementation of a PIR compiler, which is named PIRC. In the end, my plan is to emit actual Parrot Byte Code (PBC), which can then be run by Parrot. Once everything's working and tested properly, I will make a case for replacing the current PIR compiler (IMCC). It might take a while before I get to that, though.

In the mean time, I'm trying to make PIRC as feature-complete as possible, and will try to write up some of the implementation issues that have to be dealt with. This can be interesting for lurkers, who 'have always wanted to know how to do it', but also just as a way to document things.

In this article, I will discuss the implementation of a recently added feature: a register allocator. Now, the implementation I came up with still needs a lot of testing, but the idea behind it does not change. The algorithm I chose is Linear Scan Register (LSR) Allocation, which is described in detail here. This algorithm is very different from the more well-known (classic, if you like) register coloring algorithm, which is based on graph coloring theory. I won't go into details too much, except mentioning that while a register coloring algorithm can yield more efficient register usage, but is a lot more expensive in terms of processor cycles, compared to the LSR algorithm. Obviously, for dynamic languages, where runtime compilation is a common feature, this is an important feature.

Register allocation

First, a short review of register allocation. I will make some rough simplifications just for the sake of this discussion, so I probably will make some false statements here. In real CPUs, there's a limited number of registers. This is fine, as long as the number of registers is larger than the number of variables that are alive. However, once you have more variables than registers, you need to overwrite a previously used register. If the value in the register being reused for another variable is going to be used after this overwriting, then you need to make sure the value is stored somewhere temporarily, typically in memory. This is called register spilling. Then, later, when the variable that was 'spilled' is referenced again, it needs to be reloaded into a register, overwriting that register's current value, which again needs to be spilled.

In short, you typically have to map N variables onto M registers, and if N > M, you need to spill registers.

In the Parrot virtual machine, this is not necessary. Parrot allows a subroutine to have as many registers as possible (up to the physical limitations of your memory, obviously). If a subroutine needs 50 registers, then it will happily allocate those. After all, Parrot can be considered a CPU in software, which uses memory for anything where a hardware CPU uses... eh... well, hardware. (Of course, memory chips are hardware... oh well, you get my point).

In any case, this is good news for any register allocator in the PIR compiler, as it makes the job of register allocation extremely simple. PIRC has a 'vanilla' register allocator, which allocates registers using a counter, starting at 0, and increment the counter whenever it needs a new register.

However, it's still a bit of a waste. If you look at typical PIR output of Rakudo, the Perl 6 implementation running on Parrot, then you'll see it's a lot of code. A Lot. It would be good if registers can actually be reused, if the variable that it represents is never referenced again. After all, as you now know, Parrot allocates as many registers as it needs for any given subroutine, and obviously, less is better, as it saves memory.

(Ok, I admit it, I really just did it because it was a nice challenge to implement).

Now you know why register optimization is useful, let's discuss some basics of the algorithm that was implemented.

Linear Scan Register Allocation

The Linear Scan Register Allocation (LSR) algorithm is really quite simple. The basic idea is that, each variable has a certain life time. In a programming language, a variable typically has a scope, which is the maximum life span of a variable (because it will go out of scope after the scope has closed. Are you still with me?) . However, the fact that a variable has a scope doesn't mean it's being used throughout the whole scope; it's very possible, and likely, that a variable is only used in one or two statements in the scope. So, suppose there are two variables, say, foo and bar, which have mutual exclusive life spans, (this means they never live in the same 'era'). This means they can both be mapped to the same register. This is the fundamental idea behind the SLR allocator.

Data structures
First, I need to explain some basic data structures that are used in PIRC. I won't do this in too much detail; that would be a good topic for some other time.
PIRC has basically two important parts: the parser, and the back-end. The parser is implemented using a Bison (I think it uses some features that are not Yacc-compatible) specification. The back-end is a bunch of data structures that are manipulated during the parse.
In the context of register allocation, the most important data structures are the structs target, symbol and pir_reg. A symbol is a declared .local identifier; a pir_reg represents a PIR symbolic register (like $I42). A target represents a so-called l-value object; this is an object that can be assigned to. Basically, symbols and pir_reg objects have a one-to-one mapping w.r.t. the symbol or symbolic register they represent, while targets have a many-to-one relation w.r.t. the underlying symbol or pir_reg. So, suppose you declare a .local int foo, then there will be a single symbol object representing foo, but there may be many target nodes pointing to this symbol.
As symbols and pir_regs are only created once for the target they represent, the vanilla register allocator (which is a very basic, dumb allocator) will assign a new register to each new symbol/pir_reg object. Whenever a target is being parsed (and it's easy to recognize whether it's a identifier or a symbolic register), the symbol or pir_reg object for that target is looked up, and linked to the target node.
This link is very important, because it is used to tell the symbol (from now on, wherever you read symbol, you can interpret it as 'symbol or pir_reg') that it is used in the current instruction. During the parse, the compiler keeps track of an instruction counter, which just assigns numbers in a consecutive way to the instructions. So, basically whenever a target is parsed, it updates the life span of the symbol. The first usage of an identifier indicates the first usage of that symbol (and not its declaration: you may declare a symbol, but never use it).
What this means is, that after the parse, for each symbol (.local identifier and symbolic register), we have a life interval object, which knows when is the first usage of the symbol, and when is the last.

Implementation
Once you know when the variables are used, it becomes extremely simple to optimize the register usage. Basically, you iterate through each life interval object, you assign the symbol it represents a new register (a real parrot register like P2, not a symbolic register, like $P2), and you place the live interval object into a list of "active" variables. Each iteration, you walk through this list, and "expire" any live intervals that represent symbols that are no longer used. For this, the interval objects that you're iterating over must be sorted. Whenever a live interval has expired, the register it was assigned becomes available, so you can put that register on a "free" list; the next time you need a new register, you first check whether there's any "old", previously used registers are available. If not, you just increment a counter, increasing the total number of registers that Parrot must allocate.

This all might sound very complex, but, really, it's not. The implementation is only about 200 lines of code or so (that's a wild guess), and can be found in compilers/pirc/new/pirregalloc.c.

Of course, the thing needs to be properly tested, but the basic idea stays the same. There's still quite some work to be done in PIRC anyway.

Conclusion
In this article I tried to explain the implementation of a register allocator, which optimizes the register usage of code generated by PIRC, a new PIR compiler. The basic data structures were briefly explained, and the algorithm was summarized. Experience should show whether the investment was worth it, or that more heavy-weight implementations, such as graph-coloring-based algorithm should be used.

Tracking down an IMCC bug

So I was adding support for handling next/redo/last exceptions to PCT's loops the other day, and I hit a weird bug. Here's the patch.

The problem is approximately this:

$I0 = defined, stuff_to_loop_over
unless $I0, for_loop_end
push_eh for_loop_next
...
for_loop_end:
pop_eh

I'm adding the error handler there after a conditional jump, but popping the error handler off after the target of that jump, but I didn't notice this at the time. That's going to at least cause bugs at runtime, but this also caused the PIR compiler to hang. I beat my head against it for a while, posted a bug about it, and went to sleep.

The next day, I used valgrind's callgrind tool to find where it was spending it's time. The output is:

--------------------------------------------------------------------------------
            Ir  file:function
--------------------------------------------------------------------------------
13,455,028,108  /home/sweeks/src/parrot/compilers/imcc/sets.c:set_add [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
11,209,537,812  /home/sweeks/src/parrot/compilers/imcc/cfg.c:compute_dominance_frontiers [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
   135,234,114  /home/sweeks/src/parrot/compilers/imcc/imclexer.c:yylex [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
   128,962,606  /home/sweeks/src/parrot/compilers/imcc/sets.c:set_contains [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    88,825,729  /home/sweeks/src/parrot/compilers/imcc/imcparser.c:yyparse [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    70,349,560  /home/sweeks/src/parrot/compilers/imcc/instructions.c:instruction_reads [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    65,814,257  /home/sweeks/src/parrot/compilers/imcc/cfg.c:compute_dominators [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    56,483,518  /home/sweeks/src/parrot/compilers/imcc/instructions.c:instruction_writes [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    48,013,979  ???:_int_malloc [/lib64/libc-2.8.so]
    46,419,350  /home/sweeks/src/parrot/compilers/imcc/pbc.c:constant_folding [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    33,201,086  /home/sweeks/src/parrot/compilers/imcc/sets.c:set_intersec_inplace [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    29,624,696  /home/sweeks/src/parrot/compilers/imcc/symreg.c:hash_str [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    20,719,320  ???:calloc [/lib64/ld-2.8.so]
    18,291,953  /home/sweeks/src/parrot/compilers/imcc/cfg.c:bb_check_set_addr [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    17,404,418  /home/sweeks/src/parrot/compilers/imcc/reg_alloc.c:compute_one_du_chain [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    13,809,278  /home/sweeks/src/parrot/compilers/imcc/imcc.l:yylex
    12,337,246  /home/sweeks/src/parrot/src/ops/core_ops.c:hash_str [/home/sweeks/src/parrot/blib/lib/libparrot.so.0.7.1]
    12,162,840  ???:memcpy [/lib64/ld-2.8.so]
    11,450,969  ???:strcmp'2 [/lib64/ld-2.8.so]

So it's in IMCC, the PIR compiler, specifically in compute_dominance_frontiers... which is what? So let's find out.

The POD for that function says:

=item C<void compute_dominance_frontiers>

Algorithm to find dominance frontiers described in paper "A Simple, Fast
Dominance Algorithm", Cooper et al. (2001)

A quick check with google turns up the PDF I linked.

Skimming over that and the surrounding code that calls compute_dominance_frontier reveals that it's related to register allocation. I read it another couple of times, think I understand the general ideas, and go to sleep.

The next day, I chat with pmichaud about it, and he manages to trim down a simplifed test case, and also notices the actual bug in my patch, which allows me to commit that and pass a half-dozen more tests. He passes the minimal test off to chromatic, who debugs it for a bit and finds that an inner loop in compute_dominance_frontiers is alternating between 8 and 9.

chromatic suggests that I find a way to dump out the register and basic blocks information, and look for the edge identification between blocks. I only have a vague idea of what this means then, so I ask for more information. Here's chromatic's explanation:

<@chromatic> I can give you a quick overview.
<@chromatic> The alligator divides every compilation unit into basic blocks.
<@chromatic> A block is a single block of code between branch points.
<@chromatic> Every entrance and exit point demarcates a block.
<@chromatic> If you arrange the blocks in terms of a control flow graph, you can evaluate all of the possible ways you can reach a point within the block.
<@chromatic> You also keep track of which registers you use within a block.
<@chromatic> If all of the paths to a block go through another block, the latter dominates the former.
<@chromatic> All of this is to say, if you have a named register used in the first block of a unit and the final block of the unit can branch back to the first unit, you have to keep the physical register untouched.
<@chromatic> If there's a block beyond which you can never branch back, you can reuse physical registers unique to that branch and never used later.
<@chromatic> I've been unclear about name/physical register mapping, but I think you get the picture.
<@chromatic> It's the mapping of name to register that really matters.

So I start browsing that code again, but fall asleep before doing anything. Do you see the pattern here yet? ;)

The next day, I go look around in there and I find a couple of debug functions I can use to dump relevant information. Here's what I find:

Dumping the CFG:
-------------------------------
0 (3)  -> 8 1 2    <- 
1 (3)  -> 2    <- 0 
2 (3)  -> 3 9    <- 1 0 
3 (2)  -> 4    <- 2 
4 (2)  -> 5    <- 3 
5 (3)  -> 6 9    <- 8 7 4 
6 (3)  -> 7    <- 5 
7 (3)  -> 5    <- 6 
8 (2)  -> 5    <- 9 0 
9 (3)  -> 8    <- 5 2 

This is:

block number (loop depth) -> blocks that this block can branch to    <- blocks that can branch to this block

We also have:

Dumping the Dominators Tree:
-------------------------------
 0 <- ( 0)  0
 1 <- ( 0)  0  1  8  9
 2 <- ( 0)  0  2  8  9
 3 <- ( 2)  0  2  3  8  9
 4 <- ( 3)  0  2  3  4  8  9
 5 <- ( 0)  0  5  8  9
 6 <- ( 5)  0  5  6  8  9
 7 <- ( 6)  0  5  6  7  8  9
 8 <- ( 9)  0  8  9
 9 <- ( 8)  0  8  9

This is:

block number <- (immediate dominator) full list of dominators

The loop that was spinning was:

while (runner >= 0 && runner != unit->idoms[b]) {
    /* add b to runner's dominance frontier set */
    set_add(unit->dominance_frontiers[runner], b);

    /* runner = idoms[runner] */
    if (runner == 0)
        runner = -1;
    else
        runner = unit->idoms[runner];
}

Where 'runner' is the node we're currently evaluating, unit is the overall compilation unit, and idoms[] is the list of immediate dominators.

Adding some debugging printfs, I discover that the problem is when the algorithm follows block five, it spins with the runner alternating between 8 and 9. If you look back up at the dominators tree, you'll see that the immediate dominator of block 8 is block 9, and the idom of block 9 is block 8. Infinite loop.

After re-reading the algorithm and paper a few times to verify that I undersand what's going on, I add a conditional to break out of the statement if we're trying to add a block to the dominance frontiers list of a block that we've already added the current block to.

while (runner >= 0 && runner != unit->idoms[b]) {
    if (set_contains(unit->dominance_frontiers[runner], b))
        /* we've already gone down this path once before */
        runner = 0;
    else
        /* add b to runner's dominance frontier set */
        set_add(unit->dominance_frontiers[runner], b);

    /* runner = idoms[runner] */
    if (runner == 0)
        runner = -1;
    else
        runner = unit->idoms[runner];
}

Everything seemed to work fine, so after getting a review from particle, I committed.

"Final report" for Mozilla Foundation and TPF grant

Last year I received a Perl 6 development grant from the Mozilla Foundation and The Perl Foundation. Below is a copy of the final report I've submitted to close out the grant. It's also available in PDF if anyone wants a more printable version.

My thanks to everyone who helped me with this grant, and I'm looking forward to the next one.

[2008-09-11 update: the original version of this report mis-attributed the Squaak tutorial to Kevin Tew; the corrected author is Klaas-Jan Stol (kjs). My sincere apologies for the mistake, it is now corrected below.]

---

Perl 6 Development Grant
Final Report

Patrick R. Michaud
September 10, 2008

INTRODUCTION

This is the final report for the Perl 6 and Parrot development grant provided by the Mozilla Foundation and The Perl Foundation. This report summarizes the work performed under the grant, what has been accomplished, and where things are headed from here. As this report illustrates, we have achieved all of the goals and outcomes intended for this grant.

REPORT

The primary focus of the project was to get Perl 6 on Parrot development "over the hump" and acquire a critical mass of infrastructure, developers, and tools from which sustained further development of Perl 6 can take place. The project proposal identified five specific expected outcomes:

1. A working Perl 6 on Parrot implementation that supports commonly used Perl constructs and operators
   
2. Review and improvements to the Perl 6 language test suite
   
3. A substantially complete Parrot Compiler Toolkit, with documentation
   
4. Ongoing, active development efforts for other languages based on the Parrot Compiler Toolkit
   
5. An increased number of participants in Perl 6 and Parrot design, implementation, and testing
   

1. A working Perl 6 on Parrot implementation

We now have a substantial Perl 6 implementation on Parrot. At the beginning of this project, we had a rudimentary Perl 6 compiler that could handle some of the basic features and syntax of Perl. However, some key features such as arrays and hashes were only marginally implemented, and most of the translation components of the compiler were written in Parrot's intermediate assembly language (PIR).

Today the Perl 6 on Parrot compiler has been substantially rewritten using the Parrot Compiler Toolkit (described below), and is now known as "Rakudo Perl" or "Rakudo" [1]. Rakudo currently supports arrays, hashes, classes, objects, inheritance, roles, enumeration types, subset types, role composition, multimethod dispatch, type checking, basic I/O, named regular expressions, grammars, optional parameters, named parameters, slurpy parameters, closures, smart match, junctions, and many other features expected from Perl 6. Rakudo has progressed to the point that others are now using Rakudo as an Apache handler ("mod_perl6") [2], a wiki engine ("November") [3], and recently to build applications on Xlib [4]. The Perl Foundation also recently awarded a grant to Vadim Konovalov to implement a Tk GUI interface for Rakudo [5].

During the project there have been many contributors to the development of Rakudo Perl; some of the major contributors include chromatic, Vasily Chekalkin (bacek), Jerry Gay, Jeff Horwitz, Moritz Lenz, Carl Mäsak, Cory Spencer, Stephen Weeks (Tene), and Jonathan Worthington. Jonathan Worthington's efforts deserve special mention: he is primarily responsible for the bulk of the work on classes and types in Rakudo Perl, and much of his work was supported by a grant from Vienna.pm [6].

2. Review and improvements to the Perl 6 test suite

At the beginning of this project, the test suite that existed for Perl 6 had been implemented as part of the Pugs effort and contained approximately 16,000 tests. However, in many cases the tests were out of date with respect to the current Perl 6 language specification, and we needed a way for multiple independent Perl 6 implementations to be able to easily make use of the test suite.

In December 2007 I proposed a structure for reorganizing the test suite [7]; Jerry Gay and Larry Wall then extended this proposal and developed tools to make it easier to share the tests among multiple implementations. In May 2008 Moritz Lenz refactored Rakudo's test harness to provide a "make spectest_regression" target -- since then this has become our primary measure of Rakudo progress [8]. Moritz Lenz also developed a tool to display the progress in graphical form:

Adrian Kreher received a Google Summer of Code grant (with Moritz Lenz and Jerry Gay as mentors) to continue the test suite refactoring [9]. As of early September 2008, the official, refactored test suite contains a little over 8,000 tests, or approximately half the size of the original Pugs test suite. Furthermore, the official suite includes many new tests for object-oriented and typing features of Perl 6 that weren't present in the original test suite. As the graph above indicates, Rakudo is currently passing over 3,200 of the tests in the official suite, and work is continuing on refactoring the suite and increasing Rakudo's pass rate.

3. A substantially complete Parrot Compiler Toolkit, with documentation

As mentioned previously, the compilers that existed for Parrot at the beginning of the project (such as Perl 6) were primarily written in Parrot's intermediate assembly language. This made working on the compilers less accessible to new developers, as well as increasing the time needed to build a compiler. Therefore, the first couple of months of this project were spent on developing the Parrot Compiler Toolkit (PCT) and a simple Parrot language called Not Quite Perl (NQP). PCT provides an abstract syntax tree representation and code generator for Parrot languages; NQP enables compiler writers to easily create compilers and builtin functions for Parrot using a simplified Perl 6 syntax.

Once PCT and NQP were substantially complete, we were then able to convert Perl 6 (now "Rakudo Perl") and many other Parrot compilers to use the new toolkit. This went surprisingly quickly -- most of the existing compilers were converted within just a couple of weeks. In addition, a few new compilers and languages arrived on the scene: Will Coleda and Simon Cozens quickly created an implementation of LOLCODE [10], and Klaas-Jan Stol created a language called "Squaak" as a demonstration and tutorial for the toolkit [11]. A couple of quotes from the period give a sense of how these tools opened up Parrot development to others:

"The real fun, though, has been digging into perl6, the Parrot Perl 6 implementation. Recently, Patrick Michaud has been doing some incredible work building NQP (Not Quite Perl 6), a bootstrapping language for implementing Perl 6, and extensively refactoring the existing Perl 6 on Parrot compiler to fit with it. I'm still very much getting my head wrapped around the whole thing, but it's been easy enough to start digging into and implementing and fixing a few things."

- Jonathan Worthington, December 2007 [12]

"It's really, really true. Parrot lets you implement your own languages using Perl 6 rules for the grammar and Perl 6 for the compiler."

- Simon Cozens, January 2008 [13]

Both PCT and NQP stabilized early in the project; recent changes have been primarily to optimize existing features or make other minor improvements. We expect these tools to continue to evolve as needed to support compiler development; however, given the wide variety of languages being implemented using the toolkit surprisingly few changes have been needed. Primary documentation for the toolkit consists of a Parrot Design Document (PDD26) for the abstract syntax tree representation [14], the Squaak tutorial [11], and numerous example languages in the Parrot repository. More detailed documentation and examples for the toolkit are expected to be developed over the coming months.

4. Ongoing, active development efforts for other languages based on the Parrot Compiler Toolkit

Currently there is active development on at least three languages for Parrot; these include Perl 6 (Rakudo Perl), PHP (Pipp), and Ruby (Cardinal). In addition, there is ongoing but less active
development on implementations of Python (Pynie) and Smalltalk (ChitChat). All of these are based on the tools from the Parrot Compiler Toolkit. The Perl 6 and PHP implementations are usable from mod_parrot [2], and our next steps are to improve the toolkit and library conventions to support loading multiple languages simultaneously in Parrot.

5. An increased number of participants in Perl 6 and Parrot design, implementation, and testing

There can be little question that momentum for Perl 6 and Parrot development continues to grow, and the work supported by this grant has been a major catalyst for that growth. For the twelve months prior to September 2007 the Parrot subversion repository had a total of 6,634 commits; in the subsequent twelve months Parrot had 9,686 commits -- a year-over-year increase of 46% in the commit rate.

At the beginning of this project there were perhaps three or four active contributors to the Perl 6 on Parrot compiler (i.e., Rakudo Perl); over the course of the past year that number has increased to at least ten active contributors and at least as many more occasional contributors to Rakudo Perl. Parrot and the Parrot Compiler Toolkit have also garnered new contributors, including several new committers. There are also new teams of developers working on applications based on Rakudo Perl and Parrot, such as the November wiki engine and the Rakudo/Tk GUI interface.

Lastly, recent improvements in the Rakudo compiler architecture will allow much of the Perl 6 runtime library currently written in PIR to be rewritten substantially in Perl 6. This will enable even more new contributors to participate in Perl 6 development.

PROJECT EVALUATION

The project proposal identified five criteria by which the success of this project could be measured:

• Ability to write and test Perl 6 programs and language features
  
• Passing rate for Perl 6 language test suite
  
• Improved coverage and accuracy of the Perl 6 language test suite
  
• Increased number of participants in Perl 6 and Parrot development
  
• Active development of at least two other languages using Parrot compiler tools
  

This report demonstrates the success of this project along all of these measures. Perl 6 on Parrot ("Rakudo") is being used to write and test Perl 6 programs and language features, and has become a strong driver for improving the coverage and accuracy of the test suite (and indeed, of the Perl 6 language specification itself). Continual reporting and publication on Perl 6 and Parrot activities continues to attract increased interest and participation from the wider community.

Moreover, this project helped jump-start even larger fund-raising efforts. In May 2008 the Perl Foundation received a $200,000 philanthropic donation from Ian Hague; roughly half of this donation is intended to continue the Perl 6 development efforts that have been part of this project [15]. And, as mentioned earlier, Jonathan Worthington and others are receiving grants for continued work on Rakudo Perl and Parrot [6,8,16].

CONCLUSION AND FUTURE WORK

The funding provided by the Mozilla Foundation and The Perl Foundation has indeed enabled us to get Perl 6 on Parrot development "over the hump" in development. We now have a robust platform for higher-level language development on Parrot, along with an active and growing development and support community (which is the hallmark of any successful open source project). All of the desired outcomes of this project have been realized.

Our next steps will be to continue to extend and build upon the work of this project -- increasing Rakudo's coverage of the Perl 6 language and bringing all of our efforts much closer to production releases. In fact, we recently developed a "road map" for Rakudo Perl that identifies the major steps to be taken in the upcoming months and assists in coordinating the remaining development activities [17].

Lastly, I want to express my sincere appreciation to the many people who contribute time and energy to Perl 6 and Parrot, and to give special thanks to the people of the Mozilla Foundation and The Perl Foundation for their ongoing support and enthusiasm for this project. It is a great honor to work and correspond with such a terrific and professional group of individuals.

REFERENCES

1. P. Michaud (January 16, 2008), "The compiler formerly known as 'perl6'", http://use.perl.org/~pmichaud/journal/35400
2. J. Horwitz, "Mod_parrot website", http://www.smashing.org/mod_parrot/
3. C. Mäsak, "Announcing November, a wiki in Perl 6", http://use.perl.org/~masak/journal/37212
4. http://svn.perl.org/parrot/trunk/examples/nci/xlibtest.p6
5. Alberto Sim&otild;es (August 30, 2008), "2008Q3 Grants Results", http://news.perlfoundation.org/2008/08/2008q3_grants_results.html
6. "Vienna.pm funds Jonathan Worthington to work on Ra[kudo]" (April 23, 2008), http://use.perl.org/article.pl?sid=08/04/23/2314234
   
7. P. Michaud (December 20, 2007), "Proposal: refactor the test suite according to synopsis, http://groups.google.com/group/perl.perl6.compiler/msg/ed748490f030da2f
   
8. P. Michaud (June 16, 2008), "Rakudo test suite progress", http://use.perl.org/~pmichaud/journal/36695
   
9. A. Kreher, "Auzon's Blog: gsoc2008", http://auzon.blogspot.com/search/label/gsoc2008
   
10. "I HAZ A PARROT" (January 3, 2008), http://lolcode.com/news/i-haz-a-parrot
    
11. K. Stol (March 9, 2008), "PCT Tutorial Episode 1: Introduction", http://www.parrotblog.org/2008/03/targeting-parrot-vm.html
    
12. J. Worthington, "Chipping away at perl6", http://www.jnthn.net/cgi-bin/blog_read.pl?id=589
    
13. S. Cozens (January 3, 2008), "Parrot is really quite wonderful", http://blog.simon-cozens.org/post/view/132
14. "Parrot Abstract Syntax Tree (PDD 26)", http://www.parrotcode.org/docs/pdd/pdd26_ast.html
    
15. R. Dice (May 16, 2008), "TPF receives large donation in support of Perl 6 development", http://news.perlfoundation.org/2008/05/tpf_receives_large_donation_in.html
16. J. Worthington (August 5, 2008), "Multiple Dispatch Design Work", http://use.perl.org/~JonathanWorthington/journal/37101
17. "Perl 6 Development Roadmap", http://svn.perl.org/parrot/trunk/languages/perl6/ROADMAP

Using 'register' scope in Parrot Abstract Syntax Trees

Introduction
The Parrot Compiler Toolkit (PCT) is evolving, slowly becoming mature. More and more features and improvements are added over time. In this short article, we'll be looking at "register" scope in the Parrot PAST::Var node, which was added recently. For this article, I assume you're familiar with the PCT, or at least heard of it, otherwise I'd suggest reading up a bit, for instance by reading the PCT Tutorial. In order to make things as easy as possible, I'll start out with a short introduction on the Parrot Abstract Syntax Tree data structure.

PAST Variables and Scope
PCT-based compilers generate a data structure called a Parrot Abstract Syntax Tree (PAST). The PAST itself consists of a number of different PAST nodes. For instance, to represent a subroutine (or function, or procedure), you'd use a PAST::Block node, while you'd use PAST::Val nodes to represent literal constants (such as 42, "hello world", etc.).
For representing variables, you'd use a PAST::Var node. All variables have a name and a scope, implemented as attributes of the PAST::Var class. Available values for the scope attribute are, among others: "package" and "lexical", representing "global" and "lexical" (or "local", except that "lexical" implies availability in nested subs (or PAST::Block nodes) as well) scope.

Introducing Register Scope
Lexically scoped variables are stored in such a way that nested subroutines can access them too. In languages such as Perl 6 and Lua, this makes sense. However, in a language such as C (yes, there is a C implementation for Parrot as well, albeit an incomplete one) this is not needed, as C does not have nested functions. The overhead of lexicals would be a waste of your CPU cycles.
The new register scope allows for such "light-weight" local variables. Furthermore, although not implemented at the moment of writing this article, these register variables allow for reusable results. Consider the following pseudo-code example of a "with" statement. A with statement takes some expression, and the operations in the block are all executed on that expression. (Note that this is pseudo code).

with (foo) {
   .bar();
   .baz();
   .foobar();
}

This is equivalent to:

foo.bar();
foo.baz();
foo.foobar();

except that in the case of the with-statement, the expression is evaluated only once. I'm sure there are better examples to be thought of for a with statement, but this is the best I can come up with for now. Using the PCT, you could implement this as follows:

 rule with_statement {
    'with' '(' <expression> ')'
    '{' <statement>* '}'
    {*} 
}

The corresponding action method would be:

method with_statement($/) {
    my $past := PAST::Stmts.new( :node($/) );
    my $expr := $( $<expression> );
    for $<statement> {
        my $operation := $( $_ );
        $operation.unshift($expr);
        $past.push( $operation );
    }
    make $past;
}

Basically, the PAST node representing the expression is unshifted onto each operation. However, this would result in PIR code that would evaluate the expression for each statement in the with-block. This, of course, reduce the efficiency of the whole with-statement, whose semantics define that the expression is evaluated only once. In order to solve this, you can generate PIR code that evaluates the expression once, stores the result in a register variable, and use that register variable in each operation.

Why "Register" instead of "Local"?
You might wonder why this scope is called "register". The scope name "register" makes perfect sense, as this is exactly how it is implemented. A variable with "register" scope is implemented as a PIR variable declared with the .local directive. Such a variable is just a symbolic register, which makes writing PIR code by hand much easier. The PIR compiler will map these .locals to Parrot registers (of type PMC, Parrot does not support lexicals of other types). The name "register", therefore, makes perfect sense.

Using Register-scoped Variables in Your Compiler
There is not much to it to use register-scoped variables. You use them the same way as you would use global or lexical variables. The name attribute gives the register a name, and when setting the isdecl flag on it, the PAST node will generate a PIR .local declaration. In comparison, when this flag is set on a PAST::Var node with "lexical" scope, a .lex directive is generated.

Conclusion
This article discussed a recently added feature to the PCT, albeit a small one. The addition of a new scope type to PAST::Var nodes. The new "register" scope allows for light-weight local variables, and in the not too distant future will allow for reusable (intermediate) results, preventing re-evaluation of expressions in your PAST.
As you can see, the PCT is evolving over time, which allows users to create compilers for all sorts of languages targeting the Parrot virtual machine.

Announcing the Parrot Foundation

On June 9th, 2008, we filed the incorporation papers for the Parrot Foundation (abbreviated as just "Parrot", or "PaFo" if you can't resist the shiny alphabet soup). The articles of incorporation and bylaws were drafted on the mailing list and in the wiki, the same way all Parrot design documents are drafted. The design of the foundation is very much a part of the design of the whole project, tailored to the culture and customs of Parrot.

The purpose of the foundation is to hold the intellectual property of the project, to help drive development of the core codebase and language implementations, to support and grow the community around Parrot, and reach out to other language projects. As we push through the final steps to the 1.0 release, the foundation will provide the infrastructure we need to move forward.

The initial board of directors consists of: Allison Randal, Chairman; Jerry Gay, President; Will Coleda, Vice President; Shane Warden, Secretary; and Jeff Horwitz, Treasurer. The membership of the foundation will start with the current committers, and quickly expand to include all contributors. Members elect the board of directors every year, so the leadership and direction of the foundation is always guided by the developers.

It's exciting to see the foundation come together so quickly and smoothly. While the idea of a foundation for Parrot has been bubbling on the back burner for about a year, it was only two months ago that we got together and decided it was time to make it a reality.

Thanks to all who have helped make it possible, and cheers to a great future!