Pugs

Design cleanup.

The past three days weren't all about license; live design sessions on #perl6 happens every day for hours, resolving the remaining ambiguities that slows down Perl 6 parsing (due to ambiguities that requires infinite lookahead), or the parts that were easy in Parsec but was difficult to declare as Rules.

A concerte example for infinite lookaheads:

$hash<1;2;3;long;string;here>;  # one statemeent?
$hash<1;2;3;long;string;here;    # 6 statements?

Because of this, Perl 6 always require a whitespace before < to denote an infix operator; non-whitespaces always means the postcircumfix <> macro, which then desugars to a postcircumfix {} lookup.

Pugs currently uses very expensive backtracking to disambiguate these cases, so getting rid of them should dramatically reduce parsing time.

While switching to Packrat Parsing (gaal++ for the pointer) would allow infinite lookahead and backtracking with linear time, it doesn't make it easier for humans to disambiguate between the two cases above -- so we are not doing that. Instead, I'm using Christopher Kuklewicz's excellent Text.Regex.Lazy package, a compiler that turns extended regexes with customized backtracking strategies (read: Perl 6 rules) into Parsec functions.

This should allow for piecemeal migration from Pugs's Parsec parser to a grammar fully defined in Perl 6 rules syntax, and allow maximum sharing with pmichaud and fglock's parsers.

So, while I only checked in about 15 changes to Pugs this week, there were more than 20 commits to the Synopses, from TimToady, pmichaud and yours truly. Among the changes where:

• my @a = 1,2,3; # this now works, as list-context assignment is listop
• my (Int $x, Str $y) = 1, 'foo'; # this works too; "my" now takes full Signature syntax
• Backtracking patterns are now constructed by its old name, regex, instead of rules, which never backtracks.  The variant of rules that does not translate /a  b/ to /a<ws>b/ but to /ab/ is called tokens. Damian++.
• The *$foo and **$foo syntax now always means "inject content of $foo into the current argument list", and has nothing to do with list contexts anymore.
• A new form :!foo to mean the counterpart of :foo, namely a pair with foo as key and false as value.
• There is no native str type anymore; it's now always buf, so the confusions of Perl 5's buffer->string autopromotion will not appear. See my encoding::warnings for an explanation of the misdesign -- Dan Kogan and I both thinks that's the #1 Bad Idea of the Perl 5 string model, and I'm glad it's gone from Perl 6 now. (That also means Str are also immutable and Buf are always mutable -- think of the latter as Byte Arrays.)
• if foo { 4 } { 5 } now always means if (foo) { 4 }; { 5 }; instead of if foo({4}) { 5 }, regardless of  foo's signature.
• Per Migo (Mikhael Goikhman)'s suggestion during OSDC.il, a null first alternative in rules is now ignored, so we can write this BNF-ish parser:

rule answer {
    | Yes  { return 1 }
    | No   { return 0 }
    | N/A { return undef }
}

There are much more interesting changes that makes Perl 6 parsing more predictive, and Rules more expressive to capture common patterns in parsing Perl 6.  Ah, the joy of self-hosting... :-)

Pugs (non)licensing follow-up.

The comment from Garrett prompted this entry, as I'd like to clarify I'm not standing up against Artistic2 at all. :-)

I don't consider Artistic2b14 as restrictive at all (except maybe the TPF-can-update-terms-at-will clause feels a bit strange); it's certainly an improvement over the extremely ambiguous Artistic1. If you agree with the intent of Artistic1 for your previously-released original work, and trusts TPF's continuous licensing direction, then upgrading to Artistic2 is definitely a sane choice.

Re Garrett's Parrot/Artistic2 concerns, Allison noted that the "Copyright by Perl Foundation" header added to each Parrot file does not override the original author's copyright, but instead means that TPF holds the compilation copyright, by which it must be asserted to extend to all files within the Parrot tree, which means Parrot can't contain LGPL parts, or any parts that are more restrictive than Artistic2.

So to solve this problem, I simply disclaim my compilation copyright over Pugs, as well as the tarball that contains third-party (BSD, Artistic/GPL, and possibly LGPL) distributions. This means the receiver must reuse part of the code under whatever license it was originally under.

In addition to disclaiming my right to the compiled work, I also disclaim my original work contained within it, so that the receiver does not need to worry about reusing those parts of the work.  Once all the non-third-party parts are marked as such, then we can say that "the entirety of Pugs is in the public domain". Until that day, it means that the Pugs tarball doesn't impose any licenses at all, beyond the licenses in whatever its subdirectories assert. :-)

On adopting the SQLite (non)license.

Aside from $job, I spent an entire day parsing the freshly announced release of Artistic License 2.0 beta 14, which feels much like Perl 6 -- in that it streamlined and formalized the mechanism, while staying true to the original idea.

