Strangely Consistent

Musings about programming, Perl 6, and programming Perl 6

June 26 2011: Signatures

We haven't implemented a Fibonacci subroutine yet. Let's do that.

sub fib($n) {
    return 0 if $n == 0;
    return 1 if $n == 1;

    return fib($n - 1) + fib($n - 2);
}

Yes, it's recursive, meaning that it calls itself. That's perfectly fine; we just have to make sure that it bottoms out in some base case or other. That's why we have the first two lines in there, as our base cases.

(It's not a very efficient implementation. It will get unbearably slow for larger values of $n. There are better ways to implement fib, but what this version has going for it is that it's short and clear.)

But wait! There's a terrible thing that can happen to this subroutine. If we call fib(2.5) it will call fib(1.5), which will call fib(0.5), which will call fib(-0.5), and so on down to minus infinity, which is very far down indeed.

No problem, though. We just adorn fib's parameter $n with a type:

sub fib(Int $n) {
    ... # (same)
}

The only thing that changed there is the Int in front of the $n on the first line. Now when we try to call fib(2.5), we get

Nominal type check failed for parameter '$n'; expected Int but got Rat instead

Yep, 2.5 is a Rat. Short for "rational number". Now you know. Also, the thing that we just put the type in is called a signature. Hence the name of this post. Every subroutine has a signature, even if it's an empty one. The signature is like a guard that makes sure only values of the right type get through the door into the subroutine.

So, that's that problem solved. But... oh no! There's another way fib could loop infinitely. (As if it wasn't already slow enough...) What would happen if we passed in a negative integer, like fib(-1).

Well, it wouldn't get stuck in any of the base cases; it's already below them. We realize that we never really meant for someone to call fib with a negative integer argument. Argh.

What's worse, we can't just solve this by slapping a NonNegativeInt type on $n either, because there is no such type in Perl 6. Instead, we can do one of two things.

The first thing we can do is to use a where clause:

sub fib(Int $n where { $n >= 0 }) {
    ...
}

Now people will get this when they try to call fib(-1):

Constraint type check failed for parameter '$n'

I guess you can see how where clauses complement named types quite nicely. We can check anything we want inside of those. And it's shorter than writing something like this:

sub fib(Int $n) {
    die "fib can't handle negative numbers!"
        unless $n >= 0;

    ...
}

The second thing we can do is define a NonNegativeInt:

subset NonNegativeInt of Int where { $_ >= 0 };

sub fib(NonNegativeInt $n) {
    ...
}

So... subset gives us the ability to create new, narrower types. We'll see lots more about type creation in the next few days.

subset, as it happens, also uses a where clause. Of course that's because we're still doing essentially the same check, only we're declaring it outside of the signature. Note how we can't use $n inside the where clause, because $n only exists within the context of fib. But the topic variable $_ within where clauses means "the value we're talking about", and that's what we need.

When should you use where clauses directly in the signature, and when should you define subtypes? There's no right or wrong here, but it makes a lot of sense to declare a subtype if you plan to use that particular constraint in a lot of different situations.

Let's end today's post with a nice feature that we're now prepared to fully appreciate: multi subs. They're simply subroutines with the same name but different signatures:

multi sub fib(Int $n where { $n == 0 }) { 0 }
multi sub fib(Int $n where { $n == 1 }) { 1 }

multi sub fib(Int $n where { $n  > 1 }) { fib($n - 1) + fib($n - 2) }

Clearly, it gets rid of a bit of conditionals, by pushing things into signatures instead. In fact, we can write the first two multis even shorter:

multi sub fib(0) { 0 }
multi sub fib(1) { 1 }

multi sub fib(Int $n where { $n > 1 }) { fib($n - 1) + fib($n - 2) }

Look how close that is to the definition at the top of the Wikipedia page.

Multis are a great way to divide related but different behaviors into different subs. More about clever ways of subdividing things tomorrow, when we talk about classes.