Archive for December, 2012

Day 4 – Having Fun with Rakudo and Project Euler

December 4, 2012

Rakudo, the leading Perl6 implementation, is not perfect, and performance is a particularly sore subject. However, the pioneer does not ask ‘Is it fast?’, but rather ‘Is it fast enough?’, or perhaps even ‘How can I help to make it faster?’.

To convince you that Rakudo can indeed be fast enough, we’ll take a shot at a bunch of Project Euler problems. Many of those involve brute-force numerics, and that’s something Rakudo isn’t particularly good at right now. However, that’s not necessarily a show stopper: The less performant the language, the more ingenious the programmer needs to be, and that’s where the fun comes in.

All code has been tested with Rakudo 2012.11.

We’ll start with something simple:

Problem 2

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The solution is beautifully straight-forward:

    say [+] grep * %% 2, (1, 2, *+* ...^ * > 4_000_000);

Runtime: 0.4s

Note how using operators can lead to code that’s both compact and readable (opinions may vary, of course). We used

  • whatever stars * to create lambda functions
  • the sequence operator (in its variant that excludes the right endpoint) ...^ to build up the Fibonacci sequence
  • the divisible-by operator %% to grep the even terms
  • reduction by plus [+] to sum them.

However, no one forces you to go crazy with operators – there’s nothing wrong with vanilla imperative code:

Problem 3

What is the largest prime factor of the number 600,851,475,143?

An imperative solution looks like this:

    sub largest-prime-factor($n is copy) {
        for 2, 3, *+2 ... * {
            while $n %% $_ {
                $n div= $_;
                return $_ if $_ > $n;
            }
        }
    }

    say largest-prime-factor(600_851_475_143);

Runtime: 2.6s

Note the is copy trait, which is necessary as Perl6 binds arguments read-only by default, and that integer division div is used instead of numeric division /.

Nothing fancy going on here, so we’ll move along to

Problem 53

How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?

We’ll use the feed operator ==> to factor the algorithm into separate steps:

    [1], -> @p { [0, @p Z+ @p, 0] } ... * # generate Pascal's triangle
    ==> (*[0..100])()                     # get rows up to n = 100
    ==> map *.list                        # flatten rows into a single list
    ==> grep * > 1_000_000                # filter elements exceeding 1e6
    ==> elems()                           # count elements
    ==> say;                              # output result

Runtime: 5.2s

Note the use of the Z meta-operator to zip the lists 0, @p and @p, 0 with +.

The one-liner generating Pascal’s triangle has been stolen from Rosetta Code, another great resource for anyone interested in Perl6 snippets and exercises.

Let’s do something clever now:

Problem 9

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Using brute force will work (solution courtesy of Polettix), but it won’t be fast (~11s on my machine). Therefore, we’ll use a bit of algebra to make the problem more managable:

Let (a, b, c) be a Pythagorean triplet

    a < b < c
    a² + b² = c²

For N = a + b + c it follows

    b = N·(N - 2a) / 2·(N - a)
    c = N·(N - 2a) / 2·(N - a) + a²/(N - a)

which automatically meets b < c.

The condition a < b gives the constraint

    a < (1 - 1/√2)·N

We arrive at

    sub triplets(\N) {
        for 1..Int((1 - sqrt(0.5)) * N) -> \a {
            my \u = N * (N - 2 * a);
            my \v = 2 * (N - a);

            # check if b = u/v is an integer
            # if so, we've found a triplet
            if u %% v {
                my \b = u div v;
                my \c = N - a - b;
                take $(a, b, c);
            }
        }
    }

    say [*] .list for gather triplets(1000);

Runtime: 0.5s

Note the declaration of sigilless variables \N, \a, …, how $(…) is used to return the triplet as a single item and .list – a shorthand for $_.list – to restore listy-ness.

The sub &triplets acts as a generator and uses &take to yield the results. The corresponding &gather is used to delimit the (dynamic) scope of the generator, and it could as well be put into &triplets, which would end up returning a lazy list.

We can also rewrite the algorithm into dataflow-driven style using feed operators:

    constant N = 1000;

    1..Int((1 - sqrt(0.5)) * N)
    ==> map -> \a { [ a, N * (N - 2 * a), 2 * (N - a) ] } \
    ==> grep -> [ \a, \u, \v ] { u %% v } \
    ==> map -> [ \a, \u, \v ] {
        my \b = u div v;
        my \c = N - a - b;
        a * b * c
    }
    ==> say;

