Showing posts with label C. Show all posts
Showing posts with label C. Show all posts

Thursday, September 4, 2014

Matrix Multiplication, Conditional Statements, and Functions

I actually was able to finish matrix multiplication the day after my last post, which was pretty cool. Unfortunately, school has started back up, so I think development will slow quite a bit. I'm working on implementing symbol tables (needed for functions) and functions at the moment.

Matrix Multiplication


The way my program works so far (there's probably a better way) for matrices is that for printing and operations, I push all the elements onto the runtime stack in reverse order. So for printing, I just pop off the elements on the stack and throw in a couple of newlines here and there. For storing matrices in memory, I just pop each element off the stack and then put it into the memory location corresponding to its location in the matrix (according to matrix size).

Now this presented me with a problem at first with matrix multiplication, because I'd have two matrices on the stack at once and I'd be pushing the third resulting matrix on as well. I couldn't access the elements of both matrices with simple pushing and popping. One thing I forgot about  was the special stack pointer register though! So what I did was after I push the first matrix on, save the stack pointer to a temporary register, then push the second matrix on and save the stack pointer to another temporary register. Then I could simply look at an offset of these temporary registers and get the matrix element I wanted.

Conditionals


The next thing I actually worked on was if-else statements, and I actually was able to complete those as well. The syntax is pretty generic, it is simply if expression then statment list else statement list. Of course the else block is optional. The reason I ended up doing this was because I was trying to plan out functions in my language, and I was writing base functions that I wanted to include in the language, some of which require conditionals!

Functions


One of the decisions I had to make when designing functions in my language, was whether or not I wanted to include types of parameters/return values or not. While it may look prettier, I think this can lead to some issues that I don't really want to deal with. Plus the way I decided to write the functions gave me a neat way to give a variable name to the size of parameters. So without further adieu, here is what I'm planning on implementing for my function syntax. I'll give the sample declaration, the sample call to the function, and then a description in that order:

(Note: the three periods just signify some other code might be there)
\foo =
   ...
;
...
foo.
... 
This is a function call foo that takes no parameters and returns nothing. To call any function, type the name, the correct number/sized parameters, and then a period.


\foo A[m:n] =
   print A @ m - 1,n - 1
;
...
foo [1 2,3 4].
...
This is a function that takes one parameter, a matrix refered to as A (in the function) with m rows and n columns, and returns nothing. You can reference m,n, and A in the function.


\foo num -> int =
   return num + 1
;
...
if foo 0. then
   print 0
;else
   print 1
;
...
This function takes one parameter (this time an integer, as no size is declared, named num), and returns an integer. Integers can be used in conditional statements, so you could use the return value in an if statement. The integer 0 is false and everything else is true, so this code would print 0 (as foo 0. would return 1).


\foo A[m:n] -> [n:1] =
   B = [n:1]
   ...
   return B
;
...
B = foo [1 0,0 1].
...
This function takes a matrix, and returns a column vector (could also be a full matrix). You can use the sizes in the parameters in the return size as well.


\foo A[m:n] -> [m:?] =
   ...
   return B
;
...
print foo [4:4].
...
The function takes an m by n matrix and returns an matrix with m rows and an unknown number of columns. For instance, when computing the basis of a matrix, you don't know the dimension (or how many vectors will be in the basis) without reducing the matrix or using other properties.


I think these features cover a decent amount of problems that you would need to solve using my language, but obviously I might think of some more!

Moving Forward


So after I finish changing the existing code to use a more complete symbol table, I'm going to go forward with function parsing and function code generation. Perhaps after that I will take a look at assembly optimization or AST optimization.

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.