Author Archive

Perl 6 Advent Calendar 2014: Table of Contents

December 1, 2014

This post serves as a table of contents for the 2014 Perl 6 advent calendar. Links to new posts will appear here during the course of this month.

Perl 6 Advent Calendar 2013: Table of Contents

November 30, 2013

This post serves as a table of contents for the 2013 Perl 6 advent calendar. Links to new posts will appear here during the course of this month.

See also: table of contents for 2012, 2011, 2010, 2009.

Day 24 – An Advent Calendar

December 24, 2012

Recently I was unpacking some boxes of books and came across a book entitled "BASIC Computer Programs for the Home" by Charles D. Sternberg. Apparently my father had purchased this book in the early 1980s and had given it to me. In any case, my name was scrawled in the front cover in the manner an adolescent me would have done.

Mostly this book is filled with simple BASIC programs that manage simple databases of various things: recipes, household budget, address book, music collections, book collections, school grades, etc. But the program that caught my eye and made me think of the Perl 6 Advent Calendar was one for printing a calendar starting at a particular month.

Now, the version in this book is a little simple in that it asks for the starting month, year, the day of the week that the first month starts on, and how many months to print. I wanted something a little more like the Unix utility cal(1) program. Luckily, Perl 6 has date handling classes as part of the specification and both major implemenations, Rakudo and Niecza, have actual implementations of these which should make creating the calendar quite easy.

For reference, the output of the Unix cal(1) utility looks like this:

       December 2012
    Su Mo Tu We Th Fr Sa
                       1
     2  3  4  5  6  7  8
     9 10 11 12 13 14 15
    16 17 18 19 20 21 22
    23 24 25 26 27 28 29
    30 31                 

It also has some options to change the output in various ways, but I just want to focus on reproducing the above basic output.

I'll need a list of month names and weekday abbreviations:

    constant @months = <January February March April May June July
                        August September October November December>;
    constant @days = <Su Mo Tu We Th Fr Sa>;

And it looks like the month and year are centered above the days of the week. Generating a calendar for May shows this to be the case, so I'll need a routine that centers text:

    sub center(Str $text, Int $width) {
        my $prefix = ' ' x ($width - $text.chars) div 2;
        my $suffix = ' ' x $width - $text.chars - $prefix.chars;
        return $prefix ~ $text ~ $suffix;
    }

Now, the mainline code needs two things: a month and a year. From this it should be able to generate an appropriate calendar. But, we should have a reasonable default for these values I think. Today's month and year seem reasonable to me:

    sub MAIN(:$year = Date.today.year, :$month = Date.today.month) {

but if it's not today's month and year, then it's some arbitrary month and year we need info about. To do this we construct a new Date object from the month and year given.

        my $dt = Date.new(:year($year), :month($month), :day(1) );

Looking at the calendar generated for December, it seems like we may actually output up to 6 rows of numbers since the month can start and end on a partial week. In order to implement this, I think I'll need some "slots" for each day. Each slot will either be empty or will contain the day of the month. The number of empty slots at the beginning of the month correspond to the day of the week that the first of the month occurs on. If the first is on Sunday, there will be 0 empty slots, if the first is on a Monday there will be 1 empty slot, if the first is on a Tuesday, there will be 2 empty slots, etc. This is remarkably similar to the number we get when we interrogate a Date object for the day of the week. The only wrinkle is that it returns 7 for Sunday when we actually need a 0. That's easily remedied with a modulus operator however:

        my $dt = Date.new(:year($year), :month($month), :day(1) );
        my $ss = $dt.day-of-week % 7;
        my @slots = ''.fmt("%2s") xx $ss;

That gives us the empty slots at the beginning, but what about the ones that actually contain the days of the month? Easy enough, we'll just generate a number for each day of the month using the Date object we created earlier.

        my $days-in-month = $dt.days-in-month;
        for $ss ..^ $ss + $days-in-month {
            @slots[$_] = $dt.day.fmt("%2d");
            $dt++
        }

Now we've got an array with appropriate values in the appropriate positions, all that's left is to actually output the calendar. Using the header line for our weekdays as a metric for the width of the calendar, and the routine we created for centering text, we can output the header portion of the calendar:

        my $weekdays = @days.fmt("%2s").join: " ";
        say center(@months[$month-1] ~ " " ~ $year, $weekdays.chars);
        say $weekdays;

Then we iterate over each slot and output the appropriate values. If we've reached the end of the week or the end of the month, we output a newline:

        for @slots.kv -> $k, $v {
            print "$v ";
            print "\n" if ($k+1) %% 7 or $v == $days-in-month;
        }

Putting it all together, here is the final program:

    #!/usr/bin/env perl6

    constant @months = <January February March April May June July
                        August September October November December>;
    constant @days = <Su Mo Tu We Th Fr Sa>;


    sub center(Str $text, Int $width) {
        my $prefix = ' ' x ($width - $text.chars) div 2;
        my $suffix = ' ' x $width - $text.chars - $prefix.chars;
        return $prefix ~ $text ~ $suffix;
    }

    sub MAIN(:$year = Date.today.year, :$month = Date.today.month) {
        my $dt = Date.new(:year($year), :month($month), :day(1) );
        my $ss = $dt.day-of-week % 7;
        my @slots = ''.fmt("%2s") xx $ss;

        my $days-in-month = $dt.days-in-month;
        for $ss ..^ $ss + $days-in-month {
            @slots[$_] = $dt.day.fmt("%2d");
            $dt++
        }

        my $weekdays = @days.fmt("%2s").join: " ";
        say center(@months[$month-1] ~ " " ~ $year, $weekdays.chars);
        say $weekdays;
        for @slots.kv -> $k, $v {
            print "$v ";
            print "\n" if ($k+1) %% 7 or $v == $days-in-month;
        }
    }

Normally, cal(1) will highlight today's date on the calendar. That's a feature I left out of my calendar implementation but it could easily be added with Term::ANSIColor. Also, there's a little bit of coupling between the data being generated in the slots and the output processing (the slots are all formatted to be 2 characters wide in anticipation of the output). There are some other improvements that could be done, but for a first cut at a calendar in Perl 6, I'm happy. :-)