Runtime: 0.5s

Note how we use destructuring signature binding -> […] to unpack the arrays that get passed around.

There’s no practical benefit to use this particular style right now: In fact, it can easily hurt performance, and we’ll see an example for that later.

It is a great way to write down purely functional algorithms, though, which in principle would allow a sufficiently advanced optimizer to go wild (think of auto-vectorization and -threading). However, Rakudo has not yet reached that level of sophistication.

But what to do if we’re not smart enough to find a clever solution?

Problem 47

Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

This is a problem where I failed to come up with anything better than brute force:

    constant $N = 4;

    my $i = 0;
    for 2..* {
        $i = factors($_) == $N ?? $i + 1 !! 0;
        if $i == $N {
            say $_ - $N + 1;
            last;
        }
    }

Here, &factors returns the number of prime factors. A naive implementations looks like this:

    sub factors($n is copy) {
        my $i = 0;
        for 2, 3, *+2 ...^ * > $n {
            if $n %% $_ {
                ++$i;
                repeat while $n %% $_ {
                    $n div= $_
                }
            }
        }
        return $i;
    }

Runtime: unknown (33s for N=3)

Note the use of repeat while … {…}, the new way to spell do {…} while(…);.

We can improve this by adding a bit of caching:

    BEGIN my %cache = 1 => 0;

    multi factors($n where %cache) { %cache{$n} }
    multi factors($n) {
        for 2, 3, *+2 ...^ * > sqrt($n) {
            if $n %% $_ {
                my $r = $n;
                $r div= $_ while $r %% $_;
                return %cache{$n} = 1 + factors($r);
            }
        }
        return %cache{$n} = 1;
    }

Runtime: unknown (3.5s for N=3)

Note the use of BEGIN to initialize the cache first, regardless of the placement of the statement within the source file, and multi to enable multiple dispatch for &factors. The where clause allows dynamic dispatch based on argument value.

Even with caching, we’re still unable to answer the original question in a reasonable amount of time. So what do we do now? We cheat and use Zavolaj – Rakudo’s version of NativeCall – to implement the factorization in C.

It turns out that’s still not good enough, so we refactor the remaining Perl code and add some native type annotations:

    use NativeCall;

    sub factors(int $n) returns int is native('./prob047-gerdr') { * }

    my int $N = 4;

    my int $n = 2;
    my int $i = 0;

    while $i != $N {
        $i = factors($n) == $N ?? $i + 1 !! 0;
        $n = $n + 1;
    }

    say $n - $N;

Runtime: 1m2s (0.8s for N=3)

For comparison, when implementing the algorithm completely in C, the runtime drops to under 0.1s, so Rakudo won’t win any speed contests just yet.

As an encore, three ways to do one thing:

Problem 29

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

A beautiful but slow solution to the problem can be used to verify that the other solutions work correctly:

    say +(2..100 X=> 2..100).classify({ .key ** .value });

Runtime: 11s

Note the use of X=> to construct the cartesian product with the pair constructor => to prevent flattening.

Because Rakudo supports big integer semantics, there’s no loss of precision when computing large numbers like 100100.

However, we do not actually care about the power’s value, but can use base and exponent to uniquely identify the power. We need to take care as bases can themselves be powers of already seen values:

    constant A = 100;
    constant B = 100;

    my (%powers, %count);

    # find bases which are powers of a preceeding root base
    # store decomposition into base and exponent relative to root
    for 2..Int(sqrt A) -> \a {
        next if a ~~ %powers;
        %powers{a, a**2, a**3 ...^ * > A} = a X=> 1..*;
    }

    # count duplicates
    for %powers.values -> \p {
        for 2..B -> \e {
            # raise to power \e
            # classify by root and relative exponent
            ++%count{p.key => p.value * e}
        }
    }

    # add +%count as one of the duplicates needs to be kept
    say (A - 1) * (B - 1) + %count - [+] %count.values;

Runtime: 0.9s

Note that the sequence operator ...^ infers geometric sequences if at least three elements are provided and that list assignment %powers{…} = … works with an infinite right-hand side.

Again, we can do the same thing in a dataflow-driven, purely-functional fashion:

    sub cross(@a, @b) { @a X @b }
    sub dups(@a) { @a - @a.uniq }

    constant A = 100;
    constant B = 100;

    2..Int(sqrt A)
    ==> map -> \a { (a, a**2, a**3 ...^ * > A) Z=> (a X 1..*).tree } \
    ==> reverse()
    ==> hash()
    ==> values()
    ==> cross(2..B)
    ==> map -> \n, [\r, \e] { (r) => e * n } \
    ==> dups()
    ==> ((A - 1) * (B - 1) - *)()
    ==> say();

