=head1 NAME

Magazine_Article_03 - A Plan for Pugs

=head1 AUTHOR

chromatic L<chromatic@oreilly.com>

=head1 VERSION

Its published March 03, 2005 on perl.com and not changed since.
Find the original under:


=head1 ARTICLE

Autrijus Tang (L<http://www.autrijus.org/>) is a talented Perl hacker,
a dedicated CPAN contributor (L<http://search.cpan.org/%7Eautrijus/>), and
a truly smart man.  His announcement of starting an implementation of Perl 6
in Haskell (L<http://use.perl.org/%7Eautrijus/journal/22965>) on February 1,
2005 might have seemed like a joke from almost anyone else. A month later,
his little experiment runs more code and has attracted a community larger
than anyone could have predicted. Perl.com recently caught up with Autrijus
on #Perl6 to discuss his new project: Pugs (L<http://www.pugscode.org/>)>

B<chromatic:>  I've followed your journal from the beginning, but it didn't
start from the start.  Where did you come up with this crazy idea?

B<Autrijus:> Ok. The story is that I hacked SVK (L<http://svk.elixus.org/>) for
many months with clkao (L<http://search.cpan.org/%7Eclkao/>). SVK worked,
except it is not very flexible. There is a VCS named darcs
(L<http://abridgegame.org/darcs/>), which is much more flexible, but is specced
using quantum physics language and written in a scary language called Haskell
(L<http://www.haskell.org/>). So, I spent one month doing nothing but learning
Haskell, so I could understand darcs. Which worked well; I convinced  a crazy
client (who paid me to develop C<Parse::AFP>
(L<http://search.cpan.org/perldoc?Parse::AFP>) that Perl 5 is doomed because it
has no COW (which, surprisingly, it now has), and to fund me to develop an
alternate library using Haskell.

(I mean "Perl 5 is doomed for that task", not "Perl 5 is doomed in general".)

B<chromatic:>  Copy-on-Write?

B<Autrijus:> Yeah.

B<chromatic:>  So that's a "sort-of has".

B<Autrijus:> Yeah. As in, sky (L<http://search.cpan.org/%7Eabergman/>)
suddenly worked on it and claims it mostly works.  Haven't checked the code,

B<chromatic:>  It's been in the works for years.  Or "doesn't works" perhaps.

B<Autrijus:> But I digress. Using Haskell to develop I<OpenAFP.hs> led to
programs that eat constant 2MB memory, scale linearly, and are generally 2OOM
faster than my Perl library.

Oh, and the code size is 1/10.

B<chromatic:>  Okay, so you picked up Haskell to look at darcs to borrow
ideas from for svk, then you convinced a client to pay you to write in Haskell
and you started to like it.  What type of program was this?  It sounds like it
had a bit of parsing.

B<Autrijus:> AFP is IBM's PDF-like format, born 7 years before PDF.
It's unlike PDF in that it's all binary, very bitpacked, and is generally
intolerant of errors.  There was no free library that parses or munges AFP.

B<chromatic:>  Darcs really impressed you then.

B<Autrijus:> The algorithm did. The day-to-day slowness and
fragility for anything beyond mid-sized projects did not. But darcs is
improving. But yeah, I was impressed by the conciseness.

B<chromatic:>  Is that the implementation of darcs you consider slow or the
use of Haskell?

B<Autrijus:> The implementation.  It basically caches no info and
recalculates all unnecessary information.  Can't be fast that way.

B<chromatic:>  Hm, it seems like memoization is something you can add to a
functional program for free, almost.

B<Autrijus:> Yeah, and there are people working on that.

B<chromatic:>  But not you, which is good for us Perl people.

B<Autrijus:> Not me. Sorry.

Anyway. So, I ordered a bunch of books online including I<TaPL>
(L<http://www.cis.upenn.edu/%7Ebcpierce/tapl/index.html>) and I<ATTaPL>
(L<http://www.cis.upenn.edu/%7Ebcpierce/attapl/index.html>) so I could
learn more about mysterious things like Category Theory and Type Inference
and Curry-Howard Correspondence.

B<chromatic:> How far did you get?

B<Autrijus:> I think I have a pretty solid idea of the basics
now, thanks to my math-minded brother Bestian, but TaPL is a very
information-rich book.

B<chromatic:> Me, I'm happy just to recognize Haskell Curry's name.

B<Autrijus:> I read the first two chapters at a relaxed pace.
By the end of second chapter it starts to implement languages for real
and usually by that time, the profs using TaPL as textbook will tell the
students to pick a toy language to implement.

B<chromatic:> I haven't seen you pop up much in Perl 6 land though.
You seemed amazingly productive in the Perl 5 world.  Where'd Perl 6 come in?

B<Autrijus:> As an exercise.  I started using Perl 6 as the exercise.
I think that answers the first question.

Oh. p6 land.

B<chromatic:> More of a playground than a full land, but we have a big pit
full of colorful plastic balls.

B<Autrijus:> Yeah, I was not in p6l, p6i or p6c.  However, the
weekly summary really helped.  Well, because I keep hitting the limit of

B<chromatic:> It seems like an odd fit, putting a language with a good static
type system to use with a language with a loose, mostly-optional type system

B<Autrijus:> Most of more useful modules under my name,
(including the ones Ingy and I inherited from Damian) were forced to be done
in klugy ways because the p5 runtime is a mess.

B<chromatic:> You should see C<Attributes::Scary>. Total sympathy here.

B<Autrijus:> C<Template::Extract>
(L<http://search.cpan.org/perldoc?Template::Extract>) uses C<(?{})> as a 
nondet engine; C<PAR> (L<http://search.cpan.org/perldoc?PAR>) comes with its 
own F<perlmain.c>; let me not mention source filtering. All these techniques
are unmaintainable unless with large dosage of caffeine.

B<chromatic:> Yeah, I fixed some of the startup warnings in C<B::Generate>
(L<http://search.cpan.org/perldoc?B::Generate>) a couple of weeks ago...

B<Autrijus:> Cool. Yeah, C<B::Generate> is abstracted klugery and may pave a
way for Pugs to produce Perl 5 code.

B<chromatic:> Parrot has the chance to make some of these things a lot nicer.
I'm looking forward to that.  Yet you took off down another road.

B<Autrijus:> Actually, I think Pugs and Parrot will meet in the middle. Where
Pugs AST meets Parrot AST and the compiler is written in Perl 6 that can then
be run on Parrot.

B<chromatic:> I thought Pugs would get rewritten in C for Parrot?

B<Autrijus:> No, in Perl 6.

B<chromatic:>  Can GHC (L<http://www.haskell.org/ghc/>) retarget a different
AST then?

B<Autrijus:> It can, but that's not the easier plan.

B<chromatic:> It's easy for me.  I don't plan to do it.

B<Autrijus:> The easier plan is simply for Pugs to have a F<Compile.hs> that
emits Parrot AST.  Which, I'm happy to discover yesterday, is painless to
write. (Ingy (L<http://search.cpan.org/%7Eingy/>) and I did a KwidAST->HtmlAST
compiler in an hour, together with parser and AST.)

B<chromatic:>  Kwid and HTML, the markup languages?

B<Autrijus:> Yeah. Ok. So back to p6. P5's limit is apparent and not easily

B<chromatic:> It sounds like you wanted something more, and soon.

B<Autrijus:> Parrot is fine except every time I build it, it fails.

B<chromatic:> Try running Linux PPC sometime.

B<Autrijus:> Freebsd may not be a good platform for Parrot, I gathered. Or my
CVS luck is really bad. But I'm talking about several months ago.

B<chromatic:> 4.x or 5.x?

B<Autrijus:> 5.x.

B<chromatic:> Ahh, perhaps it was ICU (L<http://icu.sourceforge.net/>).

B<Autrijus:> Two out of three times is.  I think.

B<chromatic:> I guess it's too late to interest you in a Ponie then.

B<Autrijus:> I was very interested in Ponie (L<http://www.poniecode.org/>).
I volunteered to Sky about doing svn and src org and stuff, but svn was not
kind for Ponie.

B<obra:> Well, that was before svn 1.0

B<Autrijus:> Right. Now it all works just fine, except I<libsvn_wc>, but we
have svk now, and I learned that Sky has been addicted to svk.

But anyway. And the beginning stage of Ponie is XS hackery which is by far
not my forte. I've read Lathos' book (L<http://www.manning.com/jenness/>),
so I can do XS hackery when forced to but not on a volunteer basis. Oh no.

B<chromatic:> That's a special kind of pain.  It's like doing magic tricks,
blindfolded, when you have to say, "Watch me push and pop a rabbit out of this
stack.  By the way, don't make a reference to him yet...."

B<Autrijus:> So, on February 1, when I had too much caffeine and couldn't
sleep, I didn't imagine that Pugs would be anything near a complete
implementation of Perl 6.  I was just interested in modeling junctions but
things quickly went out of control.  And some other nifty things like
subroutine signatures.

B<chromatic:> There's a fuzzy connection in the back of my head about
Haskell's inferencing and pattern matching being somewhat similar.

B<Autrijus:> Sure. Haskell has very robust inferencing, pattern matching,
and sexy types. Which I'm trying to inflict on luqui (L<http://www.luqui.org/>
- Luke Palmer) to improve Perl 6's design.

B<chromatic:> As long as they do the right thing with regard to roles, go

B<Autrijus:> They do. :)

B<chromatic:> This was an academic exercise though?

B<Autrijus:> Yeah. It stayed as an academic exercise I think for two days.

B<chromatic:> "Hey, this Perl 6 idea is interesting.  I wonder how it works
in practice?  I bet I could do it in Haskell!"

B<Autrijus:> Yup.  Using it as nothing more than a toy language to experiment with, initially targeting a reduced set of Perl 6 that is purely functional. 
But by day three, I found that doing this is much easier than I thought.

B<chromatic:> Did you say "highly reduced"?

B<Autrijus:> Yeah.  Term is "featherweight".

B<chromatic:> What makes it easier?

B<Autrijus:> Parsec (L<http://www.cs.uu.nl/%7Edaan/parsec.html>) and ContT
(L<http://www.nomaware.com/monads/html/contmonad.html>). Parsec is like
Perl 6 rules.

B<chromatic:> Parsec's the most popular Haskell parsing library, right?

B<Autrijus:> Well, Parsec and Happy (L<http://www.haskell.org/happy/>).
Happy is more traditional; you write in a yacc-like grammar thing and it
generates a parser in Haskell for you. Parsec is pure Haskell. You just
write Haskell code that defines a parser.  The term is "parser combinator".

B<chromatic:> Haskell is its own mini-language there.

B<Autrijus:> It's a popular approach, yes. When you see "blah combinatar
library", think "blah mini-language".

B<chromatic:> I looked at the parser.  It's surprisingly short.

B<Autrijus:> And yet quite complete.  Very maintainable, too.

B<chromatic:> Now I've also read the Perl 5 parser, in the sense that I
picked out language constructs that I recognized by name.  Is it a combination
parser/lexer, or how does that work?  That's the tricky bit of Perl 5, in that
lexing depends on the tokens seen and lots of context.

B<Autrijus:> Yup. It does lexing and parsing in one pass, with infinite
lookahead and backtracking.  Each lexeme can define a new parser that works
on the next lexeme.

B<chromatic:> Does that limit what it can do?  Is that why it's purely
functional Perl 6 so far?

B<Autrijus:> The purely functional Perl 6 plan stops at day 3. We are now fully
IO.  Started with C<say()>, and mutable variables, and C<return()>, and
C<&?CALLER_CONTINUATION>.  So there's nothing functional about the Perl 6 that
Pugs targets now :).

B<chromatic:> Does Haskell support continuations and all of those funky things?

B<Autrijus:> Yes. And you can pick and match the funky things you want
for a scope of your code.  "In this lexical scope I want continuations";
dynamic scope, really.  "In that scope I want a logger." "In that scope
I want a pad."

B<chromatic:> Performance penalty?

B<Autrijus:> Each comes with its own penalty, but is generally small.  GHC,
again, compiles to very fast C code.

B<chromatic:> Can you instrument scopes at runtime too?

B<Autrijus:> Sure.  C<&?CALLER::SUB> works.  And C<$OUTER::var>.

B<chromatic:> Are you compiling it to native code now? I remember that being
a suggestion a few days ago.

B<Autrijus:> Pugs itself is compiled to native code; it is still evaluating
Perl 6 AST, though.

B<chromatic:> It's like Perl 5 in that sense then.

B<Autrijus:> Yes, it's exactly like Perl 5. Have you read PA01?

B<chromatic:> I have.

B<Autrijus:> Cool.  So yeah, it's like Perl 5 now.  The difference is B::* is
trivial to write in Pugs.

B<chromatic:> Except maintainable.

B<Autrijus:> And yeah, there's the maintainable bit. Pugs is <4k lines of code.
I think porting Pugs to Perl 6 will take about the same number of lines, too.

B<chromatic:> You already have one module, too.

B<Autrijus:> Yup.  And it's your favorite module.

B<chromatic:> I've started a few attempts to write Test::Builder
(L<http://search.cpan.org/perldoc?Test::Builder>) in Parrot, but I'm missing
a few pieces.  How far along are classes and objects in Pugs?

B<Autrijus:> They don't exist.  6.2.x will do that, though. But the short term
task is to get all the todo_() cleaned.  which will give us an interpreter that
really agrees with all synopses.  At least in the places we have implementation
of, that is.

B<chromatic:> I see in the dailies that you are producing boatloads of
runnable Perl 6 tests.

B<Autrijus:> Yup, thanks to #Perl6.  I seldom write tests now :) The helpful
committers do that for me.

B<chromatic:> How do you know your code works then?

B<Autrijus:> I just look at newest todo_ and start working on it.

B<chromatic:> Oh, they write tests for those before you implement them?

B<Autrijus:> Yup.  It's all test-first.

B<chromatic:> Okay, I'll let you continue then.

B<Autrijus:> Ha.  So yeah, the cooperation has been wonderful.
Camelfolks write tests and libraries, and lambdafolks makes those tests pass.
If a camelfolk wants a particular test to pass sooner, then that person can
learn from lambdafolk :). Things are easy to fix, and because of the coverage
there's little chance of breaking things.  If lambdafolks want to implement
new things that may or may not agree with synopses or p5 norm, then they
learn from camelfolks.

B<chromatic:> Have you started giving Haskell tutorials?  I know Larry and
Patrick have started to pick up some of it.  I'm pretty sure Luke and Damian
have already explored it (or something from the same family tree).

B<Autrijus:> I think I've read a paper from Damian that says
he taught Haskell in monash.  It's before the monadic revolution though.

B<chromatic:> If not Haskell, certainly something from the ML family.

B<Autrijus:> Right.  So, I've been pointing people to YAHT
(L<http://www.isi.edu/%7Ehdaume/htut/>) and #Haskell.

B<chromatic:> It sounds like you're attracting people from both sides of the
fence then.

B<Autrijus:> It indeed is. I get svn/svk patches and darcs patches.

B<chromatic:> Is there a lot of overlapping interest?  Where does it come from?

B<Autrijus:> Well, ever since the monadic revolution of '98 Haskell people have
started to do real world apps.

B<chromatic:> Now that they can do IO, for example.

B<Autrijus:> Yeah. It's been only 7 years ago.  And recently
Haskell world has its native version control system; a Perl-review like
magazine, cpan/makemaker-like infrastructure, etc.  So it's growing fast.

B<chromatic:> There's still a lot of attraction there for real world
applications, of which Pugs is one?

B<Autrijus:> Pugs is a practical project in that working on it has a chance
of solving real problems, and is very fun to boot.  And although p5 got no
respect, in general p6 is very slick.  So the mental barrier is lower for
lambdafolks to join, I think.

B<chromatic:> The lambdafolks like what they see in Perl 6?

B<Autrijus:> Yup.  I quoted Abigail on #Haskell a while ago.

B<chromatic:> I saw something earlier about access to libraries and such.
Do you have a plan for the XS-alternative?

B<Autrijus:> Yeah, Ingy is working on it F<ext/Kwid/> eventually inline
Haskell code.  And with luck, inline other kinds of code as well through
Haskell direct (the Haskell equiv of Inline).

B<chromatic:> Is this within Pugs or Perl 6 atop Pugs?

B<Autrijus:> It's within Pugs. The Parrot side had not been

B<chromatic:> Yeah, the Parrot AST needs more documentation.
You're devoting a lot of time to it.  Obra mentioned that you've cleared
most of your paying projects out of the way for the time being.  What's
the eventual end?

B<Autrijus:> And whither then? I cannot say :). As you mentioned, I've
diverted most of my paying projects away so I should have at least 6 months
for Pugs.

B<chromatic:> How about in the next month?

B<Autrijus:> This month should see robust semantics for basic
operations, the beginning of classes and objects, and many real modules
hooks to Haskell-side libraries.

B<chromatic:> I'll do T::B then.

B<Autrijus:> Oh and Pugs hands out committer bit liberally so if you want to
do T::B, I'll make you a committer :). You can start now actually. Just
write imaginary Perl 6 code, and we'll figure out how to make it run. Most
of the F<examples/*> started that way.

B<chromatic:> Ah, I'll take a look.

B<Autrijus:> Oh. Right. I was quoting Abigail.
"Programming in Perl 5 is like exploring a large medieval castle, surrounded
by a dark, mysterious forest, with something new and unexpected around each
corner. There are dragons to be conquered, maidens to be rescued, and holy
grails to be quested for. Lots of fun."

"Perl 6 looks like a Louis-XVI castle and garden to me. Straight, symmetric,
and bright. There are wigs to be powdered, minuets to be danced, all quite

I, for one, am happy for Perl to move from the dark age to the age of
enlightenment.  I think many camelfolks and lambdafolks share the same
sentiment :).