I returned to CoolBasic project after three months of learning XNA 3D game programming, and have been continuing to develop the CoolBasic Classic compiler for the last two weeks. Although the main focus has been with the compiler I also designed a new look & feel for the web portal, and it’s being reviewed by the rest of the Team. This entry, however, will be all about the compiler and what’s been done recently.

Can it produce byte code yet? Yes, to some extent. The underlying mechanics are in place, but nothing is written to any file yet. Basically, it can process expressions. This includes (but is not limited to) calculating the result value of a constant expression, resolving names (i.e. mapping the identifier names to their declared symbols), function overload resolution, automatic type conversions, and filling in the missing arguments for optional function parameters. A lot of thought has been put to optimize performance here. In fact, all those things mentioned above are done in a single iteration over the postfix presentation of the expression. I had to inspect how the .NET framework internally works with arrays, stacks, lists, and type conversion to make sure my algorithms were efficient enough. I actually ended up writing a few own implementations for those highly specialized cases I needed (where the framework equivalent would allocate memory in an inefficient way or do more work than needed, for example).

I’m about to go technical…

Expression pre-evaluation
Where I left off before my XNA experimentations, was the constant expression pre-evaluation. This is when the actual expression processor needs to be implemented. You first convert the expression into postfix notation and then evaluate it. Naturally constant expressions can contain constant symbols as well, so a circular reference safety check exists. Identifier names are resolved during evaluation because we need to know the data type of each value in order to determine the final data type and the ultimate value in case of a constant expression.

The expression processor is a single method any statement or symbol processor can call. Therefore we don’t know whether the expression is a constant expression or not (i.e. whether its value can be fully pre-calculated). When a symbol is encountered the first time, it will be “processed” (as in a constant symbol’s value needs to be known before it can be used in other expressions). Since the expression processor can be called by a function symbol’s own processor, in order to pre-evaluate optional parameters’ values, a circular reference safety check must exist for functions as well.

The constant symbol and parameter symbol processors simply check whether the result value was a constant and give an error if it isn’t. In addition, before the pre-evaluated value is assigned to a constant symbol or parameter symbol, it’s converted to the destination data type. I had to write my own optimized routines for this because the .NET framework is clearly a bit too slow with anything<-->string. And I learned how much pain in the ass it can be to convert a double value to string (just have a look at dtoa.c to get the idea) – I ended up implementing a much simpler algorithm for that conversion.

Even though constant value expressions are fully pre-calculated, I plan to add an expression simplifier for non-constant expressions as well in the future. It would basically turn expressions like a+b+2*20-c into a+b-c+40. However, this is a very difficult topic that will need much research in terms of grouping and ordering analysis, and I simply don’t want to be held back because of it (even though I have a partial implementation of it in the V3 compiler already). I don’t see it that important at the moment (in order to get this thing out someday I’ll leave it for now).

Name resolution
The expression is processed once token by token. Each encountered identifier is resolved by its name. This process is called name resolution. I have three special resolvers: Type resolver, Symbol resolver, and Overload resolver. The type resolver is called by a symbol processor (each symbol is validated by its own processor). A symbol processor exists for all symbol types. Most symbol processors resolve the associated data type, but some do additional work such as constant symbol processor who calls the expression processor in order to cache the pre-calculated value. The type resolver is the simplest one: since all type symbols must be declared in the root scope we can direct the search to that to begin with, and also only look for symbols classified as Type.

The identifier resolver is a tad more complex. It is told the context symbol and/or scope and whether the search should be locked to that context only or should it also be extended to upper levels if the name is not found immediately (one example of a locked context would be the dot notation path “a.b.c”). Unlocked search is recursive. In CoolBasic Classic, the main program exists in root scope, but it is not the root symbol; the Global symbol is the ultimate root node of the symbol tree, and all imported framework/engine functions such as LoadImage or MoveObject exist there. This means that you can override them by defining your own functions with the same name. The reason we tell the resolver both the context symbol and scope is that, for example, functions’ parameters don’t have scope during optional expression evaluation. In order to access constant symbols defined in the main program’s context, the search needs to get one symbol level up instead of scope level. Furthermore, functions’ local scopes are isolated from the main program (for obvious reasons), and local identifier, a variable or constant, name resolution cannot therefore access the main program’s base scope’s local variables and constants.

