Showing posts with label Vector. Show all posts
Showing posts with label Vector. Show all posts

Monday, May 10, 2010

Arising from Slumber

Sorry for falling off the world of Iron Man; life has been busy.

Seeing the new proto web page got me thinking I should try to bring Vector and ABC forward into the world of the current Rakudo. Okay, make clean and make work fine for Vector. make test fails every test.

So I started in with 01-basics.t. It seems to be having trouble with the custom Unicode operators. Then I remembered seeing something on #perl6 about using our with custom operators. So I added it to both the dot product operators (one of them the Texas version, "dot"). And got the following error:

error:imcc:syntax error, unexpected '\n'
in file 'EVAL_5' line -1061556260

Perl 6 experts, help?

Sunday, March 21, 2010

Apologies and Vector Again

In my last post I griped a bit about the lack of progress on several of the issues that have been bothering me. Well, it turns out there is a sad explanation for why things have been slow. I came into the Perl 6 sphere after the previous cancer bout referred to here, so this was a complete surprise for me. Of course Patrick's wife's health is vastly more important than getting my toy program working. I wish them both all the best.

In the meanwhile, while that stuff hasn't been fixed, there's apparently been a huge wave of progress with the metaops in the last week -- enough so that I thought it might be worth trying Vector again. And, well... It blew up compiling Vector.pm with a pretty obscure error message. Pretty easy to guess the source of the problem, though:


> my @a = 1..3; my @b = 3..5; say @a >>*<< @b
3815
> my @a = 1..3; my @b = 3..5; say @a »*« @b
Confused at line 1, near "say @a \x{c2}\x{bb}*"

So Texas hyper-ops work, but the proper ones do not. Well, that's an easy enough change.

Hmmm... next issue: is also is history. It's augment now. That's easy enough. And then you get Can't augment class Vector without 'use MONKEY_TYPING'. Which is also easy to fix.

Next error, though is

error:imcc:syntax error, unexpected '\n'
in file 'EVAL_5' line 58
Contextual $*PKGDECL not found


Ummm... I've got nothing. Any one have an idea what this might mean?

Wednesday, December 9, 2009

NUBS and Polynomials, with graphic

As has happened before, while putting the finishing touches on the code for this post, I suddenly realized I needed to rewrite the code before I could be happy with it. So this post will be devoid of Perl 6 code, and just discuss what is going on in the (now-improved) graphic.

The basic idea I'm illustrating here is that a NUBS curve is basically a convenient way of merging a series of partial polynomial curves. In this graphic, the NUBS curve is in black. The polynomials are in red, green, and blue.



If you start where the red doesn't overlap the black, and then follow it to the black and follow the black beyond that, you can trace the curve and get an idea of what is going on. Basically, the black NUBS curve follows one section of the red polynomial, then smoothly switches to a section of the green polynomial, and finally switches to a section of the blue polynomial. It is piecewise polynomial, in other words, with smooth transitions. (It is possible to generate unsmooth transitions too with a NUBS, or even out-and-out discontinuities, but generally this is not wanted.)

The other great thing about NUBS is how natural they are to specify, because their control points conform roughly to the shape of the curve, and modifying them changes the curve in a fairly natural fashion. I don't have time to go into great depth here, but here's a quick comparison. First, here's the code to specify the curve in the picture:

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);

Then here's the red polynomial:

(0.194444444444444, 0.111111111111111) x^3
+ (-0.916666666666667, -0.666666666666667) x^2
+ (0.583333333333333, 1.33333333333333) x^1
+ (0.694444444444444, 0.111111111111111) x^0

Actually, that's a fairly clean polynomial in this case, but even so, it's hard to work with. The bit we're interested in is parameterized from -1 to 1, so for instance, to find the starting point we need to evaluate the polynomial at x = -1:

- (0.194444444444444, 0.111111111111111)
+ (-0.916666666666667, -0.666666666666667)
- (0.583333333333333, 1.33333333333333)
+ (0.694444444444444, 0.111111111111111)
= (-1, -2)

Whereas the starting point of the NUBS version is just the first control point.

Ack. I could go on, but I fear I've exhausted the patience of the Perl readers out there. And I feel like I'm constantly butting up against the limits of Rakudo with this project, so I think I'll put it aside for a few months and tackle something else. Maybe try to whip up a grammar for ABC files, or something like that. Then return to Vector when after Rakudo has had a chance to mature a bit more...

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.

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...