As part of this, I engaged in an extremely long discussion with Allison, on her warning in #parrotsketch that inclusion of the Judy LGPL source tree in the Pugs repository will cause a licensing conflict with the Artistic license -- Inclusion of Artistic code under a LGPL project's tree is okay, but the converse is forbidden.

# Update: After some long followup discussions, it turns out it's not forbidden by law (Ruby does it with their regex.c), it's just considered extremely bad style by TPF; according to Allison, claiming the Artistic license applying to a compilation work also covers individual files in it, and it's legally dangerous -- though maybe not instantly criminal -- to have more strictly-licensed subparts in the repository tree, the way Ruby does it.

This has motivated me to move away from Pugs's current license, the now-outdated Artistic License 2.0 beta 5/GPL, as I don't want to restrict people doing anything with my compilation copyright.

All I really want to do is to let other people redistribute Pugs, in part or as a whole, without worrying anything about Pugs's license interferring with their redistribution policy. Conversely, I'd like to make use of third-party libraries without worrying about them disputing my copyright claims.

This is in resonance with the SQLite (non)license, which states:

The author disclaims copyright to this source code.  In place of
a legal notice, here is a blessing:

    May you do good and not evil.
    May you find forgiveness for yourself and forgive others.
    May you share freely, never taking more than you give.

Taking a page from this wonderful checkin from the extremely successful SQLite project, I'd like to begin the process on disclaiming my copyright over Pugs, as well as on my CPAN modules, perhaps registering this fact on the Creative Commons repository at the end of the process.

I'd like to take these steps:

• Move all third-party dependencies to a clearly marked contrib/ subtree.
• Disclaim my own copyright over the parts of the source files that makes up the pugs executable, adding to them per-file copyright-free declarations.
• Clearly mark that each aggregated modules under ext/ are under their own copyright owners and licenses.
• Implement the contributor policy, similar to the CC click-through screens, as part of the OSSF signup process on new commits for committers.

However, if people who have contributed to the src/ tree before feel uncomfortable about this change, that will necessitate a rewrite of those parts, so please voice your concerns.

Note that pretty much the same process needs to happen for Pugs relicense to Artistic 2, so this choice is simply that I think the SQLite non-licensing works better toward the goal of -Ofun. :-)

Random recaps.

This title is getting old, but that's all I can muster between two $job days.

• Yesterday's #parrotsketch log shows huge number of activities from a lot of people.
• Judy Hash totally rocks, both in performance and ease of embedding. the HsJudy binding  from the ever-inventive John Meacham (author of jhc and DrIFT) is wonderful as well.
• Arathorn++ added to Capture.pod some discussions on how Match objects (a subclass of Capture) can be fruitfully used as Captures.
• Some spirited discussions followed on representing XML trees as Captures, as well as the meaning of multidimensional (really just two-dimensional) argument lists in zip(1;2;3), and what @;moose means in a signature.
• By request from pmichaud, I tweaked Test.pm to work without junctions, as Parrot doesn't have a Junction PMC, or anything remote like juctive autothreading for function calls.  It's better for Test.pm to run on Parrot/Perl6 as early as possible, as would be a duplicate of effort to rewrite Pugs's test suite by hand using say "ok 42".
• Also, I uploaded the Pugs/PIR codegen output for all sanity tests, Test.pm and lib.pm, in the hope that it may be helpful to the Parrot/Perl6 project. Then I discovered they no longer run with Parrot HEAD -- I swear they did with 0.4.2. :-/
• Parrot/Perl6 now passes two more sanity tests: 03-equal.t and 04-if.t. The next in line is 05-sub.t...
• Pugs::Grammar::Perl6 now parses Test.pm entirely!
• I reported a puzzling parsing problem involving := treating the LHS as a Signature. It's currently the only thing blocking proper surface syntax for the rule-embedding mini language based on P6AST.

See you tomorrow. :)

Some parsing bits.

Short update today, as tomorrow $job resumes and I need to catch enough sleep -- unfortunately having to miss the midnight-#parrotsketch session yet again.

This afternoon I checked in a 10-minutes hack to src/rules/, the beginning of librules, a C-based implementation for the operator precedence parser (the token half of the Perl 6 parsing cycle), in an attempt to enhance the PIR-based PGE::Match and PGE::OPTable's performance, and provide a common layer for PIR/P5/Hs-based Rules implementations to call into.

The current design is heavily influenced by libsyck, and currently I use Judy arrays for sparse arrays and hashes, because the C API is so extremely sane. I also plan to use them for the Haskell runcore, to replace the atrociously slow IntMap-based array implementation. The other missing piece of this new-runtime puzzle is string-buffer-fragments, but that's for another day...

