Thursday, August 21, 2014

Making a compiler for a small programming language

I've been working on a compiler for a language that deals with matrices. I took a compilers class last semester, as well as a couple of classes dealing with linear algebra and matrices. I wasn't too happy with the resources out there for doing matrix operations, so I decided to write a language for it!

Here's some example syntax to start off with:

Matrix Declarations:


Nonempty


{1 2 3,4 5 6,7 8 9}
This represents a 3x3 matrix with first row 1 2 3, second row 4 5 6, third row 7 8 9.
It would look like this drawn out:
| 1 2 3 |
| 4 5 6 |
| 7 8 9 |

Empty


{3:3}
This represents a 3x3 matrix containing all zeros
It would look like this drawn out:
| 0 0 0 |
| 0 0 0 |
| 0 0 0 |

Variable storage:


My language sort of uses implicit storage in the way that you don't declare a variable's type, but all the variables are matrices.
A = {3:3} --A now contains an empty 3x3 matrix
B = {1 2,3 4} --B now contains a 2x2 matrix
C = 4 --C now contains the integer 4
D = 5 * 2 - 3 --D now contains the integer 7

Matrix Indexing:


Assume that all the variables have the values as defined in Variable Storage.
Indexes are zero based

Single element


B @ 0,0 --the upper left element in B, 1
B @ 1,1 --the lower right element in B, 4


Row


B @ 0,# --the first row of B,{1 2}
B @ 1,# --the second row of B,{3 4}

Column


B @ #,0 --the first column of B, {1,3}
B @ #,1 --the second column of B,{2,4}

Other Cool Stuff:


Now that I've discussed matrix indexing, you can also use indexing in storage.
Taking A as an empty 3x3 matrix, I could do the following:

A @ 0,# = {1 2 3}
A @ 1,# = {4 5 6}
A @ 2,# = {7 8 9}

Now A looks like:
| 1 2 3 |
| 4 5 6 |
| 7 8 9 |

But say I had a 10x3 matrix, I wouldn't want to type each row declaration out!
E = {10:3}
for x = 0,9 do
     E @ x,# = {(x+1) (x+2) (x+3)}
;
This indicates a for loop with a variable x going from 0 to 9 by 1. In each iteration it sets the xth row to contain 3 elements that are 1,2,and 3 bigger than x respectively.

I'm hoping you can imagine what E looks like now! (like A but with 7 more rows!)

What's left to do:


Matrix multiplication


I have an idea of how to go about this, so should be done soon!

Matrix operations (reduction, span, basis, transpose, inverse, etc)


I currently have a small set of operations built into the language itself (I would generate the assembly for them manually) but I think I will add functions to the language and just include a base library for these functions. This will probably take a decent amount of time!


Code optimization


The assembly that I produce at the moment is probably not the best way to do it. I also might convert it to an intermediate representation before I convert it to assembly, so I optimize it better in that stage. This is probably a while down the road though.

No comments:

Post a Comment