Parrot Bug Day, 17 May 2008

The next monthly Parrot release will take place next Tuesday, 20 May 2008. In preparation for the release, we're holding yet another monthly Bug Day, all day Saturday 17 May. Parrot hackers, contributors, fans, and hangers-on will gather in #parrot on irc.perl.org to discuss proposed patches, verify and close bugs, and help potential new contributors download, configure, build, and understand Parrot and languages hosted in the Parrot repository. If you're interested in Parrot, have some free time, and want to get your hands a little bit dirty with code, please join us. You don't need to know how to program C or PIR or even Perl 5, but knowing how to download code from a public Subversion repository and build a C program will be very helpful.

700 Ticket Challenge...

… whoops, you missed it.

chromatic challenged parrotteers on Tuesday to get the number of open/new tickets in RT down to 700 before he cuts the monthly release on May 20th. As of now, we're down to 698, twelve days early!

This is still a lot of tickets, but there's still a lot of simple cleanup that can be done.

• Bug reports on old versions of parrot. We are now releasing code every month, and there's a good chance that a bug reported on a previous version no longer exists, or has changed presentation. Try to duplicate the issue with svn-latest or the most recent dev release, and add a note indicating if you could for your platform/revision.
  
• Apply patches! If you're not sure if a patch should be applied, you can still help by trying to apply it to trunk and see if it even applies cleanly; if not, reply to the requester (and the parrot mailing list) asking them to rebase their patch and resubmit it.
  
