Friday, November 27, 2009

Wiktory!

Rakudo has been fixed, and the code I've been trying to get work for a month works beautifully now! If I understand the fix properly, the problem was in Rat addition's call to Rat.new. The code was very dumb, so it always tried set the denominator of the new Rat to the product of the denominators of the two numbers being added. Rakudo's Ints are really Int32 right now (more or less), so if that product was equal to or greater than 2**31, it was autoconverted to Num. But the Rat.new which takes positional arguments takes Ints, so it wouldn't dispatch to that. Instead it would try to dispatch to the default autogenerated named argument form of Rat.new. But that only takes the implicit self parameter, and we were sending it self, Int, Num -- thus the "too many positional arguments: 3 passed, 1 expected" error!

Rakudo now autoconverts this case (424/61731 + 832/61731) to Num to avoid the overflow in the denominator. Obviously this is less than ideal -- a denominator of 61731 would work fine for this sum -- but it does work. And how! Gone are the mysterious crashes and errors. With the number of samples cranked up, the curves look beautiful.

Now I just need to do a bit of polishing to the output and figure out how to post it to the blog. I'm definitely feeling I've accomplished something cool in Perl 6....

PS Aha! Preview graphic, I'll explain what it means next time.
NUBS curve and the three polynomials it is built from

Thursday, November 26, 2009

Aha!

A post-Thanksgiving dinner $work debugging session left me with some spare time to poke at my SVG.pm bug: that is, the "too many positional arguments: 3 passed, 1 expected" error I got when I tried to crank up the number of samples I was taking of the curve. I finally added enough says to track the error down to the simplest of operations: @N[$i] += $temp;, where $temp was 0.00686851014887172. This wasn't one of my fancy overloaded operators, it was a basic Perl 6 numeric operator. What could go wrong?

Well, I added a bunch more stuff to the say. And it turns out we are adding two Rats, 424/61731 and 832/61731. What could go wrong?

> say 424/61731 + 832/61731
too many positional arguments: 3 passed, 1 expected

If you look into infix:<+>(Rat, Rat), it just does a naive fractional add, relying on Rat.new to reduce the fraction. The problem here is that means the denominator of our new fraction starts its life as 61731 * 61731.

> say (61731 * 61731) div 246924
No applicable candidates found to dispatch to for 'infix:div'

I'm not sure what the best approach to fixing this is. Obviously I can change my code to do Nums. But I think the first step is to file a Rakudo bug.

Sunday, November 22, 2009

Euler #4

draegtun had a nice post on Project Euler #4. The goal is to find the largest palindromic product of two three digit numbers, and he lists solutions in Clojure and Python and a bunch in Perl 5. There is also a Perl 6 version by trenton in euler_bench on github.

I thought I'd try my hand at a more idiomatic Perl 6 version. Here's my first attempt:
((100..999) X (100..999)).map({$^a * $^b}).grep({$_ eq $_.flip}).max.say

Unfortunately, the usual caveats apply. This blows up the current Rakudo, no doubt because without lazy lists it tries to construct a huge list entirely in memory and then collapses. Rakudo ng has lazy lists, but it doesn't have grep or max yet. So for now, this is purely a hypothetical implementation.

However, with any luck, Rakudo ng will handle this by the end of the week...

Thursday, November 19, 2009

Rakudo ng has a good excuse

jnthn has an interesting post on the progress and problems of Rakudo's ng branch. Looking over some of the spectest files, it seems to me that ng has a good excuse for not handling many spectest files yet. By my rough count, at least 50% of the spectest files have a "rakudo skip" directive in them, ie a test Rakduo cannot handle. Because they have no equivalent "ng skip" directive set up, ng must handle every single case that Rakduo's master branch does to qualify it for inclusion in ng's spectest. If Rakudo master similarly had no skip directive, more than half of the spectest would be eliminated! So it's not surprising that ng is having growing pains on this front.

Personally, I'm quite impressed by the progress on ng. I cannot wait until I can use Perl 6's laziness -- that's a killer feature ng already has that Rakudo master lacks.