In other news, I checked in an updated version of cognominal's Siva PMC as pugscapture.pmc, a PMC that implements the invocant/sequence/mapping structure within a Capture object.  As Match objects are conceptually just a subclass of it, it may also prove to be useful for that purpose as well. Plus XML tag/children/attributes, as well as a lot of other things.

Anyway, that's it for now.  See you tomorrow. :-)

r10000!

As seen on #perl6:

< svnbot6> r10000 | audreyt++ | * Perl6::Overview::Smartmatch - Smart Matching
< svnbot6> r10000 | audreyt++ |   (Happy Birthday, Audrey. :-))

Three and half hours into my 25th birthday, I committed the 10000th revision to Pugs.  That was the last one in a series of commits to convert the highly popular docs/quickref/ tree to Perl6::Overview::*, in preparation for the CPAN release of Perl6::Doc.

Whilst I'm writing this, #perl6 and #parrot are both abuzz with commits, announced by svnbot.p6 -- in the past hour, xinming coded the newly specced &?ROUTINE to the Haskell tree (and narrowly missed r10k); fglock made Pugs::Grammar::Perl6 parse all our sanity tests; pmichaud, particle, leo and me all hacked on Parrot/Perl6, which now passed the second sanity test; a grammar and operator prototypes is gradually emerging toward valid-Perl6-ness required for self hosting...

...Indeed, among the past 14 months since I started participating in Perl 6 development, the community had never been so lively and synergetic as this moment. Kudos to all our ship-builders, and many, many happy returns!

Chicago Hackathon.

Because Stevan can't make it to Tokyo last month, and I really want to work with Patrick/Chip/Allison in realspace (especially now that things are much smoother compared to last year's Toronto hackathon), I decided to put my boycott-against-entering-states aside, and give a talk at this year's YAPC::NA on Deploying Perl 6.

So far, we already have an amazing roundup of people for the post-conference Perl 6 hackathon (<< TimToady allison chip pmichaud stevan ingy gaal nothingmuch robkinyon obra miyagawa >>). So, if  you are going to YAPC::NA as well and wouldn't mind staying around the dorm for a few days, please sign up on the Wiki page, and we will make sure that you'll have something exciting to hack on. :-)

P6AST Draft.

The long overdue PIL2 node redesign braindump + brainstorming Gobby session took place tonight, commissioned by fglock and participated by a record number of 7 lambdacamels.

The draft document really needs some tidying up, but it's a fairly complete picture of what I had in mind during the Tokyo hackathon.

Our design space was simplified enormously this time, thanks to two insights from Matz:

1. All compile-time special forms should be reconstructable as run-time method calls
2. The object space is itself an object, so precomposed objects at BEGIN{} time can be freely shuffled into runtime.

Ergo, even with separate compilation and BEGIN blocks, the AST can still be entirely dynamic and not contain any compile-time nodes. (Thanks also to ko1 for pointing me to Ruby 1.8.1 nodes.)

Also, because this tree is to be shared among three Perl 6 implementations -- none of which written entirely in Perl 6 yet (i.e. with significant Hs/Perl5/PIR parts), it is vitally important that all nodes can be translated back to Perl 6 surface syntax, and we have to forbid any backend-specific "optimization" nodes (e.g. pRawName in PIL1 for PIR codegen).

With this guarantee, the implementations can naturally converge into a self-hosting Perl 6 with maximal code sharing, instead of having subtle semantic differences.

The next step is to come up with a minimal surface form, suitable to embed inside rules, so we can manipulate the parse tree for Perl 6 with Perl 6, without requiring a fully self-hosting implementation. Then the most diverging part of the three implementations -- namely, parse tree construction -- can suffer less from the language barrier, and that would be a Good Thing. :-)

Dispatching out...

Thanks to all the feedback to yesterday's Capture.pod post, today I updated Capture.pod with more examples, including a more elaborate description on single/multiple vs subroutine/method dispatch (as requested by Humberrto), which I reproduce below:

---

What about multi-dispatch?

Multi-dispatch governs cases where multiple subroutines or methods share the same name, relying on the arity and types of tie-breaking parameters in their parameter list (Signature):

    multi f ($x: $z)             { say 'A' }
    multi f (Int $x, Int $y: $z) { say 'B' }
    multi f (Str $x, Str $y: $z) { say 'C' }

    f(1, 2);            # goes to A
    f(1, 2, 3);         # goes to B
    f('x', 'y', 'z');   # goes to C

During multi-dispatch, a tie-breaking parameter may bind to the invocant argument (e.g. for multi-methods), or one of the positional arguments.

