Bitlang

My mic failed on me so you will have to watch the annotations. Or, better read the description on this page instead. I will try to fix a better video later on when I get sound working, but I need this one for the THP Entry submission right now.

When you read this article, remember the reason for doing this:

* Specification

* Code analysis

* Testing: We can tell the compiler to not call that block (function) after all, hijacking it or spying on it.

* Keep the language small at all costs and put everything into the standard library. Writing new compilers becomes easy. Sometimes you don't need speed, you just need to get it working on a new platform (even if the examples below are extreme).

* The development of the Bitlang Compiler will be easier. (We'll use a very simple parser + LLVM.)

Higher-order blocks aren't really C-macros or C++ templates / Java generics. They're more than that and need to be powerful. For example, let's consider this:

if(a() || b()) {

...

} else if(c.blah) {

...

}

When we implement this, there are a few things to consider. If a is false, we don't want to evaluate b. Likewise, if the first if fails, we need to do the else.

To implement this, we could define (in pseudocode now):

first = 2^{ |first, second| return first }

if = 2^{ |bit expression, block run|

  return ELSE(expression ? first(false, run()) : first(true, nothing()))

}

It gets a bit ugly, but once we have if, everything will be nice in the future. Also, note that this is the specification. The heavily optimized standard library in the compiled code will look more or less exactly as if a C compiler produced it.

So, "if" is a named block that evaluates the block if expression is true. It has two parameters. Everything works nicely, we run if the evaluated expression is true and return some kind of else-type. The else type (as well as the logical-or operator || that need to skip evaluation of b() if a() is true) is harder. Here, we need to be able to take an expression and evaluate it at will. This can be used in two ways:

* Branching. This is where conditional branching comes into the picture. For not-yet optimized compilers, it happens in the ternary expression. For optimized ones, it happens right in the source code as "branch if xxx".

* Analysis. A simple example is hijacking 0^{ this is a %s string } or "this is a %s string" and return the right type. More examples would be in testing where we need to stop certain things from happening.

Things get more complex, because we can have higher-than-2 degree of blocks too, i.e. blocks than run inside the blocks inside the compiler/tool. That will be very handy for writing the compiler that interfaces LLVM.

Operator precedence is important for some applications, but it can also be dangerous. As an example, what does (1 + 2 % 2)  or (2 * 3  % 2) do? I've been bitten by this one before. For Bitlang we can't really define operator precedence, since that's up to the developer.

Let's consider some cases:

-3 + 5 <= It doesn't matter much here, but it would be good if the - was applied first.

3 - 5 <= We mean 3 + (-5), but cannot assume that here. What if order is important for some type?

3 * -5 <= Hmm, tricky one. We have two operators here but that could be one (&&, *=, << etc have two chars.)

right.index - left.index <= We mean (right.index) - (left.index), not ((right.index) - left)

1 + 3 * 5 - 4 <= Important to get the order right.

1 / 4 * 5 <= We mean (1 / 4) * 5.

We can study this as mathematics but that's not really needed. Let's just keep it simple and categorize the operators into two groups: greedy and non-greedy. Addition is an example of a greedy operation since it eats the whole multiplication-expression, while * is a non-greedy one as it doesn't eat the -4. Now, we can say that operators that begin an expression is left-unary and sticks to the immediate operand next right to it. If the operand is a variable or symbol on the other hand, the following (if any) operator is applied - UNLESS it's a greedy one, as it then have to wait for all non-greedy ones following.

How do we solve the problem where we mix +- and */? It will solve itself. But, what about the ambiguous %-operator? What about the &&, || or == as commonly used in other languages?

(a + b == c * d && e * f == g + h)

We don't want to add parentheses here. How can this be solved? It actually is solved, it works given that greedy operators eat other greedy operators - with the order being left-to-right. 1 + 2 + 3 would be computed as 1 + (2 + 3). This is something you have to deal with if you're greedy, and it's commonly reflected in mathematics too: multiplication might be order-dependent, but addition/subtraction usually isn't. And if it is, you need to have parentheses.

(a + b && c + d == e + f && g + h)

Some moron came from C and wrote this, and now his code doesn't work. Also, we have the %-problems to deal with. Ok, here are three ideas: Either bucket everythng up in more than one bucket (like conventional languages do) - we could even have one bucket for % and the like that gives warning unless you have parentheses explicitly. Or, make some operators friends, and ban others - need for parentheses all over the place. Or: Have predefined buckets, and remove % and call it .modulo with .isEven and .isOdd shortcuts. Warning on every ambiguous use that needs parentheses. This also prevents people from abusing operators. I like this last one best!

A description to the project was added. The text is put into the project description instead of here. That way, you can always read the most updated version.