Thursday, November 12, 2009

Vector and SVG: Almost There

I noticed from #perl6 that chromatic fixed a memory leak in Parrot recently, and that fix made its way to Rakudo today. I thought, hey, I've been having a bus error. Could that be caused by an out-of-memory condition? So I upgraded Rakudo, and haven't seen the bus error since. (The "too many positional arguments: 3 passed, 1 expected" remain if I crank up the number of samples taken of each curve, but hopefully now I'll be able to track that down without being knocked around by bus errors.)

So, the first thing I did to get SVG working with Nubs and Polynomial was to write a simple class which converts from "normal" XY space to SVG coordinates (which I'm referring to as NM coordinates in this code).
class Vector { ... }
subset Vector2 of Vector where { $^v.Dim == 2 };

class SVGPad
{
has Vector2 $.xy_min;
has Vector2 $.xy_max;
has Vector2 $.mn_min;
has Vector2 $.mn_max;

multi method new(Vector2 $xy_min, Vector2 $xy_max, Vector2 $mn_min, Vector2 $mn_max)
{
self.bless(*, xy_min => $xy_min, xy_max => $xy_max, mn_min => $mn_min, mn_max => $mn_max);
}

multi method xy2mn(Vector2 $xy)
{
my $t = ($xy - $.xy_min).coordinates >>/<< ($.xy_max - $.xy_min).coordinates;
return $.mn_min + Vector.new(($.mn_max - $.mn_min).coordinates >>*<< $t);
}


So the code to use this (for now) is just
class SVGPad { ... }
class Nubs { ... }
class Polynomial { ... }
sub MakePath($curve, Range $range, SVGPad $pad)
{
my @points = RangeOfSize($range.from, $range.to, 10).map({$pad.xy2mn($curve.evaluate($_))});
my $start = @points.shift;
my $path = "M {$start.coordinates[0]} {$start.coordinates[1]}";
for @points -> $v
{
$path ~= " L {$v.coordinates[0]} {$v.coordinates[1]}";
}
return $path;
}

my @control_points = (Vector.new(-1, -2),
Vector.new(1, 0),
Vector.new(1, 1),
Vector.new(0, 1),
Vector.new(1, 2),
Vector.new(1, 2),
Vector.new(1, 2));
my @knots = (-1, -1, -1, -1, 1, 2, 2, 3, 3, 3, 3);
my Nubs $nubs = Nubs.new(3, KnotVector.new(@knots), @control_points);
my Polynomial $poly1 = $nubs.evaluate(0, Polynomial.new(0.0, 1.0));
my Polynomial $poly2 = $nubs.evaluate(1.5, Polynomial.new(0.0, 1.0));
my Polynomial $poly3 = $nubs.evaluate(2.5, Polynomial.new(0.0, 1.0));

my $pad = SVGPad.new(Vector2.new(-2.5, -2.5), Vector2.new(2.5, 2.5),
Vector2.new(0, 0), Vector2.new(400, 400));
my $svg = svg => [
:width(400), :height(400),
path => [
:d(MakePath($nubs, -1..3, $pad)), :stroke("blue"), :stroke-width(2), :fill("none")
],
path => [
:d(MakePath($poly1, -2..2, $pad)), :stroke("green"), :stroke-width(1), :fill("none")
],
path => [
:d(MakePath($poly2, 0..3, $pad)), :stroke("red"), :stroke-width(1), :fill("none")
],
path => [
:d(MakePath($poly3, 1..4, $pad)), :stroke("white"), :stroke-width(1), :fill("none")
],
];

say SVG.serialize($svg);


MakePath is a simple function which takes a "curve" (that is, an object which has an evaluate function which goes from t to x, y), a Perl 6 Range to evaluate it over, and an SVGPad, and returns a SVG path object. Then we set up a fairly simple NUBS curve, use the Nubs to Polynomial version of the evaluate function to generate the corresponding Polynomial for each segment of the curve, and output all four curves to SVG. This is still a crude first approximation, but it does work; if I knew how to include SVG in this post I could show it. Next time, hopefully.

Monday, November 9, 2009

Perl 6 Syntax Highlighting

Saw Syntax::Hightlight::Perl6 mentioned on #perl6 over the weekend. I've never been very happy with using gist to provide snippets, so I thought I'd give it a whirl. I was anticipating a struggle getting it installed from CPAN, but it worked on the first go on my 5.10.0 install.

Here's my source (Perl 5.10) to provide a simple harness for using the module. (Errr... on gist, because it's a Perl 6 syntax highlighter, not a Perl 5 syntax highlighter.)

And here's sample output, used on that spelling corrector script:
use v6;

my %dictionary;
slurp("big.txt").comb(/<alpha>+/).map({%dictionary{$_.lc}++});

sub edits($word) {
my @s = (^$word.chars).map({$word.substr(0, $_), $word.substr($_)});
my @deletes = @s.map(-> $a, $b { $a ~ $b.substr(1); });
my @transposes = @s.map(-> $a, $b { $a ~ $b.substr(0, 2).flip ~ $b.substr(2) if $b.chars > 1 });
my @replaces = @s.map(-> $a, $b {$a ~ ':' ~ $b.substr(1)});
my @inserts = (@s,$word,"").map(-> $a, $b {$a ~ ':' ~ $b});
return (@deletes, @transposes, @replaces, @inserts);
}

sub edit_list_to_regex(@el) {
any(@el.uniq>>.subst(':', '<alpha>', :g).map({ rx/ ^ $_ $ / }));
}

sub correct($word) {
return $word if (%dictionary{$word});
my $regex = edit_list_to_regex(edits($word));
my @candidates = %dictionary.keys.grep($regex);
if @candidates.elems == 0 {
$regex = edit_list_to_regex(edits($word).map({edits($_)}));
@candidates = %dictionary.keys.grep($regex);
}
return @candidates.max({%dictionary{$_} // 0});
}

correct("lary").say

Nice, eh?

I'm still working on the Nubs + SVG stuff. It's so close to doing exactly what I want, but I seem to be overworking Rakudo and causing it to croak randomly...

Updated: Errr... nice except for the part where the long lines get clipped. I need to figure out how to reformat this blog...

Saturday, November 7, 2009

Arrrgh!

Very briefly got out SVG output for a NUBS curve yesterday. Tried to make it a bit nicer looking, and had it promptly dissolve in a hail of bus errors. (And occasional "too many positional arguments: 3 passed, 1 expected" errors that I think must be incorrect.) It's now reminding me of my attempt to write an Euclidean geometry proof generator in Lisp back in '92 -- seemingly minor, innocent changes in the code lead to crazy changes in where it crashes.

Anyone have hints for how to approach debugging this sort of thing in Rakudo? I know it's just part of the frustration expected for an early Perl 6 adopter, but I'd really like to get this thing working...

Wednesday, November 4, 2009

Unsolicited Code Review

I am awed by Carlin's IRC bot in Perl 6 code. It is cool and practical and working, and makes me want to steal code from it and write bots of my own.

At the same time, every time I look at the source, my eyes land on a series of elsif's, and I think "That's so Perl 5!" Here it is:

Starting at the beginning, that first line is a wonderful bit of Perl 6 craziness. $message .= split(' '); is equivalent to $message = $message.split(' ');. What's wacky about that is $message starts off as a string, and ends up an array! The next two lines make the first element of the array $command and the rest of them $params. (If you're wondering about how $message and $params can be arrays, they are array objects in scalar variables. Or something like that, I'm fuzzy on the details, but it clearly works.)

I'd recast all these lines as one simple line harking back to Perl 5, but in a nice Perl 6 way: my ($command, @params) = $message.split(' '); It would perhaps be better to split on \s+, too. And now we can switch $message away from being a rw parameter. (I believe doing that will not mess up the rest of the bot code, but I admit I haven't actually tested it.)

Then the rest of the function is probably better expressed as given / when block. The great thing is all those $command ~~ 'karma' can become just 'karma' if we do given $command.


(Hmmm... actually now that I look at it, how the heck does the Str $message is rw handle being converted to an array of strings in the old code?)

Tuesday, November 3, 2009

NURBS Knot Vector Direction Done RIght

Last post I revealed how I'd gotten myself tangled up when trying to add a "do the right thing" mode to Nubs.evaluate. I'm going to repeat that code here, as I've added one of the Nubs.evaluate functions to the mix.

These functions became overly complex because I tried to overload the KnotBasisDirection enum with an extra layer of meaning. Pulling that extra layer out and rearranging things a tad gives you vastly better code:

Notice that we've eliminated an enum value here, two cases that needed to be checked for, and simplified a third line of code. The "trick" (almost too obvious to be called a trick) is to make the default value of $direction be determined by a called to Direction, rather than calling Direction with a special value that indicates it needs to do work.

It's the best of both worlds. By default, if you don't specify $direction it will do something reasonable. And for those rare weird cases where it is important (discontinuities in the curve), you can specify the direction to use for the evaluation.

Tomorrow: On the road to SVG in Perl 6.

Monday, November 2, 2009

Why Blogging Is Good For Your Programming...

...about half of the time I go to post on something I've considered "done", the process of thinking about it makes me stop and rewrite it.

Case in point: I'm currently working on generating SVG output for Nubs and Polynomial, so that I can draw pretty pictures demonstrating the math. The very first thing I set out to was make sure that both classes had an equivalently called evaluate function, because that's what we'll use to drive the graphing. And that meant adding a bit of logic to the Nubs class.

I don't know if I've properly explained this before or not, but Nubs and Nurbs have two slightly different ways of evaluating them, which I've called Left and Right here. Neither approach can evaluate what you'd like to be the entire range of the curve: if the curve's range is [a, b], then Left works for [a, b), Right for (a, b]. That has all been handled ever since I got the Nubs to Polynomial code working correctly.

That means to have a fully working evaluate function, you need to be able to use a blended approach. So I decided that you should be able set $direction to Left, Right, or Reasonable. That meant I had to special case Reasonable in the KnotVector code, and come up with a function that did a reasonable thing if Reasonable was set. Here's the gist of that code:

Now that I've put these two together like this, the problem here is kind of glaring. KnotBasisDirection has three values, two of which are the only ones that make sense in the first function, and the third of which is the only one that makes sense in the second. I overloaded it like that merely so KnotBasisDirection could take Reasonable as a default value. Stupid.

So I had written that code and tested it and gone on to the next segment of code, and it wasn't until I started thinking about how to blog the code that I realized it was stupid and needed to be rewritten. Yay blogging!

Tomorrow: The corrected code.

Edited to add: I forgot to say "Perl 6" in this post, which is needed to make it show up in the Ironman feed, IME. (Well, just Perl would do, but I prefer to say Perl 6.)

Sunday, November 1, 2009

Spelling Corrector, Broken Unicode Regex Edition

I'm throwing this out there in hopes that wiser Perl 6 heads can help me sort out what to do with it. As I recounted two posts ago, it occurred to me that the spelling corrector could properly support Unicode if instead of the list of letter combinations you might have meant, it generated a list of regexes for them. This drastically cuts down on the combinatorial explosion from calling the edit routine twice and makes the script handle Unicode properly. On the downside, it is likely to be a good bit slower.

This script implements it. Unfortunately, Rakudo does not yet support variable interpolation in strings, so I can't test the script. Also I'm suspicious I have mucked up the combination of any and grep, but it's hard to be sure without testing the script.


Anyway, for those of you keeping score at home, Norvig's original Python script does this task in 21 lines of code. This quasi-correct Perl 6 version adds full Unicode support with just an additional 3 lines of code, for 24 total. And that's counting 4 lines which are just }, and the semi-optional use v6; line as well. Assuming fixing the issues don't require additional lines, this looks like a clear win for Perl 6. And I'm quite sure this code can be made a good bit better and clearer...