The overload resolution is an interesting one. First of all, name resolution has already succeeded on a function group symbol. Yes, we now have an extra container for all functions of the same name. It stores all overloads of that function. All we need to do is to pick the right overload and map the identifier to its symbol. So we pass a snapshot of the calculation stack to the overload resolver, and based on the data types of those values, the most appropriate overload is chosen. This means that you could have two functions of the same name, say Abs (like ‘absolute value’) that takes and returns an integer, and one that takes and returns a float. The compiler would then pick the right one based on the context in the expression, avoiding unnecessary casting and loss of precision due to choosing the wrong one. Should there be more than one equally qualified overload candidates, an error is generated. Should there be no qualified overloads at all, an error is also generated.

Completing expressions
Now what’s really new here is the injection system. It allows the addition of tokens in the middle of the token list without causing “memory move” operations like List.Insert() does (and yet we’re not operating with a linked list here – it’s not efficient enough in .NET, and I want to avoid the memory overhead generated by it). Omitted arguments for those function parameters classified as “optional” are a good example of injected tokens. But the feature also has one other very important use, for we’re also injecting type conversion tokens. This works with intrinsic data types (integer, float and string). Whenever a value of the wrong type is provided, CoolBasic Classic will try to convert the value to the correct destination type. For example, if you provide array indices as floats, they’ll be automatically converted to integers. Similarly, the function overload resolver tells back which values need to be converted and to which intrinsic data type.

We’ll probably be adding explicit type conversion operators to the language at some point as well; we’re just not sure about their naming yet. Just don’t be disappointed if you don’t see them in the first alpha or beta.

Another cool feature I’ve mentioned before is the presence of short-circuit And and Or operators. They are now fully implemented. They’re different from other operators in that while pre-calculation occurs in the same way as processing any binary operator in a postfix calculation stack, they actually produce byte code with conditional jumps instead of a single operator instruction. The hardest part was to infer the offset of the jump because type conversion instructions as well as loading omitted optional parameters to the instructions list occurs all the time (so that the offset cannot be determined during the conversion from infix to postfix). However, I came up with a clever mechanic that allows the reliable offset calculation without having to give up the idea of a single processing pass.

Byte code generation
I mentioned at the start of this blog post that I’m already able to produce byte code that would calculate the expression’s value in real Cool VES environment. A lot of different small parts had to be implemented before this goal was reached, but I think it’s now working quite well. The expression processor, in addition to calculating the result value, generates the full instruction set, including conversion instructions, short-circuit magic, and injected parameters.

One particularly tricky part was to implement dot notation path processing. While simple paths such as “a.b.c” are quite easy to pull off (just lock the name resolution context to the data type of the previous member’s value), it gets a little more complicated when assignment and arrays come in to play. I hate “exceptions to processing rules” so I had to come up with a unified model that just supports normal values, dot fields, dot array fields, and normal arrays. Array variables are always pointers to their actual buffers, but the value indicated by the index (or indices) on top of stack must be read by another instruction. And since context must be locked for the name resolution to succeed, unlike functions, the array field loader instruction cannot occur after argument values (and you cannot access elements not on top of stack which I could’ve done by creating my own custom stack structure, but it’d still be fundamentally wrong thing to do). So for an array access you need two instructions; one before and one after the arguments. Just like how C# and VB.NET compilers do it. It works now. Actually, byte code generated by CoolBasic Classic compiler is VERY similar to Microsoft CIL (Common Intermediate Language) generated by .NET compilers. For example, there’s no single instruction for operator “<=”, but it’s expressed with the combination of cgt, ldc.i4 0 and ceq instead – i.e. “not greater”.

Still few operators lack implementation of pre-evaluation support, but those should be painless to write in no time. One of these is the assignment operator (that again is a bit of a “different” case from the others), but perhaps I’ll get into that in the next blog post. Now this huge central piece is mainly done, the next big goal is to start iterating actual statements like If, While, For etc. Pretty much branching in general.

TL;DR
Expressions are now processed, and refined into real byte code that can execute on Cool VES platform. The next phase would be to process all statements, and with the help of the expression processor, create the final byte code output we can execute!

Green: done
Yellow: in the progress

Personally speaking, writing parsers for 40 different kinds of statements was a little repetitive and mechanical work (yes, we use specialized parsers instead of a state table and stack), but the boring part is now done. I’d say we’re definitely getting somewhere here. There are already 20,431 lines of C# code in 270 files, so the compiler project alone is pretty huge.

Introducing KilledWhale (the smartass).

I’ve been interested in versioning and Source Control technologies in general lately. One part of version controlling is the ability to handle conflicts when two or more developers check out a file for editing, do their changes and then check them back in. Two simultanous check-outs will often result in a conflict within the source file, and these conflicts have to be resolved through merging. Merging means that both developers’ modifications and fixes are applied to the source file, without the other’s changes getting lost in the process. Merging is one thing, but analyzing the differences is another. I decided to try out some difference tracking techniques.

