Monday, March 11, 2013

Thoughts about functions

In the last few days I thought about the following problem:

int a[5]={1,2,3,4,5};
int sum=a[0]+a[1]+a[2]+a[3]+a[4]+a[5];

It is quite clear what this code is supposed to do. But it scales very badly with the size of a. In a regular sequential programming language, you would solve the problem with a regular for loop like this:

int a[5]={1,2,3,4,5};
int sum=0;
for (I={0:4})
    sum+=a[I];

This is even correct PSHDL syntax. But due to its parallel nature, it does not do what the developer is expecting it to do here. In fact, this is just short for:

int a[5]={1,2,3,4,5};
int sum=0;
sum+=a[0];
sum+=a[1];
sum+=a[2];
sum+=a[3];
sum+=a[4];
sum+=a[5];

Well, this looks just as the same as the above. But you have to consider that the last assignment wins. A quick detour:

int a=0;
a=5;
a=7;

a is obviously 7, but it never has the value 5, not for a second, not for a pico second, just plain never! You can think about it like this: PSHDL walks through the code from the top to the bottom. When an assignment a=X is found, it remembers that upon the end of the code it will assign X to a. That is unless somewhere below it finds a=Z. In that case the X is assignment is totally forgotten and Z is assigned. The same holds true for our sum example. For PSHDL the slightly longer version is equivalent to:

int a[5]={1,2,3,4,5};
int sum=0;
sum+=a[5];

Sequential loops

One idea that comes to mind us to introduce a new keyword. For example sequential. When we now put that in front of for, the contents are interpreted sequentially. The example:

int a[5]={1,2,3,4,5};
int sum=0;
sequential for (I={0:4})
    sum+=a[I];

This would now do what the user expected it to do. But unfortunately we just gave the user a very powerful tool in his hands. There is nothing, well nothing that I want to code, that keeps him from writing:

int a[5]={1,2,3,4,5};
int sum=0;
sequential for (I={0:3}) {
    sum+=a[I];
    a[I+1]=0;
}

What is that supposed to do? The user now has the ability to write very dysfunctional code. It is very difficult to distinguish valid use cases from invalid ones, so better provide a clean concept for solving this problem.

Functions to the rescue?

However summing up an array is a very plausible thing to do and writing everything by hand is very error prune. Also it can not be done when the size of the array is parameterized. So my first idea for giving the user the ability to solve this problem properly was to allow to declare functions:

function uint doSum(uint a[]) {
    uint sum=0;
    for (I in a){
        sum+=I;
    }
    return sum;
}

int a[5]={1,2,3,4,5};
int sum=doSum(a);

This however has a few weaknesses:

  • The same syntax that is used for the parallel way of doing things is suddenly used for sequential stuff
  • The function can only sum uint arrays
  • It is very hard to create simulate-able code for this as the function would need to be unrolled into parallel code

While the second problem could be solved with type parameters, which would introduce other syntax problems, I really don't like the first problem. The user should be able to understand the model of PSHDL very quickly. Having to different kind of models does not help with that.

Maybe lambda functions?

Another thing I thought about: If using the same language to sometimes have parallel and other times have sequential meanings might confuse the user, why not use a different paradigm which can elegantly solve these kind of problems. In functional programming a solution might look like this:

int a[5]={1,2,3,4,5};
int sum=a.foldLeft{a,b|a+b};

This would have the benefit of being very short and precise. But it would demand from the user to have an idea how functional programming works. Nonetheless, the type problem would have been solved as well.

I have to admit that I like the lambda approach. But I am not sure whether many people will understand it. So to not cause utter confusion I decided that I will provide the user with sum, (left|right)Difference, xor, or, and and mul functions. Maybe those will map to a more generic version that takes an enum to select the operation like this:

int a[5]={1,2,3,4,5};
int sum=apply(a, PLUS);

The nice thing about the apply function is that you can also write it like this:

int sum=a.apply(PLUS);

Another nice aspect of it is that PLUS is an enum and as such you even provide the operation as parameter. This approach however has some disadvantages that arise from it's simplicity. How for example would we add every second item? Or how do something like a[0]*x + a[1]*x . Well those cases would require to decompose those expressions into temporary signals. On the other hand it would certainly be possible to have functions that can apply operations to an array. So that case would look like this:

int sum=a.map(MUL, x).apply(PLUS)

No comments:

Post a Comment