dagolden: My Github name has changed from dagolden to xdg

For a long time, my Github identity matched my CPAN ID and I was 'dagolden' on Github. Today, I'm switching to be 'xdg' on Github, to match my Twitter and IRC handles.

The 'dagolden' Github account has become an organization to avoid breaking links and avoid the pain of manually migrating 100's of repositories.

So, henceforth, if you want to highlight me on Github, use "@xdg", not "@dagolden".

Pradeep: apache lucy search examples

Investigating search engines and this time apache Lucy 0.4.2. I am showing a basic indexer and a small search application. See below code for indexer (This will take documents one by one and then index them). Search module will take arugument as STDIN and then will show the search result.

This is pure command line utility just to show how basic indexing and searching works using apache lucy.



use strict;
use warnings;
use Lucy::Simple;

# Ensure the index directory is both available and empty.
my $index = “/ppant/LucyTest/index”;
system( “rm”, “-rf”, $index );
system( “mkdir”, “-p”, $index );
# Create the helper…a new Lucy::Simple object
my $lucy = Lucy::Simple->new( path => $index, language => ‘en’, );

# Add the first “document”. (We are mainly adding meta data of the document)
my %one = ( title => “This is a title of first article” , body => “some text inside the body we need to test the implementaion of lucy”, id => 1 );
$lucy->add_doc( \%one );

# Add the second “document”.
my %two = ( title => “This is another article” , body => “I am putting some basic content, using some words which are also in first document like implementation”, id => 2 );
$lucy->add_doc( \%two );

# Both the documents are now indexed in path

One indexing of the documents is done we’ll make a small search script.



use strict;
use warnings;

use Lucy::Search::IndexSearcher;

my $term = shift || die "Usage: $0 search-term";

my $searcher = Lucy::Search::IndexSearcher->new( index => '/ppant/LucyTest/index');
# A basic search command line which will look for indexed items based on STDIN and will show that in which document query string is found and no of hits
my $hits = $searcher->hits( query => $term );
while ( my $hit = $hits->next ) {
print "Title: $hit->{title} - ID: $hit->{id}\n";
# End of search.cgi


If you want to explore more check Full Code on GitHub

Nestoria Dev Blog: On the hunt for dev interns in London

Welcome back Nestoria Dev Blog readers!

Sorry for the radio silence over the summer. As you may have read on the Lokku blog we have joined the Mitula Group in May and we’ve had a busy summer finding out what that means, visiting Madrid and building things with our Spanish counterparts. More on that in a future blog post I hope.

One thing that the acquisition did mean for us was a temporary pause on hiring. I’m happy to say that that’s now been lifted and we have re-opened our internship program.

We have a great history of hiring and training interns since the early days of Nestoria. A couple of our current permanent team members started out as interns, and we have one dev intern Erik who will sadly be leaving us when he moves back to Hamburg at the end of October. In his 11 month internship with us Erik has learned Perl, Puppet, Solr, and a little bit of Spanish. He’s worked on our NLP and Geocoding systems, our property alert emails, and has helped us make Nestoria Deutschland even higher quality than it was already.

Our interns make their first git commit on their first day, and launch code their first week. We throw them in at the deep end, but we never leave them alone so there’s no danger of drowning. They are required to give and attend tech talks in our weekly tech talk slot, and are expected to come into the company with fresh eyes and give us their honest opinion on what we’re doing well and what we could be doing better.

If that sounds appealing to you, or you know somebody who might be a good fit, read the full details at http://www.lokku.com/jobs/intern.html

Sawyer X: Perl 5 Porters Mailing List Summary: October 5th-11th

Hey everyone,

Following is the p5p (Perl 5 Porters) mailing list summary for the past week. Enjoy!

October 5th-11th

Karl Williamson continues his work on Unicode::Normalize and with the help of reports from Yaroslav Kuzmin was able to speed up the normalizer.

Bug reports and bug fixes

Thomas Sibley verified the possible problem with IO::Socket::INET was indeed a DNS lookup issue:

Indeed, every call to $c->get_request() calls $d->url, which calls gethostbyaddr() in the case of your usage of LocalAddr:

lib/HTTP/Daemon.pm Line 51.

James E. Keenan is on a ticket cleaning spree. He had so far taken up Perl #65052, Perl #116254, Perl #117341, Perl #117963, Perl #120330, Perl #121553, and Perl #120841.

Vincent Pit opened Perl #126240 the week prior (which last week's summary missed - sorry) on fork() causing a panic at destruction time with a debugging threaded blead perl on Mac OS X Yosemite.

Bulk88 submitted a patch in Perl #126273 to help debug work with the Save Stack, and Dave Mitchell provided several hints he finds less invasive. Interesting for anyone else seeking to debug the save stack.

Dave Mitchell had traced the cause of Perl #126145 (a mod_perl pre-compiling modules crash) back to a outdated module, Sub::Attribute.

Dagfinn Ilmari Mannsåker provided a patch in Perl #126281 to improve error messages by including the name of non-lvalue subroutines.

Perl #31923, a segfault which can be triggered by use encoding 'utf8', had been fixed.

Lukas Mai opened Perl #125305 about constant folding barewords with unary minus.

Several errno tests currently fail, reported in Perl #126306 by Jarkko Hietaniemi, relating to a similar problem in IRIX, reported by Jarkko in Perl #123977.

Perl does not warn about malformed UTF-8 characters if a string is enclosed in single quotes, now reflected in Perl #126310.

Regex bugs

Victor Adam is continuing to pursue regular expression test writing. He's been working on several bugs he had reported: Perl #126141, Perl #126177, Perl #126178, Perl #126179, Perl #126180, Perl #126181, Perl #126185, Perl #126186 (which is now fixed and resolved by Yves Orton in fee505829585692618c3f9bb28a8f0464553ec94, Perl #126187, Perl #126222, and Perl #126253.

Fuzzing to find bugs

Dan Collins opened Perl #126274, a crash caused by the following interesting set of characters:


Dan also opened Perl #126309, a segfault caused by:


Dan found even pack can crash with the following code, opened under Perl #126325:


Dan also opened Perl #126319 which causes a crash with this interesting piece of regex:



cadvise static code checker

Jarkko Hietaniemi ran a static code checker called cadvise and the report might contains some very interesting bits.

File::Glob shelling out?

Karl Williamson opened Perl #126271 which exposes a possibly unsafe (and possibly unnecessary) shelling out in File::Glob. The conversation thread exposes more reasons for it and possible solutions.

Continuing redesign of Math-BigInt

Peter John Acklam reopened the discussion on his redesign of the distribution carrying Math::BigInt, Math::BigRat, and bignum mentioning the distributions supporting both procedural function calls being supported at the same time as object-oriented style.

Bulk88 had the following quote-worthy sentence in his reply:

dont[sic] use OOP or convert functional code to OOP for the sake for religious purity.

Aristotle Pagaltzis suggested a remarkable way to deprecate the code. Worth the read.

Yet another Smart Match proposal?

Continuing the Smart Match discussion, and with impending flame risk, Dave Mitchell had bravely suggested yet another Smart Match syntax.

It seems Dave is focusing on making given/when more readable and at the same time, faster, and easier to implement.

Paul "LeoNerd" Evans suggested using new syntax keywords, such as:

use feature 'dispatch';

dispatch($str) {
    on("hello") { say "Hello, there"; }
    on("bye")   { say "Goodbye then"; }

Eirik Berg Hanssen suggests providing keywords for the comparison itself - whether scase and ncase for string vs. numerical comparison respectively, or wheneq and when== (suggested by Paul).

z/OS perl port

Karl Williamson is continuing his work on porting perl to z/OS. Only one test is failing now.

To help understand the failing test and how dynamic linking works in z/OS, Jarkko Hietaniemi, Bulk88, John Goodyear, Yaroslav Kuzmin, Ray Mullins, and Sandra jumped in to investigate and understand how z/OS works in this regard.

This might result in simply a sanity check (as Aristotle Pagaltzis described it) which does not apply in z/OS.

The thread continues here.

Coro branch that works on 5.22

Reini Urban created a Coro fork which contains patches to work on perl 5.22.

What should qr/\p{pkg::L}/ do?

Karl Williamson asks what should the regexp qr/\p{pkg::L}/ do. While currently evaluating to the Unicode property letter, Karl offers it fails on compile- or run-time as the property pkg::L is not found.

Agreed by Ricardo Signes with a suggestion to improve the error from "not found" to something more descriptive (such as "illegal name").

Warn or die on /(?-p)/?

Yves Orton had suggested to close Perl #126185 as WONTFIX since he deems warning good enough. Seconded by Karl Williamson (but to close as Rejected).

Yves also noted additional comments worth a read to anyone interested in regular expressions in finer detail.

Ignore errors configurably

Linda Walsh requests comments in Perl #126314 on a proposal for being able to configure in files to ignore new exceptions in order to handle applications which die when using fatal warnings and encountering new warnings in new versions of perl.


Second voting round on perl 5.22.1

Steve Hay has called for another round of voting on perl 5.22.1.

Hacking Thy Fearful Symmetry: A Call to All Dancer2 Plugin Writers

Was original a message to the dancer-user mailing list. Reproduced here for the signal boost. And because, hey, why not?

Underneath the surface, I've been toiling away at a new plugin system for Dancer2. This new system aims at fixing a few of the thorny issues of the current one, and add a wee bit of unicorn dust to the mix.

For plugin users, the changes are:

  • No change! The new plugins will be called the same way as the old ones -- it'll be transparent to you if a plugin is new gen or old gen. Isn't that music to your ears, or what?

  • No change! Plugins using the new system can work side-by-side with original plugins. It's all really transparent to you. Relax, we're taking care of everything.

For plugin writers, the changes are:

  • The new system inherit from Dancer2::Plugin2 (yes, I know, we just loooove that '2' digit around here...).

  • The new system is much more OO-based, which so far makes for cleaner, easier to write plugins.

  • The new system doesn't export the Dancer keywords into the plugin namespace. It removes a little bit of the sugar (you'll have to do $self->app->request instead of request() inside the plugin module), but it makes much more explicit what is the plugin class, and what is the plugin instance associated with an app.

  • Plugin can now use other plugins!

  • The list of plugin instances are also kept as an attribute in the app object, which makes introspection possible (a plugin, for example, can check if other plugin A is already loaded or not and do things in consequence).

What do I want from you?

Before unleashing D2::P2, it needs to be tested. Racke already migrated two of his plugins to D2::P2. I would like for all of you to try to migrate your plugins, and report if it was a success, or if you uncovered some sore points.

How to do that? I'm glad you asked:

  1. clone and use the Dancer2 branch

  2. read the D2::P2 docs (perldoc lib/Dancer2/Plugin2)

  3. if docs are not sufficient, check examples (/t/plugins2-*) and the already-ported modules at bullet #5 below.

  4. report all problems, head-scratchers, suggestions, etc to the D2::P2 PR

  5. you ported the plugin and all works? Post your victory to the PR dicussion at #4, and add your plugin to the list. That's important, I'll set up a job to test any new tweaks on D2::P2 to all the converted modules)

And, of course, you have questions or anything, please feel free to hit me with'em.

Perl Hacks: Build RPMs of CPAN Modules

If you’ve been reading my blog for a while, you probably already know that I have an interest in building RPMs of CPAN modules. I run a small RPM repository where I make available all of the RPMs that I have built for myself. These will either be modules that aren’t available in other RPM repositories or modules where I wanted a newer version than the currently available one.

I’m happy to take requests for my repo, but I don’t often get any. That’s probably because most people very sensibly use the cpanminus/local::lib approach or something along those lines.

But earlier this week, I was sitting on IRC and Ilmari asked if I had a particular module available. When I said that I didn’t, he asked if I had a guide for building an RPM. I didn’t (well there are slides from YAPC 2008 – but they’re a bit dated) but I could see that it was a good suggestion. So here it is. Oh, and I built the missing RPM for him.

Setting Up

In order to build RPMs you’ll need a few things set up. This is stuff you’ll only need to do once. Firstly, you’ll need two new packages installed – cpanspec (which parses a CPAN distribution and produces a spec file) and rpm-build (which takes a spec file and a distribution and turns them into an RPM). They will be available in the standard repos for your distribution (assuming your distribution is something RPM-based like Fedora or Centos) so installing them is as simple as:

sudo yum install cpanspec rpm-build

If you’re using Fedora 22 or later, “yum” has been replaced with “dnf”.

Next, you’ll need a directory structure in which to build your RPMs. I always have an “rpm” directory in my home directory, but it can be anywhere and called anything you like. Within that directory you will need subdirectories called BUILD, BUILDROOT, RPMS, SOURCES, SPECS and SRPMS. We’ll see what most of those are for a little later.

The final thing you’ll need is a file called “.rpmmacros” in your home directory. At a minimum, it should contain this:

%packager Your Name <you@email.com>
%vendor Some Organisation
%_topdir /home/you/rpm

The packager and vendor settings are just to stop you having to type in that information every time you build an RPM. The _topdir setting points to the “rpm” directory that you created a couple of paragraphs up.

I would highly recommend adding the following line as well:

%__perl_requires %{nil}

This turns off the default behavior for adding “Requires” data to the RPM. The standard behaviour is to parse the module’s source code looking for every “use” statement. By turning that off, you instead trust the information in the META.yml to be correct. If you’re interesting in hearing more detail about why I think the default behaviour is broken, then ask me in a pub sometime.

Ok. Now we’re all set. We can build our first RPM.

Building an RPM

Building an RPM is simple. You use “cpanspec” to make the spec file and then “rpmbuild” to build the RPM. You can use “cpanspec” in a few different modes. If you have the module tarball, then you can pass that to “cpanspec”.

cpanspec Some-Module-0.01.tar.gz

That will unwrap the tarball, parse the code and create the spec file.

But if you’re building an RPM for a CPAN module, you don’t need to download the tarball first, “cpanspec” will do that for you if you give it a distribution name.

cpanspec Some-Module

That will connect to CPAN, find the latest version of the distribution, download the right tarball and then do all the unwrapping, parsing and spec creation.

But there’s another, even cleverer way to use “cpanspec” and that’s the one that I use. If you only know the module’s name and you’re not sure which distribution it’s in, then you can just pass the name of the module.

cpanspec Some::Module

This is the mode that I always use it in.

No matter how you invoke “cpanspec”, you will end up with the distribution tarball and the spec file – which will be called “perl-Some-Module.spec”. You need to copy these files into the correct directories under your rpm building directory. The tarball goes into SOURCES and the spec goes into SPECS. It’s also probably easiest if you change directory into your rpm building directory.

You can now build the RPM with this command:

rpmbuild -ba SPECS/perl-Some-Module.spec

You’ll see a lot of output as “rpmbuild” goes through the whole CPAN module testing and building process. But hopefully eventually you’ll see some output saying that the build has succeeded and that an RPM has been written under your RPMS directory (in either the “noarch” or “x86_64” subdirectory). You can install that RPM with any of the following commands:

sudo rpm -Ivh <path-to-rpm>
sudo yum localinstall <path-to-rpm>
sudo dnf install <path-to-rpm>

And that should be that. Of course there are a few things that can go wrong. And that’s what the next section is about.

Fixing Problems

There are a number of things that can go wrong when building RPMs. Here are some of the most common, along with suggested fixes.

Missing prerequisites

This is also known as “dependency hell”. The module you are building is likely to require other modules. And you will need to have those installed before “rpmbuild” will let you build the RPM (and, note, they’ll need to be installed as RPMS – the RPM database doesn’t know about modules you have installed with “cpan” or “cpanminus”).

If you have missing prerequisites, the first step is to try to install them using “yum” (or “dnf”). Sometimes you will get lucky, other times the prerequisites won’t exist in the repos that you’re using and you will have to build them yourself. This is the point at which building an RPM for a single module suddenly spirals into three hours of painstaking work as you struggle to keep track of how far down the rabbit-hole you have gone.

I keep thinking that I should build a tool which parses the prerequisites, works out which ones already exist and automatically tries to build the ones that are missing. It would need to work recursively of course. I haven’t summoned the courage yet.

Extra files

Sometimes at the end of an RPM build, you’ll get an error saying that files were found which weren’t listed in the spec file. This usually means that the distribution contains programs that “cpanspec” didn’t find and therefore didn’t add to the spec file. This is a simple fix. Open the spec file in an editor and look for the section labelled ‘%files’. Usually, it will look something like this:

%doc AUTHORS Changes GitGuide.md LICENSE META.json

This is a list of the files which will be added to the RPM. See the _mandir entry? That’s the man page for the module that is generated from the module’s Pod (section 3 is where library documentation goes). We just need to add two lines to the bottom of this section:


This says “add any files you find in the binaries directories (and also any man pages you find for those programs)”.

If you add these lines and re-run the “rpmbuild” command, the build should now succeed.

Missing header files

If you’re building an XS module that is a wrapped around a C library then you will also need the C header files for that library in order to compile the XS files. If you get errors about missing definitions, then this is probably the problem. In RedHat-land a C library called “mycoolthing” will live in an RPM called “libmycoolthing” and the headers will be in an RPM library called “libmycoolthing-devel”. You will need both of those installed.

Your users, however, will only need the C library (libmycoolthing) installed. It’s well worth telling the RPM system that this external library is required by adding the following line to the spec file:

Requires: libmycoolthing

That way, when people install your module using “yum” or “dnf”, it will pull in the correct C library too. “cpanspec” will automatically generate “Requires” lines for other Perl RPMs, but it can’t do it for libraries that aren’t declared in the META.yml file.


So that’s it. A basic guide to building RPMs from CPAN distributions. There’s a lot more detail that I could cover, but this should be enough to work for 80-90% of the modules that you will want to build.

If you have any questions, then please leave a comment below.

Send to Kindle

The post Build RPMs of CPAN Modules appeared first on Perl Hacks.

NeilB: CPAN Testers needs our help

CPAN Testers needs recurring funding to cover its hosting costs. If you, or your company, rely on CPAN, then please seriously consider setting up a standing order to donate £50 (or some multiple thereof) to CPAN Testers every year. We encourage companies to use a multiple of the base £50 that reflects their reliance on CPAN and thus CPAN Testers.

CPAN Testers is an invaluable resource for all of us: it tests CPAN releases across a wide range of operating systems, versions and build configurations of Perl. This benefits the Perl community in two ways: (1) improving quality and (2) avoiding problems. If you use CPAN modules, then CPAN Testers is making those modules more reliable for you.

If you're an author, your releases will be tested on operating systems and versions of Perl that you may not have access to, and you'll be told if there are any failures. Addressing these failures makes your module more dependable. If you're going to use other modules from CPAN in your distribution, then CPAN Testers gives a good indication of how likely it is that they'll break your installation. If there are multiple modules for a given task, you can pick the one with fewest CPAN Testers failures.

The CPAN Testers service is free for all of us to use. CPAN Testers and the Metabase service it relies on were developed, and continue to be maintained, using volunteer effort. They run on serious hardware, hosted in commercial data centres, and these resources cost money, every year. Birmingham (UK) Perl Mongers have stumped up a lot of cash over the years; David Golden, Barbie and others have dipped into their own pockets. The Enlightened Perl Organisation (the good kind of EPO) has been covering the gaps. When things go wrong, they're often left scrambling for funds.

Personally, I'd rather the people working on it could focus on improving the service for all of us. This means that we need a source of recurring funding. So, as a community, I propose that we each commit what we can, every year. To make life simple, I'm suggesting that individuals, small companies, and Perl Mongers groups sign up for £50. Larger companies can hopefully sign up for £100 or some higher multiple of £50, but hopefully enough of us can sign up for at least £50 per year to provide stability, and maybe even growth. Our goal is £5000/year; any extra will go into CPAN Testers, or other parts of the CPAN ecosystem or QA activities such as the QA Hackathon.

These figures are just suggestions — the CPAN Testers team will be grateful for any and all donations, especially recurring ones.

You can set up recurring payments using PayPal at the EPO page for CPAN Testers:


If you want to discuss some other method of payment, please get in touch with Mark Keating.

When you've done that, please get in touch with me (neil at bowers dot com), so you / your company can be acknowledged in all the right places, such as the CPAN Testers sponsors page (which we're going to be reworking soon).

