Archive for May, 2010

Comparing Two Numerics

May 22, 2010

I’ve mentioned before that TimToady and I had ideas for comparing two arbitrary Numeric values. The scheme may not be mathematically ideal, but it does define a handy ordering which works predictably for all Numeric types and is easy to understand.

The idea is that any Numeric value should be able to return a list of real values to use for the purposes of comparison. For a Real, the list’s only element is the value itself. For a Complex, the list has two parts, the real and imaginary values of the Complex, in that order. For your user-defined Numeric type, its whatever list of Reals seems to fit well with the above scheme.

Then, when asked to compare to Numeric values, we generate that list of Reals for each and do a lexicographical compare on the two lists. (We don’t go into an infinite recursion here because comparing two Reals calls different code.)

I’ve been kicking around this notion for a long time now without being able to think of an appropriate name for the method to return a list of Reals. I realized yesterday that the problem was I was thinking of it as being akin to the Real Bridge method — should I call it Bridges, or something like that. But in fact, there’s no need to get Bridge involved at all, we really are just returning a list of Reals. So the perfect name (IMO) is reals.

With that out of the way, I started implementing the code as soon as I had some tuits. Here’s my first working stab at it:

multi sub infix:«<=>»(Numeric $a, Numeric $b) {
    my @a = $a.reals;
    my @b = $b.reals;
    for ^(+@a max +@b) -> $i {
        return -1 if $i >= +@a;
        return +1 if $i >= +@b;
        my $c = @a[$i] <=> @b[$i];
        return $c if $c != 0;
    }
    0;
}

Kind of messy, isn’t it? Then I realized that there was a simple meta-op-based version:

multi sub infix:«<=>»(Numeric $a, Numeric $b) {
    my @a = $a.reals;
    my @b = $b.reals;
    [||] (@a Z<=> @b), (+@a <=> +@b);
}