First of all, there are number of algorithms available. Some are easier to understand than others, and some support more features (such as the ability to detect moved lines and code blocks). The most popular method I found was the Longest common subsequence problem, and it is, in fact, used in most Version Control software. It’s a good method of producing a script that can be used to “patch” the destination file with tiny changes so that it’ll transform to that of the source file. Basically you get a set of “add this to place X” and “remove this from place Y“. Unfortunately, while this technique indeed gets the job done nicely, visualizing these kinds of changes can be confusing. When a conflict occurs, for example, determining whether the merge would break something, can be tricky.

In addition, due to how LCS works, comparing two very big files (10,000 lines or more) quickly starts to eat giant chunks of memory because the algorithm operates with a matrix of n*m, where n is the number of code lines within the first file, and m is the number of code lines within the second one. There are a number of ways how to optimize memory consuption and matrix size, but that is out of scope of this blog bost.

Ideally, when a developer encounters a conflict (and a merge needs to be done), he or she will be provided with two source files side-by-side; one from the server and the other is the local file. This view should visually present those parts that differ between the two versions. If the developer spots a problem that would break the code upon auto-merge, there should be a way to edit the file before committing. LCS cannot by itself provide good enough visual presentation because it can only tell insertions and deletions, but not modifications. For example, editing a single line would produce both “delete” and “addition” changesets.

