Rethinking Matixy Assignment

Variadic output arguments have been partially implemented in Matrixy in the "varargout" branch, but I'm starting to hit a wall with the current implementation. At the very least, it's not a clean or well-designed implementation of it. The parser is using all sorts of weird global variables and there are too many special cases to deal with.

A big portion of the issue is the problem with ambiguity between a matrix index and a function call. This statement can be either a call to function foo, or an index into matrix foo:

a = foo(b, c);

And, functions (but not matrices) can return multiple values:

[a, b(3), c(4, 5)] = foo(x, y);

So when we parse the first set of values, we don't know until we've parsed the equals-sign if it's this:

[a, b(3), c(4, 5)];

which is shorthand for this:

ans = [a, b(3), c(4, 5)];

But, I've harped on these problems all before, and I won't dig into it in depth here. What I think we need to do in Matrixy to bring some sanity back to the parser, is to create a matrix reference object that can be used to retrieve or modify values in a matrix object comprised of a combination of constant and variable references. So this line:

x = [a, b(3), c(4, 5)];

becomes this PIR code sequence:

$P0 = !index_ref(a)
$P1 = !index_ref(b, 3)
$P2 = !index_ref(c, 4, 5)
$P3 = !build_literal_matrix($P0, $P1, $P2)
$P4 = !index_ref(x)
$P3.extract_as_rvalue($P4)

And this:

[a, b(3), c(4, 5)] = foo()

Becomes this:

$P0 = !index_ref(a)
$P1 = !index_ref(b, 3)
$P2 = !index_ref(c, 4, 5)
$P3 = !matrix_accessor($P0, $P1, $P2)
$P4 = !index_ref(foo)
$P3.assign_as_lvalue($P4)

Of course these are just first drafts of the call sequences and the method names, but it does illustrate the general idea. This is going to add a pretty significant number of function calls and created PMCs to the normal control flow too, but I can worry about optimizing things once they all work.

When we attempt to pull a value from a reference object, we'll determine whether it's a matrix or a function call and handle it accordingly. If we're pushing a value to it as in an assignment, we always just assume it's a matrix. M, to the best of my knowledge, doesn't support L-value function calls.

Soon I'm going to merge the varargout branch where I have been working on variadic output arguments. Even though I know this isn't the approach I will be taking in the long term this branch does include a number of important regression tests and other refactors and enhancements that I don't want to lose. I might not end up getting to this issue until after Parrot's 2.0 release, however.

Matrixy Progress

I've been doing a lot of work on Matrixy lately. I find that recently I've been able to do a lot on that project in small bits, which is great when I want to touch it during a lunch break or between baby maintenance. I've certainly been able to work more on Matrixy this week then I have been able to write blog posts, for instance. In recent days I've:

1. Done major cleanup and expansion of the test suite
2. Added a bunch of builtins, including some new parrot-primitive functions that will allow me to write more functions in M and to possibly migrate some PIR-based builtins to M.
   
3. Refactored and cleaned up dispatch
4. Added Cell Array support
5. Added proper nargin/varargin support
6. Created a new branch to begin adding proper nargout/varargout support

It's the last item on the list that's been giving me a bunch of trouble recently, and the inherent difficulty of the task is probably the reason why I haven't gotten it working prior to now. The work I have been doing so far is mostly hackery, trying to add nargout and varargout without having to rewrite the entire grammar and dispatching mechanism . Of course, in the long run I am going to have to rewrite these things, but I'm just not ready to do that yet. I would rather have a proof of concept and some passing tests than nothing.

The problem with dispatch, or anything in M, is that everything is ambiguous until runtime. The same syntax, "X(1)" could be used to refer to the first element of the matrix X, the first element of the cell array X, or a call to the function X with an argument "1". This is further complicated by the fact that variables overshadow functions of the same name, but do not overwrite them completely. If we have a variable and a function named X, we can still access the function version using the feval builtin. In M we can also call functions without using parenthesis at all, so it isn't only the case that postfix parenthesis create ambiguity, almost every single identifier lookup requires a runtime check.

I've talked about all these syntax issues before, and won't dwell on them now. There are also semantic issues that need attention. Let's look at the case of nargout for instance.

function x, y, z = getcoords()
   ...
endfunction

