Archive for April, 2010

Idioms

April 30, 2010

I’ve contrived to do a good bit of $work programming in Perl 6 over the last few weeks, and I’ve been forced to develop a few new (or at least, new to me) idioms in the process. In particular, here’s one I mentioned on #perl6:

sub length(@points) {
    [+] (1 ..^ +@points).map({distance(@points[$_], @points[$_ - 1])});
}

Frequently in geometry you have to do something like this, where you have an array of items, and must compare each item in the list to the next. Initially I floundered around with code that looked something like this:

sub length(@points) {
    for @points.keys -> $i {
        next if $i == 0;
        distance(@points[$_], @points[$_ - 1])
    }
}

(Yes, that version doesn’t actually sum the distances, but you get the idea.) This is essentially trying to translate C++ idioms to Perl 6. The version at the top of the page is clearly better, and I was pleased with myself for working it out.

That said, it occurs to me that it would probably be better to do something like this:

sub pair-with-next(Iterable $a-iterable) {
    my $ai = $a-iterable.iterator;
    my $previous = $ai.get;
    return if $previous ~~ EMPTY;
    gather loop {
        my $current = $ai.get;
        last if $current ~~ EMPTY;
        take $previous;
        take $current;
        $previous = $current;
    }
}

(WARNING: This is completely untested code!) With that defined, you’d just say something like

sub length(@points) {
    [+] pair-with-next(@points).map(-> $a, $b {distance($a, $b)});
}

That feels much cleaner to me than the first version, and has the advantage that it can work on iterators as well as Seq/Arrays.

Church Numerals

April 25, 2010

As it is Sunday morning and I am avoiding the children’s musical service, let’s talk about Church Numerals in Perl 6. The basic notion is to represent the natural numbers in the lambda calculus in a simple, straightforward manner. Actually, the Wikipedia definition is probably better than any explaining I could do — if you don’t know them already, go and check that out.

So anyway, I decided to try to port the Haskell implementation to Perl 6. Here’s my first stab at the basic functions:

# church 0 = \f -> \x -> x

multi church(0) {
    -> &f { -> $x { $x } };
}

# church n = \f -> \x -> f (church (n-1) f x)

multi church($n) {
    -> &f { -> $x { &f(church($n - 1)(&f)($x)); } };
}

# unchurch n = n (\x -> x + 1) 0

sub unchurch(&c) {
    &c(-> $x { $x + 1 })(0);
}

> say unchurch(church(0));
0
> say unchurch(church(1));
1
> say unchurch(church(2));
2
> say unchurch(church(11));
11

This is a pretty straightforward translation of the Haskell version, and seems to work okay. Obviously the Perl 6 version is a tad more verbose — Haskell is optimized for this sort of thing, whereas the Perl 6 syntax falls out of the new for loop syntax. (Maybe not quite the best way to say that, but if you did Perl 6 for loops with the Haskell lambda syntax, for loops would be nearly unreadable, IMO.)

Maybe I’m misunderstanding something, but this function, at least as it is in Perl 6, seems like something of a cheat. That is, when you say church(4), you don’t get back the Perl 6 equivalent of f(f(f(f(x)))). Rather, you get f(church(3)(f)(x)).

At least, that’s what I think happens. I have to admit I still find reasoning about lambda functions like this very confusing. And this equally straightforward conversion doesn’t work:

# plus m n = \f -> \x -> m f (n f x)

multi plus(&m, &n) {
    -> &f { -> $x { &m(&f)(&n(&f)($x)) }}
}

> say unchurch(plus(church(2), church(3)));
4
> say unchurch(plus(church(2), church(13)));
14
> say unchurch(plus(church(2), church(1)));
2
> say unchurch(plus(church(2), church(0)));
2

If anyone has a notion what is wrong there, I’d love to hear it. Unfortunately, these functions aren’t the easiest thing in the world to debug, either.

Or wait, maybe they are!

sub church-to-Str(&c) {
    &c(-> $x { "f($x)" })("x");
}

> say church-to-Str(church(3));
f(f(f(x)))
> say church-to-Str(church(1));
f(x)
> say church-to-Str(church(0));
x
> say church-to-Str(plus(church(2), church(1)));
f(f(x))

Okay, that doesn’t offer me any particular insight at the moment, but maybe it will eventually…

Mandelbrot

April 19, 2010

I’ve dragged the Mandelbrot script from day 17 of the Advent calendar kicking and screaming to the current version of Rakudo. The big hurdle turned out to be an under-spec’d and poorly implemented corner of Range. If you specified the size on the command line, then the width / height was a string. And, well:

> say (^"501").eager.perl
(0, 1, 2, 3, 4, 5)

Once I converted width / height to a numeric type, the script worked fine.

Martin Berends wrote a beautiful little Perl 5 script to monitor run time and memory usage on a Linux box, enabling me to do a profile of how Rakudo behaves when you bump up the size of the Mandelbrot set we calculate. There is both good and bad news on this front.

The good news: we would expect that doubling the length of an edge would quadruple the time taken. Because each line of the set is output as we go, we would expect doubling the edge length would memory double the memory required. In both cases, that is exactly what we see, which means there are no unexpected N^2 or worse issues.

The bad news: The code is very slow, and worse, it uses insane amounts of memory. Generating a 1001×1001 Mandelbrot set — an operation that should only use the memory required to store 1001 Complex numbers in an array and 1001 ints in another array — takes 6.4 GB of memory. Obviously that’s not what we’re seeing, as a quick test script I just wrote shows that you can create both those arrays in under 25MB of memory. So something else is eating up memory at a ferocious rate.

Numeric Progress Report

April 18, 2010

Since my last report on the Numeric grant, most of my time has actually gone to moving my family. We are now mostly settled in two hours’ north of where we lived a month ago. In that time I made less progress than I hoped to on Numeric, but now things should be well positioned to make some real progress.

So far I’ve focused on the unpolar methods, the rounding methods, and the trig support methods. The unpolar methods, cis and unpolar, I have moved to Real, both in the spec and in the code. Implemented using the new Bridge method (my current method name for the lingua franca type I was calling RealX in previous posts, not yet specced), cis and unpolar should work for any type that does the Real role and implements a working version of Bridge. Similarly, the rounding methods, ceiling, floor, truncate, and round, are also all implemented generically in Real now. Both ceiling and floor forward to the bridge type versions of those functions, while truncate and round are built on ceiling and floor.

At Moritz’s prodding, I also moved to-radians and from-radians from Any to Numeric, made them public, and specced them. In my experience, if you’re working with trig functions, sooner or later you will need those functions. If we already have to implement them for ourselves, no reason we shouldn’t save every other Perl 6 programmer from having to do the same.

At the moment, there are several Rakudo bugs concerning roles which need to be sorted out before Numeric and Real can be fully implemented. I’m hoping to have time to work on this with Jonathan this week.

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

Permutations

April 16, 2010

Now that we are starting to get settled in to our new house, I’ve been meaning to write a progress report on the Numerics grant. This, however, is not that post. Instead it details a quick side project I’ve just done for $work. I don’t reckon I can bill them for this bit, but at least I can get a post out of it, and it definitely is helping with my debugging.

So, I needed to do permutations for a test. The following code is a pretty straightforward port of one of the solutions from HOP:

sub pattern_to_permutation(@pattern, @items1) { 
    my @items = @items1;
    my @r;
    for @pattern {
        push @r, @items.splice($_, 1);
    } 
    @r; 
}

sub n_to_pat($n is copy, $length) { 
    my @odometer; 
    for 1 .. $length -> $i { 
        unshift @odometer, $n % $i; 
        $n div= $i; 
    } 
    return $n ?? () !! @odometer; 
}

sub permute(@items) { 
    my $n = 0;
    gather loop {
        my @pattern = n_to_pat($n++, +@items);
        last unless ?@pattern;
        take pattern_to_permutation(@pattern, @items); 
    }
}

If you compare it to the original code (which itself is very pretty) on pages 131-134, this version is 14% shorter and I would argue somewhat clearer as well, thanks to the nice features of Perl 6. It also uses Perl 6′s native gather / take construct to make a lazy iterator, rather than needing HOP’s iterator code. (Note that the ugly @items = @items1 hack is a workaround for a Rakudo-bug.)

I am inclined to think that permute might belong in Perl 6′s core. If not, this code shows that it is fairly easy to implement. (That said, I have not come close to exhaustively testing this code.)

Numeric Method Rethinking

April 3, 2010

Just looking over the spec, here are four methods I think might need to relocate. I’m posting this here just to see if anyone objects to me changing the spec.

cis and unpolar are both listed as being in Numeric, but their invocants are specified as being Real. I think they both belong in Real, because conceptually they are for mapping Reals to Complex.

