Pugs

Day 178 (r5932): QuickChecking PIL.

Today I finally put the QuickCheck technology to use, having it generate a large number of PIL expressions and check that invariants hold.

For example, this property declares that untie() accepts any lvalue arguments:

prop_untie :: LV -> Bool
prop_untie x = try_ok (Untie x)

Based on the type signature, when I type test prop_untie in the ghci prompt, QuickCheck will generate 100 of random expressions that can evaluate to a lvalue, run them through Untie, and check that all of them succeeds.

I am gradually converting hand-crafted unit tests into this kind of invariant-based tests. This process prompted me to see the language in a different light: not as a black box with external expectations defined by individual unit tests, but rather a well-behaved system with invariant properties. Of course, such verifiable specification is still not as good as a proof -- but it is much more cheap and cheerful than other test methodologies that I know of.

During the quick checking, a question arises: what is the meaning of untie(&say)? Perl 5 does not have this problem, as &say is a function call there -- you cannot address a function by name. In Perl 6, it seems to me that my &foo is merely a constrained version of scalar variable my Code $foo, and &foo = sub { ... } should work as usual. I have brought this to p6l for discussion.

iblech and I also noticed that function parameter binding and normal variable binding are symmetric:

    sub f ($a, $b) {
        return (c => $a, d => $b)
    }
    ($c, $d) := f(a => $a, b => $b);

Currently the return side is not specified to observe the same rich binding semantics as the parameter side; moreover, named return values are not expressible. We think that it makes sense to unify both representations into the same binding form.

Finally, I have posted a preliminary solution to the dreaded $x = $x + my $x if $x; problem that haunted us during the hackathon. Enjoy!

Day 177 (r5924): JS backend 43% pass; new PIL runcore begins

I have finally begun formalizing and implementing (they are the same thing with Haskell anyway) the new PIL runcore, starting with the container types. I have posted a first cut at container definition that tackles the semantic of binding, tie/untie and container equivalence.

This time I have backed the implementation up with Haskell-level unit tests, as well as QuickCheck instances planned for invariant testing in the ST monad.

Most of the formalization came from iblech's JavaScript work. Today he announced that the JS backend is passing an amazing 43.75% of Pugs's 4295 unit tests, including 20 unexpected successes. This is truly amazing.

As my $work involves web servers that are 10x slower than a typical client browser, I'm tempted to play with compiling Perl 6 into Perl 5 for the server side and JavaScript for the client side, and see if it yields acceptable performance. We'll see how it goes...

Day 167..176 (r5895): Ten-day tea time of the soul.

I have been away for ten days. I blame the first two days to the overly addictive The Sims engine; however, thanks to previous inoculation from NetHack, I eventually got out of it.

During the week that followed, my time was divided evenly between new $work, and ingesting thousands of pages of papers in the hope of coming up with a sane PIL design.

To that end, in addition to formal systems such as F<:, CoC (also Fw etc -- see an explanation in CubInt), vObj (including their very convincing solution to the expression problem ) and various module systems, I also surveyed the internal calculi of two classes of languages:

Typeful static languages with first-class functions and objects

O'Caml, Nice, Scala, rHaskell, Nemerle, Boo

Dynamic languages with reconstructable types

Cecil, CMUCL/SBCL, PyPy/Starkiller, Scheme (Widera), Chuck/Squeak (Garau)

The unifying feature between the two is type inference; I believe that Perl 6 will benefit from a design for incremental staticness, a form of annotation-directed complete type inferencing. See my p6c/p6l post from some initial ideas, and the previous post for a background.

However, that relies on Perl 6 observing a sound type system in its type annotations; see this post and two self-replies after it for a brief overview of the problem. I don't know if @Larry or p6l have discussed this before; to me, this issue decides whether PIL can use user's type annotations toward static typechecks.

Perl 6 has named, multi-parameter generics, known as hierarchical types, which brings with it the variance problem. Currently, there is no syntax in Perl 6 for variance annotation; I propose that we adopt variance inference in the style of O'Haskell, possibly overridable with definition-site annotations in the style of Scala.