Tuesday, October 20, 2009

Polynomial & Vector: Together At Last

After a weekend spent studiously ignoring Perl 6, I've finally dug back in and sorted out the problems in the KnotVector / Nubs implementation. At least, every test is back to passing, and I've added a number of harder tests which pass as well. The good news is I like the code I have now a lot better than the code I thought I was ready to post last time around. (Still needs some work, though, IMO.)

Without further ado, here's the heart of what I've been trying to get at.

multi method Evaluate($t, KnotBasisDirection $direction = Left)
{
my $n0 = $.knot_vector.N0_index($.degree, $t, $direction);
return [+] ($.knot_vector.N_local($n0, $.degree, $t)
>>*<< @.control_points[$n0 .. ($n0 + $.degree)]);
}

multi method Evaluate($base_t, $actual_t, KnotBasisDirection $direction = Left)
{
my $n0 = $.knot_vector.N0_index($.degree, $base_t, $direction);
return [+] ($.knot_vector.N_local($n0, $.degree, $actual_t)
>>*<< @.control_points[$n0 .. ($n0 + $.degree)]);
}

Notice these two routines are exactly the same, except where the second uses $base_t and $actual_t, the first uses just $t both times. This allows us to always set $base_t with an actual number (so that it can be used to calculate $n0), but pass anything that logically works for $actual_t. If $actual_t is a number, then Evaluate will calculate the curve's value at that parameter value. If it is a Polynomial representing a single variable (call it what you will, I keep switching between u, t, and x in my thinking), then Evaluate will return the Polynomial representing the section of the curve specified by $base_t. If (as I keep toying around with), you passed a class representing a closure you can do math on, then you'll get a fancy closure that can evaluate that section of the curve. And so on and so forth. It's not tied to a particular implementation of Polynomial; all that's required is something that can handle a few basic math functions.

Monday, October 12, 2009

Polynomial & Vector: Debugging Update

I've tracked down the next bug mentioned at the end of my last post, and again it comes as a side effect of the hack to make it easier to code Polynomial addition. In that hack, we extend the Polynomial coefficients array with 0. But if the coefficients are Vectors, the actual extension value should be Vector.new(0, 0, 0). Just plain 0 means we eventually try to add 0 to a Vector, and since Vector doesn't support addition with a scalar, it falls back to a normal addition operator, which tries to convert Vector to a Num.

Thoughts: I don't see any obvious way to figure out the correct "zero" to extend the coefficients with. Nor do I see any obvious way to allow you to add 0 to a Vector. (At least without opening up general vector plus scalar math, which is a bad idea IMO.)

It also suggests that it may be a very good idea to go beyond implementing the operators that work to implement dying versions of the operators that shouldn't be allowed, because allowing Perl 6 to fall back to its own operators will produce less useful error messages. (Or worse, they might even "work".)

I can see one more potential error like this lurking in the Polynomial.prefix<-> code...

Sunday, October 11, 2009

Polynomial & Vector: Debugging

So, I was just going to post on working around the bug mentioned in my last post, when I noticed Moritz++ had commented with a suggested debugging approach. And we're off and running!

multi method Num()
{
die "Cannot call Num on Vector!";
}

It's not the most elegant error message, but it will do. Adding that switches from the fairly useless Method 'Num' not found for invocant of class 'Vector'
in Main (file src/gen_setting.pm, line 206)
message to the extremely interesting

Cannot call Num on Vector!
in method Vector::Num (file lib/Vector.pm, line 24)
called from method Polynomial::new (file , line )
called from sub infix:* (file lib/Polynomial.pm, line 106)
called from Main (file , line )

Aha! Not a Rakudo bug at all, this is a legit issue. When I added the fix to remove trailing zero coefficients, I wrote @x[*-1] == 0 to check for them. Odds seem very good that == calls .Num. So... a change to .abs here is probably more realistic, anyway. (Maybe? I need to ponder that.)

Hmmm... that moves the error elsewhere, to (according to the backtrace) infix:+ (file , line ). I need to go to bed now, so the final debugging will have to wait. But at a minimum, Moritz's suggestion of adding a .Num that dies appears to be a valuable Perl 6 debugging trick.

