Compiler development update

So here's an update on how things went after my previous post ("Compiler development roadmap").

After the "typerefactor" branch was more or less finished, I tried to merge it into (a copy of) the "llvm" branch. But the merge didn't work, so I decided to do things in a different way.

I created a completely new branch called "llvm-new", starting from the code of the "typerefactor" branch. Then I added the LLVM 2.4 sources to it, using the CMake build system from LLVM itself. To get the thing completely compiled and working I had to update to a SVN version of the LLVM code, though. And then I started writing my LLVM back end from scratch.

Wanting to avoid the mistakes of the first "llvm" branch, I started immediately on the implementation of a complete mechanism to manage types and to do type conversions. This means dealing with real class types, that are passed as a (this-)pointer, with primitive types that are passed as a value directly, passing parameters by reference or by value, passing values to "inout" parameters, referencing/dereferencing, indirectly returning values (using a extra hidden function parameter), etc... Eventually this implementation turned out pretty good, so it's no longer a PITA to write back end code like passing a value to a parameter.

Now I'm working on the implementation of codegen for all types (classes actually), expressions and statements. For most things implementation is easy, because I can look at the old implementation in the "llvm" branch and port that code to the new way of doing things. This new way is not just the typepassing/-conversion infrastructure; I've also changed the way I emit instructions. Previously I created the LLVM IR directly, but now I use the IRBuilder utility class from LLVM. And I now have a utility class that makes it a lot easier to emit basic blocks and branches to them.

So things are going forward slowly. I think that my "llvm-new" branch now has about 75% of the codegen functionality that was in the "llvm" branch. But things are still primitive; the compiler spits out lot of debug output followed by LLVM IR. You can try it if you want to, the code is available on the Launchpad project page:

https://code.launchpad.net/hyper

So most of my time is currently spent on the "llvm-new" branch. But that doesn't mean that the other branches are dead, however. The "typerefactor" branch now acts as a merge bridge between "llvm-new" and "main" (the 'official' front end branch). All front end related changes in "llvm-new" are regularly merged into "typerefactor". And those improvements are then merged into the "main" branch. The reason for doing things this way is that I like to keep the differences between "llvm-new" and "typerefactor" (in their front end code, at least) as small as possible. And now I can do some more or less invasive changes in the "main" branch without worrying about breaking the back end code.

As you might have noticed, progress has been going rather slowly these days. That's because I found a job as a software developer, using .NET (C# and VB). But at home it's still only Linux (Gentoo) for me. I'd prefer not to depend on Microsoft personally, but I need something to pay the bills of course.

Compiler development roadmap

You probably already know that there are two important versions of the compiler in development: the "main" branch with only a front-end (called "trunk" on Launchpad), and the "llvm" branch with an experimental LLVM-based back-end. Their source code can be found on the Launchpad project page:

https://code.launchpad.net/hyper

That page contains another development branch as well, called "typerefactor". This branch is a heavily modified version of the main branch with the purpose of refactoring the handling of types and type conversions. I started the typerefactor branch because the code of the llvm branch has become a bit difficult and fragile; the typerefactor branch will improve the front-end part of the compiler so that developing the LLVM back-end will be much easier.

Another thing on my TO-DO list is the upgrade of the back-end to LLVM 2.4. This means that I will have to replace my custom CMake build system for LLVM by the official one. Yes, you read that correctly: LLVM now has an (experimental) CMake-based build system of its own. I posted my code for building LLVM with CMake on the LLVM mailing list quite a while ago, and now someone has used that code as a start for writing a real CMake build system for LLVM (mine was very Unix-oriented and was just enough for using LLVM with my compiler front-end).

So currently I'm planning to do the following:

1. Finish the typerefactor code.
2. Create another branch, "llvm-experimental", based on the llvm branch, and merge the typerefactor code into it. It's possible that this will require some extra changes to the front-end code, and those will be merged into the typerefactor branch again.
3. Upgrade the one of the llvm branches to LLVM 2.4. What branch I will use will depend on how long it takes to finish item 2 and on how difficult the build system transition will be.
4. When item 2 is done, merge the typerefactor branch into the main branch.
   
5. When items 2 and 3 are done, merge the llvm-experimental branch into the llvm branch.
6. Implement codegen for everything the front-end currently supports (in the llvm branch).
7. Merge the llvm branch into the main branch.
   