I'm not part of the CPAN Testers team, I'm just a satisfied beneficiary who wants to help them out.

The first three companies have already signed up — see below. Full disclosure: one of them is the small company that I started with a friend.


MaxMind provides services and software for IP Geolocation (GeoIP) as well as fraud detection (minFraud). Perl is a major part of their toolbox, and they support all of the developers contributing to relevant open source communities. You may recognise some of their development team: Dave Rolsky (DROLSKY), Olaf Alder (OALDERS), Florian Ragwitz (FLORA), Mateu Hunter (MATEU), Ran Eilam (EILARA), Andy Jack (ANDYJACK), Mark Fowler (MARKF), TJ Mather (TJMATHER), William Stevenson (WDS), and Gregory Oschwald (OSCHWALD).



Cogendo helps your company and everyone in it perform at their best. We provide online performance management software that companies can use to manage their employees' objectives and performance reviews. The back end is built in Perl, and hosted with Bytemark, another company that has supported CPAN Testers over the years. Our development team also regularly contributes to CPAN: Neil Bowers (NEILB). We're only a small company, but we're happy to do our bit for such a key part of the CPAN ecosystem.



Eligo is a UK-based recruitment agency that specialises in a number of areas, including software development. Their Perl recruiter is Rick Deller, who has presented at a number of Perl events around Europe. They love the Perl community, and leapt at the chance to support CPAN Testers in this way.


The Effective Perler: Use subroutine signatures with anonymous subroutines

While working on my excellent number project, I created a subroutine that took a callback as an argument. When I dereferenced the callback I wanted to supply arguments. Since I was using Perl v5.22, I tried using a subroutine signature with it.