Friday, October 9, 2009

Polynomial & Vector: A Fly in the Ointment

This evening I was building my test case to make sure the Polynomial I am generating from the KnotVector basis actually yields the same results as the standard Nubs. Given an array of polynomials and an array of vectors, I wanted to multiply them with each other and sum the bunch. I wrote my $poly = [+] (@polys >>*<< @control_points);. When I ran it, I got back:

Ambiguous dispatch to multi 'infix:*'. Ambiguous candidates had signatures:
:(Polynomial $a, Any $b)
:(Any $a, Vector $b)

That's a beautiful error message, and completely appropriate. Both functions could do the job, each giving you their own answer. That is, (Polynomial $a, Any $b) where Any is a Vector would generate a Polynomial with Vector coefficients; (Any $a, Vector $b) where Any is a Polynomial would generate a Vector with Polynomial values. Both make sense, but for our purposes the former is probably best.

How to make that happen? The Polynomial and Vector classes are both completely independent of each other. Other than this potential intersection, they don't need to know about each other. After toying around a bit, I believe "is default" on the Polynomial multiply is the way to go.

Unfortunately, that gets me the error Method 'Num' not found for invocant of class 'Vector'. Possibly the problem is nested hyper multiply operators? Even when I map that operation, there are still two nested hyper multiply operators (both Polynomial and Vector multiply have them). Yet once again beautiful Perl 6 runs up against the awkward (and ever-improving) reality of Rakudo.

Tuesday, October 6, 2009

Vector: Quick update

I meant to post on my polynomial trick, which now works, but instead got into a long run of small changes this evening. So let me just say that abs has been moved to the setting, so tonight I wrote Vector.abs, which makes Test.pm's is_approx work to compare two Vectors. It feels like Perl 6 is becoming more useful every day.

I also put in a hack workaround for the rakudobug (reported this evening) turned up in t/05-search.t, which means all the Vector tests pass again.

I'm also starting to ponder using SVG to output some NURBS (well, NUBS for now) curves to provide a graphic illustration of what my new code here is doing...

Saturday, September 19, 2009

NURBS Knot Vectors In Perl 6 (part 3)