As I was often reading those papers and experimenting PIL designs during work breaks, my work with current Perl 5 technologies (Catalyst, Test::Base, DBD::SQLite, PDF::API2) kept me firmly grounded. While Perl 6's better is better mentality makes hard things easier, we must not at any time make easy things harder.

I'm sorry that I can't get around to summarize the amazing developments in a much more advanced JavaScript backend, self-bootstrapping MetaModel, rich new modules for HTTP/CGI and Span/Recurrences, a YAML-based new build system tonight. Meanwhile, chromatic's article on Porting Test::Builder to Perl 6 is a good read; I'm glad I fixed the last showstopping bug two days before it's published. :-)

Day 166 (r5706): Mandel.p6 on Javascript.

After working out the way to implement &last and &return using exceptions, iblech succeeded in getting mandel.p6 compiled to JS. It now works across Gecko, Opera and Internet Explorer, thanks to feedback from Arathorn and castaway,

Currently, it is likely to trigger a script running for too long warning, but Alias from #jsan suggested that we can use a trick employed by jsan:Test.Builder, namely using setTimeOut to fork off a separate thread and handle output by modifying the DOM instead of document.write.

iblech also hacked in support for array dereferencing and named parameters for PIL/JS. I think soon it will make sense to have a make jstest, using SpiderMonkey's bin/js as the runtime.

Continuing the metamodel work, stevan implemented C3 as the canonical method resolution order, and tweaked the constructor/destructor to use it. leo burned it into the Parrot ROM -- I mean VM -- for maximal performance.

Stevan is working on bootstrapping the metamodel, i.e. defining the Perl6::Object class itself as a Perl6::Object. This is analogous to our Prelude.pm work of defining as many Perl 6 builtins in Perl 6 as possible; ultimately, there will only be a handful of true primitives that absolutely has to be provided by the runtime. This ensures an identical semantics on Haskell, Perl5, Parrot and JavaScript backends, and is ultimately what the 6.28.0 milestone is about.

Two common Makefile.PL gotchas got remedied today: rkhill made sure that VC++ on Win32 would not try to build with PUGS_EMBED=perl5, and kolibrie added detection for missing libperl-dev on Debian systems.

After some handholding on p6c, our new committer philcrow added a test for a surprising behaviour: sub foo (?$x = expr) {...} did not execute expr in the subroutine's scope, but rather in caller's scope. I fixed it promptly, so philcrow can commit his newton's method root finder into the examples directory.

Arathorn and I discussed the various confusing semantics of qualified variable names on #perl6, culminating in a p6l post. I didn't realized that the main package is renamed to Main now (in S10). The Synopses indeed have a fractal structure; the more you read into them, the more there is to read...

fglock fixed the misuse of $^x inside Prelude.pm's &ceil and &floor -- implicit variables is only allowed in bare blocks now. He also made Span::Code pass all its tests in span-code.t.

kolibrie added some new test for the not-yet-supported \x{ABCD} notation; eric256 helpfully moved out fixed tests in t/pugsbugs/ into more sensible subdirectories, and tested for misparses in nested hash literals; tobez added a test for "string".reverse misbehaving under list context.

The wizard.p6 RPG was briefly broken by the new namespace handling code. eric256 and I repaired it today, so epic battles with the army of frogs can go on as usual...

Day 165 (r5671): jspugs.pl and PIL redesign.

Following eric256's suggestion, I'm adding the current revision number as part of the journal title. He also would like to reply to my journal with code examples and pick up things I missed; I think that's a great idea, and all lambdacamel are welcome to join the fun. :-)

Today iblech introduced a jspugs.pl, a nice shell for Perl6/JS development. Here is a screenshot:

% cd perl5/PIL2JS/
Welcome to JSPugs -- Perl6 User's Golfing System
Type :h for help.

* Path to pugs:                           ../../pugs           [OK]
* Path to pil2js:                         ./pil2js.pl          [OK]
* Path to the precompiled Prelude:        preludepc.js         [NOT FOUND]
* Path to PIL2JS's lib6/:                 lib6                 [OK]
* Path to the JavaScript output:          output.html          [OK]

jspugs> :h
Commands available from the prompt:
:h                      = show this help message
:q                      = quit
:conf thing [new_value] = set the path to thing
                          (pugs|pil2js|preludepc|lib6|output)