Runtime: 1.5s

Note how we use &tree to prevent flattening. We could have gone with X=> instead of X as before, but it would make destructuring via -> \n, [\r, \e] more complicated.

As expected, this solution doesn’t perform as well as the imperative one. I’ll leave it as an exercise to the reader to figure out how it works exactly ;)

That’s it

Feel free to add your own solutions to the Perl6 examples repository under euler/.

If you’re interested in bioinformatics, you should take a look at Rosalind as well, which also has its own (currently only sparsely populated) examples directory rosalind/.

Last but not least, some solutions for the Computer Language Benchmarks Game – also known as the Debian language shootout – can be found under shootout/.

You can contribute by sending pull requests, or better yet, join #perl6 on the Freenode IRC network and ask for a commit bit.

Have the appropriate amount of fun!

Day 3 – Whatever the layout manager is

December 3, 2012

Introduction

This article aims to demonstrate how Whatever — one of the many interesting Perl 6 curiosities — could be useful to easily implement and use complex things like a layout manager. In a couple of words, a layout manager is the part of a graphical interface in charge of the spatial arrangement of objects like windows or widgets. For the sake of simplicity, the layout manager implemented in this article will comply with the following three rules:

  • there are only two kinds of widgets: terminal or container, the latter can contain other widgets of either kind;
  • a widget cannot be overlapped, except for containers which fully contain their sub-widgets; and
  • only the height can be adjusted, this size can be either static, dynamic, or intentionally left unspecified.

Usage

From the user's point-of-view, this layout manager aims to be as easy to use as possible. For example, it shouldn't be hard to specify such typical interface below, inspired from a text-based program. In this example, the interface and body widgets are containers, all the others are terminals:

interface (X lines)
+----> +------------------------------------------+
|      | menu bar (1 line)                        |  body (remaining space)
|      +------------------------------------------+ <----+
|      | subpart 1 (1/3 of the remaining space)   |      |
|      |                                          |      |
|      |                                          |      |
|      +------------------------------------------+      |
|      | subpart 2 (remaining space)              |      |
|      |                                          |      |
|      |                                          |      |
|      |                                          |      |
|      |                                          |      |
|      |                                          |      |
|      +------------------------------------------+ <----+
|      | status bar (1 line)                      |
+----> +------------------------------------------+

The user don't know what the remaining space is in advance because such an interface is arbitrary resizable. As a consequence it should be specified as a non-predefined value; this is where * — the Whatever object — comes in handy. This object is interesting for two reasons:

  • from the user's point-of-view, the definition of non-static sizes is as simple as: * / 3 for the subpart 1 (dynamic) and just * for the subpart 2 (unspecified); and
  • from the developer's point-of-view, Perl 6 transforms automatically things like $size = * / 3 into a closure: x → x / 3. Then, it could be called like a regular function: $size($x).

That way, the previous GUI can be transliterated into the following lines of code:

my $interface =
    Widget.new(name => 'interface', size => $x, sub-widgets => (
        Widget.new(name => 'menu bar', size => 1),
        Widget.new(name => 'main part', size => *, sub-widgets => (
            Widget.new(name => 'subpart 1', size => * / 3),
            Widget.new(name => 'subpart 2', size => *))),
        Widget.new(name => 'status bar', size => 1)));

Implementation

The drawing of terminal widgets is straightforward since most of the work is done by containers. Those are in charge to compute the remaining space as well as to uniformly distribute widgets that have an unspecified size:

class Widget {
    has $.name;
    has $.size is rw;
    has Widget @.sub-widgets;

    method compute-layout($remaining-space? is copy, $unspecified-size? is copy) {
        $remaining-space //= $!size;

        if @!sub-widgets == 0 {  # Terminal
            my $computed-size = do given $!size {
                when Real     { $_                  };
                when Callable { .($remaining-space) };
                when Whatever { $unspecified-size   };
            }

            self.draw($computed-size);
        }
        else {  # Container
            my @static-sizes   =  grep Real,     @!sub-widgets».size;
            my @dynamic-sizes  =  grep Callable, @!sub-widgets».size;
            my $nb-unspecified = +grep Whatever, @!sub-widgets».size;

            $remaining-space -= [+] @static-sizes;

            $unspecified-size = ([-] $remaining-space, @dynamic-sizes».($remaining-space))
                                 / $nb-unspecified;

            .compute-layout($remaining-space, $unspecified-size) for @!sub-widgets;
        }
    }