Well, instead of being a slick demonstration of how powerful Perl 6 is, it has turned into a slog to find something the current Rakudo is happy with. The beautiful hyper-equation of my last post has turned into a dull and confusing series of little hyperoperations (and one which got expanded because the hyperoperator just wouldn't work).


I think all the bugs I've encountered here have already been reported, but I'm not sure. If anyone has suggestions on how to ably search RT, I'm all ears. My attempts so far have been painfully clumsy, to the point where my inclination is either to not report if I think it's likely to have been reported so far, or just report it without searching.

At any rate, let me finish by quickly sketching out a NUBS (Non-Uniform BSpline) curve class. This isn't quite as powerful a tool as a NURBS (Non-Uniform Rational BSpline), but it's still pretty powerful, and it's dead easy to implement the basic evaluate function with the tools we have so far.


Combined with the Vector class, this allows you to easily define N-dimensional NUBS curves. But we don't force the control points to be Vectors -- you can get a NUBS representation of polynomials over reals or complexes easily using this too, and if you have your own Vector class you'd prefer, that should work too, as long as you have scalar multiplication and vector addition implemented using * and +.

I do have one interesting twist left for another post on the KnotVector class, something I've always wanted to do that wasn't very practical in C++. And then I will work on expanding Nubs, and implmenting a proper Nurbs class, and looking at more complicated structures for each (surfaces, etc).

Tuesday, September 8, 2009

NURBS Knot Vectors In Perl 6 (part 1)

I'm not going to provide a lot of background for the wheres and whys of Non-Uniform Rational B-Spline (NURBS) knot vectors yet. Basically, a NURBS object is one or more knot vectors which define the parametrization and polynomials of the object, along with a bunch of Vectors to define the frame of the shape. I'm planning on spending a couple of posts working on getting a good knot vector class built up.

Confusingly enough, knot vectors have nothing directly to do with the sort of Vector we have been working with so far. From, say, a Perl 6 perspective, it would probably be more correct to call them knot arrays or knot lists. But knot vector is the traditional term, so that is what we will use.

The knot vector is a series of numbers in non-descending order, some of them repeated, that define the parameter range of the NURBS object we are looking at, and where it does interesting things. That is to say, adding a knot to the middle of the knot vector essentially splits one polynomial span the NURBS object is defined over into two joined polynomials. It's a fairly simple basis for a lot of powerful geometry.

Instead of starting by defining a knot vector class which can be the basis for NURBS objects, we're going to start by implementing the definition of the B-spline basis functions directly. (Note that the Wikipedia version there specifies it using different variable names -- our notation comes from The NURBS Book.) This would be horribly inefficient for real-world calculations, but we're just going to use it to establish good tests for our real class when that is ready.

Here's a straight forward implementation of the basis function formulas.



There are two tricky bits here. The first is that the standard definition can result in dividing zero by zero, which is defined to result in zero in this case. To keep the function implementation clean and simple, we define a "O/" operator which implements this exception to the standard rules of division.

The second wrinkle is that the standard definition has one curious blind spot. The equation does not work out when you reach the very last point! That is to say, the B-spline basis defined the standard way on a knot vector whose first value is A and last value is B covers the range [A, B). (Actually, I'm using first and last rather loosely there -- that's only true with the most common kind of knot vectors.) We define a KnotBasisDirection argument to N allows you to switch to the symmetrical definition, which is defined over (A, B]. The two definitions are identical over the interior range (A, B). The KnotBasisDirection enum has two values, Left and Right, corresponding to these choices. That's the first time I've defined an enum in Perl 6, but it seems straightforward enough.

Friday, August 28, 2009

Vector: Well, I thought I was done....

Yesterday, pmichaud++ fixed the operator overloading bug. I can confirm that using this morning's Rakudo build, V+, V-, V*, and V/ can be changed to the more expected +, -, *, and /. I haven't pushed the change to github yet -- I'm not sure what the right policy is in dealing with forcing any potential Vector users to be on the bleeding edge.

Though as nearly as I can tell, today's Rakudo works perfectly on my MacBook -- actually passes all the spectests, unlike the last official release. The only downside is one of the other Vector tests now fails. It's not exactly a crucial test, but it is a puzzling failure to me. I'm trying now to find out whether the test is wrong or something has broken in Rakudo.

The other thing I learned about was class XXXX is also, which allows you to add additional methods to a class. I've used this to resolve Vector's minor DRY issue: now the definition of the dot product operators comes before the definition of Vector.Length, allowing Vector.Length to use dot product internally.

Wednesday, August 26, 2009

Vector: Testing

Our testing logic comes via the Perl 6 Test.pm module. This comes distributed with Rakudo, but initially I cloned it to Vector just to simplify setting up the tests. The magic of Configure.pm handles the path to Rakudo's Test.pm properly, so I've deleted the Vector's local version.

The top of the file sets everything up:

etc. I'm sure there's a better way to define is_approx_vector, but this version works okay. (Actually, if - worked properly for Vector, and we defined abs to be a synonym for Length, I believe Test.pm's is_approx would compare two Vectors quite nicely.) We use test * to declare we have no plan -- that means instead of specifying the number of tests to run, we have to use done_testing at the end of the tests. Then it defines a bunch of Vectors to use in the tests, and we are off and running.

I only use a tiny subset of the functions available in Test.pm. isa_ok let's me test if the type of the supposed Vector objects is actually Vector. is checks its first two parameters for string equality. Absolute equality is a bad idea with floating point numbers, so is_approx checks that the absolute difference between two numbers is less than a small epsilon. My is_approx_vector does the same sort of thing for two Vectors.

dies_ok takes a closure and tests that it dies as expected. For instance, I use this to test that taking the dot product of Vectors of different dimensions fails instead of generating a meaningless result. lives_ok does the opposite, testing that code doesn't die without specifying what it actually does.

Put them together and it's possible to do a decent set of tests. In some cases (like 7D cross product) I had no idea what the correct answer of the operation is (other than just duplicating the formula for it again, but that seems pretty useless), but I did test that the results have the expected properties. Overall at the moment my test suite runs 256 tests, which is a lovely number IMO.

And that's pretty much it for Vector for now. I'm going to tackle doing a few simple projects using it and see what I learn from them. And I promise to revisit Vector when changes to Rakudo make it work better.

Monday, August 24, 2009

Vector: Proper file layout and makefile

In my last post I was worried about how to set up a Configure.pl for Vector. (See the comments of that post.) However, I have been able to piece together how to do it by raiding masak's grampa repo for the appropriate files.

Here's what I did:

1) Moved Vector.pm to a new lib/ directory.
2) Added grampa/lib/Configure.pm to lib/.
3) Added grampa/Configure and grampa/Makefile.in to Vector's root directory.
4) Edited Makefile.in to look for Vector.pm as the source rather than grampa.pm.

