Pugs

More whitespace sensitivity.

Today I put in the finishing touches to predictive parser, with support for "$x .= foo" and "foo.bar". In both cases, whitespace is now very important:

$x .= foo     # $x .= $x.foo
$x .=(foo()) # same thing
$x .=(foo)   # same thing
$x.=(foo)    # $x.postfix:<=>(foo())

There is no built-in Perl 6 classes with the postfix:<=> method, so the last one is probably an error.  Another example:

foo.bar;   # foo().bar()
foo.bar(); # same thing
foo .bar;  # foo($_.bar())

That is surely the correct behaviour, but my brain (too used to backtracking dwimmy parsing) still need some time to adjust from the change.  The test files, too, needs some adjusting: Of the 630 test files, 76 are still failing parsing -- usually, it's a missing whitespace here or there, but there may still be some ambiguities hidden in the corner.  Helps welcome to triage those tests!  If you'd like to help, look at this smoke test report, grep for " 0.00%" (with the space), run "./pugs -Iblib6/lib t/path/to/test.t", and try to diagnose the error.

In other news, aufrank++ started to re-read S06: Subroutines, in order to start working on a Rules-based parser for the full signature syntax, complete with the not-yet-supported features such as array/hash/structural unpacking.  Once that grammar is in place, we can use scw++'s work to use it as part of Pugs's Parsec parser, and also pack it up into a Module::Compile-based bridge to Data::Bind, to provide a modern successor to the highly impressive Perl6::Bindings for Perl 5.  Yay!

SoC, MacIntel, etc.

At xerox++'s suggestion, this year I factored Haskell-related tasks from Pugs and listed them as part of  haskell.org project ideas for Google's Summer of Code, and listed myself as a mentor on both Haskell.org and the Perl Foundation.  The perl.org project ideas list already has some Pugs-related items -- a port of DBI::PurePerl to Pugs, for example -- and I look forward to add more ideas to both lists in the days to come.

Also, thanks to xerox's effort, Pugs is now running on MacIntel, using Wolfgang Thaller's preliminary GHC 6.5 build. This of course made me wonder if I should give in and get a Pro 17" now, or wait for a probably more stable (and certainly less expensive) NonPro 15"...  I guess I'll sleep on it. :-)

Less parsefails and more parseideas.

During the waiting-time in today's porcelain painting session, I finally figured out the way to implement the "any line ending in a semicolon (except for whitespace) can terminate a statement" rule:

my &foo := {
    say 1;
    say 2;
}   # Look, no semicolon!
my &bar := {
    say 3;
    say 4;
}   # ditto

See S04: Statement-ending Blocks for details.  The solution turns out to rely on a Parsec feature: setInput, that tells the rest of the parsing to operate on a different string, instead of the current one.  With this, for statement-level parsing, we can parse the block (up to the closing '}'), mark the position, parse some whitespace, and see if the line number has changed.  If yes, then it's a statement-ending block, and we insert a semicolon right there.  However, I wonder how to port this trick into Perl 6 rules...

Also I implemented .[0] and .<name> (shorthand for $_[0] and $_<name>), as well as the nice "@foo .= map(&sqrt)" mutating-method idiom.  During the discussion in #perl6 that followed, I then stumbled upon a possible solution to the long dot not short enough problem -- thanks Juerd++ for the excellent summary on the perl6-language list!

2.5x faster than yesterday!

Continuing yesterday's Parsec work, aided by gaal++'s work on adding previous-character, capture-name and capture-position fields to the parser state, today I dropped most of the backtrack-inducing try in Parser.hs:

<TimToady> "do, or do not.  there is no try..."

This alone resulted in a modest speed up:

<gaal> so, yeah, I see about a 10% speedup

Because we are taking another Rule-bootstrapping route now (cf. scw++'s README for Pugs::Grammar::MiniPerl6), I disabled the rx_ macro for parsing rule adverbs in Perl 6, resulting in another 20% speedup:

<xinming> pugs++, It works faster 30% times than before... :-)

After that, the profile shows that the Parser no longer dominates time; the cost center had shifted to Data.Yaml.Syck, for loading the precompiled Prelude.pm.yml file.  The Syck binding is really thin, and we didn't think there's much room for improvement.

However, the re-licensing plan means we'd need to move all dependencies in src/ to third-party/, so I checked the upstream sources for new version. Much to my delight, the Data.FastPackedString (FPS) code, used by the Syck binding, has been massively optimized by lambdafolks and renamed to Data.ByteString.  Simply by upgrading to the new library, the startup time is cut by half:

<xinming> time ./pugs t/01-sanity/02-counter.t   <---  result of this....
<xinming> real    0m1.118s
<xinming> user    0m1.068s
<xinming> sys     0m0.012s
<audreyt> you have a pretty good computer :)
<audreyt> ok, r10110 landed
<audreyt> try to see if it gets faster?
<xinming> real    0m0.494s
<xinming> user    0m0.456s
<xinming> sys     0m0.020s
<audreyt> so, really 2x faster :)

Then I moved to the next hotspot in profile, the ops function that sorts token by their length, to support a longest-token-match. A Schwartzian transform suffices to speed up another 6% overall:

ops f = map (f . tail) . sort . map (\x -> (chr (0x10FFFF - length x):x))

That's the same as this (under-golfed) Perl 5:

sub ops {
    my $f = shift;
    map { $f->(substr($_, 1)) } sort map { chr(0x10FFFF-length).$_ } @_
};

Finally, I lazily memoized the Manhattan distance between all built-in types, so the 16% of run time  spent on MMD dispatch is now entirely gone. Compared to yesterday's Pugs:

$ time ./pugs.old -Iblib6/lib t/builtins/sprintf_and_as.t
real    0m11.444s
user    0m9.831s
sys     0m0.028s

$ time ./pugs -Iblib6/lib t/builtins/sprintf_and_as.t
real    0m4.394s
user    0m3.811s
sys     0m0.028s

Not bad at all for one day's work. Maybe multi-hour smoke loops will become a thing of the past. Or maybe we just need more tests. :-)

Growing a Planet...

I'm very glad to find that scw, a returning lambdacamel, has started Yet Another Pugs Hacker's Blog to chronicle his ongoing work on Pugs. It will soon join Planet Six, an aggregator on all Perl 6-related blogs -- if you have an Atom/RSS feed on Perl 6-related topics in your journal, or would like to start writing about Perl 6, please leave a comment here and we'll add it to the aggregator.

His current subproject is on a multilevel Parser-bootstrap(Perl 6, parsed with (perl6/p6rules parsed, with (parsec/p6rules, parsed with (minip6, parsed with (perl5/p6rules, parsed with (optable)))))), which will enable maximum sharing of grammar between PIR/Perl5/Haskell implementations.

In other news, the Perl 6 weekly summary, a constant presence on Planet Six, has been absent recently. Today Matt Fowles expressed his wish to pass on the summarizer hat:

Paradoxically, I have found myself wishing that there were summaries as there seems to have been a lot of movement lately and I have not had much time to read it all.

In the hopes of inspiring someone to take my place, I would like to encourage any interested party to just start summarizing and thus become the official perl 6 summarizer.

Thanks, Matt, for all your excellent summaries; I certainly enjoyed them a lot. :-)

So, if you are feeling the spirit of JFDI (pronounced Jifty), then start to backlog and post your first summary to [email protected]!

Conference Updates.

The YAPC::NA schedule has been announced. The "Perl 6" track of tuesday reads very nice, with talks from TimToady+dconway on the language, pmichaud on Parrot/Perl6, and gaal on Pugs internals.

Amusingly, without pre-coordination, the talk titles from merlyn+bdfoy, nothingmuch and me reads as a coherent whole: first "Learning Perl 6", then "Compiling Perl 6", then finally "Deploying Perl 6". :-)

Aside from the Perl 6 track, Tuesday also sees many talks on  #perl6-inspired technologies applicable to the CPAN world: Stevan on Moose.pm, the object model implementation for Perl6-on-perl5; Ingy on Module::Compile, the magic behind v6.pm; and gaal on the Pugs testing system -- you too can set up a smoke-server for your Perl 5 projects in no time.

Wednesday is #parrot-focused: we have talks on Parsing, Testing and Targetting Parrot, as well as Allison's talk on Punie that puts all of them into use to implement Perl 1. Woot!

So far 18 people has signed up for the post-conference hackathon, making it the largest Perl 6 hackathon to date. After July 1, several lambdacamels will relocate to Boston to continue hacking; if you'll be around Boston during July 2~6, feel free to leave a note in the Hackathon wiki page.

Prior to YAPC::NA, I'm also going to Nordic Perl Workshop in June 15/16; sadly I cannot stay there for a Hackathon, as on June 20 I'll visit Erik Meijer (known for LINQ, Parsec, HSP, HaskellDB, LtU rants, etc.) at Redmond, and give two talks there on Perl 6 and Pugs.

Erik is known for advocating static where possible and dynamic where needed, as well as for reconcilling multiple paradigms. His new ICFP'06 paper, Confessions of a used Programming Language salesman (getting the masses hooked on Haskell), is an excellent read; it outlines many of the same issues the Perl 6 design team is dealing with, on how to (in TimToady's words) provide -- but hide -- the fancy stuff. It's indeed very challenging, but also lots of fun! :-)