This is what I have in mind for the future, but it is not guaranteed that development will truly follow this roadmap. And it doesn't account for any front-end-only changes that I might do in the mean time.

Some things that will need to be done to the front-end:

• Add support for 'references' (or restricted pointers)
• Create a Unicode interface for the "string" type (no more random access)
• Change the handling of operator overloading for binary operators (no more global list)
  

Others things are on my possible TO-DO list as well, such as adding support for "pure" procedures, but that feature will need to be thought out (and published here) first.

About the 0.4.0 release and the back end

The compiler had a new release last month, with some big improvements. So the version number was not increased to 0.3.39, but to 0.4.0.

I did a major internal restructuring of the compiler's semantic checking, as I wrote earlier. These changes allow me to detect circular dependencies between classes, and fix some nasty bugs. I no longer keep a separate symbol table; the symbol names and symbol lookup are now embedded in the AST data structures directly.

And the compiler now finally has full Unicode support! Source files are assumed to be in UTF-8 format now, because only that format is supported at this time. It also has the advantage that it's a superset of ASCII, so you can open a source file with a dumb text editor that doesn't know about Unicode and still have readable source, except for some special characters that aren't displayed correctly because they're not ASCII. Other formats like UTF-16 are on my TO-DO list, but do not have a very high priority. And though the compiler now has Unicode support, the language still needs to be adapted partially to it. The string type, for instance, will need to have its interface changed because it will use UTF-8; the random access (array) operator needs to go, and a replacement mechanism must be provided to be able to iterate over the characters in the string.

The compiler with back end has gotten some of my attention as well. It has inherited the new features from the 0.4.0 release and can do LLVM code generation for most expressions and statements, involving only the built-in types. User-defined classes, strings, floating-point types, and the 'iterate' statement are not supported yet. I have added support for printing single characters to stdout, so I wouldn't have to wait for full string support until I could see simple test programs working. Next thing I would like to be compilable is the eight-queens program.

My efforts will be mostly on the compiler back end now. I would like to have complete code generation for what the front end currently supports, and then I can merge the llvm-branch to the main-branch so that the main release is no longer front-end only. But I guess I will need to implement a solution for the iterate problem first.

The compiler sources are getting pretty big now. The main branch now has almost 44000 lines of code, and the llvm branch has about 49000 lines (not counting the LLVM sources, of course). That's a simple count, including header files, blank lines and comments. It's still quite impressive to me, though. My biggest project ever :-)

Status update & future directions

It has been some time since my last writing here. In the mean time there have been two compiler releases, 0.3.37 and 0.3.38. Most important new features from those are:

• double pointers (pointer to pointer, look here)
  
• pointer L-values and class L-values
• sorted diagnostics, with common directory prefix printed separately
• a new type of comment
• first steps of platform detection (32 bit or 64 bit)
  

The new comment type was introduced because of an annoying property that the existing line comments have. Suppose you have a small procedure (one ore two lines lines) you want to comment out. The fastest way is to put a hash character ('#') in front of each line. But this does not work if one of the lines already has a line comment behind it; putting a hash mark in front of the line cancels out the comment that already was there, it will no longer be treated as comment text. So I created a new type of line comment that simply reaches until the end of the line, ignoring any hash characters that are already there. You just type two hash characters (with no space in between). Isn't it simple?

The platform detection that was added is limited. If you have an amd64 (or derived) CPU, it assumes the HOST platform is 64-bit. If it is not, and you have an x86 or derived CPU, the HOST is 32-bit. And otherwise it produces an error, because your platform is not supported yet. Of course, support for more architectures will come later.

I have decided to require all source files be in UTF-8 format, unless specified otherwise (by a magic number in the file). This has not been implemented yet. The char type will most likely be represented by a 32 bit number (UTF-32/UCS-4). And string will probably use UTF-8, which unfortunately requires me to remove the random access functionality.

As you probably already know, I am working on a compiler with back end. Most basic features are implemented, such as statements and expressions, integral types and arrays. Some exceptions are the iterate statement and the chained comparison expression. I would like to see some simple programs compiled completely, but that is not possible yet. A simple program could calculate something and then print the result. But: I haven't implemented standard output yet, and I haven't implemented string types yet. The standard output only accepts strings, so strings are a dependency in this case. And if I have to implement strings, I need the char type supported as well.