:precomp                = precompile the Prelude
:pil <exp>              = show PIL of expression
:pil.yaml <exp>         = show PIL of expression dumped as YAML
<exp>                   = compile expression and save as HTML
:js <exp>               = compile expression and show it
:l filename.p6          = compile file and save as HTML

jspugs> :precomp
# ../../pugs -Ilib6 -CPIL -MPrelude::JS -e ''
# ./pil2js.pl --no-jsprelude > preludepc.js
* Path to the precompiled Prelude:        preludepc.js         [OK]

jspugs> say "Hello, JSPugs!"
# ../../pugs -Ilib6 -CPIL -e say "Hello, JSPugs!"
# ./pil2js.pl --html --preludepc preludepc.js > output.html
* Path to the JavaScript output:          output.html          [OK]

Neat, no? The output.html contains a link to <script type="text/javascript" src="preludepc.js"></script>. Because the Javascript prelude is shared, code generation is quite fast now. Errors in the code generator are annotated with line/column info, thanks to the source ranges information preserved in PIL.

There is no JSAN support yet, but I suspect that one day we may compile use jsan:Form::Validator; and unite with the rhinocamel world.

In order to get tests passing and mandel.p6 to run, iblech fixed many corner cases in Pugs.Compile, including invocant handling, delayed evaluation and prettyprinting, with helpful feedback from Arathorn and other #perl6 people. Already there is talks about generating SWF/ActionScript and PDF/ECMAScript in addition to HTML output...

iblech also added YAML serialization for PIL structures. It is purely positional and not as concise as I'd like, so I talked with him and putter about how the redesigned PIL should be serialized. The consensus seems to favor a YAML-style model, with all nodes carrying a type, and with a payload of a scalar, a list of nodes, or a hash of named subnodes. For example, pugs -P YAML example.p6 would dump the PIL structure of example.p6 as YAML nodes.

On the MetaModel front, Stevan implemented the C3 Method Resolution Order for multiple-inherited objects. I like C3 a lot, and I agree with Stevan that it should be made into the default Perl 6 method dispatch order. The core idea is that, in a diamond inheritance tree:

              class A;
class B is A;        class C is A;
class BB is B;       class CC is C;
        class Z is BB is CC;

The call to Z.new.method should look up in the order of Z, BB, B, CC, C, A, instead of (as in Perl 5) Z, BB, B, A, CC, C; the latter dispatches to A happend before its subclass C -- this is part of the reason I considered multiple inheritance as insane. C3 restores much sanity here.

mugwump added a trivial implementation of &is_deeply in Test.pm by simply compare their .perl serializations. Clever.

Aankhen fixed &uri_escape in URI::Escape, and reported that printf did not handle upper-case variants of format codes, such as %X. putter fixed that promptly in Prelude.pm.

fglock refactored the infinite recurrence set structure from Span::Code into Recurrence.pm .

putter added Pugs::Internals::rule_pattern to extract the rule string out from an rule object, for his plan of writing a Rule parser in Perl 6. He worked some more on the Perl 6 Rules Grammar, but sadly PGE can't handle it yet.

Zero commits from me today to Pugs, as I'm still in paper-reading and discussion mode. I'm also picking up more $work for post-sabbatical livelihood, until I can find some sort of sponsorship for Pugs; in any case, I will try to keep about 3 days a week for Pugs. No promises, though -- as usual, all I can promise is a committer bit. :-)

Day 164: Perl 6 compiled to... Javascript!

Just as we were getting accustomed to putter's Perl6 on Perl5 work, iblech shocked us all with r5644. I will let the commit log speak for itself:

r5644: iblech | 2005-07-18 01:41:27 +0800
PIL -> JavaScript compiler.

• Pugs.Compile: Modified the declaration of PApp to accept an invocant.
• Pugs.CodeGen.PIR: Minor changes because of change #1, pugs -BPIR still passes the sanity tests.
• New directory perl5/PIL2JS, containing various modules, a README, and pil2js.pl:

    $ pugs -CPIL -Ilib6 -MPrelude::JS -we 'say 2 + 3' | \
      ./pil2js.pl -html > /tmp/t.html

