Every now and then (usually after something bigger gets finally implemented) comes the time to perform a “maintenance round” to clean up and finish the latest added features. That’s essentially what I’ve been doing lately. I want to keep it clean and tidy. I also thought that now would be the appropriate time to transform the compiler into what it’s intended to be in the end: a working console application. Until now I have had the input file hard-coded as well as the function call, to perform the actual compilation. Well, not any more. The compiler now gets called by commandline which defines all input files and/or additional options. All passed files then get parsed and compiled nicely one by one. The compiler will not be a DLL (as hinted in the previous blog entry) nor will there be any visible Windows form. There will not be a progress bar. Instead, the compiler does write some info to the Standard Output Stream – which can be directed straight to the future-coming CoolBasic editor. Possible compile time errors can be parsed from this string data. In addition, the compiler returns an exit code back to the system which tells was the compilation successfull or did it fail. Overall, this resembles how Visual Studio performs building.

I also took another round of standardizing the error messages (mainly those that get generated by Pass#2). Currently, there’s a great deal of them, and I estimate there to be a few hundred of them in total by the time the compiler will be finished. And I must say… Oh boy I’m going to be loosing some hair in an attempt of localizing them into finnish. Not because of the amount but because of their nature. The quantity of the finnish literature in modern computer programming is way below the levels when compared to other languages. Most books about programming are nowadays almost always in english which means that the finnish terminology is in danger of not being able to develop accordingly to the rules set by this industry. The impact is already very visible, and personally I’m going to be a little worried about the future-coming finnish localization… I think I will need to simply come up with some new terminology translations because there simply aren’t any established “official” words for their original english counterparts. This means that most translated terms sound silly because everyone is already used to their english meaning. There are some error messages that I already find difficult to properly translate into finnish. For now, I haven’t yet implemented the finnish translations although the support is there: someone would just have to fill in the missing strings. Well, maybe I’ll just delegate the job to someone in the devTeam later 🙂

I have finished the “maintenance round” now, and the compiler application is now operating well. I even tested running the compiler from within a .NET application, to receive its stream output. Please note that the compiler is still missing a lot of its functionality, and is not by any means, finished; It’s not yet able to produce the IL from the source code – which is pretty much the only thing remaining. Yes, the end of the tunnel is already visible, but there’s still a long walk before we reach it. I freshly added a new functionality to Pass#1 to gather detailed list of code lines and the exact method they belong to. Actually, I already had that data, but this modified collecting process gets the job done better. I now have a list of “executable code tokens” that need to be analysed for the final time, only this time we can be sure that their syntax is already OK. Practically, we’re cleaning it up, adding the needed metainfo, and dismantling it into fundamental theorems. Think about the For statement… it’s actually a While...EndWhile block.

So there’s only two major things remaining… the IL and the compiler Backend. Wow.

I’ve been working hard on CoolBasic V3 for the past few months. I have a regular job (as a programmer), so development time limits to weekends, evenings, and nights. Basically, I spend around 4-5 hours on average developing the CoolBasic Compiler every day, 8-12 hours aday during weekends and hallows. That being said, I thought that some vacation coudn’t possible be bad at all… So I kept 4 “days off” during the Easter, trying to clear my mind. But still I’m getting the feeling that I’m slacking. I finished the Expression Processor the day after I returned. As you may recall, I characterized this entity as for being the most complex procedure of the entire compiler so far. I’m very pleased that this enormous job is finally done. A few small things still remain to be taken care of, like handling access to Shared members and verifying legal type casting, but the outlines are now solid and the system seems to be working with the current (fairly sophisticated) algorithm.

There’s also something special worth mentioning: While I was creating the latest back-up copy, I noticed that there’s now exactly 1 Megabyte of pure source code. That means roughly 1 million key strokes! To visualize, count to 100 in your mind as if you were typing relatively fast. When you’re done, imagine to do it again for 10,000 more times! Yep, that’s a lot of code! Now, one could think that this can be explained with extensive copy-pasting, but that is not the case; in fact, the compiler architecture is designed to make extensive use of functional approach, meaning that practically speaking all of the procedures are so specialized that they don’t recycle code at all.

To illustrate, remember when I said that the type resolver and the identifier resolver would look alike and function similarly? That was the assumption I had before I actually got started with the Expression Processor. Well that assumption is no more, I turned things pretty much upside-down (there’s a lot more into it for the Expression Processor when compared to the Type Resolver where certain assumptions about the expression’s structure can be made). To sum up, Type Resolver is now fully operational, Name Resolution is now fully operational, Overload Resolution is now fully operational, Constant Value pre-calculator is now fully operational, and semantic checks are nearly finished. I’m also testing an idea of my own, to solve the grouping issue explained here.

EXE or DLL?
One day I was pondering which way would be better. The original approach was to make the compiler a Dynamic Linked Library, but bundle it with a Commandline Compiler (which would ultimately call the DLL anyways). If one wanted to create, say, an own IDE – or just access the compiler without CoolBasic being fully installed, there would be 2 choises depending on the situation and personal preference. However, a DLL cannot write to Standard Output Stream (well, this is actually not true, but there’s another reason why it’s a bad idea to try doing that), so compiling progress would have to either be completely silent, or the compiler would have to create a window equipped with a progression bar or at least a label with a description. Also, what *if* the compiler would crash (which of course doesn’t happen)… the entire IDE would crash, too. On the other hand, A DLL function could return a string with embedded metainfo about the end result whereas an executable can only return an error code back to the system. And then there’s the unpredictable memory and resource management of an attached DLL. Even though the CoolBasic Compiler is very well designed to free all resources after compilation, I’m still hesitating. A safe executable just ends, freeing all reserved memory 100% guaranteed. Going always through the Commandline Compiler would overcome that problem, but what’s the point of a DLL then in the first place?

As it stands now, I think I’m going to end up with Commandline Compiler only (which the IDE will silently call, meaning no visible console window will be created). This way the compiler can message back straight to the IDE, as well as provide with a log file for more details. It will also operate in an independent manner and free all its resources 100% sure. Possible OS porting will be easier in the future, too. There may be some priviledge issues involved, but let’s examine those more closely when the matter becomes more relevant.

Closing words
I’ll tweak the Expression Processor some more by fine-tuning its functionality and fixing any remaining bugs. While anything can always suddenly arise, at this point I’m confident that I can soon start thinking of the next steps. That would be something like processing all those code lines that execute program logic, and to generate appropriate IL for them. I’d say we’re half-a-way into Pass#2 now (and yet Pass#2 has more code than Pass#1 has).

Data type resolution works now in all cases (I’ve extended its capabilities since I last mentioned about it). A quick wrap-up on Pass#2 would go as follows: Before anything can be calculated – including constant expressions – the compiler will first need to resolve the data types of all identifiers. In practice, this applies to variables, constants and procedures. In the other hand, in order to make type resolution fully operational, all alias names need to be resolved beforehand. A “type” here refers to a structure or a class. Also, “name resolution” in general refers to both type resolution and normal identifier (that generates a value) resolution. These two resolvers greatly differ from each other, thus I need to implement them both in such way that they operate independently from each other – excluding the fact that the identifier resolver may call data type resolver when needed. Anyways, the type resolver must be implemented at this point whereas adding value-generating identifier resolution just isn’t possible yet.

One could wonder why can’t I start working on normal identifier name resolution now that type references have been resolved. In OOP there’s a lot semantic checks that need to be done before resolving identifier references because otherwise you would get possibly misleading errors during compile time. Those semantic checks couldn’t be done in Pass#1 because data types weren’t resolved yet. The checks include base class checks, inheritance checks, override checks, and some special rules – only to name a few. Basically the compiler iterates the symbol table here, and performs a symbol-specific set of checks. All of these checks are not mandatory in order to produce a working executable, but they’ll ensure that the source code is overall valid and semantically correct. For example, a semantic error within a base class may not occur if name resolution returned a valid reference before that.

I’m going to remove part of the ambiguous name checks in Pass#1. Procedure signatures were formed in Pass#1, and they were used to check for identical overloads. Unfortunately, qualified names can bypass these error checks, so the signatures need to be checked again after type resolution. I could let those checks be as they are, but I’d like to shift these checks over to Pass#2 semantic validator so that they appear in one place only. With small adjustments to the type resolution, I think I can cover overloads much better overall. Overloads don’t apply to functions alone anyways.

I think I can finally get started with the most complicated sub-routine of this entire compiler (Expression Processor) once I finish with these semantic checks. As a side-note, I estimate CoolBasic V3 compiler is way past the halfway now. First things first, though – let’s get these semantics over with.

So I thought that I’d get an easy start to Pass#2 by first developing the constant value pre-calculator. It seemed like a logical thing to do for starters because those pre-evaluated values will be needed in the actual compilation of executing code. So I started writing a procedure that iterates all constants from the symbol table, and then calculates their values. I had all these circular reference algorithms planned out and so on. But of course surprises do happen (actually I should have seen this coming from a mile away), and I figured that before I can implement this fancy stuff, there are a few other things to take care of.

Wait, isn’t that the same precise thing I experienced in the beginning of Pass#1… oh, umm.. Yes it is! Back in Pass#1, I was hoping to get an easy start with simple statements such as Repeat…Until. But there’s no such thing as free lunch; I had to write the containing elements first (d’oh, of course!). Those being classes, functions and so on. On top of that, those statements just happened to be the most complicated ones, so plenty of general-purpose parsers needed to be written, too. So Pass#1 was quite frontloaded instead of backloaded a burden to chew on. As I’ve written in previous blog entries, the ending of Pass#1 went relatively quickly, and was just a copy-paste fest for the most part.

So what’s the frontload here in Pass#2? Well, even though you now got your pretty symbol table and the source code on a silver platter, you will still need to solve the identifier name references correctly because constant expressions can have constant identifiers in them. These references couldn’t be made in Pass#1 because identifiers can be declared in random order. Sooo… now you find yourself together with Mr. Name Resolution. Oh, and also, please meet his brother Mr. Overload Resolver. Oh, and don’t forget their sister, Ms. Template Expander. Whoah, so I suddenly have these 3, mean looking procedures on my face – right from the start. I’m not kidding, these are probably THE 3 most difficult entities for Pass#2. And again, they must be almost completely implemented before proceeding onto further tasks. Okey, the Template Expander can wait a little bit. I can probably get this pre-calculator to work correctly on *simple code* with just the Name Resolution algorithm implemented, but the 2 remaining villains need to be taken care of soon after.

Name Resolution is essentially the process of matching source code identifier names to their actual declaration. An identifier can be located in some of the upper levels or in a completely different branch within the program hierarchy. When the identifier reference is being resolved, also the access modifiers are taken into account. All this follows a specific rule-set of the OOP member accessing. Basically, an entity always has access to upper levels, but requires Public access for branches. Inherited class-based reference to base classes can also have Protected access. Combine these to overloading, shadowing (hiding by name) and procedure overriding (hiding by name and signature), and you got yourself a nice little soup. But these are my problems anyways 🙂

I have formulated algorithms for both constant expression calculation and name resolution, and I expect to carry them out during the up-coming weeks. The pre-calculator will be a big chunk of code. At this point in development, things get really interesting (and challenging).

All those 64 parsers of Pass#1 have now been written and tested. And that’s a lot of code! Virtually every statement has now had its parser implemented, even though some of those statements will probably be disabled for the first few alpha releases. I’m kind of relieved as I’ve now reached a “check point” in the development process. Yet there’s a lot more to come. All in all, I think it’s safe to say that I’m closing in the halfway of the entire compiler now that Pass#1 is ready. The compiler made it through the baptism of fire, by properly parsing a few-hundred lines long complete test class source code.

This means that given the source code of a random test program, the compiler has now performed syntax checks for all elements of it, and that there’s now a complete symbol table for Pass#2 to play with. All metadata has now been gathered… Pass#2 has all the info it needs in order to complete the transformation into the Intermediate Language. If Pass#1 was essentially the Parser, then you can consider Pass#2 the actual Compiler; Its main job is to process the executable code within procedures – and to order it in a meaningful way. Pass#2 is a very, VERY complex process, and it has a lot more tasks than Pass#1 had. I have already assembled a list of those tasks, but I’m not going to share it just yet. I’d rather divide them into smaller topics and discuss them separately in future blog entries.

There are few preceding steps before Pass#2 can start crunching the procedure code. One of them is Interface merging and the other is the pre-evaluation of constant value expressions. The latter is probably more challenging with all this circular reference thing going on. Other “difficult” parts of Pass#2 include Name Resolution, Overload Resolver and the actual Expression Transformer. More about those later. All I wanted to say, was that there’s much work to be done, and it’s getting more difficult now. Bleh, I’m probably going to be spending even more time just thinking things through before implementation.

Pass#1 consists of dozens of parsers. All the “container” statements are already implemented and those missing are the “regular” statements i.e statements that can only be written inside a procedure which carry the actual program flow. I had no need to parse value expressions until now as I got started with statements such as If, Until, While, etc. Most of these standard statements include parts where a value is expected. And value is evaluated from an expression. Expressions can contain operators and operands and together they form a mathematical formula. A result of an expression can be a single value of any data type defined within a CoolBasic program.

The constant value expression parser was made long ago when I was writing the Function statement parser. It converts the expression to postfix notation and then attempts to evaluate it. It was perfectly sufficient for the job, so I decided to try out the same technique for the value expression parser aswell. Value expressions allow practically all expression elements whereas the constant parser implementation was merely partial due to the amount of “illegal” elements for a constant expression. The value expression parsing algorithm grew soon in size and wasn’t exactly the most enjoyable to debug with. Also, the more complicated expression elements such as jagged arrays caused all kinds of nasty problems that would have required ugly exceptions to be made for the algorihm. In order to debug the algorihm perfectly I needed long and complex test expressions. And since you’d need full debug info of what’s currently in the output queue, operator stack, and what’s the current state of the expression, it quickly lead to nice little flood in my Compiler debug window.

So I discarded the entire parser code, and started to think of new ways to check validity of a value expression. After sprawling on the couch (once again) for a couple of hours, I came up with a solution. I’d continue doing things just like I had been doing the entire time for Pass#1. Even expressions can be broken into smaller peaces, and each piece can be validated separately. One error, and the entire expression fails. Sounds like yet another great use of recursion, uh?

If you read compiler literature you’d notice that there are mainly two kinds of commonly used algorihms (not including their sub versions): The LL and LR parsers. They both scan expression terminals from left to right, and try to satisfy the requirements of an expression. The LL-parsers do this by forming the entire expression as a product of terminals and operators it comes across with, whereas the LR-parsers try to simplify the expression down to a single product. These algorithms are also known as “Top-down” and “Bottom-up” parsers. Since basically recursion is like a stack, the easiest way for me, was to use the Bottom-up parsing technique. It’s not by the book, but the basics are the same: Every time a value is expected, new recursive call is initiated. I’m not going to delve into details, but it appears to be working like a charm. Later on I also replaced the constant value expression parser.

So what this means, is that unless I hit unexpected problems, Pass#1 is finally coming toward its end. I still have lots of parsers to implement, but most of them are very simple. I should now have almost all bits of a statement, implemented as a parser. It’s just a puzzle left I need to put together with ready-to-use pieces.