A Perl6 Christmas
Dave Whipp, 02 January 2009
When asked when Perl6 will be ready, the standard reply from people working on it is “Christmas” – but the year is unspecified. This Christmas I decided to play with Rakudo, the implementation based on Parrot. It not finished yet but significant progress has been made.
My trial began with a post on rakudo.org by Patrick Michaud suggesting that people wanting to play with Perl6 might try using it to implement solutions to Microsoft’s Winter Scripting Games. There were caveats that it’s still a work in progress – only around 5000 tests from the Perl6 test suite were passing at the time – but it was sufficiently far along to be somewhat usable. He asked that we report back our experiences – hence this write up.
First thing to do was to get the latest and greatest Rakudo. I’d installed a few versions of Parrot from the monthly releases, but I decided that I should be on the cutting edge – changes were happening fast! I followed the instructions on parrot.org to sync the svn repository; build parrot; and finally Rakudo (currently in parrot/languages/perl6). Things went smoothly.
% ./perl6 –e ‘say “hello world”’
hello world
The goal of this challenge was to count the number of “pairs” in a hand of cards. To simplify, we can ignore the suite, and simply view it as a list of face values. For a set of values “2,3,3,5,5” the answer would be two; for “7,5,7,7,King”, the correct answer is three (there are three ways to get a pair of sevens from that list).
I immediately thought of the new cross-product operator:
my @x = < 7 5 7 7 13 >;
say for @x X~X @x;
Here I found my first p6 gotcha. In perl5, "say for @x" will print the values of @x, one per line. In Perl6, $_ is not implicit in a function call to the builtins: you need to use a method call:
.say for @x X~X @x;
In fact, I’d found my first bug in Rakudo: the synopsis states that “say” called with no arguments should result in a (meaningful) compiler error. It currently just prints a blank line (which is actually quite useful).
The combinations operator used to combine a list against itself will return all pairings of that list. For something to be a pair, the two values will be the same. So what I need to do is to count the number of combinations of elements for which the value is the same:
say ((@x XeqX @x).grep:{ $^same }).elems;
David Romano suggested a more elegant approach for counting them:
say [+] @x XeqX @x
which takes advantage of the fact that Boolean values numerify to 0 and 1.
Whichever counting approach is used, the final answer is way too big. The X operator returns all the permutations, thus counting each pairing twice. In addition, every element is paired with itself. We need to adjust the result:
say ( ([+] @x X==X @x) - @x.elems)/2;
This indeed prints the correct answer. And it nicely shows the power of P6. But it also suggests that more power is needed. The need to adjust the result to eliminate duplicates is bad. What is really needed is an operator that returns combinations of a list with itself, instead of permutations. I’d like to define:
sub infix:<%%> ( Any @list, Int $elems ) { … }
which would return all lists of length $elems that can be formed by taking items from @list without changing the order of the elements. Such an operator would work well (alongside the cross-product operator) as a part of the standard library. In addition to that, a second (prefix) operator
sub prefix:<%eq%> ( Any @list ) { … }
could return the list of equality tests for pairs from “@list %% 2”. We’d probably want to define that as a meta-operator (any infix operator between the “%...%” brackets, analogous to “X…X”. Unfortunately it’s not clear how to define this from the Perl6 spec. And Rakudo doesn’t even support basic operator definitions yet.
So a reasonable answer to the original challenge, using the current state of Rakudo, is something like:
sub number_of_pairs( @list ) {
return ( ([+] @list XeqX @list) - @list.elems ) / 2;
}
The pair counting challenge turned out to be a “one liner” in Perl6. This challenge proved slightly meatier. The goal is to calculate the score of a game of 10 pin bowling from a list of individual bowl scores. See the scripting-games website for more details if you don’t know the rules for calculating the score.
The characteristic of this challenge is that to calculate the score for one frame, we may need to look ahead to subsequent bowls. I decided to tackle this problem using “multi” subs – “multi frame_score { … }”. First though, the code that uses the “frame score” routine:
my @scores = <2 5 7 / 8 1 X 9 / 5 3 7 0 4 5 X 2 0>;
…
my $total = 0;
while @scores {
$total += frame_score |@scores;
say "score now $total";
my $bowls_consumed = @scores[0] eq “X” ?? 1 !! 2;
@scores.shift for ^$bowls_consumed;
}
This simply loops, consuming scores, until the list of scores is empty.
For the multi-methods, I started out by attempting to describe the different scoring patterns. There turn out to be eight of them. To describe them succinctly required an insight from Aristotle that we could use subset types to describe the different types of score:
subset Strike of Any where
{ $_ eq 'X' };
subset Spare of Any where { $_ eq
'/' };
subset Some of Any where {
$_ ~~ /\d/ };
multi frame_score ( Strike $a, Strike
$b, Strike $c ;; *@next ) { 30 }
multi frame_score ( Strike $a, Strike
$b, Some $c ;; *@next ) { 20 + $c }
multi frame_score ( Strike $a,
Some $b, Spare $c ;; *@next ) { 20 }
multi frame_score ( Strike $a,
Some $b, Some $c ;; *@next ) { 10 + $b + $c }
multi frame_score ( Some $a,
Spare $b, Strike $c ;; *@next ) { 20 }
multi frame_score ( Some
$a, Spare $b, Some $c ;; *@next ) { 10 + $c }
multi frame_score ( Some
$a, Some $b ;; *@next ) {
$a + $b }
I moved next to the challenge of finding words that correspond to phone numbers. Keypads on Phones associate each number with some number of letters. In the US, it is common for businesses to quote their phone numbers using words from these letters. This challenge was to find words that match a phone number, from a given dictionary of words. I could have simply pre calculated the phone number for each word and stored them in a hash. However, I chose a more “clever” implementation (i.e. probably not the one I’d use for real) that took advantage of junctions:
my @words = <
SEEDING
READING
ELEMENT
>.map: { [ .split("") ] };
This simply stores each word as an (anonymous) array of letters. It would be nice to have a more direct way to treat a sequence of characters as a list, but for Perl6 it appears that, as with Perl5, it is necessary to do this explicitly.
Next I use a similar pattern to describe the mapping of digits to letters:
my @mappings = <
0
1
ABC
DEF
GHI
JKL
MNO
PQRS
TUV
WXYX
>.map: { all .split("") };
This creates an array of 10 elements (one for each digit). Each element is an “all” junction of the letters that correspond to that digit. It’s an “all” junction because we’ll later use it with a “does not equal” test – we need “any” junctions for positive tests; “all” junctions for negative:
sub word_matches_number ( @word, @phone ) returns Bool {
return False unless @word.elems == @phone.elems;
return ! (^@word).grep: { @word[$^idx] ne @mappings[@phone][$^idx] };
}
This is not as elegant as I would have wished. I’m iterating using the indices of the arrays; and there’s the double negative. What I actually wanted, but which is not yet implemented in Rakudo, is to use a deep equality check, using an “any” junction of digit->letter mappings:
return @word === @mappings[@phone]
As Rakudo matures, I’ll probably revisit this to check that it works as I expect.
The remainder of the program isn’t particularly interesting:
sub find_word( $phone ) {
my @phone = $phone.split("");
for @words -> @word {
if word_matches_number( @word, @phone ) {
say "number: { @phone }";
say "result: { @word }";
return
}
}
}
One thing I discovered working with this is that I don’t yet grok Perl6 sigils. In perl5 things are simple: the sigil tells you what value to expect. In perl6, the sigil relates more to the container of the value. This difference results in my intuition letting me down – Perl6 doesn’t always do what I mean. For example, if you attempt to iterate an array-of-arrays using a for loop
for @A_of_A -> @inner_array {
then the inner array-ref is not fully dereferenced. You still need to flatten it to form a junction:
my $junction = any |@inner_array
By this time, I was getting more confidence. I looked at a couple of the other challenges, and immediately say that they could be implemented as one-lines.
A simple (though not the most efficient) way to check if a number is prime is to test if it is divisible by any smaller prime:
my @primes; for 2 .. 200 -> $n {
@primes.push($n) unless $n % any(@primes)==0
}
.say for @primes'
In many languages this requires a bit of thought – or at least some recursion. In perl6:
my @teams = "A" .. "F";
my @games = (@teams X~X @teams).grep: { [le] $_.split("") };
.say for @games.pick( @games.elems )
That middle line is horribly over-complex, however. What It’s doing is to filter the permutations of a list down to its combinations. Let’s assume we have the “combinations” operator that I described earlier and rewrite it:
my @teams = "A" .. "F";
my @games = @teams %% 2;
.perl.say for @games.pick( @games.elems )
Much better!
The final challenge was blackjack. The instructions said that we could choose to implement that aces always equal 11, but that seemed insufficiently interesting: I wanted to use junctions!
I started wtih simple definition of a deck of cards. The challenge required humanly named cards: so I create a list of pairs, and then cross against the list of suites. The deck is then shuffled using the “pick” method
my @values = (
ace => 1|11,
two => 2,
three => 3,
four => 4,
five => 5,
six => 6,
seven => 7,
eight => 8,
nine => 9,
ten => 10,
jack => 10,
queen => 10,
king => 10,
);
my @suites = < spades clubs diamonds hearts >;
my @deck = ( @values X @suites ).map: {
my ($name, $value) =
$^a.kv;
"$name of
$^b" => $value
};
my @cards = @deck.pick( @deck.elems );
Once I have a list of cards, dealing it is a simple matter of shifting cards from the top of the deck. A few “print” statements tell the player (user) what the situation is.
my @dealer;
my @player;
@dealer.push( @cards.shift );
@player.push( @cards.shift );
@dealer.push( @cards.shift );
say "DEALER:";
say @dealer[0].key; #only display the first card of dealer's hand
say "";
say "PLAYER:"; .key.say for @player;
Now we come to the main player loop. Card values are junctions, so I don't need to worry about calculating all possible values of hands that include aces. However, I do need to remember to not test for "bust" using a "greater-than" test. Because of the logic of "any" junctions, I need to check only for “21 is WIN” and then "less than 21 is not bust”. The fact that I need to get this straight when writing the code suggests that it may be a source of bugs with future maintenance. I’d advise the code that uses junctional algebra should include some comments to remind maintainers (including the original author) what assumptions need to be kept in mind
my $player_value = [+] @player.map: { .value }; # an “any” junction
loop {
my $card = @cards.shift;
@player.push( $card );
say $card.key;
$player_value += $card.value;
say "current value is { $player_value.perl }";
if $player_value == 21 {
say "congradulations, you win!";
exit 0;
}
elsif $player_value < 21 {
say "hit (h) or stay (s)";
my $choice = "stay" unless $player_value < 16;
#TODO: read =$*IN
say $choice;
last if $choice ~~ /s/;
}
else {
say "Sorry, you bust!";
exit 0;
}
}
say “”;
If we don’t hit any of the “exit 0” statements (i.e. win or bust) then eventually we’ll “stay” and let the dealer play. A problem here was to figure out what "player value" to use: we need to collapse the junction. If a player hand is (ace, ace, eight), then possible values are 10, 20, and 30. I need to make sure that "20" is used for all tests against the dealers value. I couldn't figure out an analytic way to achieve this, so I brute forced it:
$player_value = max (4 .. 21).grep: { $_ == $player_value };
This feels inelegant. If there were millions of potential values then Rakudo would need to be very clever indeed to avoid extreme inefficiency. We need some powerful operators to avoid this.
Checking for a dealer win has the same problem: I can't use "less-than" or "greater-than" tests because of possible junctional values (e.g. "ace, six, ten" is both not-bust, and greater than any possible play hand).
say "DEALER:";
.key.say for @dealer;
my $dealer_value = [+] @dealer.map: { .value };
my $done = 0;
loop {
say "dealer value: {$dealer_value.perl}";
if $dealer_value == any( $player_value ^.. 21) {
say "you loose!";
exit 0;
}
elsif $dealer_value < 21 {
my $card = @cards.shift;
@dealer.push( $card );
say $card.key;
$dealer_value += $card.value;
}
else {
say "dealer bust: you win!";
exit 0;
}
}
And so that's it. Junctions work, but I can't help feeling that we need some more language features to help with the "collapsing" of a junction to its appropriate value -- and that includes a "partial collapse" that, for example, excludes all values greater than 21 after I've checked that there'd be at least one value left over. Hmm, perhaps that could be done with a subset type...
The last of the “Scripting Games” challenges that I attempted was to implement Instant Runoff voting. I saw a couple of different approaches here:
1. maintain a list of excluded candidates and ignore them during subsequent rounds.
2. explicitly delete the losing candidate from each round from all the ballots prior to the subsequent round
Both solutions work: the first uses junctions; the other uses the "is rw" trait on a for loop. So both are of some interest.
First, the junctional approach...
my @ballots = (
[< A B C D >],
[< B D C A >],
[< C D B A >],
[< B A C D >],
[< A D C B >],
);
my @excluded;
loop {
my %tallies;
for @ballots -> @ballot {
if @ballot.first: { $_ ne all(@excluded) } ->
$chosen {
%tallies{ $chosen } ++;
}
}
my $total = [+] %tallies.values;
if $total == 0 {
say “There was no winner”;
exit 0;
}
elsif %tallies.pairs.first: { .value > $total/2
} -> $kv {
say “WINNER IS: {$kv.key}”;
exit 0;
}
else {
my $losing_tally = min %tallies.values;
for %tallies.pairs.grep: { .value == $losing_tally
} -> $kv {
my $loser = $kv.key;
say "exclude $loser";
@excluded.push: $loser;
}
}
}
That wasn't too hard. Note the "pointy-block" used with the "if" statement -- this syntax isn't limited to "for" loops!
The second approach leads to very similar code:
loop {
my %tallies;
for @ballots.grep: {.elems} -> @ballot {
%tallies{ @ballot[0] } ++;
}
my $total = [+] %tallies.values;
if $total == 0 {
say “There was no winner”;
exit 0;
}
elsif %tallies.pairs.first: { .value > $total/2
} -> $kv {
say “WINNER IS: {$kv.key}”;
exit 0;
}
else {
my $losing_tally = min %tallies.values;
for %tallies.pairs.grep: { .value == $losing_tally
} -> $kv {
my $loser = $kv.key;
say "exclude $loser";
for @ballots -> @ballot is rw {
@ballot = @ballot.grep:
{ $_ ne $loser }
}
}
}
}
say "WINNER IS: $winner";
Again I found no significant problems.
I found one “not implemented in Rakudo” issue writing this code: in-place modification of an array using arbitrary methods. Instead of:
@ballot = @ballot.grep: { $_ ne $loser }
I should have been able to write:
@ballot.=grep: { $_ ne $loser }
This should be fixed once Rakudo matures.
Another minor issue is that the reverse lookup of a key from a hash’s value requires an explicit loop. It might be nice to have some form of bidirectional hash lookup – perhaps this will appear once “Relational” operators are added via a 6PAN module.
The scripting games were a good introduction, but none required any significant amount of code. Looking for inspiration I was found a game named “Skulls and Bones” on my Tivo – a game I remember from my childhood as “connect 4”. I decided to try a Perl6 implementation of it.
The implementation required a couple of hundred lines – too big to embed in this page. So see my writeup here. This was my first foray into the Perl6 object system. During refactoring I found that things didn’t always quite DWIM: I’d copy a line from an iteration that used an implicit topic
@moves.grep: { .is_winning_move }
But when written in a method, “self” is not the topic:
method foo {
$win = .is_winnning_move; # ERROR
$win = self.is_winning_move; # OK
$win = $.is_winning_move; # OK except when indirect-object syntax is used for arguments
}
I think that it’s reasonable for the topic to not default to “self” – that would cause problems when moving code from a method-body into a block. But I think that “$.” and “self.” should be strong synonyms.
This game of Connect4 was my first non-trivial perl6 program. Rakudo isn’t quite ready for anything more complex, yet, in one important way: its error diagnostics are lacking line numbers. This might not sound like much, but object-oriented code is very fragmented: it becomes difficult to figure out where an error is, let alone what it is. I am told that this will be fixed in the next month or so: that will be welcome
The other thing I noticed was performance. My computer “AI” has a look-ahead of just two moves (searching about 50 positions), and yet this takes almost a second. To be ready for production use, speedups of at least two orders of magnitude will be needed (both compile-time and run-time). As Rakudo becomes feature-complete this will become the focus of development. Until then, the development team is probably correct to focus on functionality.
Perl6 the language is looking good. Even with the somewhat rough rendering in Rakudo, it does feel like a balanced language with many disparate pieces that all fit together.
When I first read of the new “{…}” interpolation mechanism, I was concerned. I spend a lot of time writing code generators, so curlies tend to be common character in my “print” statements. But as I got used to them, I find them very natural. I’ll probably miss them when I go back to P5 (fortunately “@{[…]}” has similar semantics).
I was somewhat surprised to not be able to find an excuse to play with hyper-operators and feed operators. These feel like they’ll be really powerful, but each time I thought to use them, I found a better way to structure my code that didn’t need them. Perhaps I need to find a problem that has a lot of regular data to manipulate.
I did find plenty of reasons to use junctions. They’re really useful – perhaps even worth sacrificing clean bit-op syntax for (I’m one of those Perl programmers that uses a lot of bit-ops). On the downside, the violation of the concept of the “excluded middle” may result in maintenance problems down the road, when junctions are overused by novices (A bit like the problems with overuse of inheritance in C++).
Multiple dispatch (and the type system it depends on) turns out to be really useful. Even when not the primary focus (as in the “bowling” challenge), I keep finding simple reasons to use it to simplify code. Look back to my connect4 code and you’ll find multi methods that allow me to manipulate the game board using either Cartesian coordinates or “Move” objects. It would be nice, though, to be able to use multiple-dispatch with anonymous groupings of “pointy-blocks” – for example, with “for” loops.
There are a bunch of things that didn’t quite feel right, but I’m willing to give the language the benefit of the doubt – and blame the immaturity of Rakudo. Missing operators forced work-arounds; buggy parsing combined with unhelpful error messages caused frustration. I’m sure that will improve over time.
I do, however, have a few language-related concerns to highlight:
Perl6 changes the semantics of sigils from those of Perl5. The reason given for this is that some beginners didn’t understand them. But I find that the same is true of the new semantics. In fact, they seem less useful now than they used to: you can store pretty much any type of value in any containers, and the sigil doesn’t appear to have a major impact on the operators that can be applied. If Perl5 was criticized for its line noise, I fear that this criticism may be more justified for perl6.
On the other hand, I’m still a beginner to perl6: my concerns might simply reflect that I don’t grok some deep underlying elegance of the perl6 semantics. Perhaps, with experience, I will come to love the new semantics, and will intuit correctly where I need to add splats (prefix:<*>) and flatten (prefix:<|>) operators to make the code do what I mean
The algebra of junctions is straight forward, but tricky. Junctions don’t collapse, even within expressions, and so great care is needed to ensure that some “excluded middle” condition sneaks into the code when your attention wanders. In fact, the lack of collapsing has caused bugs in Rakudo itself:
say “bug” if 10 < 5|25 < 20;
It is obviously true that neither 5 nor 25 falls within the range, but the lack of junctional collapse creates the bug when this chain is expanded to
say “oops” if do { my $tmp = 5|25; 10 < $tmp && $tmp < 20 };
A deliberate decision was made that Perl6 junctions are not “Quantum::Superpositions”, but I fear that this will be a frequent source of bugs in Perl6 code.
I we must forego implicit collapse semantics, we should at least have some form of explicit collapse. My earlier example of
$player_value = max (4 .. 21).grep: { $_ == $player_value };
demonstrates the brute-force approach, but this won’t scale. In quantum mechanics we “observe” a system using the dot product of a state vector with an eigenvector of the observation operator. We need something analogous here: something that “multiplies” a junction by a list (or range). Adapting the standard bra-ket notation (and avoiding existing syntax), I’d suggest something like:
$player_value = max |< 4..21 |==| $player_value >|
Maybe that’s a bit too cute – the circumfix angle brackets aren’t really justified. The important thing is to have an operator that can deal with infinite arguments in finite time. E.g.
% ./perl6 –e ‘say -Inf .. +Inf |>| one( 10..Inf )’
11
As an aside, that infinite range could be a common range against which to collapse a junction. It might be good to allow a type (including subset types) to be used in lieu of a specific range:
% ./perl6 –e ‘subset b_str where { /b/ }; say (::b_str |eq| any< abc bcd cde >).perl’
[“abc”, “bcd”]
Rakudo is obviously not finished. It has many rough edges and missing features. Its performance is slow; and its error diagnostics unhelpful. However, that is all to be expected. No one claims that it is finished. Indeed it is a pleasant surprise just how far it has progressed. And the #perl6 IRC channel is always helpful.
I was promised Perl6 for Christmas, and for Christmas I played with it as a toy. Fun, but it’s not serious use. Seeing the progress that has been made, I have some hope that next Christmas may see something close to a perl-6.0.0-alpha. There’s a lot of work to do: I’d love to see some concurrency for example, and for that there’s more work needed in the specs (and with the recent release of OpenCL there’s a risk of chasing fast-moving expectations there).
Rakudo can be used today to write real perl6 programs, but it is not yet “usable”. Diagnostic messages (beyond just the line numbers that should be added this month) need much greater depth, and there’s a huge challenge ahead to improve the performance of both the compiler and the runtime. And that’s after it implements all the Synopses – including those not yet written
Beyond the language itself we’ll need libraries. We don’t need a finished Rakudo to write them, but to release a successful perl6 they’ll be needed. Linking to Perl5 modules will provide some functionality, but there’s more to a library than just calling a set of functions. Perl6 has been referred to as an “operator-oriented” language – and that requires much more from a library than just C-linkage.
But my message here is positive. Great progress has been made, and the project appears to have momentum. Naysayers will continue to complain that it will be a teenager before it finds its way into the workplace – but that just shows that perl6 is such an advanced entity that we must respect the child-labor laws!