Parsec is Rules engine.

Today I started the process of making Parsec a valid Rules engine, due the the whitespace boundary (<ws>) handling required to distinguish these two forms:

if %ENV{'PATH'} { 'foo' }  # one "if" statement
if %ENV {'PATH'} { 'foo' } # two statements: "if" and bare-block 'foo'

This is because whitespace is never allowed before postfix operators in Perl 6, and we rely on this property to avoid infinite lookaheads for cases like "$x < 3" versus "$x<3>".

I went for the most convenient approach, namely keeping a UserState of the character class of the previous Char -- \s, \w, or others.  It works as expected, but makes parsing 30% slower again, completely offsetting the gain of conversion to predictive parsing.  I'll run some profiles and see if I can optimize it back to speed. I also added a UserState for offset, for .from/.to support. (Previously it only maintains lines and column numbers.)

The next step would be add UserState of the current named/positional captures, and then change the result type to from "a" to "Match a", then voila -- we'll have a Rules engine.  scw (recently resurfaced on #perl6) offered to write a MiniPerl6-to-Haskell compiler, so we can have a shared Perl 6 grammar and the AST production rules for Perl 6, and translate them into Perl5/Parrot/Haskell as needed.

I also pointed spinclad to the optable.c skeleton, in the hope that the three implementations -- each have an operator precendence parser, none of which particularly fast -- can share a stable, C-based implementation.  My C-fu is weak, so I'm glad to see interest on that front. :-)

In other news, particle has been populating the Parrot/Perl6 tree with symbolic and named builtin prototypes, imported from Pugs's primitives table, so unary and nullary functions can start to parse properly. Yay!

Finally, back to coding.

I'm happy to report that the intent of the licensing concerns was satisfactorily understood, and I'll be working with TPF and their lawyer to work out the details on implementing this change. (See this thread on chromatic's journal for some more details on the contextual background.)

Thanks a lot to the Perl 6 project manager, Jesse Vincent, for his tireless cat-herding skills. :-)

Prompted by Adam Kennedy's journal entry, I released the long-overdue YAML::Syck 0.42, with proper support for self-recursive data structures, as well as back compatibility with Perl 5.005.  Porting that back to Pugs should be straightforward, and will allow us to serialize mutually recursive subroutine calls, as motivated by the recent S02 change on "provisional calls":

f(1,2,3); # &f is not declared so far

In Perl 5, this code is always valid with "perl -c", regardless of whether "sub f" gets declared later in the program.  In Perl 6, TimToady recently decided that it now fails at CHECK time, if a &f cannot be located in that scope.  This means that almost all function calls now bind to some lexical function, and we can prebind the calls with their lexpad entries in the AST, drastically reducing the amount of indirections involved.

In other news, the #haskell people are now discussing unicode strings, characters with limited unicode range (Char7, Char8, Char16, etc), fixed-sized buffers, encoding tags, and other fun text-processing facilities for Haskell-prime, the next version of Haskell.

I've submitted a modest proposal to detect UTF8/16/32 source code encoding; it's an improved version of S_swallow_bom in Perl 5's toke.c, with the explicit restriction that an unmarked source stream must never be considered ISO-8859-1. I plan to deploy this heuristics for Pugs itself in the near future, so we can recognize UTF-16 source code as well.

Perl 5's defaulting-to-latin1 has caused many subtle problems (in Tokyo, Jesse and I hit that problem with Mason's on-disk file cache), and I'd be happy if both Perl 6 and Haskell can move away from this trap.

I'm still working to unbreak the whitespace problems caused by recent refactoring to Pugs.Parser to make it predictive.  Meanwhile, Ingy and I paired in realspace last night, on making a parser for Kwid-like syntax, which needs infinite lookahead (as it allows no parsefails), yet has to be executed in a reasonable time.

Thanks to Packrat, we can write in a rule-like syntax (see the bottom of Wiki.pappy), using the full backtracking and assertion power of regex, yet guarantees parse everything in linear time. Imagine that you can write /((.+)+)/-styled patterns freely, without worrying anything about performance!

Perl 6 is predictive (for human's sake, if not for computer's), so we're still going to use non-backtracking rules instead of backtracking regexes for the Perl 6 grammar.  However, Packrat is really addictive... There is already an implementation in Java called Rats!, and I think the memoization technique is quite useful to any language that supports regular expressions.

Licensing clarification.

