http://qs321.pair.com?node_id=768595

From other recient posts, I found Higher Order Perl free for the downloading. I think I had seen it before a few years ago. But now I have Perl 6 functions and "subtypes" on the brain, so this occurs to me as I read it.

The original function,
# step 1 sub binary { my ($n) = @_; return $n if $n == 0 || $n == 1; #step 2 my $k = int($n/2); my $b = $n % 2; #step 3, recursion my $E = binary($k); #step 4 return $E . $b; }
First, port that to Perl 6 without changing much.
# step 1 sub binary ($n) { return $n if $n == 0|1; #step 2 my $k = int($n/2); my $b = $n % 2; #step 3, recursion my $E = binary($k); #step 4 return $E ~ $b; }
The step 4 is edited because catenation is now done with ~ rather than a dot. The sub has a declared parameter rather than a line to extract it, and lookie here, the if statement....? $n == 0|1. This is a junction, and means just what it says: $n is equal to (0 or 1)? Picture a longer group of comparisons, as I'm sure you've had in the past, and the savings and readability mounts.

Now comes the feature I was reminded of. Perl 6 supports overloading. And you can overload like this:

sub binary (0|1 $n) { $n } sub binary ($n) { my $k = int($n/2); my $b = $n % 2; my $E = binary($k); return $E ~ $b; }
That is, a literal is considered a subset type of one value. And Junctions can be used with types as well, so you can write recursive functions with the base case as a separate function, rather than dividing it up explicitly inside the function.

Furthermore, the function has a flaw in returning funny stuff if the argument is not an integer, and may do one of several wrong things if the argument is negative. Both of these can be fixed by using overloading as well:

Change the main form from untyped to taking an Int. Now a floating point value will be truncated before the first call, avoiding the two problems the existing code has along these lines. Second, use the same overloading mechanism to look for negative values. Perhaps there will be standard types for negative, non-positive, etc. as there are in XSD. But it's not worth the trouble to declare one for a single use:

sub binary (Int where { $_ < 0 } $n) { my $E= binary(-$n); return "-" ~ $E; }
Assuming you didn't mean two's complement or something else. Hmm, that should be specifiable. Since Int does not have a word size inherent with it (it holds any size Int subject to memory limits), you have to tell it the word size for 2s complement, and that can serve as an enabling switch:
subset NegativeInt of Int where { $_ < 0 } # I decided to declare it a +fter all subset PositiveInt of Int where { $_ > 0 } sub binary (NegativeInt $n, :$wordsize) { if defined $wordsize { # do 2's complement mode PositiveInt $m= 2 ** $wordsize - $n; return binary($m); } else { return "-" ~ binary(-$n); } }
The :$wordsize with the leading colon declares a named (only) parameter, so you can now say say binary($n,:wordsize<64>) and if $n happens to be negative, you use the extra argument. In the other forms, it's harmlessly ignored.

The other interesting thing is the line that computes the 2's complement. I worried about the wordsize not being long enough, and in that case the subtraction as formulated would still be negative. Meanwhile, I could not store the result back into $n ($n= blah -$n) because the parameter is read-only. Declaring it otherwise would not help, since it is also declared as Negative. The result is supposed to be positive, so would be a type error. So... rather than use a normal Int for $m, I made that one a PositiveInt. That documents the intent neatly, and automatically gives me the test for the result not being negative also (and I know it's not zero).

Perhaps that's not the best error to get when it happens. But, think about this: if I had used restrictive typing as a matter of course and forgotten to check for this directly, I'd get the developer-friendly error rather than an infinite recursion when the inevitable happened. Then I might put in a manual error check to give a better message and carp it, but I'm letting declarations do the error checking I may have forgotten. In more complex situations, that could be less obvious.

Lesson: declared typing is declaring your assumptions.

But, there is still another issue. The wordsize might be some goofy value like "hello" or ¾ or -3+π\i. The easiest thing is to declare that to be PositiveInt as well. (In case you are wondering, π\i is because πi would run together into one word. The \ between letters is a degenerate unspace and serves to break the tokens without introducing whitespace. For 7i and such you don't have the problem)

Putting the condition in the type declaration itself is powerful because you do more than just check for the correct range. You check the overall type as well. If you wrote

PRE { !defined($wordsize) || frac($wordsize)==0 }
you are not only being unwieldy, but the test might not even make sense if the variable is some totally different type and not a real number at all. Type checking offers a powerful constraint mechanism just by declaring it.

For cases that require interrelationships between values, you do have to write the check inside the function. And the PRE block, as shown, formalizes this test as a precondition. (Conjecture: failing a precondition may optionally indicate "no fit" just like parameter types, and cause the dispatch mechanism to look for another match. Do that by throwing an exception of a built-in type for the purpose rather than just evaluating as False)

And that's only the first, rather trivial code example in the book! I think it will take me a long time to get through it again.

Comments welcome: I'll probably put these on a web page after I finish.

Updated: fix paste error in "original" listing; correct subtype to subset type.

Replies are listed 'Best First'.
Re: Reflections on “Higher Order Perl” §1.1
by parv (Parson) on Jun 05, 2009 at 06:45 UTC

    In your copy of original code, you seems to have a typo ...

    sub binary { binary my ($n) = @_; ...

    ... I was thinking that that might induce infinite recursion. Turns out code refuses to be compiled due to syntax error (and, parentheses are required to be able to cause "Deep recursion" error).

Re: Reflections on “Higher Order Perl” §1.1
by moritz (Cardinal) on Jun 10, 2009 at 07:57 UTC
    sub binary (0|1 $n) { $n } sub binary ($n) { my $k = int($n/2); my $b = $n % 2; my $E = binary($k); return $E ~ $b; }

    That's fantasy syntax, unless it was allowed in the last two weeks where I didn't have internet access. It might work along these lines:

    multi binary ($n where 0|1) { $n } multi binary ($n) { my $k = int($n/2); my $b = $n % 2; my $E = binary($k); return $E ~ $b; }

    When you post Perl 6 code these days it's worth trying it in Rakudo first, which supports all the features needed for the subroutine above (I would try it myself, but I'm currently on a machine where I can't install any programs :-/).

      A literal or an enumeration or constant is now allowed as a subset type of one. That is indeed fairly new. File a bug. That's one reason why the enumerations (e.g. True and False) got changed to capitalized, as they are grammatically types. That's straight from the camel's mouth: "basically any value can be used as a single-valued type in a signature ... and write the usual factorial with multi factorial (0) { 1 } etc"

      So it was in there a month ago, at least. He shows the declarator form of constant in that discussion, so it might have been in his head before it was checked in to STD.pm.

      Perhaps we could have a node here that runs P6 syntax through rakudo or the current STD.pm treebuilder app.

      —John

        Note that multi a(0|1) { ... } is not the same as multi a(0|1 $n) { ... }. The former is explicitly allowed as a short cut for an anyonymous parameter, ie its longer form would be Int $ where 0|1. The latter is currently not parsed by STD.pm, and I don't see which part of the specs would allow that - any pointers to a piece of spec?