Then I came across with this Patience Diff algorithm. All in all, it would seem to fit to the purpose perfectly – it offers a very nice and clear presentation of changesets between two files and doesn’t take an awfully lot of memory either. I spent hours and hours trying to find a .NET implementation of it, but as of yet there apparently just aren’t any (the number of “good” C# implementations of the other algorithms is substantially small aswell). So I started working with a proof-of-concept. I spent a little less than 2 days on this challenge, and finally came up with a working solution. When I’m writing this, my work is the only C# implementation of the Patience Diff algorithm that I know of . As a side note, there’s seemingly only one Version Control product that uses Patience Diff as its main tool, Bazaar, but apparently one can optionally enable it for Git aswell.

Here’s a sample of two slightly different files: the left side represents the original document, whereas the edited version is on the right:

The following difference graph can be generated from them (green = insert, red = delete, yellow = modify):

So what does this mean for CoolBasic? I don’t really know yet, but I have some ideas

The original CoolBasic has almost no optimizations regarding the generated byte code. This is now different: Constant value analysis can ignore code branches (such as If/Else) if the condition can be evaluated to True or False at compile time. Thus, redundant code will not even make it to the final compiled program. Also, since we have constant value pre-evaluation, some expressions will be simplified before conversion to byte code. This ought to improve the runtime performance. In addition, thanks to internal scope-specific dictionaries, resolving branch targets does not produce linear search to all recorded labels (user-defined or generated). This should improve compile time performance greatly for large programs.

We’ll see how far we end up going with code analysis in the future… I’d love to collect data such as Cyclomatic Complexity or Number of Executable Statements in order to derive a general Maintainability Index out of the given source code.

Local scoping
All scopes now have their own list of local variables. This means that the user can declare variables in a code block such as If, For, or Case. These variables are allocated when the execution begins in that block and they will cease to exist after the execution exits the scope. Therefore, it is possible to declare several variables that have the same name as long as they aren’t conflicting in an enclosing block. Consider the following example:

Dim a As Integer

If a = 1 Then
    Dim b As Integer = 2
    // Variable 'b' is only visible within this If block.

    // You cannot declare variable 'a' here because it is already declared
    // outside.
EndIf

If a = 1 Then
    Dim b As Integer = 3
    // Variable 'b' is visible within this If block and any child blocks.
    // Variable 'b' is different than the one declared in the previous
    // If block.

    For i As Integer = 1 To 10
        // Variable 'i' is only visible within this For block.

        // Varible 'b' is also visible here since it was declared
        // in an enclosing block.
        b = b + 1
    Next
EndIf

It is also possible to declare scope specific constants in the same way. Upon entering a scope the Runtime will ensure that all of its local variables are initialized with zero. Similarly, local arrays and strings can now be freed upon leaving the scope.

Short-circuit And/Or
We’ll also change the way how the Boolean And and Or operators work. They have become ‘short-circuit’, meaning that if the end result of the Boolean operation can be determined by just evaluating the first (left) operand, then the program will not evaluate the right half at all. Again this will improve runtime performance, but users need to pay close attention to their code if the right side has any function calls that need to be executed regardless of the end result of the Boolean operation. This is easily fixed, though, by storing the right side expression into a temporary variable first.

So what’s been done since last time… well, most of it has been management oriented. I feel it’s most convinient for you if I just list the things:

• We have explored alternatives to SVN version control, like Mercurial
• We actually purchased a Virtual Server for web hosting
• We now have domain coolbasic.fi (and it’s already operational on the Virtual Server)
• We have configured PHP and MySQL databases
• We have explored ways to use LDAP authentication services
• We have explored ways to improve forum experience through measures in order to shut down spam
• The PureBasic accounts have been terminated since we now use other tools

The web host isn’t fully configured yet, but we’re working on it. When that’s done, we can set up a true testing environment for web developing (full copy of the portal, forums, everything).

I saved some money for not having to purchase a new set of PureBasic one-year licenses, but then again… I did purchase the Virtual Server, and it costs roughly the same. No gain there. In addition, I just recently purchased a license of Resharper which was around 200 €. I use it together with StyleCop at work, so I’m quite used to it. Coding without these essential tools feels somehow awfully wrong nowadays. Resharper is an extension for Visual Studio that provides advanced code analysis and refactoring tools that will help you write better code that is styled and constructed according to “best practises”. It helps to improve code readability and maintainability, and overall I think the gain is notable. I’ll be spending at least a few days refactoring my existing code now…

Fortunate me, I’ve had a chance to experiment some of my compiler specific ideas at work as well (I’m working on a project where I am able to use this expertise of mine), so even though not much code have been added to the CBC compiler project for the past 2 months, I, in fact, have done something useful that will help me achieve my goal in the CoolBasic project (I proved some techniques and theories work in practise).

Until next time…

I mentioned “dummy executables”. In actuality, they’re the real CoolBasic Classic compiler and the real Cool VES linker, but they aren’t feature-complete yet. For example, the compiler only has lexical analysis and the linker only creates an empty (yet valid and runnable) executable. Both can be tested by intentionally providing invalid source (such as CB source with invalid parentheses or mismatched string quotation). This enables us to test error reporting and build step chaining properly back in Cool Developer.

I uploaded this package for the DevTeam a few days ago, however, it was only for Windows. I decided the sooner I can verify that it works on Linux as well the better. Finding out that you have to change half of your code when it’s time to deliver would such big-time. So I installed Linux on a VMWare virtual machine this weekend. I then went ahead and fetched Mono and set up the CoolBasic Classic compiler and Cool VES linker projects in MonoDevelop. They both compile out-of-the-box and seem to work properly. I was a bit surprised how easy it was. I have zero Linux experience. None, whatsoever. Now I just need to figure out how to share a folder (or something) so that my Windows 7 host and my Ubuntu can share stuff… or just link them both to SVN somehow. Lots of research work to do.

I haven’t yet gotten started with the Parsers, but let’s see what the forthcoming week produces.

Late yesterday I finished the Cool Framework Definition File importer. What this means is that the compiler can now be made aware of Cool VES symbols such as functions and constants. For example, the constant “PI” is built-in to Cool VES in the same way as “KEY_ESC” or “COLOR_RED” will be in the future. I also tested how overloaded functions import, and that part is covered as well. Overall, the importer should be done now.

What about if the user wants to declare a function or constant of the same name as one already provided by the framework definition? For example, a user-defined function named “LoadObject” (which has the identical fingerprint with the framework version). Which would the program end up invoking? In such situation there’s two options: 1) Report compile error for ambiguous symbol, or 2) Resolve always to the user-defined symbol first. I don’t like the first option because it has the potential to break code if the framework changes (such symbol is added in the future, for instance).

One important thing to know about Name Resolution is that it bubbles up the tree. That is, if no match is found in the current context, query the search in its parent symbol’s context until a match is found or the entire tree has been processed. It never iterates the children of an upper level, though. In CoolBasic Classic the prime scope is the Root – all functions and the main program belong to the Root. In addition, there’s one more scope the Root belongs to, but to which the user has no access. It’s the Global scope, and that’s where the imported symbols go. Thus, Name Resolution will stop at the root level (user code) if the match is found, and will only proceed to the Global context if it wasn’t. Therefore, user-defined symbols will override any identical framework symbols. There’s one thing to note, though. If the signatures don’t match, but the names do, Name Resolution stops at the Root scope and will report possible compile error if no compatible signatures can be found (so it’s still possible for a framework update to break existing code, but only if the user intentionally tries to invoke the framework version).

The image below illustrates the current compiler status. Green boxes are considered “ready”.