That right there is one of the major reasons I love Perl 6. Perl 5 had a lovely idiom for chained comparisons, but it required you fix the length of the chain in advance. Perl 6 lets you elegantly extend that idea to handle chains of varying length. (If you’re wondering, the Z comparison does pairwise comparison on the two arrays until one of them runs out, then we tag on one additional -1/0/+1 to indicate which array was shorter, and then run a chained || on the entire lot.

Warning: Neither code example here is fully tested yet! But I was so excited about the meta-op version I had to share.

Thanks to the Perl Foundation and Ian Hague for supporting this work.

Announce: Rakudo Perl 6 development release #29 (“Erlangen”)

May 20, 2010

On behalf of the Rakudo development team, I’m pleased to announce the May 2010 development release of Rakudo Perl #29 “Erlangen”. Rakudo is an implementation of Perl 6 on the Parrot Virtual Machine (see http://www.parrot.org). The tarball for the May 2010 release is available from http://github.com/rakudo/rakudo/downloads .

Rakudo Perl follows a monthly release cycle, with each release named after a Perl Mongers group. The May 2010 release is code named “Erlangen” in recognition of Erlangen.pm and the Perl 6 talk that Moritz Lenz, one of our core developers, gave this month.

Some of the specific changes and improvements occurring with this release include:

* Lexical classes and roles were implemented. Additionally, anonymous classes — which were never quite right in alpha — are now implemented more correctly, and anonymous roles are also supported.

* Basic support for named enumerations of the form ‘enum Weekday ‘ has been restored.

* First cut of use Foo:from and eval(‘foo’, :lang); needs Blizkost[1] to be installed to work.

* Numeric / Real roles much closer to the spec now.

* As always, many additional small features and bug fixes make working with Rakudo more pleasant.

* Rakudo now passes 32,347 spectests. We estimate that there are about 39,500 tests in the test suite, so Rakudo passes about 82% of all tests.

For a more detailed list of changes see “docs/ChangeLog”.

The development team thanks all of our contributors and sponsors for making Rakudo Perl possible, as well as those people who worked on parrot, the Perl 6 test suite and the specification.

The following people contributed to this release:
Solomon Foster, Moritz Lenz, Jonathan Worthington, Martin Berends, chromatic, Carl Masak, snarkyboojum, Stefan O’Rear, Reini Urban, Jonathan Scott Duff, takadonet, Christoph Otto, isBEKaml, ash_, bubaflub, Jimmy Zhuo, Peter Lobsinger and Patrick Abi Salloum

If you would like to contribute, see http://rakudo.org/how-to-help , ask on the perl6-compiler@perl.org mailing list, or ask on IRC #perl6 on freenode.

The next release of Rakudo (#30) is scheduled for June 17, 2010. A list of the other planned release dates and code names for 2010 is available in the “docs/release_guide.pod” file. In general, Rakudo development releases are scheduled to occur two days after each
Parrot monthly release. Parrot releases the third Tuesday of each month.

Have fun!

[1] http://github.com/jnthn/blizkost

Pred to sin some more

May 19, 2010

I’ve accomplished a good bit of work on Numeric in the last eleven days. Soon after my last post I started work on comparison operators. First I provided Real versions of the numeric comparison operators, all of which delegate to Bridge versions (implemented as Num for now). Then I removed the Num, Num version of the cmp operator, replacing it with a Numeric, Numeric version. Note that despite the presence of Numeric, Numeric cmp, numeric comparisons only work on Real types at the moment.

TimToady++ and I have a theory for supporting comparisons on generic Numeric types, but I have not started to implement it yet. My basic idea is similar to the Bridge idea for Reals. There would be a Numeric method (don’t have a name yet) which converts your generic Numeric type to a list of Real numbers. (Obviously Real numbers would convert to a single Real, Complex would convert to two, etc.) You would then compare the Reals lexicographically. This probably isn’t a mathematically sensible ordering, but it does provide a reasonable ordering that would put Reals in the order you expect and still allow you to sort Complex numbers.

After that I got sqrt working properly in the new system, adding Numeric.sqrt and Real.sqrt, and cleaning up the Num and Complex versions.

Then the big effort (at least in terms of lines of code) was getting the trig functions working properly in the new system. It was just a matter of cloning the approach I’d taken for sin for all the other functions, though there was one bizarre catch. It turned out that several of the trig functions had two different implementations in Complex. When I took away the “multi” from the first implementation, the second one kicked in — and the second one was wrong. Since I didn’t actually realize the second one was there, this lead to about an hour of extreme confusion on my part before I sorted things out.

I finished up with tweaks for ceiling, floor, and log. Then I implemented Numeric versions of postfix i, succ, and pred. These are expressed in terms of simple addition and multiplication, so Numeric’s implementations should work for any reasonably robust Numeric class. I’m guessing it will frequently be worthwhile to still have class-specific versions of succ and pred, both for efficiency and to help ensure that $x and $x.pred usually have the same type.

What’s next? As I mentioned about, generic Numeric comparison code. The rand function — it’s currently listed as Numeric, but it doesn’t take any arguments and returns a Num, so I’m not sure why. srand at least takes a Real, but again, it doesn’t really seem like it fits, IMO. Numeric.roots. Work on more tests. Fixing up the spec a bit. And I may take a look in other math libraries to see if there are obvious functions we are missing.

Thanks to the Perl Foundation and Ian Hague for supporting this work.

Sins of a Logger

May 7, 2010

I’ve been having a terrible time getting the log method to work in the Numeric / Real framework. Essentially, the problem is that there are two different concepts of log going on: log with respect to a specified base, which is defined in terms of the natural log. Perl 6’s log command combines these two into one function, with a default base of e. Still, splitting up the function into a multi was the easiest way to implement this: multi method log(Num $x:), which is used to implement multi method log(Num $x: Num $base).

That worked fine when log was not a part of Numeric or Real, but failed in different mysterious ways each time I tried to extend it to those roles. Finally this week I realized the problem: multis and roles do not mix yet in Rakudo. At all.

Knowing that, it was easy to figure out what the next step should be. I just renamed the natural log function to be log-e. (Think I will rename it to ln in a second.) Then I implemented method log(Numeric $x: Numeric $base = e) using it. This has the additional advantage of properly supporting logs where $x and $base are different types. As long as each type has log-e defined for it, and the results of those calls can be divided, the mixed type will be handled properly.

This works well in current Rakudo. Pleased with this, I went on to move the sin method to Numeric and Real as well — the trick there turned out to be removing multi from the declarations of Num.sin and Complex.sin. With that established, porting all the trig functions to the new system is just a matter of time. I do need to sit down and rethink the trig tests a bit.

Thanks to the Perl Foundation and Ian Hague for supporting this work.


Follow

Get every new post delivered to your Inbox.