Day 14 – Primal Needs

December 14, 2012

Our brains are hard-wired to look for patterns, even where none exist. So, it’s no surprise that as soon as mankind started counting things, he would look for patterns in numbers. One group of numbers that have resisted the pattern matching capabilities of the human brain are the so-called “prime numbers”. These are numbers that can only be evenly divided by 1 or themselves–they have no other factors.

But you knew that already, so why am I talking about prime numbers instead of Perl 6? Because, just like our ancestors, the people that created Perl 6 and continue to shape it to be around for the next 100 years or more find prime numbers interesting. So interesting, in fact, that the language specification was modified to include a routine for determining whether or not a number is prime.

Alpha

At first, implmementations of this prime-number-finder were pure Perl 6 and took advantage of other features of the language such as ranges and junctions. An example implementation is shown below:

    sub is-prime($n) { $n %% none 2..sqrt $n }

This implementation checks to see that none of numbers from 2 to the square root of $n will evenly divide $n. If this is the case, then the number is prime.

While the above implementation works fine, it is a little slow and it does suffer a little redundancy in the numbers it checks. For instance, if you know a number isn’t evenly divisible by 2, there’s no need to check if it’s evenly divisible by 4, yet the above algorithm does so anyway.

Beta

An improvement on the algorithm is to only check if the I between 2 and the square root of the number evenly divide the number. But … but … that’s like like defining a word in terms of itself. Thanks to ubiquitous lazy evaluation in Perl 6, that’s entirely possible. Here’s an implementation:

    my @primes := 2, 3, 5, -> $p { ($p+2, $p+4 ... &is-prime)[*-1] } ... *;
    sub is-prime($n) { $n %% none @primes ...^  * > sqrt $n }

The array @primes is an infinite, lazily evaluated sequence of numbers starting with 2, 3, and 5. The next number in the sequence is generated by creating a new sequence of odd numbers that start from the last odd number and continue until we reach a prime. That prime is the next number in the sequence. But how do we know if it’s a prime? We check with our handy C subroutine that actually uses the lazy list of primes up to the square root of the number we’re testing to see if any of them are factors.

There’s a kind of mutual recursion going on here where the @primes array effectively memoizes the primes we’ve seen so far. But … then there’s the problem that @primes will continue to grow as you check bigger and bigger numbers for prime-ness. Can we do better?

Indeed we can.

Gamma: Rabin-Miller test