Unfortunately there are some things I will have to change in the current implementation. I will need to change how the symbol table works, because it needs to support sourcefiles importing each other, making symbols visible and invisible again, etc. The current operator overloading mechanism for binary operators needs to be changed as well, because it currently requires to maintain a global list of all binops. So I will need to change their semantics; looking up a binary operator should be possible by looking at the operands instead of a global list.

The compiler's semantic processing will need to be restructured. This is how the front end currently works, in 4 phases:

1. Reading the source from file, lexing, parsing and AST building.
2. Doing resolve1 recursively: looking up typenames and calculating compile time array sizes
3. Doing resolve2 recursively: check for duplicate overloads, create default copy constructors
4. Doing resolve3 recursively: check all other semantics
   

I have thought of a better way of doing things. The first phase can remain, of course, but the other three need to be changed. I would create a single phase for all semantics. Each AST member would have two functions for semantic checking: one to check interface semantics only, and one to do all checks. Every function would have to check if it isn't in a circular dependency (such would require an error diagnostic of course) and if it hasn't been completed before (in that case it would not do the checks again). If the compiler is resolving some code that uses another class, it would only need to resolve the interface of that other class, i.e. only procedure and constructor headers, and fields. If a procedure is called, it would only need to make sure its interface was resolved. An expression's interface is its result type plus other result properties (L-value or not, compile time value or not, etc.) and those require a complete check, so for an expression there would not be a distinction between 'interface resolve' and 'complete resolve'.

There are other things to be solved as well: how to manage binary compatibility with the standard library, how to create an interface to libraries written in other language etc... These things will need lots of thinking.

Hyper compiler 0.3.35 released

It has been a long time, but here's another release. This one is nothing spectacular; most changes and improvements are internal and not visible to a user. I started to use the Boost libraries. The compiler and highlighter programs now use Boost's program_options library for parsing command-line parameters.

The lack of interesting new features in the front end is because I have worked on the back end as well. This work is in a very premature state, so you won't see a full compiler anytime soon.

Hyper compiler 0.3.34 released

There it is again, another release. It has some very nice new features. The most exciting new thing of this release is ironically not the compiler, but the syntax highlighter.

The syntax highlighter was, before this release, a very simple program. You gave it two file parameters: the first was an existing source file and the second was the name for the HTML file that needed to become the syntax-highlighted version of the original source code. The output file was HTML 4.01 transitional. The new version of the highlighter generates valid strict XHTML 1.0! It was an easy improvement, almost nothing more than replacing the doctype. OK, this change is not very important to most people. But a totally different functionality has been added as well.

The idea for a new feature came from the fact that writing documentation on my website is difficult. Explaining the language is a difficult and time consuming task. But writing example code to illustrate things was just horrible. It required manual construction of a "pre" tag with some sourcecode, interleaved with "span" tags for highlighting. And when an example needed to be changed the highlighting had to be corrected. I did not like this at all, so I figured out a way to have the syntax highlighter do this boring and error-prone task. Now I can write the documentation, have the examples as plain text in the HTML file in a special comment (so they are still very readable), and the syntax highlighter processes the HTML file and generates the highlighted version directly inside the file. Now when I change an example I can just change the sourcecode in the HTML file and then run the highlighter on it to have the desired result.

The changes in the compiler itself are mostly directed towards the back end that needs to be written. First, it now supports dynamic arrays. This is needed to be able to write container classes in the language. Checking for 'static' things is now complete as well. This is of course needed for code generation because for every non-static procedure call an object instance is required, so the compiler must be able to find it. Other important changes are mostly internal. Constant folding is now implemented for a small part of the types, and the operators of the built-in types are now represented as classes specialized for each built-in type. And also some bugfixes this time. I discover little of them, because I am (as far as I know) the only tester. You can of course improve this!

Hyper compiler 0.3.33 released

I have released a new version of the compiler again, we're at 0.3.33 right now. The version number is actually increasing less fast than before I did any releases. The first private release was 0.3.26, the first public release was 0.3.29, so this is the fifth release I have done. Before I started releasing versions I also incremented the version number, but this was a lot faster than it is now. For the same amount of changes that are now in one new release, I would have probably done about 6 or 7 version increments back then. I cannot do the same thing anymore of course, it would be silly to release a new version each time I have made a couple of trivial changes.