    method draw(Real $size is copy) {
        "+{'-' x 25}+".say;
        "$!name ($size lines)".fmt("| %-23s |").say;
        "|{' ' x 25}|".say while --$size > 0;
    }
}

Here, any Callable object can be used to specify a dynamic size, as far as it takes the computed remaining space as argument. That means it is possible to specify more sophisticated dynamic size by passing a code Block. For example, { max(5, $^x / 3) } ensures the widget has a proportional size that can't decrease below 5.

Conclusion

It's time to check if this trivial layout manager works correctly both in Rakudo and Niecza, the two most advanced implementations of Perl 6. The following test is rather simple, it creates and draws an interface, then resize it and draws it again:

my $interface =
    Widget.new(name => 'interface', size => 11, sub-widgets => (
        Widget.new(name => 'menu bar', size => 1),
        Widget.new(name => 'main part', size => *, sub-widgets => (
            Widget.new(name => 'subpart 1', size => * / 3),
            Widget.new(name => 'subpart 2', size => *))),
        Widget.new(name => 'status bar', size => 1)));

$interface.compute-layout;  # Draw
$interface.size += 3;       # Resize
$interface.compute-layout;  # Redraw

The results before and after resizing are respectively displayed below. They are close enough from the initial mockup, n'est-ce pas?

+-------------------------+            +-------------------------+
| menu bar (1 lines)      |            | menu bar (1 lines)      |
+-------------------------+            +-------------------------+
| subpart 1 (3 lines)     |            | subpart 1 (4 lines)     |
|                         |            |                         |
|                         |            |                         |
+-------------------------+            |                         |
| subpart 2 (6 lines)     |            +-------------------------+
|                         |            | subpart 2 (8 lines)     |
|                         |            |                         |
|                         |            |                         |
|                         |            |                         |
|                         |            |                         |
+-------------------------+            |                         |
| status bar (1 lines)    |            |                         |
                                       |                         |
                                       +-------------------------+
                                       | status bar (1 lines)    |

Finally, the implementation of such a flexible program is really simple in Perl 6: everything is already there, in the core language. Obviously, this trivial layout manager isn't ready for prime-time since a lot of things are missing: sanity checks, multiple dimensions, … but those are left as exercises to you, the reader ;) For any questions or comments, feel free to meet Perl 6 fellows on IRC (#perl6 on freenode).

Bonus

As seen previously, $!size can be Whatever, but it can't be whatever you want. For example, a negative Real or a string are not correct values. Once again Perl 6 provides a simple yet powerful feature: constrained types. In a couple of words this permits to define new types from a set of constraints:

subset PosReal of Real where * >= 0;
subset Size where {   .does(PosReal)
                   or .does(Callable) and .signature ~~ :(PosReal --> PosReal)
                   or .does(Whatever) };

has Size $.size is rw;

Day 2 – Anonymous functions for great good

December 2, 2012

Perl 6 has great support for functions. It packs function signatures full with awesome, and lets you have your cake and eat it a couple of times over with all the ways you can specify a function. You can specify parameter types, optional parameters, named parameters, and even those cool where clauses. If I didn’t know better, I’d suspect Perl 6 was compensating for some predecessor’s rather rudimentary handling of parameters. (*cough* @_ *cough*)

Among all these other things, Perl 6 also allows you to define functions without naming them.

sub { say "lol, I'm so anonymous!" }

How is this useful? If you can’t name the function, you can’t call it, right? Wrong.

You can store the function in a variable. Or return it from another function. Or pass it to another function. In fact, when you don’t name your function, the focus becomes much more what code you’re going to run later. Like an executable “to do”-list.

Of course, Perl 5 has anonymous functions, too. With exactly the same syntax, even. In fact, all the big languages do anonymous functions, according to this list of languages on Wikipedia. Except, it seems, the historically significant languages C and Pascal. And the more modern but lumbering Java. “Planned for Java 8″. Haha, Java, catch up! Even C++ has them now.