Well … maybe we can. It depends on your idea of “better”. The Rabin-Miller primality test is probabalistic in nature. It doesn’t require storing an ever increasing cache of prime numbers to test if they are factors of the potential prime, but there is a chance that it will tell you that a number is prime when it actually isn’t. The good news is that we can adjust the odds so that we are reasonably confident that the number is prime. Here’s an implementation (taken from http://rosettacode.org/wiki/Miller-Rabin_primality_test#Perl_6):

sub expmod(Int $a is copy, Int $b is copy, $n) {
	my $c = 1;
	repeat while $b div= 2 {
		($c *= $a) %= $n if $b % 2;
		($a *= $a) %= $n;
	}
	$c;
}

subset PrimeCandidate of Int where { $_ > 2 and $_ % 2 };

my Bool multi sub is-prime(Int $n, Int $k)            { return False; }
my Bool multi sub is-prime(2, Int $k)                 { return True; }
my Bool multi sub is-prime(PrimeCandidate $n, Int $k) {
	my Int $d = $n - 1;
	my Int $s = 0;

	while $d %% 2 {
		$d div= 2;
		$s++;
	}

	for (2 ..^ $n).pick($k) -> $a {
		my $x = expmod($a, $d, $n);

		next if $x == 1 or $x == $n - 1;

		for 1 ..^ $s {
			$x = $x ** 2 mod $n;
			return False if $x == 1;
			last if $x == $n - 1;
		}
		return False if $x !== $n - 1;
	}

	return True;
}

The third multi variant of is-prime with the signature (PrimeCandidate $n, Int $k) is where all of the magic happens. This multi is only triggered when the prime candidate ($n) is an odd number because of the definition of the PrimeCandidate type.

First, we factor out the powers of 2 from $n - 1. Since $n is an odd number, $n - 1 is even and so has at least one factor of 2. What we end up with is an odd number and some power-of-2 factors of $n - 1. We then use those factors to see if a random sample of $k numbers less than $n are congruent to the square roots of unity modulo $n (expmod handles the modular exponentiation). We repeat this for all of the powers of 2 we factored out of the original number. Fermat’s little theorem says that if we find any number where the congruence does not hold, then the number can not be prime.

The probability that this method will select a composite number as prime is based on how many numbers less than $n we choose to sample. If we select $k numbers to try, the probability is 4 ** -$k. By choosing to sample more numbers, we can quickly decrease the odds of a false positive to a negligible amount.

Wrap up

But … most people don’t really have to worry about the implementation details of is-prime. Not only have is-prime and expmod been added to the Perl 6 specification, but actual implementations (ala Rabin-Miller) have been added to the Rakudo and Niecza Perl 6 compilers. So, if you want to test your new cryptographic algorithm and need some large prime numbers, or if you’re developing a new random number generator and need some candidates for the modulus, or maybe you’re developing a new hashing algorithm, Perl 6 has a built-in is-prime that can help.

Adventures in writing a simple grammar profiler

December 7, 2011

Inspired by jnthn’s earlier post on Grammar::Debugger, I wondered how hard it would be to implement a simple Perl 6 grammar profiler.  Turns out it wasn’t that hard at all. As far as profiling goes, all I wanted was counts of how many times each rule was executed and the cumulative time each rule took to execute.    The interface I had in mind was something simple–a multi-level hash with names of grammars at the first level then, at the second level, names of the individual rules within the grammar, and finally the actual timing information.  The timing information would be accessed thusly:

say "MyGrammar::MyRule was called " ~ %timing<MyGrammar><MyRule><calls> ~ "times";
say "and took " ~ %timing<MyGrammar><MyRule><time> ~ " seconds to execute";

But first I had to figure out what jnthn’s code was doing. From the outside looking in, the basic technique is to replace the normal grammar meta-object with a custom meta-object that inherits most of the behavior of the normal grammar meta-object but replaces the normal method lookup with a custom one that returns a routine that collects the timing information while calling the original method. Looking at jnthn’s code, I see that if the method name starts with ! or is any one of “parse”, “CREATE”, “Bool”, “defined” or “MATCH”, we just return the original method without modification. This is so that we don’t trace private methods or accidentally trace methods that aren’t directly part of the grammar but are used by it. In my simple profiler, I need to get the name of the grammar, which I do by calling my $grammar = $obj.WHAT.perl. So it looks like I need to add “perl” to that list of methods to pass through unscathed. Otherwise, I get an infinite recursion. Anyway, for those method names that don’t match the aforementioned criteria, we return a custom built routine that accumulates the execution time and increments a counter for the number of calls. Seems straight-forward enough … below is the code (somewhat untested):

my %timing;

my class ProfiledGrammarHOW is Metamodel::GrammarHOW is Mu {

    method find_method($obj, $name) {
        my $meth := callsame;
        substr($name, 0, 1) eq '!' || $name eq any(<parse CREATE Bool defined MATCH perl BUILD DESTROY>) ??
            $meth !!
            -> $c, |args {
                my $grammar = $obj.WHAT.perl;
                %timing{$grammar} //= {};                   # Vivify grammar hash
                %timing{$grammar}{$meth.name} //= {};       # Vivify method hash
                my %t := %timing{$grammar}{$meth.name};
                my $start = now;                            # get start time
                my $result := $meth($obj, |args);           # Call original method
                %t<time> += now - $start;             # accumulate execution time
                %t<calls>++;
                $result
            }
    }

    method publish_method_cache($obj) {
        # no caching, so we always hit find_method
    }
}

sub get-timing is export { %timing }
sub reset-timing is export { %timing = {} }

my module EXPORTHOW { }
EXPORTHOW.WHO.<grammar> = ProfiledGrammarHOW;

Assuming the above code was saved in file called “GrammarProfiler.pm”, you’d use it by adding the line use GrammarProfiler; to the top of any program that makes grammar declarations. Then after you parse your grammar, you can call get-timing() to obtain the hash that has the timing information for the individual rules that were executed during the parse or reset-timing() to clear the timing information. Of course, a more full-fledged profiler would do much more work and provide many more profiling options, but this isn’t bad for a quick hack and it just might be useful too.

The Flip-Flop operator

December 5, 2011

Perl 5 has a binary operator called flip-flop that is false until its first argument evaluates to true and it stays true (flips) until the second argument evaluates to true at which point it becomes false again (flops).  This is such a useful operator that Perl 6 also has flip-flop, only it’s spelled ff and has a few variants:

    ff
    ff^
    ^ff
    ^ff^

The circumflex means to skip the end point on that end.

Perhaps some examples are in order …

    for 1..20 { .say if $_ == 9  ff  $_ == 13; }     # 9 10 11 12 13
    for 1..20 { .say if $_ == 9  ff^ $_ == 13; }     # 9 10 11 12
    for 1..20 { .say if $_ == 9 ^ff  $_ == 13; }     #   10 11 12 13
    for 1..20 { .say if $_ == 9 ^ff^ $_ == 13; }     #   10 11 12

In each example we’re iterating over the range of numbers from 1 to 20 and output those numbers where the flip-flop returns true. Both the right hand side of the flip-flop ($_ == 9) and left hand side of the flip-flop ($_ == 13) are evaluated on each iteration of the loop. (I’ve used simple numeric comparison on both sides of the flip-flop operators here but, in general, any boolean expression could be used.)

Each instance of the flip-flop operator maintains it’s own little bit of internal state to decide when to return True or False. All flip-flop operators are born with their internal state set to return False waiting for the moment they can be flipped and start returning True.

In the first and second examples when $_ == 9, the flip-flop operators flips their internal state to True and immediately return True.  In the third and fourth examples when $_ == 9 the flip-flop operators set their internal state to True but they return False on that iteration because of the leading circumflex.

Similarly, in the first and third examples above, once the RHS evaluates to True, the flip-flop operators flop their internal state back to False on next evaluation and return True. In the third and fourth examples, the flip-flops operators flop sooner by returning False immediately upon evaluating the RHS True.

To make the flip-flop operator flip, but never flop, use a * on the RHS:

    for 1..20 { .say if $_ == 15 ff *; }     # 15 16 17 18 19 20

Perl 6 has another set of flip-flop operators that function similar to the ones mentioned above, except the RHS isn’t evaluted when the LHS becomes true. This is particularly important when both the RHS and the LHS of the flip-flop could evaluate to True at the same time. These operators are spelled fff, fff^, ^fff, and ^fff^.

Day 20 – The Perl 6 Synopses

December 20, 2010

The tag line for this blog is “Something cool about Perl 6 every day” and today I’m going to talk about something I think is very cool—the Synopses.

First, a quick background. When Perl 6 was first announced in 2000, the community didn’t quite know what needed to be done. So a requests for comments (RFC) process was started and resulted in over 360 RFCs that suggested changes to Perl. From these RFCs Larry Wall synthesized the Apocalypses which sought to reveal the design of the language. Later, Damian Conway created the Exegeses which showed how the design could be used in practice.

Fast forward to the present day. There are several implementations of Perl 6 out there and each has their own implementation focus. One has prioritized the object model, another the parsing engine, a third has prioritized implementing the bulk of the basic Perl 6 syntax. How do each of these implementations maintain their “Perl-6-ness” while still focusing on their particular implementation niche?

The answer is the Synopses. These documents are the official Perl 6 specification. Each Synopsis covers a specific topic within the Perl 6 language that somewhat mirrors chapters in “Programming Perl” (the camel book).

What if you think you’ve found a bug in an implementation? How do you know it’s a bug? Consult the relevant Synopsis. As far as the Perl 6 community goes, what’s written in the Synopses is definitive.

What if you think there’s a bug in a Synopsis or that it contradicts another Synopsis? Either send a message to perl6-language@perl.org or drop by #perl6:irc.freenode.net to discuss it. Because here’s the other cool thing about these Synopses … they are living documents. When there is a contradiction or just something that needs clarification, talking about it with #perl6 is often all it takes to get the problem fixed. Actually, just mentioning your trouble in a public forum of some sort (twitter, a blog, etc.) is likely to garner enough attention. There are no layers of beaurocracy to navigate in order to affect change.

Now, this last thing may seem slightly bizarre, but … almost anyone can edit the Synopses. They aren’t held fixed by some divine power. All it takes is active participation in the Perl 6 discussion. There is a price for this ability however–your changes must withstand the scrutiny of the Perl 6 community. Much like a wiki, social pressures and an active community are used to maintain the integrity of the Synopses.

Day 10 – Feed operators

December 10, 2010

Anyone who has programmed in Perl 5 for a while has probably run across or written code similar to this:

    my @new = sort { ... } map { ... } grep { ... } @original;

In this construction, the data flows from the @original array which feeds into the grep, and that, in turn, feeds into the map, and then into the sort, and then finally, the result is assigned to the @new array. Because they each take a list as their final parameter, simply by juxtposition, the data feeds leftward from one operation to the next.

Perl 6, on the other hand, makes this idea of data flowing from one operation to another explicit by introducing the feed operator. The above Perl 5 code could be written like this in Perl 6:

    my @new <== sort { ... } <== map { ... } <== grep { ... } <== @original;

Note that TMTOWTDI is alive and well in Perl 6. You could have also written much the same as in Perl 5:

    my @new = sort { ... }, map { ... }, grep { ... }, @original;

The only difference would be the addition of commas.

So, what do we gain from these feed operators? Normally, when reading code, you read from left to right. In the original Perl 5 code you would read from left to right until you realize that you’re dealing with constructions where the direction of flow is right to left, then you jump to the end and follow the processing in a right-to-left manner. In Perl 6 there is now a prominent syntactic marker that clues you in to the leftward flowing nature of the data.

Still, the right-to-left nature of this code is somewhat troublesome. It may not seem so onerous if all of the code fits on one line as above. But imagine if the blocks associated with grep, map, and sort were little longer. Finding the end of the statement could be a bit annoying.

Luckily, Perl 6 has another feed operator that allows you to write the same code in a left-to-right fashion:

    @original ==> grep { ... } ==> map { ... } ==> sort { ... }  ==> my @new;

This works exactly the same as before only the direction of flow has been changed.

Here are a couple of examples of real, working Perl 6 code using the feed operators:

    my @random-nums = (1..100).pick(*);
    my @odds-squared <== sort() <== map { $_ ** 2 } <== grep { $_ % 2 } <== @random-nums;
    say ~@odds-squared;
    my @rakudo-people = <scott patrick carl moritz jonathan jerry stephen>;
    @rakudo-people ==> grep { /at/ } ==> map { .ucfirst } ==> my @who-it's-at;
    say ~@who-it's-at;

Merry Christmas!

December 25, 2009

On behalf of all the people that brought you this year’s Perl 6 Advent Calendar, I’d like to wish everyone out there a very Merry Christmas!

Day 20: Little big things

December 20, 2009

Today we look at some little big things…

There are many simple yet powerful ideas baked-in to Perl 6 that allow many wonderful things. One of these simple ideas is introspection. Introspection is the act of observing yourself. For a programming language this means that there is some mechanism by which you, the programmer, can express questions about the language in the language itself. Perl 6 is a language that supports introspection in several ways. For instance, there are methods on object instances that tell to what class the object belongs, there are methods on classes to tell what methods are available to the class, etc.

There are even methods on subroutines to ask what the subroutine’s name is:

    sub foo (Int $i, @stuff, $blah = 5) { ... }
    say &foo.name;      # outputs "foo"

Now that may seem slightly pointless, but keep in mind that subroutines can be assigned to scalars or aliased to other names or may be generated on-the-fly, so it’s name may not be immediately obvious by glancing at the code.

    my $bar = &foo;
    # ... and then much later ...
    say $bar.name;      # What was this subroutine's name again?

Here are a few other items you can introspect on subroutines.

    say &foo.signature.perl;        # What does the subroutine signature look like?
    say &foo.count;                 # How many arguments does this subroutine take?
    say &foo.arity;                 # How many are required?

That last thing we introspected from the subroutine was its arity; the number of required arguments for a subroutine/method. Because Perl can now figure that information out for itself via introspection, interesting new things are available that weren’t easy or were even non-existent before. For instance, in Perl 5, map blocks take a list of items one at a time and transform each into one or more new items to create a new list, but because Perl 6 knows how many arguments are expected, it can take as many as needed.

    my @foo = map -> $x, $y { ... },  @bar;             # take @bar two at a time to generate @foo
    my @coords = map -> $x, $y, $z { ... }, @numbers;   # take @numbers three at a time

Another benefit of this ability to introspect the number of parameters a subroutine requires is a nicer mechanism for sorting arrays by some other criteria than the default string comparison. The sort method on arrays takes an optional subroutine to act as the comparator and ordinarily this subroutine takes 2 parameters–the items of the array to be compared. So, if you were modeling people and their karma, and wanted to sort an array of people by karma, you’d write something similar to this:

#!/usr/bin/perl6

use v6;

class Person {
    has $.name;
    has $.karma;

    method Str { return "$.name ($.karma)" }  # for pretty stringy output
}

my @names = <Jonathan Larry Scott Patrick Carl Moritz Will Stephen>;

my @people = map { Person.new(name => $_, karma => (rand * 20).Int) }, @names;

.say for @people.sort: { $^a.karma <=> $^b.karma };

But! Since Perl 6 can introspect the comparator, we’ve got another option now. By passing a subroutine that only takes 1 parameter, Perl 6 can know to automatically do the equivalent of a Schwartzian Transform. The above sort can now be written like so:

    .say for @people.sort: { $^a.karma };

But wait! There’s another small syntactic advantage now that there’s only one parameter to the subroutine: implicit aliasing to $_. So we can eliminate the auto-declared placeholder variable entirely:

    .say for @people.sort: { .karma };

What this does is call the .karma method on each element of the array one time (rather than twice for each comparison as would be done with the normal comparator) and then order the array based on the results.

Another little big thing is that Perl 6 has a built-in type system. You may have noticed in the karma example above that I didn’t specify that numeric comparison should be used. That’s because perl is smart enough to figure out that we’re using numbers. If I had wanted to force the issue, I could have used a prefix + or ~:

    .say for @people.sort: { +.karma };     # sort numerically
    .say for @people.sort: { ~.karma };     # sort stringily

One place this is particularly handy is with the .min and .max methods. These methods also take a subroutine to set user-defined criteria for the ordering of elements:

    say @people.min: { +.karma }         # all numbers, so numeric comparison
    say @people.max: { ~.name }         # all strings, so string comparison

If you read yesterday’s advent post, you’ll note that there is another way to write these last few examples using a Whatever:

    .say for @people.sort: *.karma;
    say @values.min: +*.karma;
    say @values.max: ~*.name;

Which is another little big thing in Perl 6. Be sure to check out the other advent entries for even more little big things


Follow

Get every new post delivered to your Inbox.

Join 44 other followers