Archive for March, 2010

Numeric Plan of Attack

March 30, 2010

As you may know, the Perl Foundation has accepted my grant proposal to work on implementing the Numeric and Real roles in Rakudo. I’d like to thank the Perl Foundation and Ian Hague for this support, and Jonathan Worthington for his help in putting the proposal together. I’m quite excited to be working on this, and hope to have a solid implementation ready in time for Rakudo *.

I’d like to sketch out my current plan of attack on this grant. I’ve already blogged twice on changes I think the Numeric/Real spec needs. Those ideas still need some more thought, and I’d like to address Larry Wall’s suggestion for ordering Complex numbers too. Glancing over the spec just now, I think there are a few functions that ended up in the wrong role, so I’ll address that in another post soon. These are all intended to be practical changes to make the current roles work better.

I’m planning on diving right in by creating empty roles Numeric and Real and assigning them to the appropriate numeric classes. I think that can work with minimal disruption to Rakudo, and then once tests have been established for this, I will push on and start moving functions to their new locations one-by-one. (If it turns out this does create disruptions for Rakudo, I’ll branch Rakudo to work on it — but right now I expect that won’t be needed.)

As I said in the grant proposal, one thing I think is important is making it as straightforward and simple as possible to create new numeric types. As such, I plan on creating tests for this ability as well, checking how new classes fit in with the existing ones.

Schedule-wise, I expect to only get light work done in the next ten days or so, as we are in the midst of moving. Once we are settled in I plan on seriously tackling the work in an attempt to get significant work on it done by the April 22 Rakudo release.

Series Progress

March 10, 2010

After being stumped by it for a week, tonight I suddenly realized how to I could get the series operator working for the general cases. The trick was to keep an array storing the last N values generated in the series, where N is the number of arguments that the generator function takes. There was a good solid hour of banging my head against the compiler, but finally I got this:

> (1, 1, { $^a + $^b } ... *).batch(20).perl.say
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765)

Here’s the key new code:

    my $arity = any( $next.signature.params>>.slurpy ) ?? Inf !! $next.count;

    gather {
        my @args;
        my $j;
        my $top = $arity min @lhs.elems;
        for 0..^$top -> $i {
            $j = @lhs[$i];
            take $j;
            @args.push($j);
        }

        if !$limit.defined || $limit cmp $j != 0 {
            loop {
                my $i = $next.(|@args);
                my $j = $i;
 
                my $cur_cmp = 1;
                if $limit.defined {
                    $cur_cmp = $limit cmp $j;
                    last if (@args[@args.elems - 1] cmp $limit) == $cur_cmp;
                }
                take $j;
                last if $cur_cmp == 0;

                @args.push($j);
                while @args.elems > $arity {
                    @args.shift;
                }
            }
        }
    }

I’m sure there are still some bugs hiding in there, and I need to throw a bunch more tests at it, but it seems like a fair evening’s work. I would love to get series test suggestions from people, and if you’d like to play with what I’ve got now, you can grab Rakudo’s “series” branch and build it locally.

Further Thoughts On Real

March 5, 2010

So, in my first post on this subject I referred to a lingua franca type RealX for the Real role, without specifying what type RealX should be. There was a very good reason for that: I don’t know what type it should be. But I realized today that might be a feature rather than a bug.

My original assumption, when I first started thinking about these issues, was that RealX obviously had to be Num. That’s what the current source effectively does, after all. And Nums are wonderfully versatile.

For a while, though, I worried about precision. Obviously a FatRat can be much more precise than a Num. After consideration, I’m not sure how worried I am about that — as long as you are not doing abstract math, tolerance is still an issue, no matter what, and using FatRat borders on fooling yourself into not worrying about it.

But there is a much bigger catch to using Num. Once Rakudo has proper bignums, it will be child’s play to create an Int which cannot be converted to a meaningful Num. And that seems like a big problem with the idea of using Num for RealX.

On the other hand, FatRat would be a pretty reasonable RealX, I think, except that it doesn’t exist yet!

What to do? Well, look back at my example code for .RealX back in the previous post:

    multi method RealX() {
         $.cents.RealX / 100.RealX;
    }

What jumps out at me today is that this code works no matter what type RealX is! Basically it’s all a matter of expressing the value of you Real in terms of simpler Real types that already have RealX defined. All you need is for your Perl 6 implementation to define valid RealX methods for Int and Num.

So my proposal is we come up with a better name for the RealX method, and let the type it returns be implementation-defined. With any luck, that would let Rakudo use the practical current solution of Num, and still seamlessly switch over to something like FatRat when it is available.

(BTW, I think if you combine this with a great suggestion from Larry Wall, you also can extend this solution to work for general Numeric types, at least for comparisons. But that’s the subject for another post.)

Profiling versus Benchmarking

March 4, 2010

Dave Rolsky has an excellent post on Benchmarking veruss Profiling. His general point about the importance of profiling is dead on.

I do think benchmarking can be useful, if you’re doing it on a large enough hunk of code to give meaningful results — for instance, we did a lot of benchmarking on Rakudo’s spectest a few weeks ago, and ended up with a very nice speedup.