However, regardless of single- or multi- dispatch, the argument list (Capture) can never have more than one invocants.  Typically, the presence of an invocant indicates a method-call (which may fall back to a subroutine-call); the lack of invocant means a subroutine-call.

    1.foo(2);  # Int.foo with 1 as "self"; if not found,
               # then fall back to foo(1, 2)
    foo(1: 2); # same as above

    bar(1, 2); # never looks at Int.bar;
               # calls &bar in lexical/package scope

Method/subroutine calls are determined by the presence of an invocant at the calling site.  Single/multi dispatch are determined by the presence of multi in the declaration site.  The two concepts are entirely orthogonal.

---

The last line was key -- it took me several months to realize that in the Synopses, the so-called "invocant parameters" in multisubs really have nothing to do to with "invocant arguments" in method calls.  Hence I've started referring to them as "tiebreaking parameters" to reduce general confusion.

Also, instead of mixing multi and method with the MMD acronym, I've taken to say sub/method calls and single/multi dispatch, to further clarify that they are distinct (and quite unrelated) concepts.  Hope that helps...

I'll have less cycles to stay on #perl6 the next four days, as all three projects at $job are drawing into their closure, and I'd like to deliver them properly before going back to Pugs. However, we are just 35 commits away from r10000, and it might make a nice birthday gift to myself... So we'll see if I manage to send in some commits here and there. :-)

Backing out from the backtracking track.

Most of my hacking time today was spent on getting our Parsec-based parser to not backtrack so much.  But first, a little background discussion:

Currently, Perl 5 regular expressions almost always backtrack into previous parts, when the latter parts cannot match.  For example, the match below would backtrack ten times, each time trying to match different length of a, before finally giving up.

    "aaaaaaaaaab" =~ /^a+\d/

Because of this, complex regexes in Perl 5 often exhibit surprising (or downright pathological) time/space behaviours when applied to unanticipated source text.

In Perl 5, we can use the esoteric "never backtrack over this" device (?>...) to suppress backtracking:

    "aaaaaaaaaab" =~ /^(?>a+)\d/

This will eat up all the /a+/, seeing the trailing "b" does not match \d, and immediately give up there without backtracking.  TimToady noted that there are a dearth of scalable parsers written in Perl 5 regexes, which may be related to the primitive (and non-widespread) support of backtracking control.

Within Perl 6 rules, a single colon introduces a don't backtrack over me point, so the above regex can be rewritten into this far more elegant form:

    "aaaaaaaaaab" ~~ /a+ : \d/

However, @Larry is currently pondering making non-backtracking the default for
rule{...} constructs (as opposed to rx{...}, which still backtracks by default).

Now, the Perl 6 grammar was designed to be parsable with very little backtracking.  However, my early spike-prototyping demands, as well as previous brainwashing from over-exposure to Perl5 regexes (cf. Template::Extract /Template::Generate), resulted in my incessant abuse of backtracking in the Pugs parser, making it much slower than it needs to be -- especially on
parsefails.

Concretely, I abused the fast commit-by-default Parsec into a mostly backtrack-by-default parser, by sprinkling Pugs.Parser with try calls, which has the opposite effect of colons in Perl 6 Rules -- i.e. feel free to backtrack if this happens to not match.

Acting on TimToady's suggestion and luqui's observation of the obvious insanity of this approach, today I set forth to remove all try in Parsec's alternation rules (denoted by tryChoice).  Unsurprisingly, everything broke down and Prelude.pm failed to parse.  So I havn't committed it -- but there is a preliminary patch.

However, this exercise uncovered several hidden corners in Perl 6's grammar, where backtracking wasn't supposed to happen, but was nevertheless deemed to be neccessary by Parsec.

The most relevant one is the condition-part rule, as used by statement_control forms, such as if/unless/while/until.  Because Perl 6 no longer requires parentheses around conditions, we can easily get an ambiguous parse:

    if foo { 3 } { 4 }

this can mean two different things:

    if (foo) {3}; { 4 };
    if (foo {3}) { 4 };

Instead of continuing the current obviously-costly way of relying on backtracking, TimToady and I devised a clever solution, by specifying that bare blocks cease to be valid argument terms in the condition expression, unless protected by some kind of parens.

Because of this, whitespace-followed-by-opening-brace at term position always terminates the parsing of that part, and the "if (foo) {3};" interpretation always wins.  To get the other interpretation, write it as such with explicit parentheses.

I'm pretty happy that the tuned Parsec seems to be significantly faster at parsing sanity tests.  (As an aside, I also committed the same batch of sanity tests to the PGE-Perl6 tree -- the other 10k tests needs to wait until it can handle Test.pm.)

If I get some more hacking cycles tomorrow, I'll check it in and see if it can make another dent on the multiple-hours make smoke process.

But till then... Good night, and see you tomorrow. :-)