(Two-sentence summary: I intend to relicense the Pugs internals code (i.e. the bin/pugs binary) to the MIT license, and only if fellow contributors are happy with that.  Everything else under the Pugs tree is unaffected, and the the "compilation-right disclaimer" in README does not affect any code committed in Pugs in any way.)

---

I apologize that I've not conveyed the scope of licensing to our contributors properly, causing a lot of confusion.  While I have been saying "only the src/ tree will be affected" from the start, I did not clarify that the src/ here explicitly means the src/ directory in the Pugs repository, containing Haskell/C/Perl6 code that builds the main pugs executable -- i.e. it's Pugs's internals code.

I'm really, really sorry to cause people misparsing it as the "Pugs source tree".  All other subdirectories, such as t/, examples/, perl5/ ext/, doc/ and util/, remains exactly in the same licensing situation (Artistic 2.0b5/GPL) as they were.  Please see the README file for the full details, as well as my public apology to chromatic.

So, to reiterate again:

• For Pugs contributors working on non-src/ directories, such as modules, tests, examples or documentations, nothing has changed in the licensing situation, and there is no plan at all to change them.
• For Pugs contributors who have checked in src/, I would like to survey if you are okay with releasing your previous and future work under the MIT license.  If you are explicitly not okay, I'd like to know why.
• chromatic has requested that his work be pulled out from the src/ directory, because he was unwilling to release it under SQLite's terms.  However, he later amended that he would be comfortable with the MIT license.
• As my intention with src/ was merely allowing maximum reuse, I'm certainly happy to change to the MIT license's terms; I have reflected this change in the Pugs README.
• The README does not change src/'s licensing currently; nothing will take effect until the next Pugs release, which will happen only after sufficient discussion time for src/ contributors to voice their opinions.

Aside from the src/ directory, I am uncomfortable with using Artistic license as whole-distribution compilation copyright license, because according to TPF, that may make it illegal to distribute Darren Duncan's Rosetta.pm module (GPL2+) along with Pugs, and I may have already been guilty for doing that for the past Pugs releases, just like Ruby people may be criminal for that with their regex.c (LGPL2+).

Because of this, I still wish to disclaim my compilation copyright, which basically means there is no global license that covers all of Pugs's subdirectory contents. This does not affect any contributed code in any way, and new commits in non-src/ trees are still under the Artistic2.0b5/GPL license by default, unless explicitly marked otherwise in that subdirectory or file.

Again, sorry for the confusion raised around this matter. I wish my English was more clear and succint...

More licensing followup...

I just posted this reply on chromatic's journal: 

So, the relicensing has two parts:

The first part is directly addressing Allison's worry that asserting a less-restrictve "compilation copyright" than something under the source tree, will invite legal troubles. I responded by disclaiming my compilation copyright.

The second part is my wish to change the src/ tree, which comprises the source for "pugs" executable, to public domain status, by moving all third-party parts out to a separate place (third-party/), and rewriting parts of the contributions where the contributor would like to maintain Artistic2.0b5+GPL license status for their contributions.

All contributions outside the src/ tree remains unaffected.

I thank your contribution in parameter binding and object finalization. Due to the Capture unification and disappearance of References, they need to be rewritten anyway. I regret that you will not participate in the rewrite.

I have also reflected this situation in the Pugs README file.  A summary:

• Disclaiming my compilation-copyright over Pugs does not affect any contributed code.
• Moving third-party code to third-party/ does not affect any contributed code on those third-party code, since they still retain their own license.
• All contributed code outside src/ directory remains unaffected.
• The src/ directory is currently still under Artistic 2.0b5/GPL, but I'd like to relax this restriction, making the "pugs" binary itself public domain software.  This will not take effect until the next release.
• The rationale for the src/ change is that I think the social dynamics of the Pugs src/ tree differs from the intent of restrictions imposed by Artistic2.0b14.
• Also, it is more common for research/prototype project to under BSD  license, MIT  license, or public domain. I'd like to let those projects reuse Pugs's source code, which Artistic2 does not allow.
• Also, it is always possible for TPF (or anybody) to later pick up the public-domain part of Pugs, and redistribute it under Artistic2, or any other license (MPL or BSD, for example).  This ensures the possibility for a "production" version of Pugs later adopted by an organization.
• If you have previously committed into src/, and disagree with making your code available without restrictions, then please inform me, just like chromatic did.

Since chromatic considers public domain equivalent to a no-rights-retained license (e.g. MIT), and he would like his contributions to remain under Artistic/GPL, he wished that the src/ parts be rewritten, remarking that it is easier to do so rather than trying to convince him.  I have since complied with his wish, and rewrote all his code under src/ as of r10068.

Update: It turns out that chromatic thinks MIT license is okay. Pending further communication, maybe there is yet hope of agreement...