Whiteknight's Parrot Blog

Introspection, Disasembly and PACT (GSOC)

2012-02-21T00:00:00-08:00

In my post a few days ago I mentioned Google Summer of Code 2012 and gave a lightning list of simple project ideas that might be worth pursuing. Today I’m going to expand on one of these ideas because it’s fertile ground for many possible GSOC projects, including the possibility of several projects concurrently if we have multiple students interested in it.

Parrot has a lot of introspection ability, but we don’t really have the tools necessary to introspect bytecode. We need some kind of tool that, given a Sub PMC or a PackfileView PMC or similar will be able to provide a disassembled representation of the actual opcodes. Here’s a basic code example of what I am talking about:

function foo() { var x = 2; ... }

function bar() {
    var disassem = new Parrot.PACT.Disassembler();
    using foo;
    var raw = disassem(foo);
    var reg = raw.registers();          // Get register counts
    var lex = raw.lexicals();           // Get info about lexicals
    var constants = raw.constants()     // Referenced constants
    var ops = raw.opcodes();            // Symbolic Opcodes
    say(ops[0]);                        // "set_p_i, $P0, 2", etc
}

These are just some random ideas and not all of them are necessary to implement. The most important part, in my mind, is getting a list of symbolic Opcode PMCs. Each Opcode PMC would have this general form:

class Parrot.PACT.Opcode {
    var opname;         // The name or short name of the op
    var opnumber;       // The number of the opcode
    var oplib;          // The oplib which owns it
    var args;           // Array of Arguments
                        // Either Register or Constant
    ...
}

I prefix the disassembler classname with the namespace “Parrot.PACT” because eventually this should be an integral component of the PACT library. When we use PACT to assemble packfiles (and, ultimately, bytecode files) we’ll be constructing a list of these Opcode PMCs and then using a serializer to write them down to raw bytecode.

                  Serializer
Array of Opcodes ------------> Packfile Bytecode Segment

          Deserializer
Bytecode --------------> Array of Opcodes

An excellent proof of concept system would combine these two mechanisms together into a faithful round-trim assembly/disassembly mechanism. In fact, there are multiple little potential projects here that can be arranged and ordered/prioritized to create a summer-long project or many:

Create a tool to disassemble raw bytecode into Opcode PMCs, and create a disassembler program to interact with the user and print the disassembly listings to file/console.
Create a tool for round-trip disassembly and assembly. Write the disassembly type, then write a tool that does the reverse operation (take a list of Opcodes and write a valid Packfile or bytecode segment).
Create the tool to disassemble raw bytecode, then write a utility layer to construct a control flow graph from those Opcodes. This layer could be used in turn to create things like code complexity analyzers, or even simple decompilers (for the very ambitious student).
Write a tool to take a stream of Opcode PMCs and other related data (tables of constant values, annotations, debugging symbols, etc) and write them into a valid and executable packfile. This would be the base layer of the PACT assembly engine, and would be used to help build compilers and other tools.
Construct anything else PACT-related (AST and manipulators, CFG/DAG and friends, PIR->Opcode assembler, etc). There is lots of fertile ground here for projects (and we have a lot of ideas and designs already put together for these things).

There are lots of ideas here and I’ve still only scratched the surface. My goal with this post is to show how fertile this ground is, how much available work there is to be had and how many new features we desperately need.

Here’s a basic flow graph of things I’m envisioning as eventual parts of PACT or its close cousins. This will show the kinds of components that PACT may either eventually contain or serve as the common substrate for:

                                      PIR and PASM Code
                                              |
            Optimizers         Analyzers <-+  |  +-> Debugger/Live
            ^ |    ^ |           ^         |  |  |            Interpreter
            | V    | V           |         |  V  |
HLL code -> AST -> Control Flow Graph -> Opcode stream -> Packfile
             ^       |           ^         |  ^  ^           |
             |       |           |         |  |  |           |
            HLL <----+           +---------+  |  +-----------+
       (Decompiled)                           |              |
                                              |              |
                                             PIR Code <------+
                                          (Disassembly)

One day when I have more time I may try to put this together into a real image of some variety. ASCII graphics were good enough for our digital ancestors and they will suffice here for a first draft. As you can see this graph contains several components, any one of which or any small subsection might make for an interesting and extremely rewarding project over the summer. This also ignores the inherent complexity and layered architecture possible in things like the AST transformations and optimizations, register allocation, etc. My point is that even the blocks on the graph above can be further decomposed into a variety of smaller but still interesting projects. If any of this stuff looks interesting to you, please get in touch ASAP so we can start talking and planning. Obviously this is more work than one person will do in one summer, so we want to make sure we are coordinating between all interested parties.

I think that if we start on the left side of this chart and implement the routines for reading from and writing to packfiles first, we can start building layers of additional functionality on top of them. This gives us an ability to break such a big system up into managable parts, to complete some of those parts in small summer-sized chunks, and to be able to use intermediate implementations to solve real problems while we wait for the rest of the system to grow and mature.

If we had multiple students interested in working on PACT in one capacity or another it would be an awesome way to maximize developer resources and help push forward the idea of code reusability. I’m really excited about this whole area and would love it if some students were interested in it too.

Compile Winxed With Winxed

2012-02-18T00:00:00-08:00

You can compile Winxed code with Winxed itself! What’s that you say? The Winxed compiler is bootstrapped and self-hosted, and is written in Winxed and already compiles winxed? Well, that’s all true. Sort of. However there is one small caveat: The Winxed driver program historically has not been able to perform the last step of compilation. The driver compiles winxed code down to PIR, but then uses the spawnw opcode to invoke an instance of Parrot to compile the PIR down to PBC.

I’m pleased to say that this last step is no longer necessary. At least, not in Winxed master (which has not yet been snapshotted into Parrot core).

Here’s a small toy compiler driver that uses Parrot’s PackfileView PMC to compile a .winxed file down into .pbc without spawning any child processes:

function get_winxed_compiler(string pbc_name = "winxedst3.pbc")
{
    var wx_pbc = load_packfile(pbc_name);
    for (var load_sub in wx_pbc.subs_by_tag("load"))
        load_sub();
    return compreg("winxed");
}

function main[main](var args)
{
    var wx_compreg = get_winxed_compiler();
    string winxedcc_name = args.shift();
    string infile_name = args.shift();
    string outfile_name = args.shift();

    string code = (new 'FileHandle').readall(infile_name);
    var pf = wx_compreg.compile(code);
    pf.write_to_file(outfile_name);
}

That’s less than 20 lines of Winxed code to get the Winxed compiler object loaded, to compile the code and to output the PBC to file. We can make this better, of course, by being more flexible in the handling of arguments and printing out basic help and error messages and all that stuff. Eventually we are going to update the winxed executable itself to use this trick instead of spawning the child process. This should, I hope, have a noticably beneficial effect on compiling with Winxed from the commandline. For large, long builds like Rosella has, any speed improvements are appreciated.

One particularly interesting tidbit to notice is the very first line: A new syntax for handling optional parameters. I put a patch for that feature together last week and NotFound decided he could do the same thing but better than I did. So, the latest Winxed compiler (again, not yet snapshotted into Parrot Core) supports this syntax for providing default values to optional arguments. I hope that this feature is included with the 4.1 release next week. Here are some examples of the new feature in action:

// This...
function foo(var bar [optional], int has_bar [opt_flag])
{
    if (!has_bar)
        bar = default_bar_value();
    ...
}

// ...is the same as this
function foo(var bar = default_bar_value())
{
    ...
}

The initializer can be any expression value, including expressions involving previous arguments:

function foo (var bar, var baz = bar.some_method(bar))

This new syntax probably has a few kinks to work out still, but it’s a very cool and very appreciated addition. I’m hoping to use this new syntax to clean up a lot of code in Rosella and hopefully in Jaesop too.

Compiling Templates

2012-02-16T00:00:00-08:00

I had a precious few hours to myself yesterday and was able to do some updating work on Rosella’s Template library. I was able to use the time to implement a feature I had wanted for a while: template compilation. You can now compile a template into winxed code or even compile it all the way down to a Packfile. Actually, that’s sort of a lie. The Winxed compiler .compile() method returns an Eval PMC not a PackfileView PMC. I’m going to submit a patch for that soon, and when I do you’ll be able to save the template to a .pbc file.

Here’s how to use the Template library in the basic, interpreted way:

var engine = new Rosella.Template.Engine();
string output = engine.generate(template, context);

The template is a string with a format that I’ve demonstrated before, and the context is any user-defined data structure that you want to use to populate the variables in the template. I won’t go into detail about those things in this post. Now, after my recent changes and additions, you can compile your template to an executable Sub:

var engine = new Rosella.Template.Engine();
var sub = engine.compile(template);
string output = sub(context);

Or, if you really want to see the generated winxed code, you can get that:

string wx_code = engine.compile_to_winxed(template);

The compilation process does take some time, there’s no way to deny that. There are ways to mitigate that expense, of course. You can compile ahead of time and save the code to a file or even a .pbc and execute that later. There are several strategies if you’re really interested, I won’t go into too much detail here. Once the code is compiled, which can and should be done ahead of time, the time savings during execution are significant. Here’s some benchmarking I’ve done to time a relatively simple template with a ten thousand iteration <$ repeat $> loop:

Interpreted:
0.969569s - %100.000000
0.796563s - %82.156419 (-%17.843581 compared to base)
0.900937s - %92.921402 (-%7.078598 compared to base)

Compiled:
0.365500s - %37.697161 (-%62.302839 compared to base)
0.498571s - %51.421914 (-%48.578086 compared to base)
0.367616s - %37.915399 (-%62.084601 compared to base)

In some cases, pre-compiling the template can take a third as much time as interpreting the template directly. Almost every timing I’ve seen is around 50% or better of the interpreted time.

This is a very new feature and I haven’t added it to the test suite yet. Expect rough edges as I play with it and optimize it. If you’re doing a lot of templating with Rosella, this feature could help save some time for you and plus it was a really fun thing to work on.

GSOC 2012 Is Starting

2012-02-15T00:00:00-08:00

You might not see it, but I’m starting to get very excited. Discussions about the Google Summer of Code program is starting up for the 2012 summer. Projects in years past have lead to some awesome developments in Parrot, either directly or indirectly, and 2012 could easily deliver more.

For prospective students, here are some blog posts I’ve written in years past about the process, and what you need to do to get started:

If you’re interested in participating in GSoC this year, with Parrot or any other organization, I suggest you read those two posts. They’re important. Many students in school or freshly graduated may know how to code but might not know much about some of the tangential topics: source control (git, in the case of Parrot), documentation, unit testing, refactoring, etc. Now would be a great time to start brushing up on all those topics, so you don’t waste time during the summer getting your tools in place.

As usual I will try to post some ideas for projects here on this blog. If you are an eligible student and you are interested in one or more of these ideas please get in touch with me or other interested Parrot developers. If you have other ideas that I don’t mention, that’s cool too. Get in touch anyway and we can start talking about those ideas. The important thing is to talk to us. Seriously, it’s important.

Here are a few ideas off the top of my head that might be worth some more investigation. I might write additional posts about these ideas if people want more information about them:

Opcode disassembler. We have a growing set of tools for working with bytecode from running Parrot code, but we don’t have all the pieces that we would need to make a fully self-hosted disassembler. What we still need are tools to read out the raw bytecode and convert into a sequence of Opcode PMC representations, then a driver program to turn that output into readable (and hopefully round-trim compilable) disassembly output.
PACT An alternate to Parrot’s venerable PCT library, called PACT, has been in the planning stages for many months. What we need is somebody with the time and motivation to start putting those ideas into practice. A toolkit library that works with syntax trees and outputs working bytecode libraries would be quite an awesome thing to have, and would help us push the state-of-the-art for Parrot compilers up a few notches. Intended to be a layered system, the successful student could implement only a few of the necessary layers.
Jaesop Stage 1 Jaesop is a bootstrapped JavaScript compiler. Right now there is a stage 0 compiler which uses node.js to compile JS into Winxed. We need a stage 1 compiler, written in JavaScript, that can run on stage 0 and compile itself. It’s an interesting, mind-bendy kind of project. If you know compilers and you like JavaScript, this might be the project for you.
Anything Python-Related Parrot wants and needs more Python love. We’ve had a few attempts at making a working Python compiler before on Parrot. Working on any of those, starting a new attempt, or working on other ways to integrate Python and Parrot would all be greeted with some eagerness.
New Object Model Parrot needs a new object model. Right now we have 6model waiting in the environs, but we haven’t integrated it yet. There is some question about whether we want to copy+paste merge 6model as it is, or if we want to try and make a more custom adaptation of it from the ground up. Proposals to do either, or anything closely related, would be very interesting.
LAPACK Bindings for PLA I’ve wanted PLA to get LAPACK bindings for a long time now, and I’ve never had the time to do it myself. I’ve never really even had the time to design what such a thing would look like. I suspect we can do the lion’s share through raw NCI. Tools to solve matrices for eigenvalues and eigenvectors and common transformations and decompositions would be very interesting indeed.
New PackFile Loader I’ve complained about the unnecessarily magic behavior of our packfile loader before. A new, re-written packfile loader would not automatically assemble Namespace or MultiSub PMCs at load time. Down this path lay the possibility for significant performance improvements and complexity reductions in some of our oldest and least-friendly code. It would require serious changes to IMCC, PIR, and higher-level compilers like Winxed. The new NQP already does the right kind of thing and would serve as a great example to follow.
Anything Thread or Asynchrony Related Parrot has Green Threads on Unixy platforms. Extending proper support to Windows and elsewhere would be awesome (again, something I want to do but have not had time or a Windows machine for testing). Asynchronous IO using new threading primitives and anything else that you could think to build with the new threading system would be awesome. Adding in types that would help the effort such as lock-free arrays and hashes would be nice assets. Adding in support for concurrency primitives like locks, mutexes and critical sections would also be cool (and implementing those in terms of green thread primitives would be even cooler).
Divided VTABLE Parrot’s VTABLE is a huge monolithic structure, and there have been many suggestions recently that we break it down smaller chunks based on roles. The “Number” role would contain arithmetic vtables, while the “invokable” role would have VTABLE_invoke and friends. GCable role, Array role, Hash role, Metaobjecet role, etc. These are all things that we could use and would decrease overall memory footprint and increase flexibility in the system. Bonus points if this work was integrated closely with 6model and other proposed changes in our PMC subsystem.

These are just a few of the ideas I have on the top of my head this morning. Some, I’m sure, are too big. Others are too small. But in each is the kernel of a good idea and if anybody reading this is interested we should start the conversation now to get these vague ideas focused into compelling proposals.

Rosella Reflect

2012-02-01T00:00:00-08:00

Earlier this month I released the new Reflect library in Rosella. I hadn’t mentioned it before, but the library is sufficiently interesting that I want to talk about it at least a little bit. The Reflect library adds in tools for reflection. Somewhere, an etymologist weeps a tear of joy for the creative naming, I’m sure.

The Reflect library adds in wrappers for classes and packfiles that makes them easier to work with for many operations. First, I’d like to use a couple code examples to show the most basic API:

// Get the Sub PMC that we're currently executing
var s = Rosella.Reflect.get_current_sub();

// Get the current context
var c = Rosella.Reflect.get_current_context();

// Get the current object, if the current Sub is a method call
var obj = Rosella.Reflect.get_current_object();

// Get the class of the current object, if the current Sub is a method call
var c = Rosella.Reflect.get_current_class();

// Get a Module object for the packfile where the current Sub is defined
var m = Rosella.Reflect.get_current_module();

// Get a reflection wrapper object for the given Parrot Class PMC
var r = Rosella.Reflect.get_class_reflector(myClass);

// Get a Module object for the packfile in "foo/bar.pbc", loading it as
// necessary
var m = Rosella.Reflect.Module.load("foo/bar.pbc");

That’s the basic API that the library provides to get basic information about where execution is happening at the moment when the call is made. Once you have a Module object or a Class reflector object, you can do all sorts of cool things that used to be a pain in the butt to do manually:

