Categories

Posts in this category

Wed, 27 Aug 2008

Why you don't need the Y combinator in Perl 6


Permanent link

The other day on IRC we discussed the book "Higher Order Perl" and the Y combinator. Aristotle wrote an excellent article about the Y combinator in Perl.

In short it's a rather involved construction that allows you to write anonymous recursive subs that truly have no name.

If you read about it the first time, you might become scared by its complexity, and ask yourself "do I have to understand such things to become a good programmer?". The good answer is, with Perl 6 you don't, because there's an easy way to avoid the complexity:

my $factorial = sub (Int $x) {
    if ($x < 2) {
        return 1;
    } else {
        return $x * &?ROUTINE($x - 1);
    }
}

You see that Perl 6 cheats: although you never gave the sub a name (except $factorial, but you wouldn't even need that, for example when passing it as a parameter to another function), you can still access it through the &?ROUTINE variable.

It contains the innermost routine definition (sub, method, regex, submethod or whatever) in the current lexical scope. The & sigil stands for a Callable object, and the ? twigil for a variable or constant that is known at compile time ("Compiler hint variable").

So let's golf a bit. Just for the fun of it. First the if ... else can be replaced by the ternary operator ?? !!, and we don't need explicit return's:

my $factorial = sub (Int $x) {
    $x < 2 ?? 1 !!  $x * &?ROUTINE($x - 1);
}

For a golfed version you clearly don't need a type signature, and the &?ROUTINE thing has too long a name. We can circumvent it by using a block instead of a sub:

my $factorial = -> $x {
    $x < 2 ?? 1 !! $x * &?BLOCK($x - 1);
}

Actually we don't even need that -> $x declaration (a "pointy block" that other programming languages call "Lambda"), we can use a self-declared positional argument:

my $factorial = {
    $^x < 2 ?? 1 !! $^x * &?BLOCK($^x - 1);
}

Of course there's a much shorter version, but it's not recursive so it doesn't really fit the current topic: my $factorial = { [*] 1 .. $^x };, which uses the [ ] reduction meta operator.

[/perl-6] Permanent link