Advent 2015

Advent 2015

Advent is a time of preparation. A time to make ready for Christmas. But this Advent is special. This Advent, the Christmas we are preparing for is the Christmas. The one where Perl 6 is “official” and “released” and ready for the world.

In a way, it has been a year long advent for the Perl 6 developers. There have been many improvements to the Rakudo compiler over the past year. Two really big features on our way to Christmas were Normal Form Grapheme (NFG) and the Great List Refactor (GLR) , which, after the September release were largely finished.

I say “largely finished” rather than just “finished” because there are always lingering issues in any endeavor and that’s why Christmas is so important to Perl 6. With the Christmas release of Perl 6, a larger community of programmers will be poking and prodding our Perl 6 compilers and using them for real world tasks. Moreover, there may be a few hidden corners in the language specification that could lead to futures changes in the specification which would cascade to the compiler implementations. With more people trying Perl 6, it’s likely that the community of people associated with Perl 6 will also receive a boost in numbers. There may even be an influx of new Perl 6 developers. It’s an exciting time.

So, over the next 24 days, enjoy some of the many gifts that Perl 6 has to offer. Christmas is just the beginning. :-)

Perl 6 Advent Calendar 2014: Table of Contents

Perl 6 Advent Calendar 2014: Table of Contents

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

Perl 6 Advent Calendar 2013: Table of Contents

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

Day 24 – An Advent Calendar

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

Day 14 – Primal Needs

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

Adventures in writing a simple grammar profiler

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

The Flip-Flop operator

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^.