Then it's just a matter of the usual:
~/tools/rakudo/perl6 Configure
make
make test

And everything works!

Configure is smart enough to use perl6 to invoke Rakudo if your Perl 6 is set up that way. Mine's not, thus explicitly invoking it in the above. You may have to set the executable bit as well, I'm not sure how to do that in git.

A big hearty round of applause for masak++ and mberends++!

Update: I just realized I got the first step wrong. ./Configure won't do it for me (even now with the executable bit set in git); it needs to be

PERL6LIB=$PERL6LIB:lib ./Configure

so that the Configure.pm library gets picked up properly. Sorry for any difficulties this may have caused people.

Sunday, August 23, 2009

Vector: "Joining the Perl 6 Ecosystem"

After my comment yesterday about setting up a webpage pointing to the active projects coded in Perl 6 out there, the #perl6 channel reminded me about masak's proto. It is an attempt to create a simple CPAN-like tool for Perl 6. I had read about it months ago, run into some sort of difficulty using it, and just forgotten about it. But work has progressed, and masak and a few others are working on making it more powerful actively.

I've decided to try to get Vector on there, and document what I'm doing as I do it. Not that I think Vector is particularly brilliant, or that it should go in the Perl 6 CPAN when there is such a thing. But I hope it is at least both a pretty good example of how to do this sort of thing in Perl 6, and potentially a useful tool someone else could build on.

So I'm looking in the proto PIONEER file. It lists four conventions that need to be followed, the first of which is creating a deps.proto file. Vector doesn't have any dependencies; I'm not sure if having an empty file or no file is a better way of indicating that. I'm guessing an empty file, as that suggests that I have at least considered it. (Or better yet, with a comment indicating there are no dependencies?)

Next is building. Vector doesn't need a build stage, and PIONEER indicates that if there is no Makefile.PL or Configure.pl file, it just assumes the build worked, which sounds perfect for my purposes.

Step three is running tests. If there is a makefile, proto will make test. If there isn't, it will try to run prove recursively on the t/ directory. Assuming it's smart enough to run prove with the system's working Rakudo, this should work just fine with what we already have. Errr, assuming the LIB paths are set up properly.

Which is the last issue, I guess. I've just been running with Vector.pm and Test.pm in the top-level Vector directory, no need for a PERL6LIB environment variable. Will prove test figure out the paths automatically? And if I switch over to that system, should it be lib/Vector.pm or lib/Math/Vector.pm or something like that?

I think my next step is to check in what I've got now, make this post, e-mail a link to it to masak to get his comments, and head off to the pub. I will report on what happens later.

Saturday, August 22, 2009

Random Perl 6 Thoughts

A number of interesting thoughts flitted through my head when I was out walking this morning. (At least, I hope people find them interesting.) I jotted one line down for each when I got home, and now I'm trying to reconstruct them in full.