[x, y, z, w] = getcoords()

In this code snippet above, the "getcoords" function is called with 4 output arguments, but the definition of that function only provides for three. If "getcoords" doesn't explicitly check the number of outputs expected and throw an error, this assignment will proceed without a problem. x, y, and z will get the expected values in the caller context, and the w variable will simply be left undefined.

So what we have is really a fundamental disconnect between caller and callee. The callee can see how it was called by checking nargin and nargout variables, and can choose to error if those numbers do not match what it wants. A function can return a different number of values then the caller expects, too. So if I just did a call to:

getcoords();
disp(ans);

nargout here would be 0, but the function could still return 3 values which would be stored in the global default variable "ans". Yesterday I started a refactor to make this possible, by trying to break assignments up into two parts: The callee returning an arbitrary array of values and the caller having to explicitly unpack those values. It's gotten me through a number of important test cases, although it is obviously not a great or pretty solution.

[a, b, c];

is an R-value, and the generated matrix is stored in the default variable "ans". However,

[a, b, c] = foo()

is obviously an L-value, and I need to be doing some bookkeeping to keep track of the number of arguments so I can populate nargout in the call to foo (if foo is a function call, of course). So I create a global variable to store the L-values in the assignment so when I generate the actual assignment call I have access to that number. One problem I ran into yesterday though is that when a rule fails and we have to backtrack, we end up with these global variables in an unconsistent state. So the call:

foo();

doesn't have any L-values, and when I parse the function call I can't expect the global variable to exist. Likewise, when I parse:

[a, b, c];

I need to keep count of the L-values, even though this isn't an assignment. So yesterday I ran into the problem:

[a, b, c];
foo();     # Thinks nargout = 3

Fun, eh?

I'm not even entirely certain how I'm going to do all this right. Do I create a custom CallSignature subclass, and handle argument passing myself? This has the nice benefit that I can almost always treat "x(1)" as a function call, whether it's an actual function or an internal indexing function. The more I can abstract away the differences, the better. The "almost" in the previous sentence of course refers to "x(1) =" L-values, which would need to be indexed a little differently from a normal function call. And since I need to be manipulating indices before passing them to the PMC, I need to be calling a function to handle indexed assignments anyway.

It's all going to be a little tricky to get past this roadblock and to do it in a way that I find acceptable. However, Matrixy has good momentum right now and has a lot of great features already, so I'm hoping I don't get mired down for too long.

Matrixy Passing (Almost) All Tests

I went on a bit of a marathon today, and I'm pleased to announce that the pla_integration branch of Matrixy is passing almost all tests. All the tests that it is failing are relying on Complex number handling, which Parrot-Linear-Algebra doesn't support yet.

This is pretty big vindication that what I have been trying to do with Parrot-Linear-Algebra is going well: Despite the project being relatively young, the various matrix types provided by that project are turning out to be very stable and robust. The NumMatrix2D type is the most used and the most feature-full right now, but relative newcomer CharMatrix2D is proving to be very powerful and useful as well.

PMCMatrix2D is mostly unused for now. However, I do intend to use that in the near future to implement Cell Arrays in Matrixy. This is a feature that we had no good way of implementing in the old Matrixy, but in the new system it looks like a very natural extension of the other things I've been doing.

With Cell Arrays, it should be possible, if not easy, to properly implement variadic input and output function arguments. This is a huge issue that's preventing Matrixy's library of builtin functions from being accurate to the behavior provided by Octave or MATLAB. It's also preventing us from writing more functions directly in M, instead of in PIR. Even if we have to descend into inline PIR for some things, it would be great if we could write more code in M.

Starting tomorrow I'm going to try and add some preliminary Complex number support to Parrot-Linear-Algebra, and try to get the remaining Matrixy tests passing with it. With that we'll be back to where we were before the projects were split, and new development can begin in earnest.

The Path to Matrixy

I've spent a little bit of time in the last week working on the pla_integration branch for Matrixy. The goal of that branch is to update Matrixy to use Parrot-Linear-Algebra as an external dependency, and to use its matrix types natively instead of the ad hoc home-brewed aggregate types I had been using previously. In short, I'm doing things the way they should have been done in the first place.