var m = Rosella.Reflect.get_current_module();
say(m);          // Stringified, produces the name and version of the packfile
m.load();        // Execute all :tag("load") and :load functions
n.init();        // Execute all :tag("init") and :init functions
say(m.version(); // Get the version string of the packfile "X.Y.Z"
say(m.path());   // The on-disk path to the current packfile

// Get a hash of all Class PMCs defined at compile-time (using the :method
// flag on Subs) defined in the packfile, keyed by name
var c = m.classes();

// Get a list of all non-:anon functions defined in the packfile
var f = m.functions();

// Get a hash of all non-:anon functions in the packfile, organized into
// a hash keyed by namespace
var f = m.functions_by_ns();

// Get a hash of all NameSpace PMCs defined at compile-time
var ns = m.namespaces();

Once you have Class and NameSpace PMCs from the packfile, you can start to do all sorts of cool operations and analyses on them. Once you have a Class reflector object, you can do even more stuff with that:

var c = Rosella.Reflect.get_current_class();

// Create a new object of the current type
var o = c.new();

// Say the name of the class
say(c.name());

// Attributes are encapsulated as objects. You can get an Attribute
// reflector and use it later to get and set values on objects of this
// type or subclasses
var attr = c.get_attr("foo");
var value = attr.get_value(o);
attr.set_value(o, "whatever");

// Methods are also encapsulated. You can get a method reflector now and
// invoke it on objects later (including objects of different types)
var method = c.get_method("bar");
var result = method.invoke(o);
var meths = c.get_all_methods();

// Basic capability detection. Determine if objects are members of the
// class or their subsets, and determine if the class can perform certain
// methods
if (c.isa(o)) { ... }
if (c.can("bar")) { ... }

I hope the code examples make up for the terse explanations.

The Reflect library is currently focused on reading data from things like Classes and Packfiles, not on creating these things like the new PACT project is supposed to do. I want to extend this library even further with abilities to further introspect functions down to the opcode level and then…Well, when we have a stream of opcodes to analyze the possibilities are endless. I’d also like the ability to get better introspection of the interpreter and global state, though a cleaner interface than the hodge-podge of interpinfo opcodes and ParrotInterpreter PMC methods and whatever else we currently use.

As always, using the interface Rosella provides will help to insulate you from changes to the various underlying mechanisms when we finally get around to cleaning them up and making them sane. There isn’t a huge push to make such cleanups on a large scale yet, but I wouldn’t be surprised if a few things started getting prettified in the coming months at a slow pace.

I’ve already started using the new library in several of the Rosella utility programs such as those that create a winxed header file or a test suite from an existing packfile. In all cases the updated programs are both cleaner and have more functionality than the previous incarnations. Expect to see this library improve and grow in 2012 and beyond, and expect to see it work closely with PACT, once that project gets moving forward.

Rosella Test Updates and Upgrades

2012-01-30T00:00:00-08:00

The first half of this month was dominated with some epic illnesses between my family members and myself, family functions and home maintenance. What little spare time I’ve had otherwise has been devoted to writing code, as opposed to writing blog posts about writing code. The blog has suffered.

The past couple days I’ve been working on Rosella’s Test library. It’s an old but good library and is, as far as I am aware, the most full-featured and easy to use testing tool in the Parrot ecosystem. With some of these most recent changes the library is better still.

Matchers

Kakapo had a series of Matcher routines and objects as part of it’s testing facilities, and for a long time I’ve been wanting to port some of those ideas over to Rosella. As of last week, I have a simple version of them. Matchers allow you to ask the question “is this thing like that thing”, with a custom set of rules. Let me give a basic example.

Previously in Rosella if you were unit testing a method which returned an array and you wanted to check that the array contained the right values, you would have to do something like this:

var result = obj.my_method();
var expected = [1, 2, 3, 4, 5];
self.assert.is_true(result != null);
self.assert.equal(elements(result), elements(expected));
for (int i = 0; i < elements(expected); i++) {
    self.assert.equal(result[i], expected[i]);
}

That’s a lot of work, although you can cut it down a little bit if you know for certain that the array isn’t null. With the new matcher functionality, you pass in two arrays and the Test library will match them for you:

var result = obj.my_method();
self.assert.is_match(result, [1, 2, 3, 4, 5]);

Internally the Test library maintains a list of matchers by name. When you pass in two objects, it loops over the list looking for a matcher that can handle the pair. In this case, one of the default matchers the library provides looks for objects which implement the "array" role, and then does element-wise matching on them. Another similar matcher does the same for hash-like objects that implement the "hash" role.

Another matcher checks to see if one or both of the two objects are strings, and then does a string comparison on them (converting the other, if it isn’t a string already) and the last of the default matchers is used to compare floating point values with a certain error tolerance.

Since matchers are stored in a hash, you can access them by name, delete them, add your own, and replace existing ones if you want new matching semantics. This is especially useful in something like Parrot-Linear-Algebra, where I can say

$!assert.is_match($matrix_a, $matrix_b);

…and the library will automatically compare the dimensions of the matrices and the contents of them without needing nested loops and other distractions.

Nested TAP

Another item I’ve had on my wishlist for a while now has been nested TAP. I’ve always wanted to support it, and in theory at least the system was designed modularly enough to generate it without too much hassle. Last weekend I put on the finishing touches and now am proud to say that Rosella.Test can run nested tests and generate nested TAP. At the moment the interface to use it is a little ugly (I’m actively soliciting feedback!), but the capabilities are all there:

function my_test_method()
{
    self.status.suite().subtest(class MySubtestClass);
}

function my_vector_test_method()
{
    self.status.suite().subtest_vector(
        function(var a, var b) { ... },
        [1, 2, 3, 4, 5]
    );
}

function my_list_test_method()
{
    self.status.suite().subtest_list(
        function(var test) { ... },
        function(var test) { ... },
        function(var test) { ... }
    );
}

Here’s an example of output from a similar test file in the Rosella suite:

1..4
    1..2
    ok 1 - test_1A
    ok 2 - test_1B
    # You passed all 2 subtests
ok 1 - test_1
    1..3
    ok 1 - test 1
    ok 2 - test 2
    ok 3 - test 3
    # You passed all 3 subtests
ok 2 - test_2
    1..5
    ok 1 - test 1
    ok 2 - test 2
    ok 3 - test 3
    ok 4 - test 4
    ok 5 - test 5
    # You passed all 5 subtests
ok 3 - test_3
    1..1
    not ok 1 - test 1
    # failure
    # Called from 'fail' (rosella/test.winxed : 481)
    # Called from '' (t/winxed_test/Nested.t : 40)
    # Called from '' (rosella/test.winxed : 1589)
    # Looks like you failed 1 of 1 subtests run
ok 4 - test_4
# You passed all 4 tests

The fourth test expects a failure in the subtest, which is why it says it passes when there is clearly some failure diagnostics appearing. This brings me to my next point…

Cleaner Diagnostics

Before when you ran a test and had a failure, you might see something like this:

not ok 2 - ooopsie_doopsies
# objects not equal '0' != '1'
# Called from 'throw' (rosella/test.winxed : 851)
# Called from 'internal_fail' (rosella/test.winxed : 1853)
# Called from 'fail' (rosella/test.winxed : 481)
# Called from 'equal' (rosella/test.winxed : 577)
# Called from 'ooopsie_doopsies' (t/core/Error.t : 18)
# Called from 'execute_test' (rosella/test.winxed : 1455)
# Called from '__run_test' (rosella/test.winxed : 1483)
# Called from 'run' (rosella/test.winxed : 1392)
# Called from 'test' (rosella/test.winxed : 1747)
# Called from '_block1000' (t/core/Error.t : 7)
# Called from '_block1177' ( : 158)
# Called from 'eval' ( : 151)
# Called from 'evalfiles' ( : 0)
# Called from 'command_line' ( : 0)
# Called from 'main' ( : 1)
# Called from '(entry)' ( : 0)

That’s a huge mess, and it’s a mess from two sides. At the top of the backtrace, you see all sorts of Rosella internal functions involved in the assertion and error handling. The bottom half of the backtrace is devoted to entry-way stuff. In this case there’s NQP-related entry code and then the Rosella entry code. You, as the test writer, don’t care about any of that. All you care about is the code you wrote and where its broken. If you have to dig through a huge backtrace to figure out where the error is, that’s a big waste of time and effort.

Now, Rosella filters that crap out for you. Here’s the same exact failure with the new backtrace reporting:

not ok 2 - ooopsie_doopsies
# objects not equal '0' != '1'
# Called from 'equal' (rosella/test.winxed : 577)
# Called from 'ooopsie_doopsies' (t/core/Error.t : 18)

Here you see the important parts of the backtrace only: The parts you wrote and the one assertion that failed. You don’t see the internal garbage, you don’t see the entry-way garbage, because those things aren’t of interest to the test writer.

Parrot-Linear-Algebra

Another small project I did a few days ago was getting the PLA test suite working again. It’s a testament to how stable both BLAS and Parrot’s extending interfaces are. Recent Rosella refactors removed some of the special-purpose features that existed only for PLA and for no other reason (and which were a pain in the butt to maintain). I fixed up the test suite and PLA builds and runs perfectly now.

That’s what I’ve been up to this month. I’m mostly done with my cleanups to the Test library now, barring a few more interface improvements I want to make. After that I’ve got a few projects to tackle inside libparrot itself. I’ll write more about those topics when I have something to say.

Parrot 4.0.0 "Hyperstasis" Released!

2012-01-17T00:00:00-08:00

At one extreme, it is possible to approach the subject on a high mathematical epsilon-delta level, which generally results in many undergraduate students not knowing what’s going on. At the other extreme, it is possible to wave away all the subtleties until neither the student nor the teacher knows what’s going on.

-Stanley J. Farlow, Preface to Partial Differential Equations for Scientists and Engineers

On behalf of the Parrot team, I’m proud to announce Parrot 4.0.0, also known as “Hyperstasis”. Parrot is a virtual machine aimed at running all dynamic languages.

Parrot 4.0.0 is available on Parrot’s FTP site, or by following the download instructions at http://parrot.org/download. For those who would like to develop on Parrot, or help develop Parrot itself, we recommend using Git to retrieve the source code to get the latest and best Parrot code.

Parrot 4.0.0 News:
    - Core
        + Several cleanups to the interp subsystem API
        + Cleanups and documentation additions for green threads and timers
        + Iterator PMC and family now implement the "iterator" role
        + A bug in Parrot_ext_try was fixed where it was not popping a context correctly
    - Documentation
        + Docs for all versions of Parrot ever released are now available
          at http://parrot.github.com
    - Tests
        + Timer PMC tests were converted from PASM to PIR

The SHA256 message digests for the downloadable tarballs are:

a1e0bc3de509b247b2cea4863cc202cdceeaa329729416115d3c20a162a0dd88 parrot-4.0.0.tar.bz2
a63d45f50f7dd8ba76395cd2af14108412398ac24b8d827db369221cdb37fada parrot-4.0.0.tar.gz

Many thanks to all our contributors for making this possible, and our sponsors for supporting this project. Our next scheduled release is 21 February 2012.

Enjoy!

Rosella Date

2012-01-15T00:00:00-08:00

The Advent calendar idea ended up terribly. Let us never speak of it again. The holiday season was particularly busy this year with a higher-than-average load of family- friend- and work-related activities. Combine that with an unexpected (and absolutely unappreciated) invasion of a particularly unpleasant and long-lasting stomach bug, and you have something of a perfect storm. I won’t go into the details any further on this particular blog, but I will mention in passing that I’ve become extremely suspicious about the basic hygene habits of the other little turdbags that my son goes to daycare with.

To start 2012 off, and to get back into the swing of coding-for-pleasure, yesterday I went through and got the new Rosella Date library ready for prime time. The library is imperfect and incomplete, but those are things that can be fixed using the patented Andrew Style (tm) of meandering iterative development. For now, however, the library does seem to work well enough for basic tasks and it’s already proven to be a valuable tool for some tasks. Here I’m going to introduce the new library and talk about some of the things I changed in Rosella to support it and some of the ways I’ve already integrated it into the rest of the collection.

String Formatters

When you use sprintf to print out an integer (for instance) you can use some basic modifiers to control how the value is printed. %d prints out the basic version, but you can specify field width, padding, alignment and a few other details by using a format specifier like %-02d. Or, if you want to print the same value out as hex instead of base-10, you can use %x or %X, and use modifiers with those as well.

The problem with something more complex like a date/time representation is that sprintf is not able to handle them natively and some kind of mapping is needed.

Rosella has added a new StringFormatter type to the Core library to help with this problem. A StringFormatter is a type that takes an object and a format string and outputs a new string according to the two. The default StringFormatter uses sprintf internally, but other formatters may use different mechanisms and syntaxes.

var sf = new Rosella.StringFormatter();
string s = sf.format(my_obj, "This is %s");

As an aside, this does demonstrate the fact that our get_string vtable really is insufficient for a lot of purposes. I suggest that get_string should take a parameter for a format string. We could easily incorporate that into the default sprintf implementation like this:

$S0 = sprintf "%{foobar}p", $P0

In that invocation, the get_string vtable on the first parameter would be called with the string argument “foobar”. A normal invocation like this:

$S0 = sprintf "%p", $P0

…would call get_string with a null format and the behavior could be whatever the default string representation for that type is. By overriding get_string in your types to take different formats or to respond to common formats differently, you could have pretty detailed control over stringification at all levels.

Date Library

The new Date library provides a Date type for working with dates and times. You can create one in three ways:

var d = new Rosella.Date(t);
var d = new Rosella.Date(year, month, day);
var d = new Rosella.Date(year, month, day, hour, minute, second);

The first uses a system-specific time integer value to represent a time since the system epoch. This is the kind of value you get from the time opcode, or from stat calls on filesystem objects, for instance. In the third option, hours are specified on a 24-hour clock.

There are also a few functions you can call to get particular dates:

var d = Rosella.Date.now();
var n = Rosella.Date.min();
var x = Rosella.Date.max();

The first value should be the current date/time (as gotten from Parrot’s time opcode). The second value is a minimum date object which corresponds to the minimum possible date value to display and is guaranteed to be evaluated as less than any other date. The third one similarly is a maximum date value which corresponds to the maximum possible date and is guaranteed to always be compared greater than any other date.

Dates are immutable. Once you create them, they cannot be modified in-place. Instead, several operations are provided to perform operations and return new Date objects with the results. Here are some examples:

var d = Rosella.Date.now();
var e = d.add_seconds(20);
e = d.add_hours(15);
e = d.add_months(24);
e = d.add_years(1000);

In each case, the variable e becomes a new date value and d is left unmodified. Two other methods let you pick out just the date components or just the time components:

var n = Rosella.Date.now();
var d = n.date();
var t = n.time();

Finally, you can use a new DateFormatter type to format the date value into a proper stringification:

var d = Rosella.Date.now();
string s = d.format_string("yyyy - MM - dd and the time is: hh:mm:ss");

At the moment the formatter is dirt simple and only supports a few formatting codes such as yyyy, MM, dd, hh, mm, and ss. I will be making it much more useful in the coming days, if I can settle on an algorithm which doesn’t completely stink.

FileSystem

The FileSystem library now returns Date objects from certain file-time methods:

var f = new Rosella.FileSystem.File("t/harness");
var ct = f.change_time();
var at = f.access_time();
var mt = f.modify_time();

In each case, the value returned from the stat call on the file is used to create a new Date object.

Query

Dates are completely comparible, so you can sort them and work with them like other values in an iterable:

var a = [
    Rosella.Date.now(),
    Rosella.Date.max(),
    Rosella.Date.min()
];
Rosella.Query.iterable(a)
    .sort()
    .foreach(function(d) { say(d); });

This toy example sorts the three Date values, with the min first, then now, then max, and prints them out to the console. The stringified versions of the special min/max dates aren’t particularly instructive, but they do get the point across.

So that’s the new Date library. It does need more functionality and definitely needs more tests, but it is working pretty well for me now and has already proven itself useful for a number of purposes. Expect to see more of it in 2012.

Advent 9 - Jaesop

2011-12-29T00:00:00-08:00

Over the summer of 2011 we had a GSOC project that was trying to build a JavaScript compiler for Parrot. That project made some interesting progress but ultimately I think the approach ended up being flawed. That project attempted to convert JavaScript into PIR code, which is a pretty big gap in terms of both syntax and semantics.

Towards the end of the summer, after it was too late to go back and start from the beginning, I had a different idea: What if we tried to generate Winxed code instead of PIR code? Winxed would handle things like register allocation, and the Winxed syntax is so similar in some places that the translation could almost be verbatim copying. I put those ideas together with node.js and the cafe compiler and Jaesop was born.

Jaesop intends to be a full JavaScript on Parrot compiler. The plan is to write as much of it in JavaScript itself as possible, and bootstrap upwards. The first component, “stage 0” uses node.js to run a converter that compiles Javascript code into winxed. That’s the only part we have working right now, but what we do have is working pretty well.

In 2012 I want to get the next component, “stage 1” working. Stage 1 will use the stage 0 compiler to compile itself. It will be written in JavaScript (translated to Winxed en passant) and will be running entirely on Parrot. My goal for stage 1 is to be generating bytecode directly instead of generating either Winxed or PIR as an intermediary. That’s going to require some serious help from a compiler toolkit of some variety and I have very high hopes for using PACT for this purpose when it’s ready.

Stage 0 works very well and passes a small but interesting test suite I’ve set up for it. It does not self-compile, but there are only a few relatively small things standing in the way. For instance, regular expression support and pcre bindings are not complete yet, and the grammar currently requires semicolons at the end of statements but the code generated from Jison does not always contain semicolons. I also haven’t built in the require() function, which is used by the stage 0 compiler to load in the various code files. These are all small issues and with a small amount of work I expect stage 0 to be able to self-host. Whether I want to expend that effort or focus attention on stage 1 instead is a different question entirely.

In 2012, once PACT has matured and 6model has been integrated into Parrot I expect to get back to work aggressively on Jaesop. I’m looking for helpers too, in case anybody reading this wants to get involved in the development of a new JavaScript compiler. I’ll put out more of a call to arms when the prerequisites are in place and we’re ready to get the wheels turning on stage 1. I estimate that by spring or early summer we should be ready to get started on the next phase of Jaesop development.

Advent 8 - Rosella

2011-12-28T00:00:00-08:00

I had already written a post about Rosella for my woefully inadequate advent calendar, but it got lost to the sands of time (I think it’s on my other computer, committed but not pushed). Considering that I should have been on schedule to be on post #21 or #22 by now but am instead only on #8, I can’t really afford to not write a post when I have the ideas inside me. This post is also going to be about Rosella, and if I ever find the first one I may post that as well. I clearly haven’t had enough spare writing time this month to be even remotely picky about what I post or when.

I’m thinking I might like to try this little experiment again later in the year, when I’ve had more time to prepare and have fewer other things in real life demanding my undivided attention. Maybe we’ll shoot for some kind of christmas-in-July thing. Until then, I’ll happily conceed the “best Advent Calendar” crown back to moritz and the Perl peoples.

Rosella is a library project I started as a way to let me work on lots of different project ideas I had without having to duplicate build and test infrastructure. The goals from the project were solidified pretty early in the project lifecycle and have remained unchanged ever since: To provide solutions to common developer problems, in pure Parrot, in ways that are portable, reusable, and configurable. I’ve already talked about three of the oldest and most important libraries in the set: Test, Harness and MockObject on Day 5 of this Advent calendar. My other written-but-not-published post talked about three additional libraries as well: Query, FileSystem and Proxy. To avoid much duplicate effort in case I do ever find that post again, I’ll write about a few different libraries: Container, Random and Template.

The Container library is one of the oldest libraries in Rosella. It is an implementation of a dependency injection container for Parrot, and originally lived in it’s own Parrot-Container repository on github. My other library, for unit testing was also a separate repo. One day I was thinking about how I might like to use the Parrot-Container project to manage dependency injection in the Harness library, and trying to figure out how I wanted to manage the software dependencies. I wanted to use the Container library in the implementation of the unit test Harness, but I wanted to use the Harness and Test libraries to implement the test suite for the Container library repository. Combine that with a bunch of other ideas for new libraries I had brewing in the back of my mind and Rosella was quickly born.

The Container library is not quite as easy to use as a counter-part in the .NET or JVM environments because things are not always strongly typed, especially not at compile time or early in runtime when the container is initializing but the various bits of initialization logic in the program have not yet run. The Rakudo folks with their fancy object system and notion of gradual typing might have a different idea, but in terms of pure-parrot code, as Parrot exists right now, we can’t query a Sub PMC and ask it what types of parameters it expects to receive. For people who might be familiar with other dependency injection (or “inversion of control”) systems like Unity or Ninject, the syntax for setting up Rosella’s container type might seem a little verbose. It’s plenty powerful (and I have plenty of plans to upgrade things as Parrot’s threading support and object system improve in 2012 and beyond), but it is verbose:

var container = new Rosella.Container();
container
    .register(class Foo)
    .register(class Bar,
        new Rosella.Container.Resolver.TypeConstructor(class Bar, "Bar", 1, 2, 3)
        new Rosella.Container.LifetimeManager.Permanent()
    )
    .register(class Baz,
        new Rosella.Container.Resolver.TypeConstructor(class Baz, "BUILD"
            new Rosella.Container.Argument.Resolve(class Foo),
            new Rosella.Container.Argument.Resolve(class Bar)
        )
        new Rosella.Container.Option.Attribute("my_attr", "value"),
        new Rosella.Container.LifetimeManager.Thread()
    )
    .alias(class Baz, "Baz");
var b = container.resolve(class Bar);

The part that is significantly more verbose here than you would expect in Unity for example is the part where I have to specify the types of arguments to pass to the constructor. In a platform like .NET, the container can read the type metadata from the constructor object itself and make that decision. In Parrot, since we currently don’t make that kind of information available, you must specify. In Rosella’s offering you do have many of the features that you would expect from one of the more well-known containers: the ability to specify registration lifetimes, the ability to initialize objects by making method calls and setting attribute values after construction, the ability to specify global singleton instances, etc. It is a pretty cool tool, but I haven’t yet made as much use of it as I would have liked. In 2012 I expect to start integrating the container library into some of the other libraries, such as Harness, CommandLine and Template, to make user configuration easier and more straight-forward.

The Random library is a relative newcomer to Rosella, but is already demonstrating its usefulness in a variety of ways. The Random library was born from a few ideas I had turned into GCI tasks. An intrepid young student wrote an implementation of the Mersenne Twister algorithm for me in Winxed, and I set about writing up several other components such as a Box-Muller transform, a UUID generator, a Fisher-Yates array shuffler and a few other things. Now, you can do cool things with random numbers:

var prng = Rosella.Random.default_uniform_random()
int r = prng.get_int();

var uuid = Rosella.Random.UUID.new_uuid();
string id = string(uuid);

var a = [1, 2, 3, 4, 5, 6, 7, 8];
Rosella.Random.shuffle_array(a);

Implementations of things aren’t all perfect and there are a handful of bugs to be worked out (especially bugs resulting from arithmetic differences between 32-bit and 64-bit machines) but it is already very usable and reliable for the most part. If you need a random number generator, or a UUID generator, or other random-related things, this is a very nice tool to have available.

The Template library is something I wanted to write for a long time, but had to wait until all the prerequisites were in place first. Template is a text-templating engine library. You create an Engine object and feed it two basic pieces of information: The string template to use and the data context object to fill in the blanks. Presto-chango, out comes the complete text.

The Template engine can execute basic logical operations depending on the values in the data context, it can compile and execute inline snippets of code, it can load and assemble pieces of template from separate files, and do several other things that you would expect a templating library to do. I could write many examples of templates and their use, but I’ll stick with only one small example here for brevity:

Template:

Let's learn about <%
    var bar = context["animals"];
    return elements(bar);
%> new animals!
<$ for sound in animals $>
    The <# __KEY__ #> says <# sound #>
<$ endfor $>

Code:

string template = ...;
var context = {
    "animals" : {
        "Cow" : "Moo",
        "Bear" : "Growl!",
        "Cat" : "I CAN HAZ CHEESEBURGER"
    }
};
var engine = new Rosella.Template.Engine();
string output = engine.generate(template, context);

And the end result would be something like this (minus hash ordering concerns):

Let's learn about 3 new animals!
The Cow says Moo
The Bear says Growl!
The Cat says I CAN HAZ CHEESEBURGER

Rosella eats plenty of it’s own dogfood here. Several test files in the Rosella test suite and a few boiler-plate source code files are generated using the Rosella Template library. I’m planning to start using it to generate skeleton files for Rosella documentation as well. In the future, I may also use it to help with generating content for this very blog!

In 2012 Rosella is going to be adding a bunch of cool new stuff. Considering how far Rosella has come by now and the fact that it’s less than a year old, it’s kind of hard to speculate where we will be next year around this time. I’m planning to add a new Date/Time library within the next few weeks. I’m also planning a new reflection/packfile library, a benchmarking library, a code assertions library, and rewrites to several of the existing libraries to add new functionality and optimize performance in some key ways. Those are only my plans for the first two or three months of 2012!

Advent 7 - Google GCI and GSoC

2011-12-22T00:00:00-08:00

When you want to find something on the internet, Google is a pretty popular tool to use. When you want to get some code written, Google turns out to also be a pretty good idea.

Google has been doing it’s Summer Of Code (GSOC) program for several years now and every summer it’s a smashing success. Last year they started up with a new program called the Google Code In (GCI). That program, while wildly different from GSOC, is also incredibly awesome. Every year Parrot receives a huge amount of code from these programs, and we would not be where we are today without them.

The Summer of Code program is very straight forward: Every year we receive applications from college age and some highschool-aged students for projects. Over the course of the summer the accepted applicants work diligently and at the end, if they are successful, they get paid. Also there are cool T-shirts. The GCI program is aimed at younger students, mostly those in high school. Instead of one large project spanning several months, the GCI students work on a large number of bite-sized tasks from many organizations. Each task is worth points, and the students who have the most points at the end of the program receive a prize. Also, I think there are monetary rewards for completing a certain number of tasks.

Last year we had a huge number of tasks completed by several GCI students. We had many bits of code written or re-written, some new documentation written, and many many tests added. Our project-wide test coverage metrics increased dramatically, since we had several tasks devoted to test coverage and several talented young coders who were chasing them down. Once you figure out how to write tests, subsequent tasks go much more quickly. We had some students who, after getting the hang of things, were able to complete several tasks per day at the end.

I heard one or two accusations that Parrot was inflating point values by offering tasks that could be completed so quickly. I pointed out that many tasks were considered very hard by students at the beginning, but as their familiarity of the code increased the relative difficulty decreased. It wasn’t a problem of Parrot’s tasks being too easy, but the students learning and improving much faster than we could keep up with. By the end of the program we were learning that the difficulty really needed to ramp up over the course of GCI, because students would be capable of much more towards the end than they would be at the beginning.

This year things are going a little bit more slowly. We have fewer of the “increase test coverage” tasks, because our test coverage is still so high from last year in the core VM. I’ve scoured several potential sources of tasks including searching for TODO notes in the Parrot source code, scanning through our myriad of trac tickets, digging into ecosystem projects (Plumage and Rosella especially) and begging other contributors for task ideas. Already we’ve seen some very useful bits of code contributed to the project, including new features and impressive cleanups and refactorings of old crufty code.

GCI this year is essentially closed off. There were two opportunities to publish new tasks and those have both passed. Students are slowly working their way through the remaining tasks in the queue until the program ends in a few weeks. However, next year I’m sure we’re going to see both another GSOC and another round of GCI (At least, I hope we see them, since these are both so awesome!).

Despite being months away we’re already starting to look for project ideas and potential applicants for GSOC. Getting good ideas picked early allows us time to refine them, and getting familiar with potential applications now helps us to learn more about them and be more comfortable with them when time comes to make final selections. GCI doesn’t require so much preparatory work, but it would be nice if we went into next year with a larger pile of varied tasks for students to work on, instead of needing to scramble to create tasks in sufficient numbers at the last minute.

GSOC and GCI have both been amazingly successful programs in the past and I am hoping that trend continues into the future. Parrot has benefited from both programs to an amazing degree, and with a little bit of luck and a lot of planning we can keep the train moving into 2012 and beyond.

If you’re a highschool or college-aged coder, or know somebody who is, and would like to talk about getting involved with either program in 2012 (especially if you would like to work with Parrot specifically!) please let me know and I can make sure you get pointed in the right direction.

Advent 6 - Embedding

2011-12-17T00:00:00-08:00

In late 2010 and early 2011 we spent a good amount of effort building a new embedding API for Parrot. I would like to say that the new API replaced an older, inferior API but that’s not really the case. We didn’t really have an old embedding API per se. We had a mismash of functions in a file called embed.c, but they hardly represented a consistent API, much less a complete set of things that an embedder would need. If anything the old embedding API was the entirety of all publicly exported functions from libparrot combined with a handful of utility functions that embedders in the past also needed.

In short, it was a mess. By early 2011 we had a much nicer API around to play with. Now that 2011 is almost over, the new API is considered to be extremely stable and robust.

Last December I started a project called ParrotSharp which embeds a Parrot Interpreter into the .NET CLI with C#. I haven’t shown that project too much love in recent months, but as of today it’s still building and seems to run correctly (although my IDE is telling me it can’t find NUnit on my system, so it won’t run my tests). That has to tell you something, when code I wrote months ago with the embedding API still works correctly even though so many things have changed in Parrot since then.

Parrot’s embedding API is a little bit verbose but very easy and straight forward to use. Also, all API functions return a true/false status value, so calls can easily be chained together. Here is an example of the embedding API in action:

int main(int argc, char** argv) {
    Parrot_PMC interp, bytecodepmc, args;
    Parrot_Init_Args *initargs;
    Parrot_String filename;

    GET_INIT_STRUCT(initargs);

    if (!(
        Parrot_api_make_interpreter(NULL, 0, initargs, &interp) &&
        Parrot_api_set_executable_name(interp, argv[0]) &&
        Parrot_api_pmc_wrap_string_array(interp, argc, argv, &args) &&
        Parrot_api_string_import(interp, "foo.pbc", &filename) &&
        Parrot_api_load_bytecode_file(interp, filename, &bytecodepmc) &&
        Parrot_api_run_bytecode(interp, bytecodepmc, args)
    )) {
        Parrot_String errmsg, backtrace;
        Parrot_Int exit_code, is_error;
        Parrot_PMC exception;

        Parrot_api_get_result(interp, &is_error, &exception, &exit_code, &errmsg);
        if (is_error) {
            Parrot_api_get_exception_backtrace(interp, exception, &backtrace);
            // Print out exception information to the console, or whatever
        }
    }

    Parrot_api_destroy_interpreter(interp);
    exit(exit_code);
 }

This is, essentially, a simple program to execute a bytecode file. However, it does show some of the basics of the embedding API. Every function returns a true/false, pass/fail status bit. All data types passed around are properly wrapped Parrot_PMC or Parrot_String types and it almost never uses any other raw pointer types. Also since we’re using PMC and STRING types, Parrot’s GC manages all the memory for you and you don’t need to be freeing things or cleaning things up (except for the interpreter itself).

This example above only shows a handful of API functions, but there are several dozen of them in the API and more can be easily added. We have API routines for performing a variety of actions on Strings and PMCs. We have API routines for loading, executing and writing bytecode. The API has decent defaults so you can just get an interpreter up and running quickly if you want, but it also have a variety of routines for tweaking and configuring the interpreter too. And, like I said (and I’ll say it a million times more if I have to) we can always add new methods to the embedding API if there is a need.

We have at least the basics of a C# wrapper projects in the wings, and I’ve been planning a proper C++ wrapper for a while too but I haven’t gotten around to it yet. That would make an excellent, smallish project for an intrepid newcomer to work on, especially one that knows C++. I like to think it should be easy to embed Parrot as a plugin for things like text editors or other pluggable unixy programs, but I haven’t taken the time to really dig into any of them yet. This might make another great project for an eager new parrot hacker.

Advent 5 - Testing

2011-12-16T00:00:00-08:00

Ever since I started working with Parrot I’ve noticed something interesting about the community: They were very interested in unit testing. Parrot alone as a suite with over ten thousand tests (and I still feel like there are some portions of the VM that are heavily under-tested). When I first joined Parrot I had never written a unit test nor did I really understand the value of testing. I was a newbie fresh out of school where such practical aspects as that were never covered. Despite my unfamiliarity with testing, I very quickly decided it was a good idea and that more tests can definitely make software more awesome.

Writing tests for Parrot and Parrot-related projects is quite easy because we have the infrastructure for it. The easiest way to write tests, in my opinion, is with Rosella, but we have a Test::More library as well that can be used for great effect and is the primary testing tool used in Parrot’s own test suite.

Several months ago we had Tapir, a simple TAP harness project written by dukeleto and others in NQP. There was also a project called Kakapo written by Austin Hastings which included several unit test and mock object utilities, also written in NQP. I absorbed a lot of ideas from both projects (and eventually rewrote those ideas in Winxed) for the Rosella Test, Harness and MockObject libraries.

Writing tests for Parrot is a great way to get involved in the project if you’re a new user, a great way to get familiarized with the capabilities of the VM, and a very big benefit to the project in any case. First let’s talk about Test::More as it’s used in the Parrot test suite and then I’m going to talk about Rosella’s test offerings.

Test::More is a very simple TAP producer library that implements a few standard test functions like plan(), is(), ok(), and a few others. You use Test::More like this:

.sub main :main
    .include 'test_more.pir'
    plan(5);
    ok(1, "This test passes");
    ok(0, "This test fails");
    is(1, 1, "These things are equal");
    isnt(1, 0, "These things aren't equal, test passes");
    is(1, 0, "These things aren't equal, so the test fails");
.end

The test harness reads the TAP output from the test file, checks the plan, checks the results of each individual tests, and gives you a readout of the overall pass/fail status of the test.

Test::More is very simple, and if you’ve used a TAP library before the basics of it should be very easy to grasp. Plus, if you look through the Parrot test suite (t/ directory and subdirectories) you’ll see plenty of examples on usage.

Rosella offers several test-related libraries as part of it’s collection: Test (a unit testing library), Harness (a library for building test harnesses) and MockObject (a mock-object testing extension) are all standard parts of the Rosella lineup. There’s also an experimental Assert library that adds some new testing features as well.

Rosella ships with a default testing harness called rosella_harness which is available when you install Rosella. You can run it at the commandline with a list of directories like this:

$> rosella_harness t/foo t/bar t/baz

The harness will run through all *.t files in the given directories, reading the she-bang line in the file and using that program to execute the file. This is the fastest way to get started with testing. Of course, you can also use the Harness library to build your own harness in only a few lines of winxed code:

$include "rosella/harness.winxed";
function main[main]() {
    var harness = new Rosella.Harness();
    harness
        .add_test_dirs("Automatic", "t/foo", "t/bar", "t/baz", 1:[named("recurse")])
        .setup_test_run(1:[named("sort")]);
    harness.run();
    harness.show_results();
}

The listing for a harness written in NQP is almost as short, and I’ve shown it several times on this blog before.

Writing a unit test file with Rosella Test is similarly easy:

$include "rosella/test.winxed";
class MyTest {
    function test_one() {
        self.assert.equal(1, 1);
    }
}
function main[main]() { Rosella.Test.test(class MyTest); }

Each method in the MyTest class will be run as a test. Each test method may contain zero or more assertions. If all assertions pass, the test passes. If any assertion fails the whole test method immediately aborts and is marked as having failed. Unlike Test::More above, we don’t need to explicitly count the number of tests for plan(). Instead, the library counts the number of methods for us automatically.

Rosella’s MockObject library can be used together with the Test library to add MockObject support to your tests. Mock Objects, as I’ve said before and I’ll say a million times again in the future, are tools that can do as much harm as good, especially if they are used incorrectly. Here’s an example of a test using MockObject:

$include "rosella/test.winxed";
$include "rosella/mockobject.winxed";
class MyTest {
    function test_one() {
        var c = Rosella.MockObject.default_mock_factory()
            .create_typed(class MyTargetClass);
        c.expect_method("foo")
            .once()
            .with_args(1, 2, "test")
            .will_return("foobar");
        var o = c.mock();
        var result = o.foo(1, 2, "test");
        self.assert.equal(result, "foobar");
        c.verify();
    }
}
function main[main]() { Rosella.Test.test(class MyTest); }

You have to do more setup for the test with mockobjects, but you get a lot more flexibility to do black-box testing and unit testing with proper component isolation. I won’t try to sell mock object testing here in this post, only demonstrating that it is both possible and easy with Rosella.

Parrot has several thousand tests in its suite. Winxed has a small but growing test suite. Rosella currently runs “728 tests in 116 files”. parrot-libgit2 has a growing test suite. Rakudo has a gigantic spectest suite. Jaesop has a growing suite of tests. NQP has tests. PACT is going to have extensive tests, once it has code worth testing. Plumage has tests (though not nearly enough!). PLA has a relatively large suite of tests. Testing is a hugely important part of the Parrot ecosystem, and we currently have several tools to help with testing. Expect the trend to continue, with more tests being written for more projects in 2012.

Advent 4 - Threading

2011-12-15T00:00:00-08:00

In GSOC two years ago my student Chandon started working on a very cool new project for Parrot: Hybrid Threads. I hadn’t really put too much thought into the future of Parrot’s concurrency architecture until that point and the idea certainly seemed novel and interesting to me. We went ahead with the project not quite sure how far he would get but very eager to see something happen with our ailing threading system.

The problem, needless to say, ended up being much larger than a project for a single summer and by the end of it Chandon had most of a green threads implementation set up, but nothing that was quite mergable to master. His branch sat, un-merged and un-molested, for a year before anybody decided to take a second stab at it.

Several months after Chandon’s work ended I sat down and started seriously thinking about what I wanted Parrot’s concurrency system to look like in the future. If we could have anything we wanted, what is it exactly that we would want? I started by reading up on all sorts of other technologies: Erlang, node.js, stackless threads in python, and others. I even read a few tangentially related materials, like some of the problems with common string optimizations. Ideas in hand, I began writing a short series of blog posts describing my personal conclusions. My plan for concurrency was very close to Chandon’s hybrid threads idea but with a few extra details filled in. I suggested that we should stick with the hybrid threads approach, explicitly restrict cross-thread data contention by using messages and read-only proxies, avoid locking as much as possible, and rely on the immutability of certain data to keep things as simple as possible.

I didn’t have the time to work on all this myself, at least not until several other projects cleared my TO-DO list. This is where hacker nine comes in. Nine wanted to work on adding threading to Parrot and liked the hybrid threads approach and some of the ideas I had been working on. So he checked out a copy of Chandon’s green_threads work, updated to master, and started fixing things. A few weeks later green_threads was merged to master with Linux support only. I said I would work to port the system to Windows as well and nine would push forward with the hybrid portion of the hybrid threads design.

We’re not ready with that yet, but we are getting painfully close to a working system. I’ve been stymied by the house hunt and the fact that I don’t have a windows system at home to play with. Nine has had a few infrastructural difficulties, especially with GC, but he’s making great progress regardless.

Here’s an overview of the threading system we’re working towards in brief: We will have two layers of concurrency: The first are the Tasks, or “green threads”. Each Task represents an individual unit of executing work and multiple Tasks can execute together on a single thread. They do this through preemptive multitasking, the Parrot scheduler occasionally fires alarms and switches Tasks on the current thread if there is more than one in the queue. Since Parrot uses Continuation Passing Style internally, this mechanism is relatively simple to implement (It’s the alarms that are surprisingly difficult and not cross-platform, but the actual Task switching is quite simple after that).

Multiple Tasks running on a single thread gives more of an illusion of concurrency than the real thing, because you aren’t making use of multiple cores in your processor hardware or exploiting any context-switching optimizations at the lowest levels of threads. What we will have to take things to the next level is the OS threads implementation. Internally Parrot will maintain a pool of worker threads. When you create a Task you will have an option about where to dispatch it: On the current thread (useful where we need safe read/write access to PMCs on the same thread without locking), on a specific target thread, or on a completely new thread. Or, if you don’t want to specify you can let the scheduler dispatch the Task to the best thread.

When you think about what this kind of system enables, it’s actually pretty impressive: easy asynchronous IO (schedule an IO request Task on a dedicated IO thread), easy event handling (schedule a new Task on the current thread to keep data locality), easy threading (schedule a new Task, the scheduler will set up the Thread for you), easy eventing loops (main thread reads event sources and schedules Tasks), easy library callbacks (library callback schedules a Task in the owner thread), auto-threaded array operations (schedule tasks for subsets of the data, the scheduler puts the tasks on the threads with lowest latency) and a variety of other modern techniques. This system, once it’s completed and all the bugs are ironed out, will really be a big boost for Parrot in terms of feature set and usability.

I don’t know when we will be ready to merge, but I can’t imagine it will happen before the 4.0 release. Sometime in early 2012 expect to see the new hybrid threading implementation for Parrot, even if it only works on Linux initially. By the 4.6 release I expect we will have a pretty robust hybrid threading system available on all our target platforms, and several of our HLLs and libraries will be making use of it.

Advent 3 - Winxed

2011-12-14T00:00:00-08:00

Already this advent series of posts is an unmitigated disaster. The last two days of ommissions can be squarely blamed on my wife and her parents, and last night I will blame on Septa (for eating 5 hours of my day because of “mechanical problems”). Here, finally, is day 3 of my miserable failure of an advent calendar.

For the third post in my almost-advent calendar, I’m going to talk about Winxed.

Winxed, written by long-time Parrot hacker NotFound, is quite an interesting project and is definitely worth learning more about. It serves as something of a counterpoint to NQP, the other lower-level Parrot language in the ecosystem but the two aren’t competing. I think they are very complimentary. Where NQP is designed to help building compilers (Rakudo Perl6 especially), Winxed seems much more geared towards writing libraries and utilities. It’s for this reason that I’ve written my library project, Rosella, in Winxed.

In return for making such an awesome language, I’ve turned around and started writing some comprehensive documentation about Winxed on the Rosella website.

Winxed is written in itself using a home-brewed recursive descent parser. To perform the bootstrapping, the stage 0 winxed compiler is written in C++. In stage 0, a paired-down version of the language is used to compile the stage 1 compiler which is written in that subset. Stage 1 is used to compile stage 2, which is a more full-featured version of the language. Stage 2 is used to compile itself into stage 3. Stage 3 is what you and I use when we install Winxed.

It sounds much more complicated than it is, but the net result is clear and simple: Winxed written in Winxed. If you know Winxed, or are familiar with some of the big languages it is inspired by (C++, Java, C#, JavaScript), you’ll be able to not only write software for Parrot, but also be able to hack on the Winxed compiler itself. I’ve submitted a few patches and feature additions, and I’ve found it to be a pleasure to work on.

It’s not anything goes on the compiler, however. NotFound maintains pretty tight editorial control over the software. The consistency of vision and planning does produce refreshingly nice results, though. He’s very good about taking requests and suggestions, so if you see something that’s missing definitely drop him a line.

Since bundling with Parrot in th 3.6.0 release, which incidentally is when NotFound started keeping track of version numbers, the language has come a long way: Various optimizations, a debugging mode with optional asserts and conditionals, several new built-in functions, support for multiple dispatch and most recently a new “inline” feature which allows you to inline certain types of code for performance improvements by avoiding extra PCC calls.

Here is a random-ish sample of Winxed code that I’ve been playing around with recently, written in Winxed for testing some new ideas I’m thinking of adding to Rosella:

function main[main](var args)
{
    var rand = Rosella.Random.default_uniform_random();
    var mutator = new Rosella.Genetic.Mutator(
        function() {
            float value = float(rand.get_float()) * 1000.0;
            return new Data(value);
        }
    );
    var e = new Rosella.Genetic.Engine([10, 3, 0], mutator,
        function(var d) {
            int x = int(d.value) - 200;
            ${ abs x };
            return x;
        }
    );
    var w = e.run(500).first().data();
    say(float(w.value));
}

This sample is a driver program for a new Genetic Algorithms library that I’m playing with. This toy example uses the Genetic Engine type to pick some random numbers at each generation for five hundred generations to try and get a random number which is closest to 200.0. It’s a trivial example to be sure, and I’ll write more about that library in the future if anything ever comes of it. That’s not the important part of this example, however. The important part is the Winxed syntax. The syntax should be immediately familiar to anybody who has used JavaScript or C++ and any of its descendents. Here we can clearly see closures created with the function keyword, creating objects with new (Winxed is OO, not prototype-based like JavaScript), low-level types like float and int, Parrot Sub flags like [main] (AKA :main in PIR) and calling PIR opcodes directly (the ${ ... } syntax). Winxed in a nutshell is an an answer to this question: What would it look like if I took a language like C++ or JavaScript and bent it to work closely with Parrot?

Winxed creates a nice mix of dynamic behavior with static analysis. There is plenty of syntax and semantics in the compiler that can be used to inline code, propagate constants, statically link functions by name instead of doing named lookups, checking known types at compile time and issuing warnings, and other tools that would be more familiar to a user of statically typed languages.

I don’t know where NotFound is planning to take Winxed in 2012. His relentless pursuit of new features, better internals, more optimizations, better diagnostics and other improvements leaves open many potential avenues for him to travel down.

I have a few ideas for features I might like to propose and provide patches, many of which will be intended to mirror changes that will need to be made in Parrot. I have been thinking about submitting a patch to add some cleaner syntax for parameter and argument flags instead of using PIR flags by name directly. I’m also keen to get Winxed updated to use some of my new PCC changes as soon as they are available. It will make both a great test case for the new functionality and a good demonstration of any performance benefits to be had. Eventually I would like to get Winxed updated to generate .pbc packfiles directly instead of generating PIR and using IMCC as an intermediary. That’s a pretty big project, and might have to wait until we get more work done on PACT. Again, this would make an excellent demonstration of the functionality, when we have it ready to test.

I personally use Winxed to implement my Rosella project and the first stage of my JavaScript compiler “Jaesop”. Other people are using it as well. Hacker plobsing has used it for a few projects, including an OMeta parser port. Hacker benabik is using it for PACT, a re-design of the Parrot Compiler Toolkit. Dukeleto is writing bindings for libgit2 in Winxed. NotFound is writing xlib bindings in Winxed called Guitor (and some of the example programs are actually quite impressive already). There are many other examples of projects that are or will be written in Winxed, and I’m sure the number will only increase in 2012.

If you’re doing systems-level library or utility work on Parrot in 2012, Winxed is probably the language you are going to be using. I’ll talk about compilers and NQP in later posts.

Advent 2 - Contributing to Parrot

2011-12-11T00:00:00-08:00

I asked for some ideas about topics to write about for this advent calendar thing, and PerlJam (Perl hacker and long-time Parrot ecosystem contributor and well-wisher) suggested I devote a post to how to contribute to Parrot. Say no more! I think it’s an excellent idea for a second post. This, the second day of my lazy, late pseudo-advent calendar for Parrot will be devoted to contributions.

In the olden-days of Parrot, like last year, we used SVN. These were dark and dangerous times when new contributors were forced to submit their proposed changes in patch files via email. There was much weeping and gnashing of teeth. However, we finally made the switch not only to version control with git but also hosting with github. Now contributing to Parrot or any of its many ecosystem projects is a snap. Create a fork of the repository you want to contribute to, make your edits and commit them, and then open a github pull request. It’s so easy, you’re going to be wishing you started doing it earlier. Seriously, what are you waiting for?

If you submit enough cool changes, we’ll probably do one or both of the following:

Ask you to add your name to CREDITS, so you can get MAD PROPZ for everybody to see.
Give you a commit bit to the repo because seriously, you’re doing too much awesome work and we don’t want to have to play intermediaries between you and the code.

We may also try to rope you into doing other stuff, like being one of our monthly release managers (looks great on a resume, especially if you’re entry-level), writing blog posts, mentoring GSoC and GCI students, and writing even more awesome code. If you ever read the book The Giving Tree, it’s kind of like that except everybody wins and the ending is much happier.

Parrot is a relatively rare kind of project because we have so much happening at so many levels of abstraction. If you’re a nuts and bolts kind of coder and like doing stuff “on the metal”, we have plenty of internals work that needs doing: Threading and Concurrency, Garbage Collection, Object Model, and more optimizations than you can shake a stick at. If you’re more of a middle-ware person we have lots of libraries and infrastructure projects to work on. Then we have HLL compilers like Rakudo that need help and finally end-user code and programs written in those HLLs.

Want to write games? We have xlib and opengl bindings available. Sure they may need a little bit of love, but we have them and they work very well.

Like compilers? We have a handful in development and are always looking for more. Winxed is a fun and familiar (For C++ and Java lovers) systems language. I’m working on a new bootstrapped JavaScript compiler. In the past we’ve had Ruby, Python and Tcl compilers under development, and things

Like Perl6? RAKUDO RAKUDO RAKUDO! Also, Rakudo.

Like writing documentation or making cool new websites to hold our docs? We need you! We’ve got lots of documentation that we need to expose to the users better, and we are missing lots of documentation that needs to be written. Also, since code is changing at a break-neck pace we need to update all the docs we have.

If you like solving problems, fixing bugs or implementing cool new code then we have tons of jobs for you! Sign up for a free account on Github if you don’t have one already. Search around the various Parrot repositories or search for “Parrot” to find a repository you want to hack on. Create a fork and get to work! If you want to contribute to a particular project or particular type of project and aren’t sure where or how is the best place, come talk to us and we’ll try to get you pointed in the right direction.

Speaking of talking to us, there are three good ways to get into contact with us Parrot folks, if you want to chat: IRC (#parrot on irc.parrot.org), The parrot-dev email list (parrot-dev at lists.parrot.org) or in comments and pull requests on github. Leave a comment on this blog too, and I’ll help you personally.

Parrot is a big open-source project with lots of work to be done at every level of abstraction. We’re always looking for new contributions and new contributors. If you’re interested in getting involved, don’t hesitate to get in contact with us and start writing some great code.

Advent 1 - Parrot

2011-12-10T00:00:00-08:00

I had intended to publish this advent post yesterday, but even though I had it mostly pre-written I couldn’t find 5 minutes in the day to do it. An inauspicious start to this little sequence! It is already painfully clear that this advent calendar of mine isn’t going to be nearly as reliable or successful as moritz’s. To (finally) kick off this pseudo-advent calendar I’m going to jump right in and talk about the main course, the bird, Parrot. This post is going to be a short retrospective about the developments in 2011 and some clues about where we are heading (or, where I hope we are heading) next year. I’ll very likely post a more in-depth yearly retrospective around the 4.0 release in January.

Parrot, as we all know, is a virtual machine aimed at running dynamic languages. Originally it was envisioned as the backend VM for the new Perl6 language, but Parrot quickly deviated from that path. The idea quickly became to create a language-agnostic platform for hosting a variety of languages in a common, interoperable way.

I don’t want to attempt a complete retelling of the history of the project. I wasn’t around for most of it and at best I’m going to give a faulty recount. Regardless, it doesn’t really matter how we got to where we are now. What matters is what our current trajectory is. Prior to 2011 Parrot had been trying to do many things well but did no single thing well enough to really drive adoption. I think we’ve made up our minds to refocus our efforts on supporting Perl6 specifically, and many of the biggest developments planned for 2012 are going to be headed in that direction. Almost all of the work I personally am planning to do next year will be directly tied to Rakudo, trying to make their system even better, and to give them a better and more compelling infrastructure to do their thing on.

2011 has seen a lot of changes to Parrot, though the vast number of them are internal and involve code that is cleaner and more maintainable, even if not much more functional or with better performance. This continues a trend that was happening in 2010 and even earlier: The biggest tasks we’ve been working on in the last few years involve trying to get some of our older, uglier, and more brittle systems up to a decent level of quality to support additional future work. It’s the nature of the beast, and as much as I would love to say that the code we had was perfectly pretty to begin with, in many cases it has not been. This is not to disparage any prior contributors. If the history of Parrot tells us anything, it’s that Parrot hackers historically didn’t (and honestly, might still not completely) understand exactly what the goals were. So many decisions intellgently made with the best of intentions lead in the exact wrong directions. Such is life. So many systems were prototyped and those prototypes silently became “the real thing” without anybody explicitly giving a stamp of approval.

Starting several years ago we had many subsytems either deleted outright because they were unsalvagable or dramatically rewritten. Some of those events were a little painful, but in all cases we did what was necessary. Because of all the hard work from our development team we are really starting to get to a point where big system improvements and feature additions are not only possible but now very plausible. Things that would have been near impossible to implement in the code base as of 2009 are very reasonable to consider doing in 2011 and 2012. That’s a big step up, even if many of these changes aren’t visible to the end user.

Much of my personal work has been focused on getting some of the essentials into place with regards to the core execution pathway: IMCC, Embedding API, packfiles, etc. The new embedding API was added in January. IMCC’s new public interface was likewise improved and several bits of related code were cleaned in April. The new PackfileView PMC type, the load_bytecode_p_s opcode, the new bootstrapping frontend, and the new :tag syntax for PIR all came in the second half of the year. Starting in early 2012 I’m going to be ripping out all the old cruft that these things were designed to replace, and we are going to see some improvements in code quality to go along with that.

Previously, users had the :load, :init and :main flags to try and schedule when certain subroutines should be executed. The rules for all these flags were messy and overlapping, and they still weren’t considered enough for all necessary use-cases. Some people had suggested adding even more subroutine flags with more special-case semantics throughout the Parrot codebase. This, in my mind, was nonsensical.

Now in Parrot you can use the new :tag syntax to tag a sub with any flag you want:

# Almost same as old :load
.sub 'foo' :tag("load")

# Almost the same as old :init
.sub 'bar' :tag("init")

# Couldn't do this before!
.sub 'baz' :tag("SomethingNew")

And now with the new PackfileView PMC you can find and execute subroutines by tag at any time you want without having to hope and pray that the magical Parrot behavior will do what you need when you need it:

$P0 = load_bytecode "foo.pbc"
$I0 = $P0.'is_initialized'("SomethingNew")
if $I0 goto already_initialized
$P1 = $P0.'subs_by_tag'("SomethingNew")
...
$P0.'mark_initialized'("SomethingNew")
already_initialized:
...

Yes, it is a little bit more code for the end user (or intrepid HLL developer) to write, but the increase in control and flexibility more than makes up for it, in my mind. Plus, this kind of code is very easy to abstract away into a new function, so you only need to write it once. For the record, and I know I’ve discussed this topic at length on my blog in the past, the above code snippet actually executes faster than the old magical semantics, despite the fact that we have more explicit PIR code and more code total running in the runloop instead of at the C level.

The packfile loader, PIR compilation symantics and the way things like Classes, Namespaces and Multisubs are created will all be changing in 2012 for the better. Expect to see performance improvements and feature additions to these things in 2012. If you’re being smart and writing your code in Winxed or NQP we will try our best to keep you shielded from almost all of these changes. If you’re writting code in PIR I feel bad for you, son. I’ve got 99 problems and PIR is like 97 of them.

In a related note, a selection of other Packfile-related PMCs were refactored in January and now we have the ability to create usable bytecode from a Parrot-run program. The interface isn’t great and we haven’t made much use of this ability yet, but I expect big things to happen in 2012 with PACT (benabik’s rewrite of PCT) and maybe a few details coming to Rosella as well.

In 2012 I expect that we are going to finish the work we started in 2011 and have IMCC removed as a permanent built-in part of Parrot. It will still be available to people who want it as an optional library, but it will not be a part of the libparrot binary itself. This is going to have some big ramifications throughout some of the oldest and ugliest parts of the code base and will allow us to start pursuing several goals: Decreasing total code size, especially for embedded environments, being much more flexible about compilers and cleaning up the compreg system, divorcing packfile creation from packfile execution, giving us a much cleaner and more usable interface for executing packfiles, and breaking up some of the syntactic quirks of PIR from the inner semantics of Parrot. It really doesn’t seem like much but trust me when I say that removing IMCC represents more than just some theoretical edification, it opens many doors that we do want and need to travel through soon.

In March bacek added the new Generational garbage collector (GMS), and it became the default collector in May. Performance jumped considerably, especially for Rakudo; although I think some other optimizations can push the performance numbers even better. Sometime in 2012 I want to test out an idea I have with cutting out indirect function calls in the GC, and then I want to dig through some profiles to see where else I can squeeze out a few percentage points. I don’t know if there will be much, but it never hurts to look. With threading on the horizon, I also want to look into a few concurrency-friendly GC algorithms that we can utilize to cut GC overhead and maybe improve GC performance for heavily concurrent workloads.

Parrot hacker plobsing had been doing a lot of NCI-related work through the year, adding the StructView, Ptr, PtrBuf and PtrObj PMC types to replace some of the older types we had for working with raw pointers. These tools are pretty low-level and don’t always expose a very friendly interface (as we would expect at such a low level of abstraction), but have a lot of potential that we can definitely build on. Not all of the NCI changes were met with great enthusiasm (especially those that broke some order signature syntaxes), but getting NCI cleaned up and fixed up is a major hurdle for us that we have to leap over in spite of the pain. Being able to share common native library bindings among multiple HLLs is a huge deal for Parrot, and has the potential to become a major selling point if we can get it done correctly. The Rakudo/NQP folks have also been doing some cool-looking NCI work that we may want to copy in whole or in part, so look forward to those kinds of developments in 2012 as well. Hacker NotFound has been working on a new project called Guitor which uses pure Winxed code to create graphical user interfaces by calling into xlib using Parrot’s NCI. The work he’s been doing is pretty fantastic, and serves as a clear demonstration that NCI is working and working reasonably well.

Adding new native library bindings for Parrot is a very productive and very informative way to get started hacking with Parrot, for anybody who is interested!

Parrot’s object model has remained relatively static for a while, despite the fact that the problems and limitations with it are well known and oft-decried. I hard started to port 6model, the new Rakudo object model developed by Jonathan Worthington, over to Parrot in the summer months but put that work on hold while I came up with a better plan. I kept hoping that development on 6model would slow down and become more stable so I could find a good jumping off point to start with, but that never happened. Eventually I am going to need to just put my foot down and start moving code around. Expect 6model to come to Parrot in early 2012, especially if a few other people volunteer to help.

Winxed, NotFound’s system-level language for Parrot was added as a snapshot to the Parrot repository in July, and has continued to improve by leaps and bounds in that time. Recently NotFound added syntax for inline functions, which can help to improve performance in many places. I’ve got a few syntax ideas I want to play with and try to contribute as well. If we can divorce Winxed a little further from IMCC and PIR syntax (especially in the area of calling conventions and flags), we can be more free to change Parrot’s internals because Winxed’s abstracted syntax will create more of a buffer for us. In 2012 I would like to continue the trend of using PIR less and less, and using Winxed and NQP more and more for basic Parrot tasks.

Specaking of which, NQP-rx, an older variant of the amazingly useful NQP language is showing it’s age and may be dead in 2012. I would love to see it replaced by the newer 6model-powered NQP, especially once we get 6model in Parrot natively. Then we will have two awesome lower-level languages to play with in an interchangable, inter-usable way.

Late 2011 also brought us nine’s rewrite of Green Threads. They aren’t working on Windows yet, but they are working reasonably well on Linux and (I think) Mac although some kinks are still being worked out. In early 2012 expect to start seeing his implementation of full hybrid threads which are already looking awesome. As with the green threads Windows support may come later, especially since we seem to have a relative dearth of hackers working on that platform right now. When I finally get my new laptop I’ll keep windows around to dual-boot from, and will do my best to get concurrency working as well there as anywhere. As always, help in this endeavor would be appreciated. If you’re interested in Parrot concurrency, be it implementation of the internals or using it to write cool new programs and libraries, definitely let me know.

Also in 2012 expect to start seeing some of my proposed changes to PCC start getting integrated into the system. Actually, you probably won’t see them, most of the changes will be transparent in IMCC or maybe in new optimized code generated by Winxed and NQP. We’ll definitely see a few percentage points in performance improvement across PCC calls to start, and opportunity for further improvements after that.

This little retrospective has already grown into a substantial post so I won’t write too much more. Expect other posts in this advent series to be shorter and sweeter (and hopefully, more on time).

Parrot Advent Calendar

2011-12-08T00:00:00-08:00

Rakudo hacker moritz is auditioning for the role of the Good Idea Fairy, which I personally think he’s a shoe-in for. A few days ago in the IRC chatroom he had this gem:

moritz>      hey, have you ever thought of starting a parrot advent calendar?
whiteknight> moritz: sort of, but I wouldn't want to steal your thunder
moritz>      whiteknight: I wouldn't worry about that. There's usually half a
             dozen advent calendars in the Perl community, and we don't seem
             to suffer from that
...
moritz>      whiteknight: don't feel obliged, 'twas just a quick idea. Maybe
             next year if it's too much work this year
whiteknight> moritz: If there is one thing I like doing, it's stealing good
             ideas from the Rakudo folks

So that’s what I’m going to try to do: Do a daily advent-ish sort of calendar for Parrot as similar to the one that moritz does himself as I can manage. Instead of a normal advent calendar which would be the first 25 days of December, I’m going to do the remaining days leading up to New Years. Since I’m already running irrepairably late, I won’t be able to do 25 daily posts between now and then. All the better, really, since I am having trouble coming up with that many ideas! Give me a break, I’m new to this whole advent thing.

What I say I would like to do, and what I am actually able to get done in the coming days are two entirely different things. Add the usual holiday stressors and time-sinks with the cleanups and organizational hassles of moving to a new house (That’s right, we got the house!) and suddenly doing a blog post every day seems like a pretty daunting order. Again, I will do my best

Every day from now till the end of the year, starting tomorrow, I’m going to try to post at least a short blurb about something cool in the world of Parrot. I’ll try to focus on things that we’ve done cool in 2011 or are planning to do come 2012, but if I can find some things worth writing about that are older and are standing the test of time particularly well, I’ll write about that too.

If this goes well and I don’t get all lazy and skip too many days, maybe we can turn this into some sort of regular tradition. If other Parrot hackers want to jump in and write a short guest post here on this blog, or write their own posts elsewhere, let me know. More help is more awesome!

Obviously I’m going to mention some of the projects I’ve been working on because those are the things I know the most about. I’ll try to include a bunch of cool projects from other people too. Please send me ideas if there is something you want to read about in the coming month.

Tomorrow the advent calendar officially starts. I’m going to begin by talking about the main course: the bird.

Sorting Algorithms from GCI

2011-11-26T00:00:00-08:00

Since I haven’t been posting often enough recently, and my schedule is so screwed up because of holidays and the like, and since I happen to have two drafts available I’m posting them both today.

A while back I was playing around with some sorting algorithms and benchmarks sorting_benchmarks for Parrot. I had a quicksort hybrid implementation written in winxed that was consistently out-performing the built-in C implementation of quicksort by about 20%. I decided that I wanted to play with a few more algorithms, especially algorithms which were known to have different performance characteristics on different input types.

For GCI I created two new tasks asking for alternate sort implementations. The first was a Timsort implementation, and the second was for Smoothsort. GCI students Yuki’N and blaise each delivered a winxed implementation of their respective sort, and now I’m able to do some interesting benchmarks showing how they work on different inputs. Here are some of those results:

N = 100000
SORT_TRANSITION = 6

FORWARD-SORTED (PRESORTED) BENCHMARKS

sort with .sort BUILTIN (reversed)
    9.872862s - %100.000000
    Number of items out of order: 0
sort with Rosella Query (reversed)
    8.623591s - %87.346416 (-%12.653584 compared to base)
    Number of items out of order: 0
qsort+insertion sort (reversed)
    7.812607s - %79.132142 (-%20.867858 compared to base)
    Number of items out of order: 0
timsort (reversed)
    0.693221s - %7.021481 (-%92.978519 compared to base)
    Number of items out of order: 0
Smoothsort (reversed)
    2.154514s - %21.822589 (-%78.177411 compared to base)
    Number of items out of order: 0

REVERSE-SORTED BENCHMARKS

sort with .sort BUILTIN (reversed)
    10.000436s - %100.000000
    Number of items out of order: 0
sort with Rosella Query (reversed)
    8.891811s - %88.914232 (-%11.085768 compared to base)
    Number of items out of order: 0
qsort+insertion sort (reversed)
    8.555817s - %85.554438 (-%14.445562 compared to base)
    Number of items out of order: 0
timsort (reversed)
    0.812737s - %8.127015 (-%91.872985 compared to base)
    Number of items out of order: 0
Smoothsort (reversed)
    10.521473s - %105.210141 (+%5.210141 compared to base)
    Number of items out of order: 0

RANDOM BENCHMARKS

sort with .sort BUILTIN (random)
    13.536509s - %100.000000
    Number of items out of order: 0
sort with Rosella Query (random)
    12.566452s - %92.833773 (-%7.166227 compared to base)
    Number of items out of order: 0
qsort+insertion sort (random)
    11.859363s - %87.610203 (-%12.389797 compared to base)
    Number of items out of order: 0
Timsort (random)
    14.461384s - %106.832449 (+%6.832449 compared to base)
    Number of items out of order: 0
Smoothsort (random)
    12.764498s - %94.296823 (-%5.703177 compared to base)
    Number of items out of order: 0

The SORT_TRANSITION parameter above is the size of the array below which the hybrid sort switches from quicksort to insertion sort. 6 is an arbitrary value, but seems to have reasonably good results. I could spend some time to tune this value, but I haven’t.

These benchmarks show some things we already knew: the built-in Quicksort implementation from Parrot is poor across the board. The Quicksort variant that’s in Rosella is better, and my hybrid quicksort+insertion sort variant is better still. What’s interesting to see is how Timsort and Smoothsort perform on these workloads.

Timsort is designed to work well with “real-world” data which is already sorted or already partially sorted. It identifies runs in the data that are already mostly sorted and merges subsequent runs together. Timsort also has the nice feature of identifying runs which are already reverse-sorted and does a very fast reverse to get them ready for merging. We see that the Timsort blows all other challengers out of the water when the array is already sorted and already reverse-sorted. In these instances, the analysis stages of Timsort figure out that no sorting is ever necessary.

Smoothsort constructs a special type of heap from the input data, and uses basic balancing operations on the heap to find the largest value, extracts it, and rebalances the heap. It works very well for the pre-sorted case, but not quite as well as Timsort because it does need to construct this heap first then iterate over it. Smoothsort goes so quick because the heap rebalancing operations when the array is already sorted are almost free. So Smoothsort is quick on a pre-sorted array, but we also see that it’s terrible when the input array is reverse sorted. Timsort still does very well in this case.

When the array is completely random, the story is a little bit different. Both Timsort and Smoothsort lose to the quicksort implementations for completely random data. Timsort actually is worse than Parrot’s built-in quicksort, one of the few results we measure to be slower. Smoothsort is in the same ballpark as the Rosella quicksort, but is a few percent off of the hybrid sort.

If I had to put together a small report-card for these algorithms under all these conditions, it would look something like this:

algorithm       pre-sorted      reversed        random
------------------------------------------------------
quicksort       B               B               A
hybrid sort     B+              B+              A+
Timsort         A+              A+              C
Smoothsort      A               C               B+

At a glance you can really see where each algorithm excels.

It’s worth nothing here that all these implementations are relatively naive and unoptimized. So we can say that “But Algorithm X could be optimized to be even better!”, but the same can be said about all of them. I’ll be doing some of that in the coming days, but I don’t expect any radical changes.

What I would like to do in the future is provide a default sort implementation but also have the sorting interface take some sort of optional “hint” flag that can tell the sorter about certain properties of the data, and select an algorithm specifically tuned for that workload. From the data I have seen so far, I suspect I would like to use by quicksort hybrid as the default, but be able to switch to Timsort if the user hints the input data might already be partially sorted.

Addenum about Big-O and Algorithms

Everybody will tell you that quicksort is O(n log n) on average, and has a pathological worst-case that’s O(n^2). People will also happily point out that something like Timsort has a best case of O(n). What these simple expressions ignore are all the details. The pathological worst case of Quicksort requires a very specific input ordering and an absolute worst selection of the pivot element at each recursion. Even basic modifications to the algorithm or using a hybrid approach completely eliminates these worst-cases. Without such basic modifications the worst-case is certainly possible, but relatively unlikely.

What people also forget when talking about big-O notation are the coefficients. When I say that quicksort has average complexity of O(n log n), what I really mean is that the amount of time it takes is:

t = c * n * log(n) + f(n) + d

Where f(n) is any function that grows more slowly than n * log(n), and c and d are arbitrary coefficients. The quicksort algorithm, properly implemented and optimized, has very low coefficients. The algorithm requires very little setup (d) and performs relatively few operations per iteration (c). The reason why Parrot’s built-in quicksort performs so poorly is because the c there involves recursive PCC calls and nested runloops, so c is unnecessarily large. Just by having it all run in a single runloop we can drop c enough to beat the original implementation. The two implementations use almost exactly the same algorithm, so it’s differences in c (and, to a smaller extent, differences in d) that result in the timing improvements.

Insertion sort, and this is why I picked it to be part of my hybrid quicksort, has O(n^2) complexity, but with very low c. Below a certain threshold, the quick sort algorithm becomes dominated by recursion calls and stack management, and below that threshold the insertion sort performs better. Basically, there’s a very narrow window below which insertion sort’s O(n^2) is lower than quicksort’s O(n log n). By switching algorithms below that threshold, we can squeeze out a few extra percentage points in performance savings. I could easily have used something else like Bubblesort here for the same kind of effect.

Timsort, because it does involve ahead-of-time analysis steps to detect pre-sorted runs is always going to be at something of a disadvantage when faced with a purely-random input. Assuming it’s core sorting algorithm is as efficient on random data as quicksort is (it isn’t, but we can pretend), Timsort is always going to lose those benchmarks because quicksort will be just as fast during the sorting and wont have a forward analysis phase.

Smoothsort is very interesting from a mathematical perspective, and it doesn’t do ahead-of-time analysis like Timsort does. Of course, it does need to construct that special heap, which likewise acts like a damping agent on overall performance results. Smoothsort does very well on pre-sorted data, reasonably well on random data, and completely falls apart when the data is almost exactly reverse-sorted. I suspect we could do some kind of analysis there to detect the worst case and build our heaps backwards, but that would further cut into the performance cost of the common cases.

Rosella Random Library and GCI

2011-11-26T00:00:00-08:00

I’ve never been too happy with the random number generation capabilities of Parrot. Parrot essentially provides a thin wrapper around the system rand and srand capabilities, with an unimaginative interface. This is a fine system for most purposes, but sometimes you need something a little bit different, or want to substitute your own version without too much hassle.

One of the tasks I submitted to GCI was asking for an implementation of the Mersenne Twister algorithm, a good and well-known algorithm to generate pseudo-random numbers. GCI student Yuki’N, who was also a prolific contributor last year for the program, submitted a fine implementation for Rosella to use. Shortly thereafter I wrote up a quick Box-Muller implementation to get normally-distributed numbers too. Now, Rosella has a pretty decent start of a random number library.

For an example I wrote up a short histogram program to display the output. Here are the histograms for the Mersenne Twister and the Box-Muller generators:

Histogram of 500 uniformly-distributed floats:
0: ##########################
1: ####################
2: ##########################
3: ##########################
4: #############################
5: #########################
6: ###########################
7: ########################
8: ####################
9: #######################
10: ############################
11: ##############
12: ###############################
13: #########################
14: ##############
15: ##########################
16: ##########################
17: ##############
18: ##############################
19: #######################

Histogram of 500 normal-distributed floats:
0: #
1: #
2: ####
3: ######
4: ########
5: ########################
6: #######################
7: #########################################################
8: ##########################################################################
9: ###################################################################
10: ################################################################
11: ####################################################
12: #######################################################
13: #########################
14: #################
15: ########
16: ##########
17: #
18:
19: ##

These are the two distributions that I wanted to have most, but they are certainly not the only one ones available.

And random number generation is not the only feature that this library will have, either. The Rosella Query library currently had an implementation of a Fisher-Yates Shuffle algorithm for shuffling an array. I moved that implementation to the new Random library already and updated it to use the Mersenne Twister as the random number source instead of Parrot’s built-in rand opcode.

I have got a handful of other small features and additions that I would like to add to this library, but considering that it is so straight-forward and algorithmic I expect I can make it stable pretty soon without much headache.