There are two major components I'd still like to get into Vector. Yesterday I started trying to figure out how to use postcircumfix to allow users to treat a Vector as is it is an array of coordinates. That is to say, instead of $vector.coordinates[1], you'd say $vector[1]. This is definitely supposed to be possible in Perl 6, but I was utterly unable to get it to work in Rakudo. Of course, I don't know that I was using the proper syntax. I definitely know I didn't understand the examples in the spec. (In my defense, there are no examples of how you'd use this feature in practice there.)

Second, I'm still frustrated by the Rakudobug that prevents you from overloading an operator using code that depends on another version of that operator. My solution of just choosing some Unicode character that gave the impression of standard ASCII character I really wanted to use was enough to get me going, but it offends my sense of elegance. I've decided to prefix the proper ASCII operator with "V" (for Vector) instead for now, which strikes me as slightly better, but still falling short of proper Perl 6. (If only I had another day each week so I could spend some time hacking Rakudo itself, going after this bug would be my first priority...)

Moving on to the bigger picture, I got to wondering if it might be worth having a web page that points to the github repos of the various Perl 6 coding projects going on. As much as anything this was prompted by seeing Moritz's cool post on visualizing match objects and not knowing where I could grab his SVG::MatchDumper code. I know it's probably too soon to have a Perl 6 CPAN, but it's never too soon to make it easy for people to find cool Perl 6 code.

That got me thinking about Masak's Druid project, and how cool it would be to write AI players for that. I've always wanted to try my hand at that sort of thing, but except for some brief and fun attempts in college I've never actually gotten around to it. Of course, not having any clue of workable Druid strategies would make this trickier.

Which made me think how fun it would be to have a Risk game in Perl 6, with hot-plug-able AI players so people could pit their code other's code in battle. I'm presuming there's some way to eval a class from a string, passing the result into a harness which controls that class's interaction with the main game structure....

Thursday, August 20, 2009

Vector: Philosophy

I thought I'd go over some of my design decisions for this project. The first, and most obvious, is that I decided to forgo efficiency in terms of scope. I'm not one of those people who say efficiency is not important; in my experience, when doing serious geometric work, code can never be too fast. But by the same token, it will be years before it might even make sense to think about using Perl 6 for serious numerical work. So it makes good sense here to shoot for versatility rather than speed. If for some reason you think it makes sense to have an 13-dimensional vector of complex numbers, Vector can do it.

I've also chosen to let Perl 6 generate errors like mismatched dimensions rather than catching them directly in code. For instance, I've only defined the cross product for 3D and 7D Vectors. If you try to call cross product on vectors of other dimensions, you will get a "No applicable candidates found to dispatch to" error message. Now that I think about this, I'm inclined to think this is the wrong answer. I could provide more awesome error messages without a whole lot more work. I should probably figure out the right way to do that.

There are two closely related classes that frequently go with a Vector class: UnitVector and Point. In Perl 6, UnitVector is a simple matter of saying subset UnitVector of Vector where { (1 - 1e-10) < $^v.Length < (1 + 1e-10) };. (I discussed the implications of doing it this way in my previous post.)

Point is a little more tricky. An N-dimensional point looks pretty much exactly like an N-dimensional vector. The only practical difference I'm aware of is how they handle being transformed. With a point, you factor in the change to the origin of the change of basis matrix. With a vector, you ignore the change to the origin. (There are other type distinctions, like a point subtracted from another point should be a vector, and it doesn't make sense to add two points. But in practice, these distinctions cause problems without any corresponding pluses that I can see.)

Most of the geometry libraries I've worked with ignore this distinction in the type system entirely, just making points and vectors two different names for the same class. My current inclination is to ignore points altogether, making everything a Vector. I think I will have to try implementing some actual code using Vector to see how this works out.

Another issue I'm pondering is Length and LengthSquared. I actually have multiple issues with these functions as implemented, and I haven't worked out what the proper solution is. As currently structured, they are in the wrong spot in the file. Both are most cleanly implemented in terms of dot product. But they are defined before dot product, because they are Vector class members while dot product is an external operator that works on the Vector public interface.

The obvious answer to this is to make Length and LengthSquared regular subs that take Vectors. But that brings on really weird conundrums of object-orientation. The only reason to have a LengthSquared function is that for positive x & y, x < y iff x*x < y*y, so you can save two square root calculations if all you're interested in is the relative lengths of two vectors. That might make sense if you've got an efficient low-level C++ implementation of a 2D vector. It's kind of silly if you're thinking of a more high-level implementation of, say, a 9D vector.

But worse, it actually amounts to exposing the underlying representation of the Vector! It is "an optimization" because calculating the length involves a square root call. But many sensible alternate representations of Vectors (like polar coordinates) will actually store the length directly -- in which case LengthSquared requires more calculations than Length, rather than fewer!

So, those arguments have convinced me to do away with the LengthSquared function altogether. (Not yet reflected in code as I type this.) On the other hand, they suggest to me that Length really should be a Vector member function, because while for this implementation of Vector it can efficiently be a non-member function, for many other implementations that would represent a serious pessimization. (I was going to say that on the other hand Unitize should be external, but there are cases when that would be a pessimization as well. Hmmm.)