sqrt is listed in Real, but of course there is a version for Complex as well. roots on the other hand, is Numeric. It seems to me conceptually these are basically the same thing. I’m not sure what the right answer is here. I’ve been thinking of Quaternions as my canonical example of a non-Real, non-Complex Numeric type. I believe they have a solid concept of square roots. I don’t know if they have a concept of N-root that corresponds to the roots function.

Anyone else have thoughts on these?

Rakudo Progress

April 3, 2010

I couldn’t be happier with the progress made on Rakudo today. I think we added nearly 2000 passing tests to the test suite — it looks scarily like the April release we might have as many passing tests as “Rakudo Alpha” did when it was retired. (Okay, for the most part I think the new passes are from the hard work of jnthn++, masak++, and moritz++.)

I think a quick look at today’s changes in the reduce metaop [op] help illustrate how wonderfully powerful the current Rakudo is. First, moritz and I took the old reduce method and changed it to this:

our multi sub reducewith(&op, Iterable $an-iterable,
                         :$chaining,
                         :$right-assoc,
                         :$triangle) {
    my $ai = $an-iterable.iterator;
    $ai = $ai.Seq.reverse.iterator if $right-assoc;

    my $result = $ai.get;
    if $result ~~ EMPTY {
        return &op();
    }

    if $chaining {
        my $bool = Bool::True;
        my @r = $bool;
        loop {
            my $next = $ai.get;
            last if $next ~~ EMPTY;
            $bool = $bool && ($right-assoc ?? &op($next, $result) !! &op($result, $next));
            @r.push($bool) if $triangle;
            $result = $next;
        }
        return @r if $triangle;
        return $bool;
    } else {
        my @r = $result;
        loop {
            my $next = $ai.get;
            last if $next ~~ EMPTY;
            $result = $right-assoc ?? &op($next, $result) !! &op($result, $next);
            @r.push($result) if $triangle;
        }
        return @r if $triangle;
    }
    $result;
}

That’s not trivial, but it is very straightforward Perl 6. (I do think it could still use a good code review / refactor.) Then jnthn wired this version into the reduce metaop with a few simple changes to the grammar and actions. (For those of you too lazy too click through, that’s a patch which changed three lines and added three more.)

That may seem simple, but consider that this patch fixes long standing bugs from Rakudo Alpha (heck, even back to Pugs!) and adds significant new functionality Rakudo Alpha never had:

> say 2 ** 3 ** 4
2.41785163922926e+24
> say [**] 2, 3, 4
2.41785163922926e+24
> say ([\**] 2, 3, 4).perl
[4, 81, 2.41785163922926e+24]

Rakudo now makes adding functionality like this downright easy.

Edited to add: mberends++ suggested I should add some more examples, so that inexperienced programmers do not think this is just some fancy way to chain powers. (I used that merely because it is the canonical example of a reduce operation older versions of Perl 6 got wrong.) So without further comment, here are some more examples:

> say [*] 1..10
3628800
> say ([\*] 1..10).perl
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
> say ([=>] 1..10).perl
1 => 2 => 3 => 4 => 5 => 6 => 7 => 8 => 9 => 10
> say ([=>] 1..10).kv.perl
(1, 2 => 3 => 4 => 5 => 6 => 7 => 8 => 9 => 10)
> say ([\~] 'a'..'g').perl
["a", "ab", "abc", "abcd", "abcde", "abcdef", "abcdefg"]
> say ([\R~] 'a'..'g').perl
["a", "ba", "cba", "dcba", "edcba", "fedcba", "gfedcba"]

Dipping My Toe In

April 1, 2010

On Tuesday I went ahead and added the Numeric and Real roles to Rakudo. Initially they only applied to Rat and Complex, but jnthn++ added a patch that allows roles to be added to classes when they are augmented, and now Int and Num also do Real.

I then tried moving the abs method to the Real role, and ran into trouble. Apparently multi methods in roles are NYI in Rakudo, and fail hard. Luckily this was pretty easy to work around in this case, as abs doesn’t really need the multi in the short term. That let me get Real.abs up and running properly. (I might add that Real.abs is a case study in how getting the abstractions right makes the code very simple: it is a one line method that should work for any Real that properly handles the less-than operator and negation.)

The next issue I hit was when I tried to add Numeric.abs as well. Apparently if Real does Numeric, and both have abs methods, Rakudo fails hard. This has also been reported to jnthn, and I hope there will be patch for both these errors in the next few days.

At any rate, I definitely consider this a good start. I think my next step is probably to figure out a better (if still short-term) name than RealX


Follow

Get every new post delivered to your Inbox.