How important are anonymous functions? Very. In the 1930s, Alan Turing showed how all computer processes could be simulated using just a pre-programmed machine that looks like a tape recorder, reading and writing values on a really long tape. (The Turing Machine.) Meanwhile, across the Atlantic, Alonzo Church showed how all computer processes could be simulated using just anonymous functions, no tape recorder required. (Lambda calculus.) It’s all quite elegant.

Later languages like Lisp and Scheme lean heavily on anonymous functions as a key component in the language. And lately a scrappy language called JavaScript, which also leans heavily on anonymous functions, has taken over the world while we were all busy surfing the web.

But let’s talk possibilities here. What can anonymous functions do for us? And how would it look in Perl 6?

Well, take sorting as a famous example. You could imagine Perl 6 having a sort_lexicographically function and a sort_numerically function. But it doesn’t. It has a sort function. When you want it to sort in a certain way, you just pass an anonymous function to it.

my @sorted_words = @words.sort({ ~$_ });
my @sorted_numbers = @numbers.sort({ +$_ });

(Technically, those are blocks, not functions. But the difference isn’t significant if you’re not planning to return anywhere inside.)

And of course it goes further than just those two sort orders. You could sort by shoe size, or maximum ground speed, or decreasing likelihood of spontaneous combustion. All because you can pass in any logic as an argument. Object-oriented people are very proud of this pattern, and call it “dependency injection”.

Come to think of it, map and grep and reduce all depend on this kind of function-passing. We sometimes refer to passing functions to functions as “higher order programming”, as if it was only something people with special privileges should be doing. But in fact it’s a very useful and broadly applicable technique.

The above examples all run the anonymous functions as part of their own execution. But there’s no need to restrict ourselves to this. We can create functions, return them, and then run them later:

sub make_surprise_for($name) {
    return sub { say "Sur-priiise, $name!" };
}

my $reveal_surprise = make_surprise_for("Finn");    # nothing happens, yet
# ...wait for it...
# ...wait...
# ...waaaaaaait...
$reveal_surprise();        # "Sur-priiise, Finn!"

The function in $reveal_surprise remembers the value of $name even though the original function passing it in has exited long ago. That’s pretty nice. This effect is referred to as the anonymous function closing over the variable $name. But there’s no need to get technical — the long and short of it is “it’s awesome”.

And in fact, it feels quite natural if we just look at anonymous functions alongside other staple storage mechanisms such as arrays and hashes. All of these can be stored in variables, passed as arguments or returned from functions. An anonymous array allows you to store a sequence of things for later. An anonymous hash allows you to store mappings/translations of things for later. An anonymous function allows you to store calculations or behavior for later.

Later this month, I’ll go through how to exploit dynamic scoping in Perl 6 to create nice DSL-y interfaces. We’ll see how anonymous functions come into play there as well.

Perl 6 Advent Calendar 2012: Table of Contents

December 1, 2012

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

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

Day 1 – State of Perl 6 in 2012

December 1, 2012

Welcome to another edition of your annual Perl 6 advent calendar.

As is tradition on the first of December, you can read a short overview over what has changed in the past year, and where we are standing now.

The list of major changes to the specification is pretty short. The IO subsystem has undergone a rewrite, and now much better reflects the realities in implementations, and actually has a measure of common sense applied. S32::Exceptions has gone through lots of changes (mostly extensions), and now there is a decent core of exception classes in Perl 6.

Both Rakudo and Niecza, the two major Perl 6 compilers, have matured a great deal. Contrary to last year, chances are pretty good that if your program works on one of the compilers, it also works on the other. Niecza also temporarily overtook Rakudo on the count of passing tests.

Niecza had a revamp of the roles implementation, has gained constant folding, awesome Unicode support in regexes, list comprehensions and a no strict; mode. To name just a few of the major changes.

Rakudo now supports heredocs, all phasers (special blocks like BEGIN, END, FIRST, …), longest-token matching in regexes, typed exceptions, much nicer backtraces and operator adverbs. And it now has a debugger, which is shipped with the Rakudo Star distribution.

The module ecosystem has grown a lot, and there is much more documentation for Perl 6 than a year ago.

So, after all these changes, where are we now?

Reports from production uses of Perl 6 are slowly starting to trickle in, and these days if your Perl 6 code has bugs, the chances are much higher that your code is to blame than the compilers. Perl 6 has never been this much fun to use. It surely has been a good and productive year for Perl 6, and we’re sure that this last month will continue the tradition. Have fun!


Follow

Get every new post delivered to your Inbox.

Join 37 other followers