• Triage TODO items. Many of the TODO items came from XXX comments in the code. Check to see if this is an actual coding task, or something that can be solved by a simple documentation patch.
• Close tickets! Sometimes a ticket will end up getting resolved via comments in email (saved as history on the ticket), but a bug admin simply hasn't gotten around to closing the ticket yet. If you're not a bug admin, you can ping the parrot-porters mailing list at perl.org or let us know on IRC (#parrot on irc.perl.org)
  

Keeping a better handle on what we have in our issue list helps us know how much work is left before we get to 1.0.

So, even if you're not comfortable with hacking on parrot guts, consider helping out with the queue. This can free up those hackers to spend more time implementing features and fixing bugs.

And if you are comfortable, feel free to grab a bug and dig in!

Thanks!

Output of Episode 9's Game of Life

In Episode 9, the source code for John Conway's Game of Life was posted. If you don't feel like doing exercises or just want to see what it looks like without doing any trouble, here's what it looks like (this is life generation 9).

-----------------------------------------
-----------------------------------------
-----------------------------------------
-----O-----------------------------------
----OO-----------------------------------
--OO--O----------------------------------
-----OO----------------------------------
--OOOOO------------------OOO-------------
------------------------O---O------------
-----------------------O-----O-----------
----------------------O---O---O----------
----------------------O--O-O--O----------
----------------------O---O---O----------
-----------------------O-----O-----------
------------------------O---O------------
-------------------------OOO-------------
-----------------------------------------
-----------------------------------------
-----------------------------------------
-----------------------------------------
-----------------------------------------

Life - generation: 9

But really, it doesn't compare to seeing this program run on Parrot :-)

Update: The sources for Squaak have been added to the Parrot repository. Update your local copy today, run Configure, build Squaak, and run "../../parrot squaak.pbc examples/life.sq".

Solutions to the PCT Tutorial Exercises

Below you can find links to the solutions to the exercises of the PCT tutorial.
Episodes 1 and 2 didn't have any exercises.

1. Episode 3
2. Episode 4
3. Episode 5
4. Episode 6
5. Episode 7
6. Episode 8
7. Episode 9
   

Solutions to the Exercises of Episode 8

1. We've shown how to implement keyed variable access for arrays, by implementing the action method for index. The same principle can be applied to keyed access for hashtables. Implement the action method for key.

method key($/) {
my $key := $( $<expression> );

make PAST::Var.new( $key, :scope('keyed'),
                         :vivibase('Hash'),
                         :viviself('Undef'),
                         :node($/) );
}

2. Implement the action methods for array_constructor and hash_constructor. Use a PAST::Op node and set the pasttype to 'call'. Use the "name" attribute to specify the names of the subs to be invoked (e.g., :name("!array") ). Note that all hash fields must be passed as named arguments. Check out PDD26 for doing this, and look for a "named " method.

method named_field($/) {
    my $past := $( $<expression> );
    my $name := $( $<string_constant> );
    ## the passed expression is in fact a named argument,
    ## use the named() accessor to set that name.
    $past.named($name);
    make $past;
}

method array_constructor($/) {
    ## use the parrot calling conventions to 
    ## create an array, 
    ## using the "anonymous" sub !array 
    ## (which is not a valid Squaak name)
    my $past := PAST::Op.new( :name('!array'), 
                              :pasttype('call'), 
                              :node($/) );
    for $<expression> {
        $past.push($($_));
    }
    make $past;
}

method hash_constructor($/) {
    ## use the parrot calling conventions to 
    ## create a hash, using the "anonymous" sub 
    ## !hash (which is not a valid Squaak name)
    my $past := PAST::Op.new( :name('!hash'), 
                              :pasttype('call'), 
                              :node($/) );
    for $<named_field> {
        $past.push($($_));
    }
    make $past;
}

3. We'd like to add a little bit of syntactic sugar for accessing hashtable keys. Instead of writing foo{"key"}, I'd like to write foo.key. Of course, this only works for keys that do not contain spaces and such. Add the appropriate grammar rule (call it "member") that enables this syntax, and write the associated action method. Make sure this member name is converted to a string.
Hint: use a PAST::Val node for the string conversion.

rule postfix_expression {
| <key> {*}         #= key
| <member> {*}      #= member
| <index> {*}       #= index
}

rule member {
'.' <identifier>
{*}
}

method member($/) {
my $member := $( $<identifier> );
## x.y is syntactic sugar for x{"y"},
## so stringify the identifier:
my $key    := PAST::Val.new( :returns('String'),
                            :value($member.name()),
                            :node($/) );

## the rest of this method is the same
## as method key() above.
make PAST::Var.new( $key, :scope('keyed'),
                         :vivibase('Hash'),
                         :viviself('Undef'),
                         :node($/) );
}

Solutions to the Exercises of Episode 7

1. Currently, Squaak only has grammar rules for integer and string constants, not floating point constants. Implement this grammar rule. A floating-point number consists of zero or more digits, followed by a dot and at least one digit, or, at least one digit followed by a dot and any number of digits. Examples are: 42.0, 1., .0001. There may be no whitespace between the individual digits and the dot. Make sure you understand the difference between a "rule" and a "token".

token float_constant {
    [
    | \d+ '.' \d*
    | \d* '.' \d+
    ]
    {*}
}

2. Implement the missing operators: (binary) "-", "<=", ">=", "==", "!=", "/", "%", "or"

For sake of completeness (and easy copy-paste for you), here's the list of operator declarations as I wrote them for Squaak:

rule expression is optable { ... }

proto 'infix:or' is precedence('1')
                 is pasttype('unless') { ... }
proto 'infix:and' is tighter('infix:or')
                  is pasttype('if') { ... }

proto 'infix:<'   is tighter('infix:and') { ... }
proto 'infix:<='  is equiv('infix:<') { ... }
proto 'infix:>'   is equiv('infix:<') { ... }
proto 'infix:>='  is equiv('infix:<') { ... }
proto 'infix:=='  is equiv('infix:<') { ... }
proto 'infix:!='  is equiv('infix:<') { ... }

proto 'infix:+'   is tighter('infix:<')
                  is pirop('n_add')   { ... }
proto 'infix:-'   is equiv('infix:+')   
                  is pirop('n_sub')   { ... }

proto 'infix:..'  is equiv('infix:+')   
                  is pirop('n_concat') { ... }

proto 'infix:*'   is tighter('infix:+') 
                  is pirop('n_mul')     { ... }
proto 'infix:%'   is equiv('infix:*')   
                  is pirop('n_mod')     { ... }
proto 'infix:/'   is equiv('infix:*')   
                  is pirop('n_div')     { ... }

proto 'prefix:not' is tighter('infix:*')   
                   is pirop('n_not')   { ... }
proto 'prefix:-'   is tighter('prefix:not')
                   is pirop('n_neg')   { ... }

proto 'term:'      is tighter('prefix:-') 
                   is parsed(&term)      { ... }

Solutions to the Exercises in Episode 6

Without further ado, the solution to the exercise in Episode 6:

1. By now you should have a good idea on the implementation of scope in Squaak. We haven't implemented the for-statement yet, as it needs proper scope handling to implement. Implement this. Check out Episode 3 for the BNF rules that define the syntax of the for-statement. When implementing it, you will run into the same issue as we did when implementing subroutines and parameters. Use the same trick for the implementation of the for-statement.

First, let us look at the BNF of the for-statement:

for-statement ::= 'for' for-init ',' expression [step]
                  'do'
                  block
                  'end'

step          ::= ',' expression

for-init      ::= 'var' identifier '=' expression

It's pretty easy to convert this to Perl 6 rules:

rule for_statement {
    'for' <for_init> ',' <expression> <step>?
    'do' <statement>* 'end'
    {*}
}

rule step {
    ',' <expression>
    {*}
}

rule for_init {
    'var' <identifier> '=' <expression>
    {*}
}

Pretty easy huh? Let's take a look at the semantics. A for-loop is just another way to write a while loop, but much easier in certain cases. This:

for var <ident> = <expr1>, <expr2>, <expr3> do
   <statement>*
end

corresponds to:

do
  var <ident> = <expr1>
  while <ident> <= <expr2> do
     <statement>*
     <ident> = <ident> + <expr3>
  end
end

If <expr3> is absent, it defaults to the value "1". Note that the step expression (expr3) should be positive; the loop condition contains a "<=" operator. When you specify a negative step expression, the loop variable will only decrease in value, which will never make the loop condition false (unless it overflows, but that's a different issue; this might even raise an exception in Parrot; this I do not know). Allowing negative step expressions introduces more complexity, which I felt was not worth the trouble for this tutorial language.

Note that the loop variable <ident> is local to the for loop; this is expressed in the equivalent while loop by the surrounding do/end pair: a new do/end pair defines a new (nested) scope; after the "end" keyword, the loop variable is no longer visible.

Let's implement the action method for the for-statement. As was mentioned in the exercise description, we're dealing with the same situation as with subroutine parameters. In this case, we're dealing with the loop variable, which is local to the for-statement. Let's check out the rule for for_init:

method for_init($/) {
    our $?BLOCK;
    our @?BLOCK;

    ## create a new scope here, so that we can
    ## add the loop variable
    ## to this block here, which is convenient.
    $?BLOCK := PAST::Block.new( :blocktype('immediate'),
                                :node($/) );
    @?BLOCK.unshift($?BLOCK);

    my $iter := $( $<identifier> );
    ## set a flag that this identifier is being declared
    $iter.isdecl(1);
    $iter.scope('lexical');
    ## the identifier is initialized with this expression
    $iter.viviself( $( $<expression> ) );

    ## enter the loop variable into the symbol table.
    $?BLOCK.symbol($iter.name(), :scope('lexical'));

    make $iter;
}

So, just as we created a new PAST::Block for the subroutine in the action method for parameters, we create a new PAST::Block for the for-statement in the action method that defines the loop variable. (Guess why we made for-init a subrule, and didn't put in "var <ident&gt = <expression>" in the rule of for-statement). This block is the place to live for the loop variable. The loop variable is declared, initialized using the viviself attribute, and entered into the new block's symbol table. Note that after creating the new PAST::Block object, we put it onto the stack scope.

Now, the action method for the for statement is quite long, so I'll just embed my comments, which makes reading it easier.

method for_statement($/) {
    our $?BLOCK;
    our @?BLOCK;

First, get the result object of the for statement initialization rule; this is the PAST::Var object, representing the declaration and initialization of the loop variable.

    my $init := $( $<for_init> );

Then, create a new node for the loop variable. Yes, another one (besides the one that is currently contained in the PAST::Block). This one is used when the loop variable is updated at the end of the code block (each iteration). The difference with the other one, is that it doesn't have the isdecl flag, and it doesn't have a viviself clause, which would result in extra instructions checking whether the variable is null (and we know it's not, because we initialize the loop variable).

    ## cache the name of the loop variable
    my $itername := $init.name();
    my $iter := PAST::Var.new( :name($itername),
                               :scope('lexical'),
                               :node($/) );

Now, retrieve the PAST::Block node from the scope stack, and push all statement PAST nodes onto it.

    ## the body of the loop consists of the statements written by the user and
    ## the increment instruction of the loop iterator.

    my $body := @?BLOCK.shift();
    $?BLOCK  := @?BLOCK[0];
    for $<statement> {
        $body.push($($_));
    }    

If there was a step, we use that value; otherwise, we use assume a default step size of "1".
Negative step sizes won't work, but if you Feel Lucky, you could go ahead and try. It's not that hard, it's just a lot of work, and I'm too lazy for that now.... ehm, I mean, I leave it as the proverbial exercise to the reader.

    my $step;
    if $<step> {
        my $stepsize := $( $<step>[0] );
        $step := PAST::Op.new( $iter, $stepsize, :pirop('add'), :node($/) );
    }
    else { ## default is increment by 1
        $step := PAST::Op.new( $iter,
                               :pirop('inc'),
                               :node($/) );
    }

The incrementing of the loop variable is part of the loop body, so add the incrementing statement to $body.

    $body.push($step);

The loop condition uses the "<=" operator, and compares the loop variable with the maximum value that was specified.

    ## while loop iterator <= end-expression
    my $cond := PAST::Op.new( $iter, $( $<expression> ),
                              :name('infix:<=') );

Now we have the PAST for the loop condition and the loop body, so now create a PAST to represent the (while) loop.

    my $loop := PAST::Op.new( $cond, $body,
                              :pasttype('while'),
                              :node($/) );

Finally, the initialization of the loop variable should go before the loop itself, so create a PAST::Stmts node to do this:

    make PAST::Stmts.new( $init, $loop,
                          :node($/) );
}

Wow, we've done it! This was a good example of how to implement a non-trivial statement type using PAST.