my $max_a = bisect(
	sub ( $a, $k ) { sqrt( $a * 10**$k + $a**2 ) },
	my $threshold = 1

I had no reason to think that it wouldn’t work but the idea hadn’t occurred to me when I wrote about subroutine signatures as a new feature in v5.20. The section on “Signatures” in perlsub doesn’t have an example with an anonymous subroutine. And it works. But, maybe it’s not supposed to. This is an experimental feature and it is undocumented, but I hope it sticks around.

Consider what I would have to write without the signatures. I could assign the arguments myself:

sub { my( $a, $k ) = @_; sqrt( $a * 10**$k + $a**2 ) }

This is different than the signatures, though. I don’t check the number of arguments, possibly set defaults, and many other niggling tasks I don’t like re-typing.

I could also use the elements in @_ directly:

sub { sqrt( $_[0] * 10**$_[1] + $_[0]**2 ) }

That is ugly in even a way a staunch Perler will admit, and I know that single-element access to Perl special arrays tends to throw off newbies. I’m guilty of this because I haven’t had a prettier alternative that I’ve seen in other languages:

import math
lambda a, k: math.sqrt( a * 10**k + a**2 )
# ruby
lambda { |a, k| Math.sqrt(a * 10**k + a**2) }
# smalltalk
[ :a :k | (a * (10 raisedTo: k) + a squared) sqrt ]

Perl 6 has the pointy block syntax along with other cool ways to create fancy subroutines:

# perl6
-> $a, $k { sqrt($a * 10**$k + $a**2) };

Now that I have this syntax in Perl, even if it is experimental, I know that I’m going to abuse it and come to rely on it.

dagolden: How to trim PDF margins and edit metadata

I often download academic articles as PDFs to read later. I regularly find two really annoying problems:

  1. Huge margins make the PDF nearly unreadable on my Kindle Fire
  2. Title and authors are missing from PDF metadata, making them harder to find later via search

Today, I found an answer to the first and wrote an answer to the second.

For fixing huge margins, I found the free briss tool, which shows a composite image of all odd and even pages and lets you set a crop box around them.

briss in action cropping PDF margins

briss in action cropping PDF margins

To fix the metadata, I did a bit of Googling for tools, then realized I could whip up a tool with Perl and PDF::API2 faster than hunting for an existing one.

This program reads PDF metadata, opens an editor with the data in JSON format, and takes the result and saves it to a new PDF.

#!/usr/bin/env perl
use v5.10;
use strict;
use warnings;

use JSON::MaybeXS;
use PDF::API2;
use Path::Tiny;

die "Usage: $0 <infile> <outfile>\n" unless @ARGV == 2;

my ( $infile, $outfile ) = @ARGV;

unless ( $infile || -r $infile ) {
    die "Input file '$infile' can't be read\n";

my $pdf = PDF::API2->open($infile);
my $json = JSON::MaybeXS->new( utf8 => 1, pretty => 1 );
my $temp = Path::Tiny->tempfile;
$temp->spew( $json->encode( { $pdf->info } ) );

if ( $ENV{EDITOR} ) {
    system( $ENV{EDITOR}, $temp )
      and die "Error editing temp file: $!\n";
else {
    die "No EDITOR environment variable set.\n";

$pdf->info( %{ $json->decode( $temp->slurp ) } );

Sawyer X: Perl 5 Porters Mailing List Summary: September 27th - October 4th

Hey everyone,

Following is the p5p (Perl 5 Porters) mailing list summary for the past week. Enjoy!

September 27th - October 4th

Bug reports and bug fixes

Storable's tests don't seem to be able to run in parallel, as Perl #126213 points out.

James E. Keenan suggests moving forward on the patch by Tony Cook to address Perl #126084 fixing the do undef problem Ricardo Signes raised.

Konstantin Kokin reported in Perl #126224 apparent slowness in IO::Socket::INET when testing with ab. Paul "LeoNerd" Evans suggested it might have to do with DNS queries (which Konstantin rejected) and ventured that IO::Socket::IP might do better. Mark Overmeer mentioned that playing with ab parameters, especially -c, provided a positive change, meaning it might have to do with ab itself. He also suggested DNS indeed could be related.

Zhenyi Zhou opened Perl #126229, explaining that POSIX's strerror clears the value of $!. It was reduced further by Zhenyi and Dave Mitchell to:

$! = 29;
{ local $! = $! }
print "[$!]\n"; # prints "[]"

In Dave's words:

Its a messy interaction between local() and magic vars. I'm not sure it can be fixed.

Ed Avid raised Perl #126239, addressing File::Glob's confusing documentation regarding the GLOB_NOCHECK option.

Bulk88 provided a patch in Perl #126242 to fix a compilation error when using NO_HASH_SEED in combination with the default hash algorithm (PERL_HASH_FUNC_ONE_AT_A_TIME_HARD), existing since 5.17.10.

Todd Rinaldo provided a patch in Perl #126244 to remove B::Section, as Todd describes:

This package is a vestigial reminant of B::C's removal [...]

Regex bugs

Victor Adam is continuing his quest for finding weird Regexp bugs and raised Perl #126222, finding a problem with:

print /(?(?!)(?{print "Yes"})|(?{print "No"}))/

This was fixed by Yves Orton just a few days later in 6625d92602279361acd0c6185b78c6d201fd81e0.

Victor also raised Perl #126253, expecting perl to die when seeing the two following regexp patterns:


And following up on one of his ticket, Victor, he also whipped up a patch to fix Perl #126181 (a bug he opened the week prior), handling \c inside (?[]).

Fuzzing to find bugs

In this week's portion of "bugs dicovered by fuzzing", Dan Collins opened Perl #126257, reduced to:


and Perl #126258, derived from:


and Perl #126260, caused by:


and Perl #126261, caused by such a nasty regexp, I cannot even include it. :)


Supporting qr/\p^L/

Following the conversation on \p with a space, Karl Williamson asked for comments regarding \p (the syntax for named Unicode properties) with a following caret (^) symbol. One suggestion is not supporting it, the other is making it the same \P. This would mean that:


would be the equivalent of:

  • Aristotle Pagaltzis asked why have one support the other.
  • Abigail supported throwing an error.
  • Ricardo Signes agreed.
  • Eric Brine provided a few points in favor and many against, summarizing he also doesn't like it.

Remove unused defines in perl.h

Karl Williamson also raised Perl #231533 a few define statements in perl.h which he suggests to remove. According to Karl, they currently aren't in used in Perl core, in CPAN, probably by anyone else, and they are wrong on EBCDIC platforms.

$SIG{__WARN__} and PL_warnhook can have different values

Max Maischein opened Perl #125439 discussing the ability of $SIG{__WARN__} and PL_warnhook to have different values, which he thinks is similar to the (patched by him) behavior of $$.

For example, PerlIO_find_layer assigns directly to PL_warnhook without updating $SIG{__WARN__}, and buggy XS modules could do the same.

Max suggests picking up Coro's implementation which always write+read PL_warnhook, analogous to $SIG{__DIE__}.

If this was indeed embraced, Coro could eliminate its workaround for patching the magic vtable entries.

Dave Mitchell supports the proposition.

Max is now working on a patch.

WinCE smokes and the problem with CPAN smokers

Ricardo Signes was wondering on the ability to receive semi-regular smoke reports of WinCE.

Bulk88 noted the different considerations in WinCE which make it difficult to test: WinCE Perl cannot redirect stdio easily, PP system() not available, the console window itself is drawn by perl using a 3rd party library(!), no shell process.

Bulk88 also suggested a way to allow testing on WinCE by transporting the reports to a different machine that will process them.

Aristotle Pagaltzis explained that it is possible that the standardization of CPAN smoke testers, which made it very simple to set up smokers, actually works against our favor since they are created in a similar way, thus lending to the "monoculture" situation of smoker set ups being too common and not varied enough.

The %! hash

Following last week, Felipe Gasper stressed the point that, if we don't document how %! should be used people might use it in a way that works but isn't intended, and which might change.

How to use it:

if ( $!{'NOENT'} ) { ... }

How not to use it:

if ( $! == $!{'ENOENT'} ) { ... }

Ricardo Signes introduced 3b90fd9 to address this.

Turning compile-time warnings off for good

Sam Kington raised a problem they're having at work while upgrading to a perl 5.20.3. Using smartmatch extensively, warnings are beginning to mount up. Using no warnings 'experimental::smartmatch' handles the warnings until they load any module that introduces all warnings again, such as Moose or Dancer (or Dancer2).

Unfortunately perl has no way to prevent a different module from importing warnings into your namespace after you've adjusted them to your satisfaction.

Several offers were made, but at the end of the day, Zefram concluded that the only way to handle this properly would be in the modules themselves.

Sawyer X (me) introduced a change into Dancer 2, which David Precious will adapt to the feature-frozen Dancer 1, to allow importing Dancer without the additional pragmas it provides:

use strict;
use warnings;
no warnings 'experimental::smartmatch';
use Dancer2 ':nopragmas'; # does not reimport

perl's AUTHORS file

In an earlier thread (stemming from Perl #126057, a problem with the pending-author.t test), Dave Mitchell wondered whether we should still be maintaining an AUTHORS file instead of simply using Git's history.

There were objections from James E. Keenan and Abigail, expressing that maintaining the file has little overhead and both helps a way to honor contributors and is needed in case contributors do not have a perl git repository available for their contribution. It was decided to keep it then.

Process of using undocumented globals

Karl Williamson provided a patch to clarify the process of using undocumented globals. In short:

One should send email to p5p first to get the go-ahead for documenting and using an undocumented function or global variable.


Grant report and major speed-up

Dave Mitchell provides his #98 and #99 grant reports.

The highlights include working on making EXTEND and MEXTEND (macros for growing the stack) more robust against count truncating and wrapping (derived from Perl #125937, mentioned in last week's summary) and optimizing the Boyer-Moore string finder (used in regexps and index).

The latter is an important speed improvement, as explained by Dave:

On my glibc linux x86_64 systems, this code is now 7 times faster:

$s = "a" x 1000 . "wxyz";
$s =~ /wxyz/ for 1..30000;

The commit includes the fascinating details.

Follwing this work, Aristotle Pagaltzis revealed index to still be faster, opting Yves Orton to suggest there's further optimization to be achieved on this.

Lexical topic removed!

Father Chrysostomos provided a branch to remove the lexical topic variable my $_. It was rebased and merged by Ricardo Signes with the help of Dagfinn Ilmari Mannsåker.

If you have any code that runs my $_, please update it, since the feature will officially be removed in perl 5.24.

Perlgeek.de : All Perl 6 modules in a box

Sometimes when we change things in the Perl 6 language or the Rakudo Perl 6 compiler that implements it, we want to know if the planned changes will cause fallout in the library modules out there, and how much.

To get a quick estimate, we can now do a git grep in the experimental perl6-all-modules repository.

This is an attempt to get all the published module into a single git repository. It is built using git subrepo, an unofficial git extension module that I've been wanting to try for some time, and that seems to have some advantages over submodules in some cases. The notable one in this case being that git grep ignores submodules, but descends into subrepos just fine.

Here is the use case that made me create this repository: Rakudo accesses low-level operations through the nqp:: pseudo namespace. For example nqp::concat_s('a', 'b') is a low-level way to concatenate two strings. User-level programs can also use nqp:: ops, though it is generally a bad idea, because it ties the program to the particular compiler used, and what's more, the nqp:: ops are not part of the public API, and thus neither documented in the same place as the rest of Perl 6, nor are there any promises for stability attached.

So we want to require module authors to use a pragma, use nqp; in order to make their use of compiler internal explicit and deliberate. And of course, where possible, we want them to not use them at all :-)

To find out how many files in the ecosystem use nqp:: ops, a simple command, combined with the power of the standard UNIX tools, will help:

$ git grep -l 'nqp::'|wc -l

That's not too bad, considering we have... how many modules/distributions again?

Since they are added in author/repo structure, counting them with ls and wc isn't hard:

ls -1d */*/|wc -l

Ok, but number of files in relation to distributions isn't really useful. So let's ask: how many distributions directly use nqp:: ops?

$ git grep -l nqp:: | cut -d/ -f1,2 |sort -u|wc -l

23 out of 282 (or about 8%) distributions use the nqp:: syntax.

By the way, there is a tool (written in Perl 6, of course) to generate and update the repository. Not perfect yet, very much a work in progress. It's in the _tools folder, so you should probably filter out that directory in your queries (though in the examples above, it doesn't make a difference).

So, have fun with this new toy!

Dave's Free Press: Journal: Module pre-requisites analyser

Dave's Free Press: Journal: CPANdeps

Dave's Free Press: Journal: Perl isn't dieing

Perlgeek.de : A new Perl 6 community server - update

In my previous post I announced my plans for a new Perl 6 community server (successor to feather.perl6.nl), and now I'd like to share some updates.

Thanks to the generosity of the Perl 6 community, the server has been ordered and paid. I am now in the process of contacting those donors who haven't paid yet, leaving them the choice to re-purpose their pledge to ongoing costs (traffic, public IPv4 addresses, domain(s), SSL certs if necessary) and maintenance, or withdraw their pledges.

Some details of the hardware we'll get:

  • CPU: Intel® Xeon® Haswell-EP Series Processor E5-2620 v3, 2.40 GHz, 6-Core Socket 2011-3, 15MB Cache
  • RAM: 4x8GB DDR4 DDR4 PC2133 Reg. ECC 2R
  • HD: 2x 2TB SATA3-HD

The vendor has told me that all parts have arrived, and will be assembled today or tomorrow.

Currently I lean towards using KVM to create three virtual hosts: one for websites (*.perl6.org, perlcabal.syn), one for general hacking and IRC activity, and one for high-risk stuff (evalbots, try.rakudo.org, ...).

I've secured the domain p6c.org (for "perl 6 community"), and the IPv4 range - and the IPv6 net 2001:780:101:ff00::/64.

So the infrastructure is in place, now I'm waiting for the delivery of the hardware.

Perlgeek.de : doc.perl6.org: some stats, future directions

In June 2012 I started the perl6/doc repository with the intent to collect/write API documentation for Perl 6 built-in types and routines. Not long afterwards, the website doc.perl6.org was born, generated from the aforementioned repository.

About 2.5 years later, the repository has seen more than one thousand commits from more than 40 contributors, 14 of which contributed ten patches or more. The documentation encompasses about 550 routines in 195 types, with 15 documents for other things than built-in types (for example an introduction to regexes, descriptions of how variables work).

In terms of subjective experience, I observed an increase in the number of questions on our IRC channel and otherwise that could be answered by pointing to the appropriate pages of doc.perl6.org, or augmenting the answer with a statement like "for more info, see ..."

While it's far from perfect, I think both the numbers and the experience is very encouraging, and I'd like to thank everybody who helped make that happen, often by contributing skills I'm not good at: front-end design, good English and gentle encouragement.

Plans for the Future

Being a community-driven project, I can't plan anybody else's time on it, so these are my own plans for the future of doc.perl6.org.

Infrastructural improvements

There are several unsolved problems with the web interface, with how we store our documents, and how information can be found. I plan to address them slowly but steadily.

  • The search is too much centered around types and routines, searching for variables, syntactic constructs and keywords isn't easily possible. I want it to find many more things than right now.
  • Currently we store the docs for each type in a separate file called Type.pod. Which will break when we start to document native types, which being with lower case letters. Having int.pod and Int.pod is completely unworkable on case-insensitive or case-preserving file system. I want to come up with a solution for that, though I don't yet know what it will look like.
  • doc.perl6.org is served from static pages, which leads to some problems with file names conflicting with UNIX conventions. You can't name a file infix:</>.html, and files with two consecutive dots in their names are also weird. So in the long run, we'll have to switch to some kind of dynamic URL dispatching, or a name escaping scheme that is capable of handling all of Perl 6's syntax.
  • Things like the list of methods and what they coerce to in class Cool don't show up in derived types; either the tooling needs to be improved for that, or they need to be rewritten to use the usual one-heading-per-method approach.


Of course my plan is to improve coverage of the built-in types and routines, and add more examples. In addition, I want to improve and expand on the language documentation (for example syntax, OO, regexes, MOP), ideally documenting every Perl 6 feature.

Once the language features are covered in sufficient breadth and depth (though I won't wait for 100% coverage), I want to add three tutorial tracks:

  • A track for beginners
  • A quick-start for programmers from other languages
  • A series of intermediate to advanced guides covering topics such as parsing, how to structure a bigger application, the responsible use of meta programming, or reactive programming.

Of course I won't be able to do that all on my own, so I hope to convince my fellow and future contributors that those are good ideas.

Time to stop rambling about the future, and off to writing some docs, this is yours truly signing off.

Dave's Free Press: Journal: YAPC::Europe 2007 report: day 3

Perlgeek.de : The Fun of Running a Public Web Service, and Session Storage

One of my websites, Sudokugarden, recently surged in traffic, from about 30k visitors per month to more than 100k visitors per month. Here's the tale of what that meant for the server side.

As a bit of background, I built the website in 2007, when I knew a lot less about the web and programming. It runs on a host that I share with a few friends; I don't have root access on that machine, though when the admin is available, I can generally ask him to install stuff for me.

Most parts of the websites are built as static HTML files, with Server Side Includes. Parts of those SSIs are Perl CGI scripts. The most popular part though, which allows you to solve Sudoku in the browser and keeps hiscores, is written as a collection of Perl scripts, backed by a mysql database.

When at peak times the site had more than 10k visitors a day, lots of visitors would get a nasty mysql: Cannot connect: Too many open connections error. The admin wasn't available for bumping the connection limit, so I looked for other solutions.

My first action was to check the logs for spammers and crawlers that might hammered the page, and I found and banned some; but the bulk of the traffic looked completely legitimate, and the problem persisted.

Looking at the seven year old code, I realized that most pages didn't actually need a database connection, if only I could remove the session storage from the database. And, in fact, I could. I used CGI::Session, which has pluggable backend. Switching to a file-based session backend was just a matter of changing the connection string and adding a directory for session storage. Luckily the code was clean enough that this only affected a single subroutine. Everything was fine.

For a while.

Then, about a month later, the host ran out of free disk space. Since it is used for other stuff too (like email, and web hosting for other users) it took me a while to make the connection to the file-based session storage. What happened was 3 million session files on a ext3 file system with a block size of 4 kilobyte. A session is only about 400 byte, but since a file uses up a multiple of the block size, the session storage amounted to 12 gigabyte of used-up disk space, which was all that was left on that machine.

Deleting those sessions turned out to be a problem; I could only log in as my own user, which doesn't have write access to the session files (which are owned by www-data, the Apache user). The solution was to upload a CGI script that deleted the session, but of course that wasn't possible at first, because the disk was full. In the end I had to delete several gigabyte of data from my home directory before I could upload anything again. (Processes running as root were still writing to reserved-to-root portions of the file system, which is why I had to delete so much data before I was able to write again).

Even when I was able to upload the deletion script, it took quite some time to actually delete the session files; mostly because the directory was too large, and deleting files on ext3 is slow. When the files were gone, the empty session directory still used up 200MB of disk space, because the directory index doesn't shrink on file deletion.

Clearly a better solution to session storage was needed. But first I investigated where all those sessions came from, and banned a few spamming IPs. I also changed the code to only create sessions when somebody logs in, not give every visitor a session from the start.

My next attempt was to write the sessions to an SQLite database. It uses about 400 bytes per session (plus a fixed overhead for the db file itself), so it uses only a tenth of storage space that the file-based storage used. The SQLite database has no connection limit, though the old-ish version that was installed on the server doesn't seem to have very fine-grained locking either; within a few days I could errors that the session database was locked.

So I added another layer of workaround: creating a separate session database per leading IP octet. So now there are up to 255 separate session database (plus a 256th for all IPv6 addresses; a decision that will have to be revised when IPv6 usage rises). After a few days of operation, it seems that this setup works well enough. But suspicious as I am, I'll continue monitoring both disk usage and errors from Apache.

So, what happens if this solution fails to work out? I can see basically two approaches: move the site to a server that's fully under my control, and use redis or memcached for session storage; or implement sessions with signed cookies that are stored purely on the client side.

Ocean of Awareness: PEG: Ambiguity, precision and confusion


PEG parsing is a new notation for a notorously tricky algorithm that goes back to the earliest computers. In its PEG form, this algorithm acquired an seductive new interface, one that looks like the best of extended BNF combined with the best of regular expressions. Looking at a sample of it, you are tempted to imagine that writing a parser has suddenly become a very straightforward matter. Not so.

For those not yet in the know on this, I'll illustrate with a pair of examples from an excellent 2008 paper by Redziejowski. Let's start with these two PEG specifications.


One of these two PEG grammars accepts the string "aaa" but not the string "aa". The other does the opposite -- it accepts the string the string "aa" but not the string "aaa". Can you tell which one? (For the answer, see page 4 of Redziejowski 2008.)

Here is another example:

    A = "a"A"a"/"aa"

What language does this describe? All the strings in the language are obviously the letter "a", repeated some number of times. But which string lengths are in the language, and which are not? Again the answer is on page 4 of Redziejowski 2008 -- it's exactly those strings whose length is a power of 2.

With PEG, what you see in the extended BNF is not what you get. PEG parsing has been called "precise", apparently based on the idea that PEG parsing is in a certain sense unambiguous. In this case "precise" is taken as synonymous with "unique". That is, PEG parsing is precise in exactly the same sense that Jimmy Hoffa's body is at a precise location. There is (presumably) exactly one such place, but we are hard put to be any more specific about the matter.


The advantage of using a syntax-driven parser generator is that the syntax you specify describes the language that will be parsed. For most practical grammars, PEG is not syntax-driven in this sense. Several important PEG researchers understand this issue, and have tried to deal with it. I will talk about their work below. This is much more at stake than bragging rights over which algorithm is really syntax-driven and which is not.

When you do not know the language your parser is parsing, you of course have the problem that your parser might not parse all the strings in your language. That can be dealt with by fixing the parser to accept the correct input, as you encounter problems.

A second, more serious, problem is often forgotten. Your PEG parser might accept strings that are not in your language. At worst, this creates a security loophole. At best, it leaves with a choice: break compatiblity, or leave the problem unfixed.

It's important to be able to convince yourself that your code is correct by examining it and thinking about it. Beginning programmers often simply hack things, and call code complete once it passes the test suite. Test suites don't catch everything, but there is a worse problem with the beginner's approach.

Since the beginner has no clear idea of why his code works, even when it does, it is unlikely to be well-organized or readable. Programming techniques like PEG, where the code can be made to work, but where it is much harder, and in practice usually not possible, to be sure why the code works, become maintenance nightmares.

The maintenance implications are especially worrisome if the PEG parser is for a language with a life cycle that may involve bug fixes or other changes. The impact of even small changes to a PEG specification is hard to predict and hard to discover after the fact.

Is PEG unambiguous?

PEG is not unambiguous in any helpful sense of that word. BNF allows you to specify ambiguous grammars, and that feature is tied to its power and flexibility and often useful in itself. PEG will only deliver one of those parses. But without an easy way of knowing which parse, the underlying ambiguity is not addressed -- it is just ignored.

My Marpa parser is a general BNF parser based on Earley's. It also can simply throw all but one of the parses in an ambiguous parse away. But I would not feel justified in saying to a user who has an issue with ambiguity, that Marpa has solved her problem by throwing all but one arbitrarily chosen result.

Sticking with Marpa for a moment, we can see one example of a more helpful approach to ambiguity. Marpa allows a user to rank rules, so that all but the highest ranking rules are not used in a parse. Marpa's rule rankings are specified in its BNF, and they work together with the BNF in an intuitive way. In every case, Marpa delivers precisely the parses its BNF and its rule rankings specify. And it is "precision" in this sense that a parser writer is looking for.

Is there a sensible way to use PEG?

I'll return to Marpa at the end of this post. For now, let's assume that you are not interested in using Marpa -- you are committed to PEG, and you want to make the best of PEG. Several excellent programmers have focused on PEG, without blinding themselves to its limitations. I've already mentioned one important paper by Redziejowski. Many of Redziejowski's collected papers are about PEG, and Redziejowski, in his attempts to use PEG, does not sugarcoat its problems.

Roberto Ierusalimschy, author of Lua and one of the best programmers of our time, has written a PEG-based parser of his own. Roberto is fully aware of PEG's limits, but he makes a very good case for choosing PEG as the basis of LPEG, his parser generator. LPEG is intended for use with Lua, a ruthlessly minimal language. Roberto's minimalist implementation limits the power of his parser, but his aim is to extend regular expressions in a disciplined way, and a compact parser of limited power is quite acceptable for his purposes.

Matching the BNF to the PEG spec

As Redziejowski and Ierusalimschy and the other authors of Mascarenhas et al, 2013 recognize, not knowing what language you are parsing is more than an annoyance. We can call a language "well-behaved for PEG" if the PEG spec delivers exactly the language the BNF describes.

Which languages are are well-behaved for PEG? According to Mascarenhas et al, 2013, the LL(1) languages are well-behaved. (The LL(1) languages are the languages a top-down parser can parse based on at most one character of input.) Syntax-driven parsers for LL(1) have been around for much longer than PEG -- one such parser is described in the first paper to describe recursive descent (Peter Lucas, 1961). But most practical languages are not LL(1). Redziejowski 2013 and Redziejowski 2014 seek to extend this result by defining the language class LL(1p) -- those top-down languages with one "parsing procedure" of lookahead. The LL(1p) languages are also well-behaved for PEG.

Mascarenhas et al, 2013 also look at a different approach -- instead of writing a PEG specification and trying to keep it well-behaved, they look at taking languages from larger top-down classes and translating them to PEG. I don't know of any followup, but it's possible this approach could produce well-behaved top-down parsers which are an improvement over direct-from-PEG parsing. But for those who are open to leaving top-down parsing behind, a parser which handles languages in all these classes and more is already available.


In this post, I have adopted the point of view of programmers using PEG, or thinking of doing so. My own belief in this matter is that very few programmers should want to bother with the issues I've just described. My reason for this is the Marpa parser -- a general BNF Earley-driven parser that

  • has an implementation you can use today;
  • allows the application to combine syntax-driven parsing with custom procedural logic;
  • makes available full, left-eidetic knowledge of the parse to the procedural logic;
  • and parses a vast class of grammars in linear time, including all the LR-regular grammars.

The LR-regular grammars include the LR(k) and LL(k) grammars for all k. LR-regular includes all the languages which are well-behaved under PEG, and all of those that Mascarenhas et al, 2013 consider translating into PEG.


Comments on this post can be made in Marpa's Google group, or on our IRC channel: #marpa at freenode.net. To learn more about Marpa, there's the official web site maintained by Ron Savage. I also have a Marpa web site.

Perlgeek.de : CPAN Pull Request Challenge: A call to the CPAN authors

The 2015 CPAN Pull Request Challenge is ramping up, and so far nearly two hundred volunteers have signed up, pledging to make one pull request for a CPAN distribution for each month of the year.

So here's a call to the all the CPAN authors: please be supportive, and if you don't like for your CPAN distributions to be part of the challenge, please send an email to neil at bowers dot com, stating your PAUSE ID and the fact that you want to be excluded.

How to be supportive? The first step is to act on pull requests. If you don't have time for a review, please say so; getting some response, even if it's "it'll be some time 'till I get around to reviewing this" is much better than none.

The volunteers have varied backgrounds; some are seasoned veterans, others are beginners who will make their first contribution to Open Source. So please be patient and encouraging.

If you have specific requirements for contributions, add a file called CONTRIBUTING or CONTRIBUTING.md to your github repositories where you state those requirements.

And of course, be civil. But that goes without saying, right? :-)

(And to those CPAN authors who haven't done it yet: put your distributions on github, so that you're not left out of the fun!

Happy New Year everybody, and have a great deal of fun!

See also: Resources for the CPAN Pull Request Challenge.

Dave's Free Press: Journal: Devel::CheckLib can now check libraries' contents

Ocean of Awareness: Fast handy languages

Back around 1980, I had access to UNIX and a language I wanted to parse. I knew that UNIX had all the latest CS tools. So I expected to type in my BNF and "Presto, Language!".

Not so easy, I was told. Languages were difficult things created with complex tools written by experts who understood the issues. I recall thinking that, while English had a syntax that is as hard as they come, toddlers manage to parse it just fine. But experts are experts, and more so at second-hand.

I was steered to an LALR-based parser called yacc. (Readers may be more familiar with bison, a yacc successor.) LALR had extended the class of quickly parseable grammars a bit beyond recursive descent. But recursive descent was simple in principle, and its limits were easy to discover and work around. LALR, on the hand, was OK when it worked, but figuring out why it failed when it failed was more like decryption than debugging, and this was the case both with parser development and run-time errors. I soon gave up on yacc and found another way to solve my problem.

Few people complained about yacc on the Internet. If you noise it about that you are unable to figure out how to use what everybody says is the state-of-the-art tool, the conclusions drawn may not be the ones you want. But my experience seems to have been more than common.

LALR's claim to fame was that it was the basis of the industry-standard C compiler. Over three decades, its maintainers suffered amid the general silence. But by 2006, they'd had enough. GCC (the new industry standard) ripped its LALR engine out. By then the trend back to recursive descent was well underway.

A surprise discovery

Back in the 1970's, there had been more powerful alternatives to LALR and recursive descent. But they were reputed to be slow.

For some applications slow is OK. In 2007 I decided that a parsing tool that parsed all context-free languages at state-of-the-art speeds, slow or fast as the case might be, would be a useful addition to programmer toolkits. And I ran into a surprise.

Hidden in the literature was an amazing discovery -- an 1991 article by Joop Leo that described how to modify Earley's algorithm to be fast for every language class in practical use. (When I say "fast" in this article, I will mean "linear".) Leo's article had been almost completely ignored -- my project (Marpa) would become its first practical implementation.

Second-order languages

The implications of Leo's discovery go well beyond speed. If you can rely on the BNF that you write always producing a practical parser, you can auto-generate your language. In fact, you can write languages which write languages.

Which languages are fast?

The Leo/Earley algorithm is not fast for every BNF-expressible language. BNF is powerful, and you can write exponentially ambiguous languages in it. But programmers these days mostly care about unambiguous languages -- we are accustomed to tools and techniques that parse only a subset of these.

As I've said, Marpa is fast for every language class in practical use today. Marpa is almost certainly fast for any language that a modern programmer has in mind. Unless you peek ahead at the hints I am about to give you, in fact, it is actually hard to write an unambiguous grammar that goes non-linear on Marpa. Simply mixing up lots of left, right and middle recursions will not be enough to make an unambiguous grammar go non-linear. You will also need to violate a rule in the set that I am about to give you.

To guarantee that Marpa is fast for your BNF language, follow three rules:

  • Rule 1: Your BNF must be unambiguous.
  • Rule 2: Your BNF must have no "unmarked" middle recursions.
  • Rule 3: All of the right-recursive symbols in your BNF must be dedicated to right recursion.

Rule 3 turns out to be very easy to obey. I discuss it in detail in the next section, which will be about how to break these rules and get away with it.

Before we do that, let's look at what an "unmarked" middle recursion is. Here's an example of a "marked" middle recursion:

       M ::= 'b'
       M ::= 'a' M 'a'

Here the "b" symbol is the marker. This marked middle recursion generates sequences like

       a b a
       a a b a a

Now for an "unmarked" middle recursion:

       M ::= 'a' 'a'
       M ::= 'a' M 'a'

This unmarked middle recursion generates sequences like

       a a
       a a a a
       a a a a a a

In this middle recursion there is no marker. To know where the middle is, you have to scan all the way to the end, and then count back.

A rule of thumb is that if you can "eyeball" the middle of a long sequence, the recursion is marked. If you can't, it is unmarked. Unfortunately, we can't characterize exactly what a marker must look like -- a marker can encode the moves of a Turing machine, so marker detection is undecidable.

How to get away with breaking the rules

The rules about ambiguity and recursions are "soft". If you only use limited ambiguity and keep your rule-breaking recursions short, your parser will stay fast.

Above, I promised to explain rule 3, which insisted that a right recursive symbol be "dedicated". A right recursive symbol is "dedicated" if it appears only as the recursive symbol in a right recursion. If your grammar is unambiguous, but you've used an "undedicated" right-recursive symbol, that is easy to fix. Just rewrite the grammar, replacing the "undedicated" symbol with two different symbols. Dedicate one of the two to the right recursion, and use the other symbol everywhere else.

When NOT to use Marpa

The languages I have described as "fast" for Marpa include all those in practical use and many more. But do you really want to use Marpa for all of them? Here are four cases for which Marpa is probably not your best alternative.

The first case: a language that parses easily with a regular expression. The regular expression will be much faster. Don't walk away from a good thing.

The second case: a language that is easily parsed using a single loop and some state that fits into constant space. This parser might be very easy to write and maintain. If you are using a much slower higher level language, Marpa's optimized C language may be a win on CPU speed. But, as before, if you have a good thing, don't walk away from it.

The third case: a variation on the second. Here your single loop might be getting out of hand, making you yearn for the syntax-driven convenience of Marpa, but your state still fits into constant space. In its current implementation, Marpa keeps all of its parse tables forever, so Marpa does not parse in constant space. Keeping the tables allows Marpa to deal with the full structure of its input, in a way that a SAX-ish approaches cannot. But if space requirements are an issue, and your application allows a simplified constant-space approach, Marpa's power and convenience may not be enough to make up for that.

The fourth case: a language that

  • is very small;
  • changes slowly or not at all, and does not grow in complexity;
  • merits careful hand-optimization, and has available the staff to do it;
  • merits and has available the kind of on-going support that will keep your code optimized under changing circumstances; and
  • is easily parseable via recursive descent:

It is rare that all of these are the case, but when that happens, recursive descent is often preferable to Marpa. Lua and JSON are two languages which meet the above criteria. In Lua's case, it targets platforms with very restricted memories, which is an additional reason to prefer recursive descent -- Marpa has a relatively large footprint.

It was not good luck that made both Lua and JSON good targets for recursive descent -- they were designed around its limits. JSON is a favorite test target of Marpa for just these reasons. There are carefully hand-optimized C language parsers for us to benchmark against.

We get closer and closer, but Marpa will never beat small hand-optimized JSON parsers in software. However, while recursive descent is a technique for hand-writing parsers, Marpa is a mathematical algorithm. Someday, instructions for manipulating Earley items could be implemented directly in silicon. When and if that day comes, Earley's algorithm will beat recursive descent even at parsing the grammars that were designed for it.


Comments on this post can be made in Marpa's Google group, or on our IRC channel: #marpa at freenode.net. To learn more about Marpa, there's the official web site maintained by Ron Savage. I also have a Marpa web site.

Dave's Free Press: Journal: I Love Github

Dave's Free Press: Journal: Palm Treo call db module

Perlgeek.de : A new Perl 6 community server - call for funding

So far, many Perl 6 developers have used feather as a generic development server. Juerd, who has genereously provided this server for us for free for many years, has announced that it will be shut down at the end of the year.

My daytime job is at a b2b IT outsourcing and hosting company called noris network, and they have agreed to sponsor the hosting/housing of a 1U 19" server in one of their state-of-the-art data centers in Nürnberg, Germany.

What's missing is the actual hardware. Some folks in the community have already agreed to participate in funding the hardware, though I have few concrete pledges.

So here is the call to action: If you want to help the Perl 6 community with a one-time donation towards a new community server, please send me an e-mail to moritz at faui2k3 dot org, specifying the amount you're willing do pledge, and whether you want to stay private as a donor. I accept money transfer by paypal and wire transfer (SWIFT). Direct hardware donations are also welcome. (Though actual money will be deferred until the final decision what hardware to buy, and thus the total amount required).

How much do we need?

Decent, used 1U servers seem to start at about 250€, though 350€ would get us a lot more bang (mostly RAM and hard disk space). And in general, the more the merrier. (Cheaper offers exist, for example on ebay, but usually they are without hard disks, so the need for extra drives makes them more expensive in total).

With more money, even beefier hardware and/or spare parts and/or a maintainance contract and/new hardware would be an option.

What do we need it for?

The main tasks for the server are:

  • Hosting websites like perl6.org and the synopses
  • Hosting infrastructure like the panda metadata server
  • Be available for smoke runs of the compilers, star distributions and module ecosystem.
  • Be available as a general development machine for people who don't have linux available and/or not enough resources to build some Perl 6 compilers on their own machines comfortably.
  • A place for IRC sessions for community memebers
  • A backup location for community services like the IRC logs, the camelia IRC eval bot etc. Those resources are currently hosted elswewhere, though having another option for hosting would be very valuable.
  • A webspace for people who want to host Perl 6-related material.
  • It is explicitly not meant as a general hosting platform, nor as a mail server.


    If the hardware we get is beefy enough, I'd like to virtualize the server into two to three components. One for hosting the perl6.org and related websites that should be rather stable, and one for the rest of the system. If resources allow it, and depending on feedback I get, maybe a third virtual system for high-risk stuff like evalbot.

    As operating system I'll install Debian Jessie (the current testing), simply because I'll end up maintaing the system, and it's the system I'm most familiar with.

Perlgeek.de : Profiling Perl 6 code on IRC

On the #perl6 IRC channel, we have a bot called camelia that executes small snippets of Perl 6 code, and prints the output that it produces. This is a pretty central part of our culture, and we use it to explain or demonstrate features or even bugs in the compiler.

Here is an example:

10:35 < Kristien> Can a class contain classes?
10:35 < Kristien> m: class A { class B { } }; say A.new.B.new
10:35 <+camelia> rakudo-moar 114659: OUTPUT«No such method 'B' for invocant of 
                 type 'A'␤  in block <unit> at /tmp/g81K8fr9eY:1␤␤»
10:35 < Kristien> :(
10:36 < raydiak> m: class A { class B { } }; say A::B.new
10:36 <+camelia> rakudo-moar 114659: OUTPUT«B.new()␤»

Yesterday and today I spent some time teaching this IRC bot to not only run the code, but optionally also run it through a profiler, to make it possible to determine where the virtual machine spends its time running the code. an example:

12:21 < moritz> prof-m: Date.today for ^100; say "done"
12:21 <+camelia> prof-m 9fc66c: OUTPUT«done␤»
12:21 <+camelia> .. Prof: http://p.p6c.org/453bbe

The Rakudo Perl 6 Compiler on the MoarVM backend has a profile, which produces a fancy HTML + Javascript page, and this is what is done. It is automatically uploaded to a webserver, producing this profile.

Under the hood, it started with a patch that makes it possible to specify the output filename for a profile run, and another one to clear up the fallout from the previous patch.

Then came the bigger part: setting up the Apache virtual host that serves the web files, including a restricted user that only allows up- and downloads via scp. Since the IRC bot can execute arbitrary code, it is very likely that an attacker can steal the private SSH keys used for authentication against the webserver. So it is essential that if those keys are stolen, the attacker can't do much more than uploading more files.

I used rssh for this. It is the login shell for the upload user, and configured to only allow scp. Since I didn't want the attacker to be able to modify the authorized_keys file, I configured rssh to use a chroot below the home directory (which sadly in turn requires a setuid-root wrapper around chroot, because ordinary users can't execute it. Well, nothing is perfect).

Some more patching and debugging later, the bot was ready.

The whole thing feels a bit bolted on; if usage warrants it, I'll see if I can make the code a bit prettier.

Perlgeek.de : YAPC Europe 2013 Day 2

The second day of YAPC Europe was enjoyable and informative.

I learned about ZeroMQ, which is a bit like sockets on steriods. Interesting stuff. Sadly Design decisions on p2 didn't quite qualify as interesting.

Matt's PSGI archive is a project to rewrite Matt's infamous script archive in modern Perl. Very promising, and a bit entertaining too.

Lunch was very tasty, more so than the usual mass catering. Kudos to the organizers!

After lunch, jnthn talked about concurrency, parallelism and asynchrony in Perl 6. It was a great talk, backed by great work on the compiler and runtime. Jonathans talk are always to be recommended.

I think I didn't screw up my own talk too badly, at least the timing worked fine. I just forgot to show the last slide. No real harm done.

I also enjoyed mst's State of the Velociraptor, which was a summary of what went on in the Perl world in the last year. (Much better than the YAPC::EU 2010 talk with the same title).

The Lightning talks were as enjoyable as those from the previous day. So all fine!

Next up is the river cruise, I hope to blog about that later on.

Perlgeek.de : The REPL trick

A recent discussion on IRC prompted me to share a small but neat trick with you.

If there are things you want to do quite often in the Rakudo REPL (the interactive "Read-Evaluate-Print Loop"), it makes sense to create a shortcut for them. And creating shortcuts for often-used stuff is what programming languages excel at, so you do it right in Perl module:

use v6;
module REPLHelper;

sub p(Mu \x) is export {
    x.^mro.map: *.^name;

I have placed mine in $HOME/.perl6/repl.

And then you make sure it's loaded automatically:

$ alias p6repl="perl6 -I$HOME/.perl6/repl/ -MREPLHelper"
$ p6repl
> p Int
Int Cool Any Mu

Now you have a neat one-letter function which tells you the parents of an object or a type, in method resolution order. And a way to add more shortcuts when you need them.

Ocean of Awareness: Linear? Yeah right.


I have claimed that my new parser, Marpa, is linear for vast classes of grammars, going well beyond what the traditional parsers can do. But skepticism is justified. When it comes to parsing algorithms, there have been a lot of time complexity claims that are hand-wavy, misleading or just plain false. This post describes how someone, who is exercising the appropriate degree of skepticism, might conclude that believing Marpa's claims is a reasonable and prudent thing to do.

Marpa's linearity claims seem to be, in comparison with the other parsers in practical use today, bold. Marpa claims linearity, not just for every class of grammar for which yacc/bison, PEG and recursive descent currently claim linearity, but for considerably more. (The mathematical details of these claims are in a section at the end.) It seems too good to be true.

Why should I believe you?

The most important thing to realize, in assessing the believability of Marpa's time complexity claims, is that they are not new. They were already proved in a long-accepted paper in the refereed literature. They are the time complexity claims proved by Joop Leo for his algorithm in 1991, over two decades ago. Marpa is derived from Leo's algorithm, and its time complexity claims are those proved for Leo's algorithm.

Above I said that Marpa's time complexity claims "seem" bold. On any objective assessment, they are in fact a bit of a yawn. The claims seem surprising only because a lot of people are unaware of Leo's results. That is, they are surprising in the same sense that someone who had avoided hearing about radio waves would be surprised to learn that he can communicate instantly with someone on the other side of the world.

So, if there's so little to prove, why does the Marpa paper have proofs? In Marpa, I made many implementation decisions about, and some changes to, the Leo/Earley algorithm. None of my changes produced better time complexity results -- my only claim is that I did not change the Leo/Earley algorithm in a way that slowed it down. To convince myself of this claim, I reworked the original proofs of Leo and Earley, changing them to reflect my changes, and demonstrated that the results that Leo had obtained still held.

Proofs of this kind, which introduce no new mathematical techniques, but simply take a previous result and march from here to there by well-know means, are called "tedious". In journals, where there's a need to conserve space, they are usually omitted, especially if, as is the case with Marpa's time complexity proofs, the results are intuitively quite plausible.

Getting from plausible to near-certain

So let's say you are not going to work through every line of Marpa's admittedly tedious proofs. We've seen that the results are intuitively plausible, as long as you don't reject the previous literature. But can we do better than merely "plausible"?

As an aside, many people misunderstand the phrase "mathematically proven", especially as it applies to branches of math like parsing theory. The fact is that proofs in papers often contain errors. Usually these are minor, and don't affect the result. On the other hand, Jay Earley's paper, while one of the best Computer Science papers ever published, also contained a very serious error. And this error slipped past his Ph.D. committee and his referees. Mathematical arguments and proofs do not allow us to achieve absolute certainty. They can only improve the degree of certainty.

There's a second way to dramatically increase your degree of conviction in Marpa's linearity claims, and it is quite simple. Create examples of problematic grammars, run them and time them. This is not as satisfying as a mathematical proof, because no set of test grammars can be exhaustive. But if you can't find a counter-example to Marpa's linearity claims among the grammars of most interest to you, that should help lift your level of certainty to "certain for all practical purposes".

Much of this increase in certainty can be achieved without bothering to run your own tests. Marpa is in wide use at this point. If Marpa was going quadratic on grammars for which it claimed to be linear, and these were grammars of practical interest, that would very likely have been noticed by now.

I'm still not convinced

Let's suppose all this has not brought you to the level of certainty you need to use Marpa. That means the reasonable thing is to continue to struggle to work with the restrictions of the traditional algorithms, right? No, absolutely not.

OK, so you don't believe that Marpa preserves the advances in power and speed made by Leo. Does that mean that parsers have to stay underpowered? No, it simply means that there should be a more direct implementation of Leo's 1991, bypassing Marpa.

But if you are looking for an implementation of Leo's 1991 algorithm, I think you may end up coming back to Marpa as the most reasonable choice. Marpa's additional features include the ability to use custom, procedural logic, as you can with recursive descent. And Marpa has worked out a lot of the implementation details for you.


Comments on this post can be made in Marpa's Google group, or on our IRC channel: #marpa at freenode.net. To learn more about Marpa, there's the official web site maintained by Ron Savage. I also have a Marpa web site.

Appendix: Some technical details

Above I talked about algorithms, classes of grammars and their linearity claims. I didn't give details because most folks aren't interested. For those who are, they are in this section.

yacc is linear for a grammar class called LALR, which is a subset of another grammar class called LR(1). If you are willing to hassle with GLR, bison claims linearity for all of LR(1). Recursive descent is a technique, not an algorithm, but it is top-down with look-ahead, and therefore can be seen as some form of LL(k), where k depends on how it is implemented. In practice, I suspect k is never much bigger than 3, and usually pretty close to 1. With packratting, PEG can be made linear for everything it parses but there is a catch -- only in limited cases do you know what language your PEG grammar actually parses. In current practice, that means your PEG grammar must be LL(1). Some of the PEG literature looks at techniques for extending this as far as LL-regular, but there are no implementations, and it remains to be seen if the algorithms described are practical.

The Marpa paper contains a proof, based on a proof of the same claim by Joop Leo, that Marpa is linear for LR-regular grammars. The LR-regular grammars include the LR(k) grammars for every k. So Marpa is linear for LR(1), LR(2), LR(8675309), etc. LR-regular also includes LL-regular. So every class of grammar under discussion in the PEG literature is already parsed in linear time by Marpa. From this, it is also safe to conclude that, if a grammar can be parsed by anything reasonably described as recursive descent, it can be parsed in linear time by Marpa.

Perlgeek.de : New Perl 6 community server now live, accepting signups

The new Perl 6 community server is now alive and kicking.

As planned, I've set up KVM virtualization, and so far there are two guest systems. hack.p6c.org is meant for general Perl 6 development activity (which also includes irssi/weechat sessions), and is equipped with 20GB RAM to handle multiple concurrent rakudo-jvm compilations :-). It runs a pretty bare-bones Debian Jessie.

Update: there is now a website for the new server.

www.p6c.org is the web server where I plan to host perl6.org and related (sub-)domains. It's not as beefy as hack, but sufficiently large to compile and run Rakudo, in preparation for future Perl 6-based web hosting. Currently I'm running a copy of several perl6.org subdomains on it (with the domain name p6c instead of perl6 for test purposes); the plan is to switch the perl6.org DNS over once all of the websites have been copied/migrated.

If you have a Perl 6 related use for a shell account or for serving websites, please request an account by email (moritz.lenz@gmail.com) or IRC (moritz on freenode and magnet), including:

  1. Your desired username
  2. What you want to do on the machine(s) (not necessary for #perl6 regulars)
  3. Which of the machine(s) you need access to
  4. Optionally an openssh public key
  5. Whether you'd be willing to help a bit with sysadmin tasks (mostly apt-get update && apt-get dist-upgrade, restarting hung services, killing huge processes)
  6. Software you need installed (it's OK to not know this up-front)

Note that feather.perl6.nl will shut down soon (no fixed date yet, but "end of 2014" is expected), so if you rely on feather now, you should consider migrating to the new server.

The code of conduct is pretty simple:

  1. Be reasonable in your resource usage.
  2. Use technical means to limit your resource usage so that it doesn't accidentally explode (ulimit comes to mind).
  3. Limit yourself to legal and Perl 6-related use cases (no warez).
  4. Help your fellow hackers.

The standard disclaimer applies:

  • Expect no privacy. There will potentially be many root users, who could all read your files and memory.
  • There are no promises of continued service or even support. Your account can be terminated without notice.
  • Place of jurisdiction in Nürnberg, Germany. You have to comply with German law while using the server. (Note that this puts pretty high standards on privacy for any user data you collect, including from web applications). It's your duty to inform yourself about the applicable laws. Illegal activities will be reported to the authorities.

With all that said, happy hacking!.

Dave's Free Press: Journal: Graphing tool

Dave's Free Press: Journal: Travelling in time: the CP2000AN

Dave's Free Press: Journal: XML::Tiny released

Dave's Free Press: Journal: YAPC::Europe 2007 report: day 1

Dave's Free Press: Journal: Thanks, Yahoo!

Dave's Free Press: Journal: YAPC::Europe 2007 report: day 2

Ocean of Awareness: Parsing: Top-down versus bottom-up

Comparisons between top-down and bottom-up parsing are often either too high-level or too low-level. Overly high-level treatments reduce the two approaches to buzzwords, and the comparison to a recitation of received wisdom. Overly low-level treatments get immersed in the minutiae of implementation, and the resulting comparison is as revealing as placing two abstractly related code listings side by side. In this post I hope to find the middle level; to shed light on why advocates of bottom-up and top-down parsing approaches take the positions they do; and to speculate about the way forward.

Top-down parsing

The basic idea of top-down parsing is as brutally simple as anything in programming: Starting at the top, we add pieces. We do this by looking at the next token and deciding then and there where it fits into the parse tree. Once we've looked at every token, we have our parse tree.

In its purest form, this idea is too simple for practical parsing, so top-down parsing is almost always combined with lookahead. Lookahead of one token helps a lot. Longer lookaheads are very sparsely used. They just aren't that helpful, and since the number of possible lookaheads grows exponentially, they get very expensive very fast.

Top-down parsing has an issue with left recursion. It's straightforward to see why. Take an open-ended expression like

    a + b + c + d + e + f + [....]

Here the plus signs continue off to the right, and adding any of them to the parse tree requires a dedicated node which must be above the node for the first plus sign. We cannot put that first plus sign into a top-down parse tree without having first dealt with all those plus signs that follow it. For a top-down strategy, this is a big, big problem.

Even in the simplest expression, there is no way of counting the plus signs without looking to the right, quite possibly a very long way to the right. When we are not dealing with simple expressions, this rightward-looking needs to get sophisticated. There are ways of dealing with this difficulty, but all of them share one thing in common -- they are trying to make top-down parsing into something that it is not.

Advantages of top-down parsing

Top-down parsing does not look at the right context in any systematic way, and in the 1970's it was hard to believe that top-down was as good as we can do. (It's not all that easy to believe today.) But its extreme simplicity is also top-down parsing's great strength. Because a top-down parser is extremely simple, it is very easy to figure out what it is doing. And easy to figure out means easy to customize.

Take another of the many constructs incomprehensible to a top-down parser:

    2 * 3 * 4 + 5 * 6

How do top-down parsers typically handle this? Simple: as soon as they realize they are faced with an expression, they give up on top-down parsing and switch to a special-purpose algorithm.

These two properties -- easy to understand and easy to customize -- have catapulted top-down parsing to the top of the heap. Behind their different presentations, combinator parsing, PEG, and recursive descent are all top-down parsers.

Bottom-up parsing

Few theoreticians of the 1970's imagined that top-down parsing might be the end of the parsing story. Looking to the right in ad hoc ways clearly does help. It would be almost paradoxical if there was no systematic way to exploit the right context.

In 1965, Don Knuth found an algorithm to exploit right context. Knuth's LR algorithm was, like top-down parsing as I have described it, deterministic. Determinism was thought to be essential -- allowing more than one choice easily leads to a combinatorial explosion in the number of possibilities that have to be considered at once. When parsers are restricted to dealing with a single choice, it is much easier to guarantee that they will run in linear time.

Knuth's algorithm did not try to hang each token from a branch of a top-down parse tree as soon as it was encountered. Instead, Knuth suggested delaying that decision. Knuth's algorithm collected "subparses".

When I say "subparses" in this discussion, I mean pieces of the parse that contain all the decisions necessary to construct the part of the parse tree that is below them. But subparses do not contain any decisions about what is above them in the parse tree. Put another way, subparses know who they are, but not where they belong.

Subparses may not know where they belong, but knowing who they are is enough for them to be assembled into larger subparses. And, if we keep assembling the subparses, eventually we will have a "subparse" that is the full parse tree. And at that point we will know both who everyone is and where everyone belongs.

Knuth's algorithm stored subparses by shifting them onto a stack. The operation to do this was called a "shift". (Single tokens of the input are treated as subparses with a single node.) When there was enough context to build a larger subparse, the algorithm popped one or more subparses off the stack, assembled a larger subparse, and put the resulting subparse back on the stack. This operation was called a "reduce", based on the idea that its repeated application eventually "reduces" the parse tree to its root node.

In handling the stack, we will often be faced with choices. One kind of choice is between using what we already have on top of the stack to assemble a larger subparse; or pushing more subparses on top of the stack instead ("shift/reduce"). When we decide to reduce, we may encounter the other kind of choice -- we have to decide which rule to use ("reduce/reduce").

Like top-down parsing, bottom-up parsing is usually combined with lookahead. For the same lookahead, a bottom-up parser parses everything that a top-down parser can handle, and more.

Formally, Knuth's approach is now called shift/reduce parsing. I want to demonstrate why theoreticians, and for a long time almost everybody else as well, was so taken with this method. I'll describe how it works on some examples, including two very important ones that stump top-down parsers: arithmetic expressions and left-recursion. My purpose here is bring to light the basic concepts, and not to guide an implementor. There are excellent implementation-oriented presentations in many other places. The Wikipedia article, for example, is excellent.

Bottom-up parsing solved the problem of left recursion. In the example from above,

    a + b + c + d + e + f + [....]

we simply build one subparse after another, as rapidly as we can. In the terminology of shift/reduce, whenever we can reduce, we do. Eventually we will have run out of tokens, and will have reduced until there is only one element on the stack. That one remaining element is the subparse that is also, in fact, our full parse tree.

The top-down parser had a problem with left recursion precisely because it needed to build top-down. To build top-down, it needed to know about all the plus signs to come, because these needed to be fitted into the parse tree above the current plus sign. But when building bottom-up, we don't need to know anything about the plus signs that will be above the current one in the parse tree. We can afford to wait until we encounter them.

But if working bottom-up solves the left recursion problem, doesn't it create a right recursion problem? In fact, for a bottom-up parser, right recursion is harder, but not much. That's because of the stack. For a right recursion like this:

    a = b = c = d = e = f = [....]

we use a strategy opposite to the one we used for the left recursion. For left recursion, we reduced whenever we could. For right recursion, when we have a choice, we always shift. This means we will immediately shift the entire input onto the stack. Once the entire input is on the stack, we have no choice but to start reducing. Eventually we will reduce the stack to a single element. At that point, we are done. Essentially, what we are doing is exactly what we did for left recursion, except that we use the stack to reverse the order.

Arithmetic expressions like

    2 * 3 * 4 + 5 * 6

require a mixed strategy. Whenever we have a shift/reduce choice, and one of the operators is on the stack, we check to see if the topmost operator is a multiply or an addition operator. If it is a multiply operator, we reduce. In all other cases, if there is a shift/reduce choice, we shift.

In the discussion above, I have pulled the strategy for making stack decisions (shift/reduce and reduce/reduce) out of thin air. Clearly, if bottom-up parsing was going to be a practical parsing algorithm, the stack decisions would have to be made algorithmically. In fact, discovering a practical way to do this was a far from trivial task. The solution in Knuth's paper was considered (and apparently intended) to be mathematically provocative, rather than practical. But by 1979, it was thought a practical way to make stack decisions had been found and yacc, a parser generator based on bottom-up parsing, was released. (Readers today may be more familiar with yacc's successor, bison.)

The fate of bottom-up parsing

With yacc, it looked as if the limitations of top-down parsing were past us. We now had a parsing algorithm that could readily and directly parse left and right recursions, as well as arithmetic expressions. Theoreticians thought they'd found the Holy Grail.

But not all of the medieval romances had happy endings. And as I've described elsewhere, this story ended badly. Bottom-up parsing was driven by tables which made the algorithm fast for correct inputs, but unable to accurately diagnose faulty ones. The subset of grammars parsed was still not quite large enough, even for conservative language designers. And bottom-up parsing was very unfriendly to custom hacks, which made every shortcoming loom large. It is much harder to work around a problem in a bottom-up parser than than it is to deal with a similar shortcoming in a top-down parser. After decades of experience with bottom-up parsing, top-down parsing has re-emerged as the algorithm of choice.


For many, the return to top-down parsing answers the question that we posed earlier: "Is there any systematic way to exploit right context when parsing?" So far, the answer seems to be a rather startling "No". Can this really be the end of the story?

It would be very strange if the best basic parsing algorithm we know is top-down. Above, I described at some length some very important grammars that can be parsed bottom-up but not top-down, at least not directly. Progress like this seems like a lot to walk away from, and especially to walk back all the way to what is essentially a brute force algorithm. This perhaps explains why lectures and textbooks persist in teaching bottom-up parsing to students who are very unlikely to use it. Because the verdict from practitioners seems to be in, and likely to hold up on appeal.

Fans of deterministic top-down parsing, and proponents of deterministic bottom-up parsing share an assumption: For a practical algorithm to be linear, it has to be deterministic. But is this actually the case?

It's not, in fact. To keep bottom-up parsing deterministic, we restricted ourselves to a stack. But what if we track all possible subpieces of parses? For efficiency, we can link them and put them into tables, making the final decisions in a second pass, once the tables are complete. (The second pass replaces the stack-driven see-sawing back and forth of the deterministic bottom-up algorithm, so it's not an inefficiency.) Jay Earley in 1968 came up with an algorithm to do this, and in 1991 Joop Leo added a memoization to Earley's algorithm which made it linear for all deterministic grammars.

The "deterministic grammars" are exactly the bottom-up parseable grammars with lookahead -- the set of grammars parsed by Knuth's algorithm. So that means the Earley/Leo algorithm parses, in linear time, everything that a deterministic bottom-up parser can parse, and therefore every grammar that a deterministic top-down parser can parse. (In fact, the Earley/Leo algorithm is linear for a lot of ambiguous grammars as well.)

Top-down parsing had the advantage that it was easy to know where you are. The Earley/Leo algorithm has an equivalent advantage -- its tables know where it is, and it is easy to query them programmatically. In 2010, this blogger modified the Earley/Leo algorithm to have the other big advantage of top-down parsing: The Marpa algorithm rearranges the Earley/Leo parse engine so that we can stop it, perform our own logic, and restart where we left off. A quite useable parser based on the Marpa algorithm is available as open source.


Comments on this post can be made in Marpa's Google group, or on our IRC channel: #marpa at freenode.net. To learn more about Marpa, there's the official web site maintained by Ron Savage. I also have a Marpa web site.

Perlgeek.de : YAPC Europe 2013 Day 3

The second day of YAPC Europe climaxed in the river boat cruise, Kiev's version of the traditional conference dinner. It was a largish boat traveling on the Dnipro river, with food, drinks and lots of Perl folks. Not having fixed tables, and having to get up to fetch food and drinks led to a lot of circulation, and thus meeting many more people than at traditionally dinners. I loved it.

Day 3 started with a video message from next year's YAPC Europe organizers, advertising for the upcoming conference and talking a bit about the oppurtunities that Sofia offers. Tempting :-).

Monitoring with Perl and Unix::Statgrab was more about the metrics that are available for monitoring, and less about doing stuff with Perl. I was a bit disappointed.

The "Future Perl Versioning" Discussion was a very civilized discussion, with solid arguments. Whether anybody changed their minds remain to be seen.

Carl Mäsak gave two great talks: one on reactive programming, and one on regular expressions. I learned quite a bit in the first one, and simply enjoyed the second one.

After the lunch (tasty again), I attended Jonathan Worthington's third talk, MoarVM: a metamodel-focused runtime for NQP and Rakudo. Again this was a great talk, based on great work done by Jonathan and others during the last 12 months or so. MoarVM is a virtual machine designed for Perl 6's needs, as we understand them now (as opposed to parrot, which was designed towards Perl 6 as it was understood around 2003 or so, which is considerably different).

How to speak manager was both amusing and offered a nice perspective on interactions between managers and programmers. Some of this advice assumed a non-tech-savy manager, and thus didn't quite apply to my current work situation, but was still interesting.

I must confess I don't remember too much of the rest of the talks that evening. I blame five days of traveling, hackathon and conference taking their toll on me.

The third session of lightning talks was again an interesting mix, containing interesting technical tidbits, the usual "we are hiring" slogans, some touching and thoughtful moments, and finally a song by Piers Cawley. He had written the lyrics in the previous 18 hours (including sleep), to (afaict) a traditional irish song. Standing up in front of ~300 people and singing a song that you haven't really had time to practise takes a huge amount of courage, and I admire Piers both for his courage and his great performance. I hope it was recorded, and makes it way to the public soon.

Finally the organizers spoke some closing words, and received their well-deserved share of applause.

As you might have guess from this and the previous blog posts, I enjoyed this year's YAPC Europe very much, and found it well worth attending, and well organized. I'd like to give my heart-felt thanks to everybody who helped to make it happen, and to my employer for sending me there.

This being only my second YAPC, I can't make any far-reaching comparisons, but compared to YAPC::EU 2010 in Pisa I had an easier time making acquaintances. I cannot tell what the big difference was, but the buffet-style dinners at the pre-conference meeting and the river boat cruise certainly helped to increase the circulation and thus the number of people I talked to.

Dave's Free Press: Journal: YAPC::Europe 2007 travel plans

Perlgeek.de : A small regex optimization for NQP and Rakudo

Recently I read the course material of the Rakudo and NQP Internals Workshop, and had an idea for a small optimization for the regex engine. Yesterday night I implemented it, and I'd like to walk you through the process.

As a bit of background, the regex engine that Rakudo uses is actually implemented in NQP, and used by NQP too. The code I am about to discuss all lives in the NQP repository, but Rakudo profits from it too.

In addition one should note that the regex engine is mostly used for parsing grammar, a process which involves nearly no scanning. Scanning is the process where the regex engine first tries to match the regex at the start of the string, and if it fails there, moves to the second character in the string, tries again etc. until it succeeds.

But regexes that users write often involve scanning, and so my idea was to speed up regexes that scan, and where the first thing in the regex is a literal. In this case it makes sense to find possible start positions with a fast string search algorithm, for example the Boyer-Moore algorithm. The virtual machine backends for NQP already implement that as the index opcode, which can be invoked as start = index haystack, needle, startpos, where the string haystack is searched for the substring needle, starting from position startpos.

From reading the course material I knew I had to search for a regex type called scan, so that's what I did:

$ git grep --word scan
3rdparty/libtommath/bn_error.c:   /* scan the lookup table for the given message
3rdparty/libtommath/bn_mp_cnt_lsb.c:   /* scan lower digits until non-zero */
3rdparty/libtommath/bn_mp_cnt_lsb.c:   /* now scan this digit until a 1 is found
3rdparty/libtommath/bn_mp_prime_next_prime.c:                   /* scan upwards 
3rdparty/libtommath/changes.txt:       -- Started the Depends framework, wrote d
src/QRegex/P5Regex/Actions.nqp:                     QAST::Regex.new( :rxtype<sca
src/QRegex/P6Regex/Actions.nqp:                     QAST::Regex.new( :rxtype<sca
src/vm/jvm/QAST/Compiler.nqp:    method scan($node) {
src/vm/moar/QAST/QASTRegexCompilerMAST.nqp:    method scan($node) {
Binary file src/vm/moar/stage0/NQPP6QRegexMoar.moarvm matches
Binary file src/vm/moar/stage0/QASTMoar.moarvm matches
src/vm/parrot/QAST/Compiler.nqp:    method scan($node) {
src/vm/parrot/stage0/P6QRegex-s0.pir:    $P5025 = $P5024."new"("scan" :named("rx
src/vm/parrot/stage0/QAST-s0.pir:.sub "scan" :subid("cuid_135_1381944260.6802") 
src/vm/parrot/stage0/QAST-s0.pir:    push $P5004, "scan"

The binary files and .pir files are generated code included just for bootstrapping, and not interesting for us. The files in 3rdparty/libtommath are there for bigint handling, thus not interesting for us either. The rest are good matches: src/QRegex/P6Regex/Actions.nqp is responsible for compiling Perl 6 regexes to an abstract syntax tree (AST), and src/vm/parrot/QAST/Compiler.nqp compiles that AST down to PIR, the assembly language that the Parrot Virtual Machine understands.

So, looking at src/QRegex/P6Regex/Actions.nqp the place that mentions scan looked like this:

    $block<orig_qast> := $qast;
    $qast := QAST::Regex.new( :rxtype<concat>,
                 QAST::Regex.new( :rxtype<scan> ),
                      ?? QAST::Regex.new( :rxtype<pass> )
                      !! (nqp::substr(%*RX<name>, 0, 12) ne '!!LATENAME!!'
                            ?? QAST::Regex.new( :rxtype<pass>, :name(%*RX<name>) )
                            !! QAST::Regex.new( :rxtype<pass>,
                                       :name(nqp::substr(%*RX<name>, 12)),

So to make the regex scan, the AST (in $qast) is wrapped in QAST::Regex.new(:rxtype<concat>,QAST::Regex.new( :rxtype<scan> ), $qast, ...), plus some stuff I don't care about.

To make the optimization work, the scan node needs to know what to scan for, if the first thing in the regex is indeed a constant string, aka literal. If it is, $qast is either directly of rxtype literal, or a concat node where the first child is a literal. As a patch, it looks like this:

--- a/src/QRegex/P6Regex/Actions.nqp
+++ b/src/QRegex/P6Regex/Actions.nqp
@@ -667,9 +667,21 @@ class QRegex::P6Regex::Actions is HLL::Actions {
     self.store_regex_nfa($code_obj, $block, QRegex::NFA.new.addnode($qast))
     self.alt_nfas($code_obj, $block, $qast);
+    my $scan := QAST::Regex.new( :rxtype<scan> );
+    {
+        my $q := $qast;
+        if $q.rxtype eq 'concat' && $q[0] {
+            $q := $q[0]
+        }
+        if $q.rxtype eq 'literal' {
+            nqp::push($scan, $q[0]);
+            $scan.subtype($q.subtype);
+        }
+    }
     $block<orig_qast> := $qast;
     $qast := QAST::Regex.new( :rxtype<concat>,
-                 QAST::Regex.new( :rxtype<scan> ),
+                 $scan,

Since concat nodes have always been empty so far, the code generators don't look at their child nodes, and adding one with nqp::push($scan, $q[0]); won't break anything on backends that don't support this optimization yet (which after just this patch were all of them). Running make test confirmed that.

My original patch did not contain the line $scan.subtype($q.subtype);, and later on some unit tests started to fail, because regex matches can be case insensitive, but the index op works only case sensitive. For case insensitive matches, the $q.subtype of the literal regex node would be ignorecase, so that information needs to be carried on to the code generation backend.

Once that part was in place, and some debug nqp::say() statements confirmed that it indeed worked, it was time to look at the code generation. For the parrot backend, it looked like this:

    method scan($node) {
        my $ops := self.post_new('Ops', :result(%*REG<cur>));
        my $prefix := self.unique('rxscan');
        my $looplabel := self.post_new('Label', :name($prefix ~ '_loop'));
        my $scanlabel := self.post_new('Label', :name($prefix ~ '_scan'));
        my $donelabel := self.post_new('Label', :name($prefix ~ '_done'));
        $ops.push_pirop('repr_get_attr_int', '$I11', 'self', %*REG<curclass>, '"$!from"');
        $ops.push_pirop('ne', '$I11', -1, $donelabel);
        $ops.push_pirop('goto', $scanlabel);
        $ops.push_pirop('inc', %*REG<pos>);
        $ops.push_pirop('gt', %*REG<pos>, %*REG<eos>, %*REG<fail>);
        $ops.push_pirop('repr_bind_attr_int', %*REG<cur>, %*REG<curclass>, '"$!from"', %*REG<pos>);
        self.regex_mark($ops, $looplabel, %*REG<pos>, 0);

While a bit intimidating at first, staring at it for a while quickly made clear what kind of code it emits. First three labels are generated, to which the code can jump with goto $label: One as a jump target for the loop that increments the cursor position ($looplabel), one for doing the regex match at that position ($scanlabel), and $donelabel for jumping to when the whole thing has finished.

Inside the loop there is an increment (inc) of the register the holds the current position (%*REG<pos>), that position is compared to the end-of-string position (%*REG<eos>), and if is larger, the cursor is marked as failed.

So the idea is to advance the position by one, and then instead of doing the regex match immediately, call the index op to find the next position where the regex might succeed:

--- a/src/vm/parrot/QAST/Compiler.nqp
+++ b/src/vm/parrot/QAST/Compiler.nqp
@@ -1564,7 +1564,13 @@ class QAST::Compiler is HLL::Compiler {
         $ops.push_pirop('goto', $scanlabel);
         $ops.push_pirop('inc', %*REG<pos>);
-        $ops.push_pirop('gt', %*REG<pos>, %*REG<eos>, %*REG<fail>);
+        if nqp::elems($node.list) && $node.subtype ne 'ignorecase' {
+            $ops.push_pirop('index', %*REG<pos>, %*REG<tgt>, self.rxescape($node[0]), %*REG<pos>);
+            $ops.push_pirop('eq', %*REG<pos>, -1, %*REG<fail>);
+        }
+        else {
+            $ops.push_pirop('gt', %*REG<pos>, %*REG<eos>, %*REG<fail>);
+        }
         $ops.push_pirop('repr_bind_attr_int', %*REG<cur>, %*REG<curclass>, '"$!from"', %*REG<pos>);
         self.regex_mark($ops, $looplabel, %*REG<pos>, 0);

The index op returns -1 on failure, so the condition for a cursor fail are slightly different than before.

And as mentioned earlier, the optimization can only be safely done for matches that don't ignore case. Maybe with some additional effort that could be remedied, but it's not as simple as case-folding the target string, because some case folding operations can change the string length (for example ß becomes SS while uppercasing).

After successfully testing the patch, I came up with a small, artifical benchmark designed to show a difference in performance for this particular case. And indeed, it sped it up from 647 ± 28 µs to 161 ± 18 µs, which is roughly a factor of four.

You can see the whole thing as two commits on github.

What remains to do is implementing the same optimization on the JVM and MoarVM backends, and of course other optimizations. For example the Perl 5 regex engine keeps track of minimal and maximal string lengths for each subregex, and can anchor a regex like /a?b?longliteral/ to 0..2 characters before a match of longliteral, and generally use that meta information to fail faster.

But for now I am mostly encouraged that doing a worthwhile optimization was possible in a single evening without any black magic, or too intimate knowledge of the code generation.

Update: the code generation for MoarVM now also uses the index op. The logic is the same as for the parrot backend, the only difference is that the literal needs to be loaded into a register (whose name fresh_s returns) before index_s can use it.

Dave's Free Press: Journal: Wikipedia handheld proxy

Dave's Free Press: Journal: Bryar security hole

Dave's Free Press: Journal: POD includes

Perlgeek.de : First day at YAPC::Europe 2013 in Kiev

Today was the first "real" day of YAPC Europe 2013 in Kiev. In the same sense that it was the first real day, we had quite a nice "unreal" conference day yesterday, with a day-long Perl 6 hackathon, and in the evening a pre-conference meeting a Sovjet-style restaurant with tasty food and beverages.

The talks started with a few words of welcome, and then the announcement that the YAPC Europe next year will be in Sofia, Bulgaria, with the small side note that there were actually three cities competing for that honour. Congratulations to Sofia!

Larry's traditional keynote was quite emotional, and he had to fight tears a few times. Having had cancer and related surgeries in the past year, he still does his perceived duty to the Perl community, which I greatly appreciate.

Afterwards Dave Cross talked about 25 years of Perl in 25 minutes, which was a nice walk through some significant developments in the Perl world, though a bit hasty. Maybe picking fewer events and spending a bit more time on the selected few would give a smoother experience.

Another excellent talk that ran out of time was on Redis. Having experimented a wee bit with Redis in the past month, this was a real eye-opener on the wealth of features we might have used for a project at work, but in the end we didn't. Maybe we will eventually revise that decision.

Ribasushi talked about how hard benchmarking really is, and while I was (in principle) aware of that fact that it's hard to get right, there were still several significant factors that I overlooked (like the CPU's tendency to scale frequency in response to thermal and power-management considerations). I also learned that I should use Dumbbench instead of the Benchmark.pm core module. Sadly it didn't install for me (Capture::Tiny tests failing on Mac OS X).

The Perl 6 is dead, long live Perl 5 talk was much less inflammatory than the title would suggest (maybe due to Larry touching on the subject briefly during the keynote). It was mostly about how Perl 5 is used in the presenter's company, which was mildly interesting.

After tasty free lunch I attended jnthn's talk on Rakudo on the JVM, which was (as is typical for jnthn's talk) both entertaining and taught me something, even though I had followed the project quite a bit.

Thomas Klausner's Bread::Board by example made me want to refactor the OTRS internals very badly, because it is full of the anti-patterns that Bread::Board can solve in a much better way. I think that the OTRS code base is big enough to warrant the usage of Bread::Board.

I enjoyed Denis' talk on Method::Signatures, and was delighted to see that most syntax is directly copied from Perl 6 signature syntax. Talk about Perl 6 sucking creativity out of Perl 5 development.

The conference ended with a session of lighning talks, something which I always enjoy. Many lightning talks had a slightly funny tone or undertone, while still talking about interesting stuff.

Finally there was the "kick-off party", beverages and snacks sponsored by booking.com. There (and really the whole day, and yesterday too) I not only had conversations with my "old" Perl 6 friends, but also talked with many interesting people I never met before, or only met online before.

So all in all it was a nice experience, both from the social side, and from quality and contents of the talks. Venue and food are good, and the wifi too, except when it stops working for a few minutes.

I'm looking forward to two more days of conference!

(Updated: Fixed Thomas' last name)

Dave's Free Press: Journal: cgit syntax highlighting

Ocean of Awareness: What makes a parsing algorithm successful?

What makes a parsing algorithm successful? Two factors, I think. First, does the algorithm parse a workably-defined set of grammars in linear time? Second, does it allow the application to intervene in the parse with custom code? When parsing algorithms are compared, typically neither of these gets much attention. But the successful algorithms do one or the other.

Does the algorithm parse a workably-defined set of grammars in linear time?

"Workably-defined" means more than well-defined in the mathematical sense -- the definition has to be workable. That is, the definition must be something that, with reasonable effort, a programmer can use in practice.

The algorithms in regular expression engines are workably-defined. A regular expression, in the pure sense consists of a sequence of symbols, usually shown by concatenation:

a b c

or a choice among sequences, usually shown by a vertical bar:

a | b | c

or a repetition of any of the above, typically shown with a star:


or any recursive combination of these. True, if this definition is new to you, it can take time to get used to. But vast numbers of working programming are very much "used to it", can think in terms of regular expressions, and can determine if a particular problem will yield to treatment as a regular expression, or not.

Parsers in the LALR family (yacc, bison, etc.) do not have a workably defined set of grammars. LALR is perfectly well-defined mathematically, but even experts in parsing theory are hard put to decide if a particular grammar is LALR.

Recursive descent also does not have a workably defined set of grammars. Recursive descent doesn't even have a precise mathematical description -- you can say that recursive descent is LL, but in practice LL tables are rarely used. Also in practice, the LL logic is extended with every other trick imaginable, up to and including switching to other parsing algorithms.

Does it allow the user to intervene in the parse?

It is not easy for users to intervene in the processing of a regular expression, though some implementations attempt to allow such efforts. LALR parsers are notoriously opaque. Those who maintain the LALR-driven Perl parser have tried to supplement its abilities with custom code, with results that will not encourage others making the same attempt.

Recursive descent, on the other hand, has no parse engine -- it is 100% custom code. You don't get much friendlier than that.


Regular expressions are a success, and will remain so, because the set of grammars they handle is very workably-defined. Applications using regular expressions have to take what the algorithm gives them, but what it gives them is very predictable.

For example, an application can write regular expressions on the fly, and the programmer can be confident they will run as long as they are well-formed. And it is easy to determine if the regular expression is well-formed. (Whether it actually does what you want is a separate issue.)

Recursive descent does not handle a workably-defined set of grammars, and it also has to be hand-written. But it makes up for this by allowing the user to step into the parsing process anywhere, and "get his hands dirty". Recursive descent does nothing for you, but it does allow you complete control. This is enough to make recursive descent the current algorithm of choice for major parsing projects.

As I have chronicled elsewhere, LALR was once, on highly convincing theoretical grounds, seen as the solution to the parsing problem. But while mathematically well-defined, LALR was not workably defined. And it was very hostile to applications that tried to alter, or even examine, its syntax-driven workings. After decades of trying to make it work, the profession has abandoned LALR almost totally.

What about Marpa?

Marpa has both properties: its set of grammars is workably-defined. And, while Marpa is syntax-driven like LALR and regular expressions, it also allows the user to stop the parse engine, communicate with it about the state of the parse, do her own parsing for a while, and restart the parse engine at any point she wants.

Marpa's workable definition has a nuance that the one for regular expressions does not. For regular expressions, linearity is a given -- they parse in linear time or fail. Marpa parses a much larger class of grammars, the context-free grammars -- anything that can be written in BNF. BNF is used to describe languages in standards, and is therefore itself a kind of "gold standard" for a workable definition of a set of grammars. However, Marpa does not parse everything that can be written in BNF in linear time.

Marpa linearly-parsed set of grammars is smaller than the context-free grammars, but it is still very large, and it is still workably-defined. Marpa will parse any unambiguous language in linear time, unless it contains unmarked middle recursions. An example of a "marked" middle recursion is the language described by

S ::= a S a | x

a string of which is "aaaxaaa", where the "x" marks the middle. An example of an "unmarked" middle recursion is the language described by

S ::= a S a | a

a string of which is "aaaaaaa", where nothing marks the middle, so that you don't know until the end where the middle of the recursion is. If a human can reliably find the middle by eyeball, the middle recursion is marked. If a human can't, then the middle recursion might be unmarked.

Marpa also parses a large set of unambiguous grammars linearly, and this set of grammars is also workably-defined. Marpa parses an ambiguous grammar in linear time if

  • It has no unmarked middle recursions.
  • All right recursions are unambiguous.
  • There are no cycles. A cycle occurs, for example, if there is a rule A ::= A in the grammar.
  • Marpa's level of ambiguity at any location is bounded by a constant.

The term "level of ambiguity" requires a bit of explanation. At any given location, there can be as many rules "in play" as you like, without affecting the level of ambiguity. The key question: What is the maximum number of different origins that a rule might have? (The "origin" of a rule is the location where it begins.) That is, can a rule currently in play have at most 20 different origins? Or could it have its origin at every location so far? If the maximum number of origins is 20 or any other fixed constant, the level of ambiguity is "bounded". But if the maximum number of origins keeps growing as the length of the input grows, the level of ambiguity is unbounded.

For the unambiguous case, Marpa's workable definition encompasses a much larger class of grammars, but is no more complex than that for regular expressions. If you want to extend even further, and work with ambiguous grammars, the definition remains quite workable. Of the four restrictions needed to ensure linearity, the one requiring a bounded level of ambiguity is the only one that might force you to exercise real vigliance -- once you get into ambiguity, unboundedness is easy to slip into.

As for the other three, cycles never occur in a practical grammars, and Marpa reports them, so that you simply fix them when they happen. Most recursions will be left recursions, which are unrestricted. My experience has been that, in practical grammars, unmarked middle recursions and ambiguous right recursions are not especially tempting features. If you note whenever you use a right recursion, checking that it is not ambiguous, and if you note whenever you use a middle recursion, checking that it is marked, then you will stay linear.

To learn more about Marpa, there's the official web site maintained by Ron Savage. I also have a Marpa web site.


Comments on this post can be made in Marpa's Google group, or on our IRC channel: #marpa at freenode.net.

Dave's Free Press: Journal: CPAN Testers' CPAN author FAQ

Perlgeek.de : Why is it hard to write a compiler for Perl 6?

Russian translation available; Пост доступен на сайте softdroid.net: Почему так трудно написать компилятор для Perl 6?.

Today's deceptively simple question on #perl6: is it harder to write a compiler for Perl 6 than for any other programming language?

The answer is simple: yes, it's harder (and more work) than for many other languages. The more involved question is: why?

So, let's take a look. The first point is organizational: Perl 6 isn't yet fully explored and formally specified; it's much more stable than it used to be, but less stable than, say, targeting C89.

But even if you disregard this point, and target the subset that for example the Rakudo Perl 6 compiler implements right now, or the wait a year and target the first Perl 6 language release, the point remains valid.

So let's look at some technical aspects.

Static vs. Dynamic

Perl 6 has both static and dynamic corners. For example, lexical lookups are statical, in the sense that they can be resolved at compile time. But that's not optional. For a compiler to properly support native types, it must resolve them at compile time. We also expect the compiler to notify us of certain errors at compile time, so there must be a fair amount of static analysis.

On the other hand, type annotations are optional pretty much anywhere, and methods are late bound. So the compiler must also support features typically found in dynamic languages.

And even though method calls are late bound, composing roles into classes is a compile time operation, with mandatory compile time analysis.

Mutable grammar

The Perl 6 grammar can change during a parse, for example by newly defined operators, but also through more invasive operations such as defining slangs or macros. Speaking of slangs: Perl 6 doesn't have a single grammar, it switches back and forth between the "main" language, regexes, character classes inside regexes, quotes, and all the other dialects you might think of.

Since the grammar extensions are done with, well, Perl 6 grammars, it forces the parser to be interoperable with Perl 6 regexes and grammars. At which point you might just as well use them for parsing the whole thing, and you get some level of minimally required self-hosting.

Meta-Object Programming

In a language like C++, the behavior of the object system is hard-coded into the language, and so the compiler can work under this assumption, and optimize the heck out of it.

In Perl 6, the object system is defined by other objects and classes, the meta objects. So there is another layer of indirection that must be handled.

Mixing of compilation and run time

Declarations like classes, but also BEGIN blocks and the right-hand side of constant declarations are run as soon as they are parsed. Which means the compiler must be able to run Perl 6 code while compiling Perl 6 code. And also the other way round, through EVAL.

More importantly, it must be able to run Perl 6 code before it has finished compiling the whole compilation unit. That means it hasn't even fully constructed the lexical pads, and hasn't initialized all the variables. So it needs special "static lexpads" to which compile-time usages of variables can fall back to. Also the object system has to be able to work with types that haven't been fully declared yet.

So, lots of trickiness involved.

Serialization, Repossession

Types are objects defined through their meta objects. That means that when you precompile a module (or even just the setting, that is, the mass of built-ins), the compiler has to serialize the types and their meta objects. Including closures. Do you have any idea how hard it is to correctly serialize closures?

But, classes are mutable. So another module might load a precompiled module, and add another method to it, or otherwise mess with it. Now the compiler has to serialize the fact that, if the second module is loaded, the object from the first module is modified. We say that the serialization context from the second module repossesses the type.

And there are so many ways in which this can go wrong.

General Featuritis

One of the many Perl 6 mottos is "torture the implementor on behalf of the user". So it demands not only both static and dynamic typing, but also functional features, continuations, exceptions, lazy lists, a powerful grammar engine, named arguments, variadic arguments, introspection of call frames, closures, lexical and dynamic variables, packed types (for direct interfacing with C libraries, for example), and phasers (code that is automatically run at different phases of the program).

All of these features aren't too hard to implement in isolation, but in combination they are a real killer. And you want it to be fast, right?

Dave's Free Press: Journal: Thankyou, Anonymous Benefactor!

Dave's Free Press: Journal: Number::Phone release

Dave's Free Press: Journal: Ill

Dave's Free Press: Journal: CPANdeps upgrade

Perlgeek.de : Writing docs helps you take the user's perspective

This year, most of my contributions to Perl 6 have been to the documentation, or were directly inspired by writing the documentation.

Quite often when I write documentation, I start thinking things like this is a bit awkward to explain, wouldn't it be more consistent if ... or what happens when I use a negative number here? The implementation disallows it, but does it actually need to? or if I tell people to just pass this particular value most of the time, why not make it the default?.

Like most people who aspires to be a good programmer, I'm lazy. In particular, I hate doing pointless work. And documenting inconsistencies or missing default values or arbitrary restrictions definitively feels like doing work that shouldn't be necessary. So with a sigh I overcome my laziness, and try to fix stuff in the code, the tests, and sometimes the design docs so I can be more lazy in documenting the features. And of course, to make the overall experience more pleasant for the end user.

I've been skeptical of README-driven development in the past, dismissing it as part of the outdated (or at least for software not suitable) waterfall model, or as "no plan survives contact with the enemy". But now that I'm writing more docs, I see the value of writing docs early (of course with the provision that if things turn out to be impractical a documented, the docs may still be revised). Because it's very easy as a developer to lose the user's perspective, and writing docs makes it easier (at least for me) to look at the project from that perspective again.


With the philosophy part done, I'd like to bring some examples.

The missing default value

In Perl 6 land, we distinguish meta classes, which control behavior of a type, and representations, which control memory layout of objects.

Most Perl 6 objects have the representation P6opaque, which provides opaque, efficient storage for objects with attributes, properties, slots, or however you call per-object storage in your favorite language. Special representations exists for interfacing with C libraries, concurrency control and so on.

The class Metamodel::Primitives provides primitives for writing meta classes, with this method:

method create_type(Mu $how, $repr) { ... }

$how is our standard name for Meta stuff (from "Higher Order Workings", or simply from controlling how stuff works), and $repr is the name of the representation.

Somebody new to meta object stuff doesn't need to know much about representations (except when they want to very low-level stuff), so the docs for create_type could have said if you don't know what representation to use, use P6opaque. Or I could just establish P6opaque as a default:

method create_type(Mu $how, $repr = 'P6opaque') { ... }

There, less to document, and somebody new to this stuff can ignore the whole representations business for a while longer.

Arbitrary restrictions

The method rotor on the List was intended to create a list of sublists with fixed number of elements from the original list, potentially with overlap. So the old API was:

method rotor($elems = 2, $overlap = 1) { ... }

And one would use it a

.say for (1..7).rotor(3, 1);
# 1 2 3
# 3 4 5
# 5 6 7

Again I had an issue with default values: It wasn't clear to me why $elems defaulted to 2 (so I removed that default), or whe $overlap defaulted to 1. Wouldn't 0 be a more intuitive default?

But my main issue was that the implementation disallowed negative overlaps, and the design docs were silent on the issue. If you visualize how rotor works (take $elems elements from the list, then step back $overlap elements, then rinse and repeat), it's clear what negative overlaps mean: they are steps forward instead of backwards, and create gaps (that is, some list elements aren't included in the sublists).

And once you allow negative steps backwards, why not go work with steps forward in the first place, which are more intuitive to the user, and explicitly allow negative steps to create overlaps?

So that's what we did, though the end result is even more general.

The crucial question here was why disallow negative overlaps?, or recognizing that a restriction was arbitrary. And then lifting it.

Wording of error messages

Error messages are important to communicate why something went wrong.

We used to have the error message Could not find an appropriate parametric role variant for $role. A test for a good error message is: ask why?, and if the piece of code that threw the error can know the answer, the error message needs improving.

In this case: why can't the runtime environment find an appropriate variant? Because it didn't try hard enough? No. Because it's buggy? I hope not. It can't find the candidate because it's not there. So, include that answer in the error message: No appropriate parametric role variant available for $role.

(Uninformative/lazy error messages are one of my favorite topics for rants; consider the good old SIOCADDRT: No such process that route(8) sometimes emits, or python's Cannot import name X -- why not? ...)

So, write those docs. Write them at a time where you can still change semantics. Keep asking yourself what you could change so the documentation becomes shorter, sweeter, easier understandable.

Dave's Free Press: Journal: YAPC::Europe 2006 report: day 3


Header image by Tambako the Jaguar. Some rights reserved.