• t/01-sanity mostly pass! (see http://m19s28.vlinux.de/iblech/stuff/not_perm/pil2js-demo/)
• t/01-sanity/03-equal.t doesn't pass because of a bug in Pugs.Compile ("3 || 4" is compiled to "&infix:(3, 4)" instead of "&infix:(3, {4})" or something similar.
• See perl5/PIL2JS/README for a list of things which already work.

Wow. Seeing 05-sub.t compiled into 05-sub.t.html really made my day. Wow.

Day 163: Papers... and more papers.

Before putting PIL evaluator to action, I thought I'd take some time off to read relevant papers. But as I chase the references, everything seems to be related to each other, and before long I find myself reading fascinating things that may not have any obvious connections with PIL. ;-)

Stevan asked me to put links to what I've read. Below is a quite incomplete list, in roughly chronological order.

I started off with the two QuickCheck papers. I had a passing understanding of specification-based testing, mostly via Test::LectroTest, but the papers highlighted many aspects I've never thunk of. Grokking the coarbitary construct is a lot of fun; it is fascinating how QuickCheck can generate arbitary functions randomly, purely based on its type signature.

From QuickCheck I've moved to Scrap your boilerplate with class, the third paper in the SYB series, which provides a nice way to do generic programming in Haskell. In the design pattern world, the generic programming strategies would be known as visitor, composite and other related patterns; in the SYB papers, similar ideas are expressed in a very concise fashion, and the notion of type class variables feels very natural indeed.

SYB's predeccessor, Strafunski, proved to be rather hard to grok in one sitting. I got sidetracked to its SDF component, which describes a nice way to do scannerless parsing -- that is, parsing directly from character level, without a tokenizer. Pugs uses this approach too, and I confess I've never felt the use for a tokenizer. But perhaps I'm spoiled by fast computers, perl5's capable regex engine, and the even more capable Parsec. Still, SGLR/SDF is far easier to reason about than parser combinators or regex with embedded code, and if its claim of superior performance is true, the it's definitely worth more investigation.

From there I moved to the Lambda cube, and the Calculus of constructions (CoC). First-class types and bindings is one of Perl 6's shining new features; the design team recognizes its importance and uses, but very little is understood in how it works in the implementation level, and how it interacts with constraint-based subtyping.

As CoC allows no subtypes, I turned to Scala, an advanced multi-pradigmic language featuring not only subtyping and trait-based mixins, but also generics, views, macros and inferencing, which are all underspecified parts of Perl 6. I have just begun reading the Scala papers, but the first one (the vObj paper) is already extremely enlightening -- especially because it contains detailed comparison with both OO-style languages like Java, as well as functional-style languages in the ML family.

I have also looked at PyPy's parser and evaluator, and skimmed through many other papers in several detours, but the above are the primary ones. The lyf so short, the craft so longe to lerne...

Day 162: Say hello to P5ugs!

Building on yesterday's PIL/P5 evaluator work, today putter started implementing primitive functions in Perl 5, starting with &say:

$ cd pugs/perl5/PIL-Run
$ perl crude_repl.pl
p5ugs> say "Hello, Perl 5!"
----
Hello, Perl 5!

1

If you'd like to join the Perl6-on-Perl5 effort, please see the PIL::Run TODO file. mugwump added readline support for crude_repl.pl, based on his Scriptalicious.pm module.

QtPlatypus interviewed me about the PIL/Macro plans, and the need of a Macro synopsis. He updated the notes/plan file with the raw log; masak cleaned it up a bit, but it can still use some more editing before merging to PA02.

On the Perl 5 MetaModel front, Stevan added support for $?SELF, currently called as SELF() because Perl 5 does not have twigils,.

fglock's work on Span::Code continued apace, adding stringification and intersection support over heterogenous range types.

On the bot front, kolibrie prettified time format for seenbot.p6; coke suggested that svnbot.p6 should print a separate header for each commit, and iblech implemented it promptly. iblech also added branch information for the leo-ctx5 branch -- that's right, the #parrot IRC channel uses Pugs-based svnbot6 to track parrot commits. :-)

Oh, and I managed to find a tiny slice of time to release a new version of Template::Extract, based on brian d foy's excellent suggestion. Maybe I'll manage to find another slice for PAR tomorrow...

Anyway, that's it for today. See you!

Day 161: Prototype PIL evaluator in Perl 5.

Today I did a lot of reading and much less coding. Meijer's Static Typing Where Possible, Dynamic Typing When Needed is very close to lwall's position on Perl 6, and I think a non-intrusive inferencer will be a Good Thing for Perl. A certain summer coder, Gary Jackson, is working on such an inferencer for Perl 5, and I eagerly anticipate his work.

To me, the gist of Meijer's positions is maximizing inference power with optional type annotation, yet do not shy away from runtime checks where static checking becomes infeasible:

1. We should not ditch runtime typechecks as static typing people usually do; otherwise Array of Num becomes monomorphic, and you can't even store an Int into it without verbose casting or wild-card type annotations.
2. We should not ditch type inference as dynamic typing people usually do; inferencing makes program much more concise and optimizers much more efficient -- one can even derive constructors automagically based on static information.

Also I started learning Erlang. For single-process applications, its expressive power is less than Haskell, and I miss static types (but not much), but its handling of messaging and recovery is very elegant. STM captures some of the elegance, but single-assignment makes things so much easier -- after all, variables are much nicer when they cannot change. ;-)