But I suspect we could have gotten even better results if we’d all been using a good Parrot profiler…

Thoughts on Real

March 3, 2010

I’ve been musing on this for about a month now, meaning to write it up. Since I discussed the basic idea last night on #perl6 with Larry, I guess now is as good a time as any. (Note that Larry did not endorse the idea at the time, but he didn’t shoot it down, either.)

My notion is that the Real role needs to have a lingua franca type, which I’ll call RealX for the moment. If every type that does Real defines a RealX conversion function, then Real can provide sensible default versions of most of the things the Real role needs to do.

For example, last night the issue was comparing an Int and a Rat using cmp. It turns out that in Rakudo, cmp has a case for comparing two Nums (and Int is a type of Num), but Rat was not included. This means it fell back to its default string comparison when passed an Int and a Rat, which is a Bad Thing. For the moment, I solved the issue in the series branch by adding versions of cmp which were Rat-aware.

But ideally, we’d like to be able to compare any two classes which do the Real role, even if those two classes know nothing about each other. Without some notion of a lingua franca for Real, this is a huge headache. With a lingua franca RealX, though, the implementation is trivial:

multi sub infix:<cmp>(Real $a, Real $b) { 
    $a.RealX <=> $b.RealX; 
}

That’s all that’s need to make cmp work correctly for any pair of future Real classes that might be written (assuming they both implement the .RealX conversion).

But the notion doesn’t stop there. It would allow us to provide sensible default versions of most of the methods and subs on Real:

multi sub infix:<+>(Real $a, Real $b) { $a.RealX + $b.RealX; }

Real multi method sin ( Real  $x: TrigBase $base = $?TRIGBASE ) is export {
    $x.RealX.sin($base);
}

etc.

The effect would be twofold. It would allow otherwise unrelated Real types to work together pretty seamlessly. But it would also greatly simplify fully implementing new Real types, as the default versions of many of the Real methods would be all most types would ever need.

An simple example class might look like this:

class Dollar does Real {
    has Int $.cents;
    multi method new(Int $cents is copy) {
        self.bless(*, :cents($cents));
    }
    multi method RealX() {
         $.cents.RealX / 100.RealX;
    }
    multi method perl() {
        "Dollar.new($.cents)";
    }
    multi method succ() {
        Dollar.new($.cents + 100);
    }
}

That’s about all that would be needed to create a fully functional Real type. In practice, of course, you’d probably want to provide a custom .Str method and operators for addition, subtraction, multiplication, and comparison between two Dollars or a Dollar and and an Int.

I’ve purposely left the question of what type RealX should be for a later post, not least because I have no clear winner yet for what the best type would be.

Simple Series

March 2, 2010

Today I created two new test files in t/spec/S03-operator. series-simple.t has some early tests for arity-1 series — that is to say, either series generated from the relationships between the first few elements, or series generated by an arity-1 closure. (The two forms are processed more or less identically — the first form generates an arity-1 closure internally.) The initial tests just compare the first five (or so) elements from an infinite list to what we think they should. After pondering a bit, I did come up with a simple arity-1 closure which is both deterministic and neither arithmetic nor geometric:

> (1, { 1 / ((1 / $_) + 1) } ... *).batch(10).perl.say
(1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9, 1/10)

series-arity0.t only has one series so far:

    my @rolls = ({ (1..6).pick } ... *).batch(20);
    is +@rolls, 20, 'Got the number of rolls we asked for';
    is @rolls.grep(Int).elems, 20, 'all the rolls are Ints';
    is @rolls.grep(1..6).elems, 20, 'all the rolls are in the Range 1..6';

Unfortunately, this case went to the old series operator code, which couldn’t handle it. For the moment, I have crafted a simple alternative which passes this test:

our multi sub infix:<...>(Code $lhs, Whatever) {
    gather {
        loop {
            my $i = $lhs.();
            my $j = $i;
            take $j;
        }
    }
}

So the next step would seem to be to add limiting here. The spec has some specific language on the subject, which I believe must be brand-new: “If any value in the series is eqv to the limit value, the series terminates, including that final limit value. For any value after the first lefthand value, if that value and the previous value fall on opposite sides of the limit, the series terminates without including either the limit value or the value that exceeded the limit.” That should be pretty easily to implement, I think.

One question that popped into my head while I was thinking about this. Is there anything in the current spec that says the values returned by the series must be of the same type? We’re already violating that with most geometric series (they start with an Int, and quickly move to Rats). It seems to me there might be interesting examples where each element might be of a different type. Imagine a arity-0 generator that randomly selects one of a handful of types to return a fresh instance of…

Series Branch

March 2, 2010

After discussing it a bit on #perl6, I decided to create a new branch of Rakudo for work on the series operator. Then I got sidetracked for a while. I just finally got back on track and added it, pushing the same source I included here a few days ago.

Next step, I think, is establishing one or more baby test files for the new code, and then expanding them and the implementation.


Follow

Get every new post delivered to your Inbox.