The changes I have made in the latest version of the compiler are steps towards a working code generator. I am giving priority to the front end things that are needed by the compiler back end. The first such thing in the release of today is checking for the program entry point. This includes checking a 'begin' specification if it is present, finding the 'static procedure main' and doing the necessary checks on it. Another improvement is a basic support for constant folding, except that no folding is done at the moment, but the compiler can already use unsigned integer literals in type checking. This feature is used by another one: checking of array sizes. You can declare arrays with fixed size and the compiler will check their compatibility. And the third important change is passing of parameters that are not to be changed, i.e. 'in' parameters. They are now passed by reference and completely read-only.

The next things on my 'to do'-list are real constant folding and constructor initializer lists. I suppose those are sufficient to allow me to start working on the code generator. I still have compilation problems with the LLVM tools as I wrote in my previous blog post. I don't think this will be a problem because the compiler front end linked with LLVM works perfectly. I can still compile the official version of LLVM and use its tools on the LLVM bytecode generated by my compiler.

Another thing: I don't really get any feedback of users yet. So if you try the compiler, please let me know what you think! Tell me the things you like, not just what you don't like. I have installed a visitor counter on my website some time ago, and it seems that I do have some visitors looking around. Yay! :-)

Hyper compiler 0.3.32 released

Today I have released a new version of the compiler. The most important new thing is support for the new namespace system. This means that finally all example programs are accepted by the compiler, including the new Hello World! Imports are not yet really supported; imports of user-defined sourcefiles are ignored, and the only allowed standard library import is the import of 'system.stdio'. The new compiler now also supports chained comparison operators, so you can now use code like:

if x = y = z then
# TODO : implement this
end

Another nice thing to have is that the compiler will generate a warning by default for this code. Something like:

file.hyp:3:2: warning: TODO: implement this

The compiler will actually notice 'TODO' or 'FIXME' in comments and generate warnings for them. In my opinion warnings provide useful information so they are enabled by default. But you can turn them off individually if you like with a commandline switch like "-W-no-todo".

As you can see the compiler still isn't at version 0.4.0 yet. Well, I have chosen for a different approach. I will keep releasing the front end of the compiler as I am doing now, and I will develop a version of the compiler with LLVM back end in parallel. The version 0.4.0 will be given to a release that marks an important event for the front end; maybe when I am ready to start the implementation of more advanced things like inheritance. I do not plan to release the version-with-back-end to the website soon because it will be completely unusable until some time in the future. And if no one cares anyway, then why bother releasing it?

Hyper compiler 0.3.31 released

I have released a new version of the compiler. This release is fairly bigger than the previous one. It contains more new features and has undergone internal structure improvements.

The compiler now checks for the presence of return statements in procedures that return something. Another very important new feature is public/private access checking. Some small things are not checked yet, like for example the usage of private conversion constructors for passing arguments to a procedure. And const checking is now complete (at least to my knowledge), which means that the compiler does additional checks for const procedures and calling procedures on a const object.

Some things that are not listed in the changelog: a new test program was added, the Hello World test program. This already uses the new import and namespace semantics so the compiler currently rejects it. And the compiler now allows import directives but currently ignores them.

Hyper compiler 0.3.30 released

I've just released a new version of the compiler for Hyper. You can download it from here.

A short list of changes in this release:

• highlighter now uses the same style as the Hyper website
• copy constructors are now checked and auto-generated if needed
• 'inout' is now used for parameters that used 'var'
• the 'this' keyword is now supported in expressions
• access specifiers in a namespace are no longer supported

And next to these changes, the compiler has been restructured internally a bit as well.

Compiler goes public!

Yesterday I put the compiler sources on my website. The compiler is finally available to everyone who wants to take a look. You can download the sources from here. The released version is 0.3.29, a release that already dates from mid-september, but was only available to some limited test audience. I got almost no feedback, so I figured I could make it already available on my website to have a larger potential of testers.

As said on the download page this is a development release so it probably has lots of bugs, and on top of that it doesn't support all 'official' language features yet. It also requires CMake to build. You will have to build it yourself from source because no precompiled binaries are available.
Another thing you need to know is that the compiler only accepts filenames in Unix format. So Windows users will have to use the compiler under Cygwin until Windows filenames are supported in some future release.

If you are a programmer, I hope you will try it and give some feedback! For information about the language, see the language reference on the website. The documentation you find there is not really complete at this time and is sometimes very brief but it will give you a start.