While I was in study mode, some lambdacamels are madly hacking. putter popped up with lots of PIL questions to a confused stevan; we didn't understand what he was getting at, until putter revealed crude_repl.pl, a working Perl 5 interpreter that parses and runs Haskell PIL structures. It is exceedingly kludgy, but we are all suitably impressed:

<autrijus> oh wow, a Hs parser
<wolverian> I think that deserves a respectful silence. or a frightened one.
<stevan> putter: I just thought you were curious, but you are serious :)

Aankhen and iblech did a very simple eval.p6 that evaluates Perl 6 code with eval and $result.perl; I wonder if someone will export the pluggable evaluator (envEval) and evolve this into a debugger shell...

fglock, continuing his work on Span.pm, produced Span::Code, a two-way iterator and recurrence set interface defined with closures. It is quite expressive; see the "all non-zero integers" demo in the synopsis for an example.

On the metamodel front, stevan hacked in submethod support, which verifies that the invocant is indeed monomorphic to the containing class.

scook0 prettified the Haddock a bit; masak wants .<key> = 'value' and wrote tests for it; rafl refactored our debian packaging metadata; iblech... well, did lots of things as usual. :-)

Oh, and it looks like cwest may start adopting an anarchistic model for JSAN development, beginning with the #jsan channel in irc.freenode.net, a public svn repository, in addition to the jsan-devel mailing list. Best wishes to cwest and the imminent legion of rhinocamels!

Day 160: Pugs 6.2.8 released!

After nearly 1000 commits, two hackathons, and an entire month of hard work, I am delighted to announce that Pugs 6.2.8 is finally upon us:

http://pugscode.org/dist/Perl6-Pugs-6.2.8.tar.gz
SIZE = 1309147
SHA1 = efd32419dcddba596044a42564936888a28b3c69

A live CD is available as usual, courtesy of Ingo Blechschmidt:

http://linide.sf.net/pugs-livecd-6.2.8.iso

This release represents a new direction in Pugs development. Instead of a proof-of-concept Perl 6 interpreter, our new focus is toward a full-fledged Perl 6 compiler suite, with a core representation (PIL, Pugs Intermediate Language) and multiple backends, including Parrot, Haskell and Perl 5.

Moreover, we are gradually porting more parts of Pugs from Haskell to Perl 6. In particular, src/perl6/Prelude.pm is now the preferred place to implemente new built-in functions that can be defined with other primitives; the Parrot backend uses more primitives defined in src/perl6/Prelude/PIR.pm.

The next Pugs Apocryphon will cover this new roadmap in detail; meanwhile, please read docs/notes/plan for an overview.

Again, thanks to all lambdacamels for building this new ship with me.

Enjoy!
/Autrijus/

Changes for 6.2.8 (r5573) - July 13, 2005

Pugs Internals