As of Sunday evening, the branch could build, run, and execute the test suite. There are several tests that are failing still (many of which are to be expected), but a good number that are successfully passing too, which is good.

String handling is one area where I was expecting some serious regressions, and was not surprised in that regard. M uses a very idiosyncratic handling as I've mentioned before, and all tests that are relying on complicated string behavior are failing miserably. In response to this, last night I created a new matrix type in the Parrot-Linear-Algebra project: a 2D character matrix type that will be used to implement Matrixy's string handling. My task now is to improve this new matrix type (including adding a test suite for it) and integrating it into Matrixy. I started some of that last night but haven't pushed any of my work to the public repo yet.

Another thing I added last night was the "matrix" role. Any of the matrix types in Parrot-Linear-Algebra will now respond positively to a "does 'matrix'" query. An object that fulfills the matrix role will have the following properties:

1. Contains a number of elements arranged in a rectangular NxM grid
2. Elements can be accessed linearly using a single integer index (behavior varies by type, but it is always possible)
3. Elements can be accessed by X,Y 2-ary coordinates to retrieve a value
4. Matrices can grow automatically to accommodate newly inserted values
5. Matrices should stringify in such a way where each row of the matrix will be on it's own line (rows separated by newlines). The formatting of each individual row is dependent on the type of the matrix.

With a nice standard interface like this, these matrix types should be consistently usable from HLLs, and I know Matrixy is going to be making aggressive use of these features to implement even it's most basic behaviors. I may try to add new requirements to this list, specifically there are some methods that I would like every matrix type to have (is_scalar(), is_empty(), etc.), and maybe a few other behaviors that should become standard between all our types. I'm starting to think that a templating system will become a necessity to prevent us from needing to rewrite similar algorithms for what could become dozens of matrix and vector types. The improved grammar support in NQP-RX may be the catalyst that makes these changes possible. It's another task for another day.

Speaking of tasks, on the near-term TODO list I plan to add specialized vector types to Parrot-Linear-Algebra, add tests for the new matrix and vector types, beef up the CharMatrix2D type to handle the string operations that Matrixy needs, and continue fixing the pla_integration branch for Matrixy to pass more of it's tests. On top of all that, there's a testing hackathon this weekend that I want to participate in, some work for Wittie that I need to finish, and possibly having a baby. Could turn out to be the very busy next few days for me!

String Handling in M

I've been doing a lot of work recently on the pla_integration branch for Matrixy. The goals of this branch (which is likely to just become the new master) are to integrate Matrixy with the Parrot-Linear-Algebra project, and use it's new matrix types instead of home-brewing our own types.

