Tail-call elimination and moving to github

My main goals this week have been getting a tail-call elimination optimization to work in NQP-rx and moving my GSoC project to an external repository to make it easier for other projects to use it. Both of these goals have been successful. You can find the tail-call elimination optimization here. My GSoC project can now be found on github or installed via Plumage with ./plumage install tree-optimizations.

The first problem I had with implementing tail-call elimination was that PAST::Transformer didn't traverse the "viviself" and "vivibase" attributes of PAST::Var nodes; it turns out that NQP-rx(and doubtless many other PCT-based HLLs) places the PAST::Block node for a subroutine declaration in the viviself attribute of the corresponding PAST::Var node. Wednesday, I implemented walking(with PAST::Walker) all of the PAST::Node attributes that seem to be able to contain another PAST::Node(specifically: PAST::Var's viviself and vivibase and PAST::Block's control and loadinit). Thursday I implemented transforming viviself and vivibase attributes in PAST::Transformer. Friday, I moved my project to github, and subsequently got PAST::Pattern's transform method to properly transform the viviself and vivibase attributes.

With that done, I was ready to get tail-call elimination working. However, I misunderstood how to do tail-calls with PAST::Op; I ended up spending the rest of the night reading and working on side projects. Saturday, I managed to get it working for calls where the subroutine is not stored in the "name" attribute of the call node. For example, explicitly package-qualified calls would be properly optimized into tail-calls. Finally, tonight, after pmichaud pointed me to find_sub_not_null, the tail-call elimination optimization works even for normal sub calls.

This is the example code I used to test it:

sub repeat(&sub, $count) {
    if $count {
	&sub($count);
	return repeat(&sub, $count - 1);
    }
}

my $n := 0;
repeat({ $n++; }, 50000);
say($n);

With standard NQP, this fails due to exceeding the maximum recursion depth after only about a thousand calls. With the optimization, the program fully executes. In fact, it worked even if the count I supplied to repeat was as high as 66245(anything higher causes a segfault for me).

As I briefly mentioned above, I moved my project's code to a github repository, transitioned to using distutils for building, and had it added to plumage under the name "tree-optimization". The motivation for this was that bacek++ was asking my mentor chromatic and myself for my project to either be merged into trunk or moved to its own separate repository. He didn't explicitly state the reason for his request, but there are a few benefits I can see for developers of projects using Tree::Pattern/Walker/Transformer and their subclasses:

  • You will never have to wait for me to merge Parrot trunk into my branch again before you can take advantage of changes to unrelated parts of Parrot.
  • You will no longer need to have an extra build of Parrot just to use the libraries.
  • You can more easily try it out: just clone the git repository and run "parrot-nqp setup.nqp" to build and "parrot-nqp setup.nqp install" to install; alternately, using Plumage, it's a simple matter of "./plumage install tree-optimization".
  • Because it is a separate module instead of a Parrot svn branch, HLL devs have the option of actually using it, not just trying it out, much sooner. If Rakudo, Partcl, or NQP-rx decides that they want to incorporate optimizations using Tree::Pattern into their releases, all they have to do is either require that tree-optimizations be installed or add to their build process a step to fetch and install it if it isn't already installed. Bacek's PIR compiler in NQP, PIRATE, already requires tree-optimization.

This week is mid-term evaluations week for GSoC students. I hope to get mine done in the next couple of days and be able to return to focusing on writing more optimizations and improving the libraries.

If you're a HLL developer who wants to optimize their compiler's generated code, now is a great time to try doing so with my GSoC project. The API is mostly stable and there's quite a bit of functionality available, especially for PAST optimization. If you need any help or have any feedback, you can reach me via email or #parrot on irc.perl.org, with the nickname tcurtis.