• Added code generation backends: PIR, PIL
  • Pugs can now generate PIL (Pugs Intermediate Language)
  • ...and emit PIR (Parrot Intermediate Representation) from PIL
  • New make pirsmoke target runs test suite using PIR backend
  • Test.pm can be compiled to PIR
  • Prelude/PIR.pm added with Perl 6 versions of some builtins
  • pugs -CPIL -e 'say 123' for dumping PIL from code
• Implicit variables like $^a now only work in bare blocks
• Initial support for %*INC: multiple require calls run only once
• Named binding is now done in an inferencing phase before positional binding
• New Haskell builtins: IO::tell and internal filehandle test functions
• New PIR-specific builtin: leave
• New Prelude builtins: File::seek, localtime, trans
• New builtin classes: Proxy, Control::Caller, Time::Local
• New trait for Prelude.pm: is builtin (installs into the global namespace)
• Pairs in variables now bind to named parameters just like pair literals do
• Parse trusts ClassName and my $foo is trait_name as no-ops
• Parse fractional number literals starting with a leading dot: .1 -.1
• Qualified names and exports now dealt with consistently
• Support for does RoleName and is ClassName within class declarations
• &foo in module Foo now looks up &Foo::foo as well
• @?INIT and @?CHECK renamed back to @*INIT and @*CHECK space
• Bare and Parametric types merged into Block
• MY, OUR, OUTER, CALLER can no longer be used as user-defined packages
• Prelude.pm is now pre-compiled to reduce startup time
• multi foo { ... } is now a shorthand for multi sub foo { ... }
• my Foo $foo .= new(...) parses and works
• our variables in packages now generate qualified symbols
• use perl5:DBI replaces the old use DBI--perl5 syntax

Bundled Modules

• New Perl 6 modules:
  • DateTime::Set
  • DateTime
  • HTTP::Server::Simple
  • Module::Pluggable::Fast
  • Perldoc (partial port)
  • Set::Infinite
  • Span
  • Tree::Visitor and Tree::Visitor::FindByPath
  • WTemplate - the first Perl 6 templating engine
• New Pugs-specific modules:
  • Perl-Compiler, a PIL representation in Perl 6
  • perl5/PIL-Run, a Perl 5 prototype of Perl 6 runtime environment
  • perl5/Perl6-MetaModel, a Perl 5 prototype of Perl 6 object model
• Completed port: Locale::KeyedText
  • Compiles, executes, and passes whole pristine test suite
  • Updated version to 1.5.0, corresponding to the Perl 5 version 1.05
  • Some skips and workarounds remain due to missing Pugs features
• Completed port: Test::Builder

Test, Examples and Documentations

• Examples of methods acting on builtin types in examples/vmethods/
• Interpreter and debugger for the l33t language in examples/obfu/l33t.p6
• Low level sanity tests in t/01-sanity/ for the PIR code emitter
• More JAPHs added to examples/japhs/
• New directories: examples/continuation and examples/unitfunctions
• Overview of PIL-based compilation roadmap in docs/notes/plan
• Perl 6 Rule grammar and related files added to module/Grammars/
• Script to generate Haskell source's import graph as util/importgraph.pl
• Updates and cleanups to PA01; master copy is now docs/01Overview.kwid
• YAPC::NA talk: Apocalypse Now (in docs/talks/Apocalypse_Now.spork)

Bug Fixes

• Call parrot with -G (CGP) instead of -j (JIT) runcore to avoid segfaults
• Fixed !~ to mean negated ~~ instead of ne
• Fixed .isa to agree with smartmatch results
• Fixed order of method invocation in BUILDALL and DESTROYALL
• New environment variable PUGS_PARROT_OPTS for invoking external parrot
• Qualified and global variables may now be used without declaration
• $hashref.does(Hash) now returns true
• &say =:= &say now evaluates to true
• (42).kv now dies and (42,).kv works
• [1] <=> [2] no longer misparsed as [1]{'='}[2]
• caller now counts eval and the topmost main as one frame
• qq{ ... { code } ... } no longer ignores the interpolated code
• redo and next now works correctly inside loop blocks
• sleep() returns seconds slept instead of undef
• try is now capable of catching all type casting errors