I'm already seeing some good results: I've got lots of important tests passing and performance seems to be nice (though startup time and PCT processing time overall are worse, but that's another issue for another day). However, the one area where I am still having a lot of problems is in fixing the handling of strings.

Strings in M are very idiosyncratic. This is especially true when we start mixing strings with matrices. One good thing I am finding is that the various idiosyncracies and even--dare I say--inconsistencies help give a certain insight into the way Octave does it's parsing. We should be able to take those insights and try to produce a sane and compliant parser for Matrixy. Best way to proceed is through a series of examples. As a reminder about M, lines not terminated by a semicolon print their results to the screen, and the % sign is the comment delimiter. I'll show the output of each line in comments below it:

x = ["ok";"w00t"]
% ok
% w00t

Here is a very simple case. We have a matrix with two rows, each row contains a string. When printed, each row of the matrix is printed on a newline. One thing to notice and remember for later is that the strings on these two lines are not the same lengths.

x = ["ok"; 65, 66]
% ok
% AB

M has a lot of close ties to Fortran, which is what the original version of Matlab was developed in. In later times I believe it was ported to C and then to Java, taking characteristics of each implementation language along the way. In any case, there are some very obvious influences from Fortan and C on the M language. One such influence is that strings are simply arrays of characters. When we are printing out a matrix that has some kind of internal "I am a matrix of strings" flag set, integer values are converted to their ASCII equivalents and treated as characters.

x = ["ok"; 65, 66, 67]
% "Error: number of columns must match (3 != 2)"

Here is a slightly strange result. In the first example I showed, we can have a matrix where the string literals on each row are different lengths. In the second example I showed that we can treat integers as characters in forming string literals inside a matrix. However here we see a surprising result: If we try to make a row of all integers and a row that is a string, they must have the same length.

x = ["A", 66; "C", 67]
% AB
% CD

Mixing integers and strings on a single row works.

x = ["A", 66; "C", 68, 69]
% "Error: number of columns must match (3 != 2)"

...but the rows must be the same lengths when we build them like this.

x = ["ABC"; "D"; "E", 70]
% "Error: number of columns must match (1 != 3)

And we can see from this error message that suddenly line 2 ("D") throws an error because it's not the same length as line 1 ("ABC"), even though this would have worked if we hadn't included line 3 ("E", 70). As a more complicated example, and to clarify how strings of uneven lengths are stored, see this example:

x = ["ABCDE"; "F"];
x(2, 5) = "G";
x
% ABCDE
% F   G

So we can see from here that strings aren't inserted into matrices with arbitrary lengths, they are padded out to be the same length with spaces. Finally:

foo = "Awesome";
x = [foo; 65]
% "Error: number of columns must mach (1 != 7)

So we can see that the checks for these matrix sizings are happening at runtime, not at parse time. (This small example could be explained away by aggressive constant propagation in the optimizer, but I will assure the reader that this holds true in "real" cases as well).

We can divine a few parser rules from all this:

1. If we have strings in the matrix, we flag the matrix as being a stringified one and print it as a string. This means converting any integers in the matrix to characters in the row-string.
   
2. If we have integer or number literals in the matrix, even if they can be converted to ASCII characters, the rows of the matrix must have the same lengths.
3. Judging from the third-to-last example, they appear to do these length checks and string checks on the matrix after parsing is completed (otherwise, why would it have errored on lines 1 and 2 not being equal length when it didn't see the integer until line 3?).
4. These checks happen at runtime.
   

What I think we need to do for parsing these literals is the following:

1. We parse each row separately, and pass them to a row object constructor at runtime.
2. If the row contains any strings, set the "has strings" flag. If the row contains any numbers, set the "has numbers" flag.
   
3. We pass all row objects to a matrix constructor
4. If all rows are strings, and no rows have numbers, pad the strings with spaces and insert them into a character matrix (like a normal matrix, but defaults to printing like an array of ASCII characters). Done.
   
5. Check row lengths. If all are not the same at this point, throw an error. Done.
   
6. If any rows contain strings, create a new character matrix object and populate it with all data, no padding. Done.
   
7. If rows only contain numbers, create a normal NumMatrix2D PMC, populate it and return that. Done.
   

As an aside, there's another example that is worth showing:

x = ["ABC"; 68.1, 69.2, 70.3]
% "ABC"
% "DEF"
x(2, 2)
% ans = E

We see here that floating-point numbers are converted to ASCII integers when inserted into the character matrix, and that rounding sticks: you can't get the original non-integral value back after the conversion. So all my ideas above with the character matrix type should work with this.

So that's what I think we're going to have to do if we want to faithfully reproduce the behavior of Octave. This system will make matrix literals in the code a bit of a performance drain, but that's what we're going to have to live with for now.

Proper Matrices in Matrixy

I started a branch in Matrixy (it's own little adventure!) to start working on improved integration with parrot-linear-algebra. Matrixy currently uses nested ResizablePMCArray PMCs to implement matrices. This carries a few problems with it and is a huge performance bottleneck.

When I started work on Matrixy I had in mind to create classes for the fundamental things like Matrices and Vectors, but also the other types like cell arrays and structs. My work at the time was very naive, and I expected to be implementing all the various numerical algorithms myself. It wasn't until Blair mentioned it to me that I really thought about using an optimized library like BLAS, although that brings with it it's own hardships. Libraries like BLAS saves us the effort of implementing all the operations from scratch, but requires that we be able to write glue code for interfacing with the library functions. Tradeoffs.

Nested RPAs were easy because they were a pure-PIR solution that could be made to work quickly. The PMC manages it's own memory, so our only job was to manage the individual arrays. There is a certain amount of effort involved in keeping the matrix square when we resize (very expensive) and a certain amount of effort involved in marshalling data into BLAS API functions (very expensive), but we were able to get a lot of development done using the quick prototype.

in Parrot-Linear-Algebra we're providing PMC types that store data in a low-level C data buffer, in a format that is amenable for use directly in BLAS. Also, since it's a square buffer by default, we don't have to do anything special to keep it square on resize: We create a new buffer of the necessary size and block-copy items from the smaller old buffer to the larger new buffer. This might not be the most efficient way to handle it, but if we consider that matrices can be preallocated quickly, it's not going to be a huge bottleneck and a good developer can avoid it almost entirely. The new PMC type also provides all the necessary VTABLEs, so we can interact with it in a very natural way from PIR. Code that we were executing in large PIR functions before can now be performed using single opcodes, or single method calls.

So the general plan for the branch is to change Matrixy to have a strict dependency on parrot-linear-algebra. I will cut out all the code that manages custom RPA types and replace it with (hopefully smaller and better) code to interact with NumMatrix2D PMCs instead. Along the way, I'll be adding METHODs to the PMC type to perform the interactions with BLAS that we were previously doing in PIR. This should provide us a significant speedup in most cases, clean up the code significantly, and get us on the right path for future developments. I've already added several METHODs and VTABLEs for various purposes: clone, transpose, attribute access, fill, etc. These all need testing and improving of course, but I've been on too much of a roll with Matrixy to do these things.

One cool method that I added last night was an "iterate function" method. It takes a Sub object, which it invokes on every element in the matrix and replaces the current value with the result of the Sub. Since Matrixy has a lot of functions that act independently on every item in the array, this was a pretty natural thing to add. Also, since we're doing this in C now instead of PIR, we open up all sorts of possibilities like automatically threading large requests for improved performance. I think Parrot's threads system has some work to do yet before this becomes a viable optimization, but it's still interesting to think about.

Here's a PIR example of iterating a function:

.sub main :main
 $P0 = new ['NumMatrix2D']
 .const Sub helper = "add_to_each"
 $P0[1;1] = 4
 $P0[0;1] = 3
 $P0[1;0] = 2
 $P0[0;0] = 1
 # 1 2
 # 3 4
 $P0.'iterate_function_inplace'(helper, 2)
 # 3 4
 # 5 6
 $P0.'iterate_function_inplace'(helper, 5)
 # 8  9
 # 10 11
.end

.sub 'add_to_each'
 .param pmc matrix
 .param num value
 .param num to_add
 $N0 = value + to_add
 .return($N0)
.end

I haven't done any testing on this yet, but this is what it will look like when it's all working properly. There are a lot of functions that act item-wise on each element in a matrix, and this little helper routine is going to make those all much easier and cleaner to implement.

Matrices

Yesterday I put together a prototype of a matrix PMC for the parrot-linear-algebra project. Today, it's building and can be used in Parrot, thanks to efforts from darbelo and desertm4x. It doesn't do much yet, since we haven't implemented many bindings for the CBLAS library. But it's a good way to store a 2-dimensional matrix of floating point numbers. The new PMC type, which I hope is only the first of many related PMCs, is called NumMatrix2D.

Linear algebra is a big deal in the world of computing. When people talk about high performance computing, mathematical or scientific simulations, or other related topics, they're generally talking about applications involving linear algebra. Computer hardware optimizes for certain matrix and vector operations, and highly-tuned software libraries implement a wide set of other operations. Linear Algebra operations can be used to implement large sets of numerical algorithms. But, each matrix operation is composed of large numbers of scalar operations. For this reason, if we want to implement a linear algebra interface to Parrot, performance of the various primitive operations is critical.

Matrixy currently uses nested ResizablePMCArray PMCs to implement it's matrices. This is problematic for a number of reasons, and performance suffers significantly because of it. What I want to do soon, now that the NumMatrix2D builds, is to use it in Matrixy as the fundamental matrix data type. This should drastically improve performance and help to get rid of a lot of unnecessary code.

Parrot-Linear-Algebra has a few things that it needs now. I'll discuss each separately.

Be installable

We need Parrot-Linear-Algebra to be installable so we can use the NumMatrix2D PMC type in other languages and projects easily. I tried a few naive things today, but obviously don't know enough about even my own platform to make this happen, much less to make it happen in many target platforms.

Test Suite

Now that we have something to test, we need to write a test suite. We want lots of tests so that we can keep track of regressions for NumMatrix2D, and maybe even do a little bit of proper Test-Driven-Development of new features.

In general, I would really like to have the test harness be not written in Perl5. I would like to avoid Perl5 as a dependency throughout this project, and I would like to try to only rely on Parrot and languages which run on Parrot. To my knowledge, nobody has yet written a complete test harness that runs on top of Parrot, so that may have to be a new project I start work on soon.

[Update 27 Oct 2009: I've been informed by dukeleto that Plumage in fact has a test harness written in pure NQP. I plan to "borrow" that later for both Matrixy and Parrot-Linear-Algebra.]

More BLAS Bindings

The goal for Parrot-Linear-Algebra, at least as of the last "meeting" I had with some of the other committers, was that we were going to try to build BLAS bindings into the NumMatrix2D PMC itself, and add separate NCI bindings for other libraries (LAPACK, etc).

Some of the API functions will fit neatly into VTABLEs: add, substract, multiply. Others will need to be made into METHODs instead. This gives us lots of flexibility while keeping the most common operations fast.

BLAS Detection

At the moment, we don't do any automatic detection of BLAS or one of it's various implementations. What we need to do is write a series of configure probes that will look for various implementations and generate the necessary interfaces automatically. We would like to support CBLAS, ATLAS, and GSL directly, if possible. Other implementations (and believe me, there are many) would be great too. Since BLAS is critical for high-performance computing and computing benchmarks, there are many implementations which are tuned and optimized for individual processor types. We want to support the common types initially, but provide enough flexibility that people could implement new probes for other similar libraries as needed.

Road Ahead

There is obviously a lot of work left to do, but we've made the important first few steps already. Highly performant matrix types and bindings to optimized linear algebra libraries will open the door for all sorts of high-performance computing applications to start targetting Parrot. It will also, of course, remove some roadblocks from Matrixy development. Anybody who's interested in joining the effort should feel free to get in touch here, via email, or on IRC.

Matrixy and Parrot-Linear-Algebra

I wrote a post about the current state of Matrixy and my ongoing plans for its development. The feedback was swift and very positive. I've now moved Matrixy to Github. In addition I separated out the CLAPACK and CBLAS library binding stuff (what little there was) into another repo, also on Github. The library package will be known by the absolutely uncreative name "parrot-linear-algebra". I might rename it if somebody comes up with something very clever, but a nice simple utilitarian name suits the project just fine for now. It is very simple and doesn't actually "do" anything yet, so best to worry about creative branding later when there is something to show.

I was also able to find some interested participants, and have handed out some commit bits to dukeleto, darbelo, and desertm4x to help work on these things. All of them have shown a lot of interest in the projects, and I'm hoping we can attract a few more people as well. Matrixy is interesting for people who have ever used M before and would like to use it to write programs on top of Parrot. This is a relatively limited set, as I've mentioned before M is a bit of a niche language. However, the linear algebra package has huge potential to affect a number of people, because it could be integrated into all sorts of other libraries and compiler projects. Of course, the linear algebra package is much less mature then Matrixy is becoming, so we need a lot of help with that.

Parrot-Linear-Algebra Tasklist

These are the things that Parrot-Linear-Algebra needs in the short term:

1. Get suitable licensing information in place, README, and other metadata. I think I like Artistic2.0 for the license, but I could be persuaded to use an alternative pretty easily.
   
2. CLAPACK and CBLAS API functions have a lot of very exotic function signatures. We need to either add permanent NCI bindings to Parrot to handle these or (preferably) give Parrot a proper NCI frame builder to build these on all systems.
3. We need to write wrappers for all the functions, and there are a LOT of functions to wrap. A nice lazy Wrapper-Builder routine, or some kind of PMC type that could rapidly generate NCI PMCs on demand and cache them would be a nice addition, because it would prevent us from having to create tons of unused and unneeded bindings up front.
   
4. We need a proper 2-D matrix data type PMC that will be able to interface quickly with the library wrappers. This is probably the single biggest piece of primary development that we need, at least initially.
   

Matrixy Tasklist

Here is a list of things that I think Matrixy really needs in the near-term:

1. It needs to build against an installed Parrot. darbelo was looking at this problem last night and the prognosis is not good: Configure.pl and Makefile both probably need to be completely rewritten. Update: At the time of publishing, darbelo has already fixed this. Matrixy should now build against an installed Parrot at version 1.6.0 or higher.
2. Set up Matrixy to require the Parrot-Linear-Algebra package. We should be able to detect whether the library exists and (if we have git installed) grab the latest copy from Github.
3. Set up all the fancy-pants stuff that Rakudo has for requiring a specific version of Parrot (and also Parrot-Linear-Algebra), and being able to check out and build that version if necessary.

Once we have these things, primary feature development will be able to continue like normal and we'll be able to start adding all the missing syntax and cool new stuff that Matrixy really needs.

So Matrixy development will hopefully be getting back into full swing, and I'll be able to add some of the remaining syntax items (variadic input and output arguments, for instance) that I hadn't been able to implement before now. The linear algebra package also needs a lot of work and a few interested volunteers to get up to speed and become a useful resource for other projects.

Matrixy: Moving Forward

The world of Parrot is an ever-moving target, but my poor compiler project Matrixy has been laying fallow for several months. Matrixy, for those who haven't seen me write about it before, is an implementation of the M language (MATLAB/Octave, not the new, weird, .NET language). MATLAB/Octave is the standard language of choice for many branches of science and engineering. I have never seen another language, except maybe R, which is so catered to the task of design and simulation, and it has some of the best integrated mathematics support I have ever seen.

Matrixy History

I started what is now called Matrixy about two years ago now when I was still in grad school. Part of my thesis involved writing an assembler in MATLAB for a new processor architecture I was designing in the visual programming component Simulink. Since I was just getting involved in Parrot at the time (and was reading the classic Dragon Book cover-to-cover in my leisure time), I decided an M compiler would be a great project to start. I put it on hold during GSOC and immediately thereafter when I was still burried knee-deep in Parrot core internals work. Luckily the idea was rescued by a guy named Blair who set up a project on googlecode and together we made a lot of progress implementing the syntax and semantics of the core language. Part of the standard M package is a huge list of built-in functions, something we didn't even attempt to reproduce.

Blair moved on to other projects, and I haven't turned back to Matrixy in months. It's sat completely dormant for months now, and needs a breath of life pumped into it. I can't think of a better time to do that either: With PCC refactors landing soon (I hope) and Plumage taking off, there is plenty of opportunity to get Matrixy up and running again. Here's a list of things I would like to do with the project, and I am looking for helpers and volunteers who would like to get involved.

Linear Algebra Libraries

Integral to M is comprehensive linear algebra support. This is what makes it such a great tool for engineers to use. Implementing these features, we've written bindings for Parrot to the CLAPACK and CBLAS linear algebra libraries. With Plumage quickly growing into a great ecosystem project, I would like to separate out the CBLAS and CLAPACK libraries into a separate "Linear Algebra Pack" to be dowloaded through Plumage.

This is going to require some work, however. CBLAS and CLAPACK have several functions with very exotic function signatures, and currently we would need to recompile Parrot to include them. Once Parrot has a proper NCI call frame builder, we don't need to worry about that.

Separating our libraries out into separate projects is going to help other languages and projects on Parrot who want to use them. However, it's going to require adding non-local dependencies to Matrixy's makefile. Small price to pay for the greater good.

Proper Matrix Data Types

One thing that M requires is a native matrix data type. We've managed to get along so far with an ad hoc system of nested ResizablePMCArray objects, but that's a terrible (and slow!) solution. Better yet would be to write up a good set of dedicated PMC types that implement a 2-D floating point matrix or vector. Having that PMC type support a sparse mode, or having a separate sparce array type would be fantastic too. If we included these PMC types with the "Linear Algebra Pack" that I talked about above, we would be able to quickly integrate robust linear algebra support in any language or project running on top of Parrot.

Imagine that in a few months time you could be using Perl6 or PHP or TCL to manipulate numerical matrices and performing complex linear algebra on them at blinding native code speeds!

Make Matrixy Installable

Matrixy currently doesn't work with an installable Parrot. In fact, Matrixy isn't really installable by itself either. We need to fix these things.

Matrixy needs to work against an installed Parrot so we can start properly tracking point releases instead of SVN head. Of course I always expect there to be exceptions to the rule, but it's a good policy to get into the swing of.

Matrixy also needs to be able to be packaged up and installed, especially through Plumage.

Move Matrixy to Github

Actually, this is something I think I can do on my own. I don't have any problem with Googlecode, but I feel the sea change pulling us towards Git and I would like to host at least one project through Git so I can start getting good with the tool. Github seems like a great place and I really like the social atmosphere.

Conclusion

Obviously there is a lot of primary development to be done too. We're a long way away from even having the complete syntax working, much less the semantics and the gigantic runtime library. However, with a few small changes Matrixy could be well along it's way to being not only a first class compiler project on Parrot, but a contributing force to other language projects as well.

If you have any knowledge about working with an installed Parrot, or working with Plumage, I would love to hear from you! Once I get things moved up to Github, I'll have plenty of commit bits to hand out to interested contributors.

Matrixy: Current Status

In a post yesterday I mentioned Matrixy, and today I wanted to give a quick overview about the state of that project.

History

Matrixy was an Octave/Matlab clone that I had started working on a while ago when I first got involved with Parrot. I had been working on it idly while still in school, but never made it very far because of my lack of knowledge at the time and my other commitments (like, school). I got in contact with a guy named Blair from the UK who was interested in working on the project, and together we set up a project page on Google Code to pursue it.

For a while things moved pretty quickly and we were able to implement many of the idiosyncratic features of that language reasonably well. Blair also did some great work writing bindings for CLAPACK and CBLAS, so Matrixy has reasonable linear algebra support (although many operations just haven't been implemented yet) through those libraries.

However, things eventually slowed down. Blair started working on some changes to function dispatch that would enable variable function parameter lists and variable function return lists. Because of his work in this area, I held off on some of my own dispatch-related work, and started focusing on Parrot proper. Long story short, Blair got stymied by some bugs in Parrot which also happened to be things that I was blocking on (PCC refactors being a good example), and development on Matrixy stopped completely. Yesterday I fixed a few small things, but that's hardly the same as the project being active.

Current Status

Despite the fact that Matrixy isn't being as actively developed now as it has been in the past, it still has and supports a number of important language features. Not all of the implementations are as good or as efficient as they should be, but they do exist. Here's a quick rundown:

1. Support for variables, scalars, and matrices, and most of the operators that act on those things. This includes automatically-growing matrices, autovivification, basic matrix operations, and functions that can tell whether a value is a matrix, a vector, or a scalar. 2-D matices only.
   
2. Support for basic string operations, string printing, string concatenation
3. Nearly-proper handling of semicolons to print statement values
   
4. Nearly-proper disambiguation between variables and functions using parenthesis
5. Proper runtime loading of library functions from files. So the function foo() will be automatically found and loaded from file foo.m
6. if/then/else, for loops, maybe some other control structures too that I can't remember.
   
7. Ranges and iterators using ..
8. Calls to system commands using !
9. handing of path search locations
10. Function handles and anonymous functions
11. Complex numbers
12. try/catch
13. Several library functions written in PIR and M.
14. Help functions to read documentation from M files
    

So that's a decent list of features that work or mostly-work, and that's nothing to thumb your nose at.

The Path Ahead

There are obviously more things that we need: cell arrays, structures, nargin/varargin/nargout/varargout, and others. We also need to find some kind of graphics package to tap into eventually that will enable us to implement some of the graphing functions. There are hundreds of other functions as well that need to be implemented and tested, more then I would be able to name here.

At the moment Matrixy only works with a development Parrot, it needs to be made to work with an installed Parrot (or both, if possible).

It needs to be better tested and several corner cases need to be stabilized.

And I really think that we need some significant internal refactors for a variety of systems and functions. I would love to even rewrite some of the PIR parts in Close, if I was able to do that.

I would like to separate it out into two separate (but related) projects: the Matrixy compiler itself, and the linear algebra libraries that could be reused by other languages to gain immediate, powerful, linear algebra support.

Overview

So that's a general overview of what Matrixy is, what it's current state is, and where I think development is headed. I don't think I will be focusing much of my effort on it in the near-term because of other tasks I want to work on for Parrot, and other things I have going on in real life. However, I will be dabbling on it here and there, and would like to get other developers interested in working on it too. No reason why it shouldn't be progressing just because I am not devoting a lot of time to it.