As you've probably guessed by now, writing about these things forces me to think about them more deeply!

General: I've updated to the PDX release of Rakudo this morning, and Vector still passes all 204 tests! Though that number is likely to go down when I delete LengthSquared, because I'll need to remove some tests in the process.

Tuesday, August 18, 2009

Vector: Perl 6 is full of awesome

I've made a bunch of small changes since my last post, all of them delightful. First up, I finally switched has $.coordinates to has @.coordinates. This required switching all the usages of coordinates in the class definition. But much to my surprise, it did not require changing any of the usages outside the definition.

That's because the typical usage was something like $a.coordinates. What I realized this morning was that this is not a reference to the $.coordinates class member. Rather, it is a call to an automatically generated .coordinates method, which returns the $.coordinates member. That means switching to @.coordinates just means that .coordinates returns an array rather than a scalar reference to an array. No change at all is needed in how the method is used.

I realize that all the experienced Perl 6 hands just assumed I knew that when I wrote $a.coordinates. But I didn't, and it is a pleasant surprise.

My next discovery plays off of something I worked out days ago, but hadn't realized all the implications of until this morning. If you define operator +, Perl 6 automatically generates operator += for you. Now, presumably it just internally translates $a += $b to $a = $a + $b. This means the behavior of += is very different in C++ and Perl 6.

In C++, if you say a += b, a is still the same object before and after the operation; it just has a different value afterward. In Perl 6, $a actually is a different object after $a += $b. It doesn't even have to have the same type as it did before. Consider these two tests I added this morning:

In the first, $a starts out a Vector and ends up a Num. That's why the second code dies -- $a is declared a Vector.

That, in turn, means that you can declare the internals of a Vector "ro" and still use += on Vector variables. Each Vector is immutable, but a new Vector is created and assigned to the left-hand side.

This is great for obeying the LSP. For instance, if I define a UnitVector to be a Vector where { $v.Length == 1 }, then I can pass a UnitVector to a function written only knowing about the Vector class and it will automatically do the right thing. This is very different from C++, where passing a UnitVector to an algorithm expecting Vector can muddle up the type system.

The += operator itself provides a prime example of this. The += operator I've already (implicitly!) defined for Vector will work perfectly if passed a UnitVector; it will simply convert the first argument from UnitVector to Vector and get on with life. (I suppose if you have explicitly declared the first argument to be of type UnitVector it will signal an error.) In C++, if you didn't overload += especially for UnitVectors it would break the type invariant for the UnitVector.

One final bit of Perl 6 operator magic:

This defines a new parenthetical operator to calculate the length of a Vector, mimicking the standard mathematical notation. Not much more to say about that than "Awesome!" (Well, I haven't figured out a Texas equivalent yet -- but I've not worried because there is also the Length method.)

Also, I've figured out how to easily handle the Unicode dot and cross operators in TextMate. I programmed tab triggers for each (in the Perl environment) so that if you type, say, "dot" and hit tab, it substitutes the Unicode symbol for the word. It is the best of both worlds: easy to type and still pretty.

Monday, August 17, 2009

Vector: Str and perl

Str and perl are two methods that I had to poke around a bit to figure out that I needed them, and how to define them, but are perfectly simple when defined. I started simply looking for how to overload say for Vector. I'd poked around for this a bit when I realized it was a perfectly stupid idea. I mean, that might be great for saying a single Vector, but it would be terrible for something like say "$c is the cross product of $a and $b".

Clearly, what I really wanted to do was overload ~ for Vector. I don't recall now whether I found what I was looking for in the specs or the Setting. Either way, here is the simple way to do this in the Vector class definition.

I don't quite understand the why our is needed here. I'm guessing it has something to do with explicitly declaring the return type (Str). Past that, the code is perfectly straightforward and elegant.

I spent some time thinking about making a new method that took a string representation of a Vector and parsed it, sort of a reverse of the Str method. But it was clear it could get very tricky with more complicated vectors -- for instance, a Vector of Vectors.

Then I realized that Perl 6 had a mechanism for outputting objects in a fashion they could be eval'ed in again: perl. Unfortunately, the default perl function just returns "Vector.new()" when called on a Vector object. According to #perl, this is intended to automatically do the right thing for cases like this sometime in the future. In the mean time, it is easily overloaded to something that works using the above code.