And then onto other issues at hand. The new compiler (written in C#) is progressing nicely. In the beginning there’s naturally lots of plain setup to do just to get most of the needed entities created. It’ll get more interesting soon, though. For the past week, I’ve used approximately 4 to 6 hours almost every day after work to establish the new compiler solution. That’s a healthy 12-14 hours of programming a day . Time flows easily when you listen to inspirational music. Currently, the compiler parses the command line arguments, initializes a build job, and invokes the lexer on the source file. Half of all token types are already recognized, and there’s also one dummy parser (which, for testing purposes, only prints all tokens to the console output). I expect to finish the lexical analysis on the remaining token types soon. And then I can start implementing the statement parsers – which ought to be interesting because I now have some new tools at my disposal, thanks to object oriented platform.

I decided to take a little different approach for error reporting. All old compilers shut down the process immediately after encountering the first compile error. This new design doesn’t do that, but the compiler creates a list of compile errors instead and prints them to the standard error stream. This allows Cool Developer editor to compose a neat listing the user can then iterate through and fix more issues at once before re-building. This will probably save time on trial-error, and thus enhance productivity. Basically, this concept requires the compiler to be able to recover from compile errors and simply continue the process from the next statement. Oh, architectural joy! In addition, the compiler now also supports warnings i.e. messages that don’t count as errors, but still hold information about problems in code. Warnings don’t cause the compilation to fail, but they too will be listed in Cool Developer’s user interface.

As a bonus, you’d call the CoolBasic Classic compiler from command line like this (subject to change):

cbccompiler mygame.cbc /out mygame.obj /def coolves.fw

You can optionally enable Finnish interface by adding /lang fi

I think that procedural coding in general, an inadequate editor, a bit too simple tools, and a somewhat limited debugger will not serve our best interests in the long run. To me personally, it’s not too encouraging to open up our current development environment and start writing productive code anymore. I’m a professional C# developer, and this procedural coding (I once preferred) is becoming a mental burden for me. It has definitely affected my motivation in a negative way. I know I said a year ago that in order to create a fast and compact compiler, a procedural approach would be ideal. But I consider pleasant and powerful tools equally important because it enhances productivity of the programmer and maintainability of the project. I’m referring to Visual Studio (which in my opinion is the best IDE out there) as well as to Intellisense, refactoring, code analysis, unit testing, and other very powerful tools provided by it. After all, I think that if the compiler required a tad more memory and it took 2 seconds longer to build a game, it wouldn’t hurt too much (in a year the computers running the compiler are probably multiple times faster anyways).

So we’ve come to a point where we’re going to port our existing code over to C++ and C#. This will make a whole lot of new possibilities available to us: We can now harness the power of modern development environments, get more productive, and we no longer have to worry about the import files. We can trust that the generated ASM is correct and that using external libraries won’t conflict (that much, at least). There are pros and cons in object oriented design, but overall I’m confident that the marginal speed gain provided by procedural coding style isn’t going to outweigh anything. One of the most important things is that the developers are happy and get to work on something they enjoy.

The Cool VES game engine is going to be re-written in C++. This still enables us to inject ASM to where speed is critical. We’re also experimenting with a new multimedia library that ought to ease our job when implementing certain command sets in the future. We also continue developing Cool VES for both Windows and Linux.

I also mentioned C#. That’s for the CoolBasic Classic compiler! Now, this is quite interesting because there has been one project (that has nothing to do with us) I’m aware of, that attempted to write a compiler in C# about a year ago. It didn’t turn out that well, and currently the project in question is apparently frozen. One would think that this should be considered a warning example, but yet I’m willing to try doing the same thing because I really think it’s possible and quite doable. Yes, there are some serious challenges, and the architecture plays an exceptionally big role here. C# makes it possible to create a very high-level and sophisticated core for the compiler, and I’m very excited about it. Only a day after the meeting, I already had an initial architecture plan and a Visual Studio solution in place. Given that procedural model is seriously impacting my motivation, I actually believe I’ll get the job done faster now that I have good tools – even when it means I basically have to start over.

Many people associate C# to the Windows operating system. While it is true that C# is largely used to write software for the Microsoft .NET Framework, not everyone is aware that you can target programs written in C# to other platforms as well, like Linux. Just as Cool VES is intended to have both Windows and Linux versions, CoolBasic Classic compiler should also be available on Linux. I’ll be using Mono for that, but more information about that will be published at a later time.

If this becomes an epic fail, I can always revert back to the old compiler, although I highly doubt that. “I want to believe” . In fact, I should have known better when I made the decision of the development environment almost a year ago. I hope I get it right this time…

TLDR; We decided to start using more powerful development tools, and we’re all now more productive and happy.