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.

Launchpad

As the title of this posting says, I have registered a project on Launchpad for my programming language Hyper:

https://launchpad.net/hyper

The main website for the language is still here:

http://users.edpnet.be/hyperquantum/hyper/

Why Launchpad instead of, say, Sourceforge? Because Launchpad is one of the few websites that has support for the Bazaar version control system. So I can easily upload the code to Launchpad with a simple "bzr push", and anyone can easily branch from it and make his own changes. And it's always nice to have an extra backup of my code :)

The project will probably slow down in the near future, as I have graduated now (masters degree, computer science) and am looking for a job.

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 :-)

iterate revisited

I am going to talk a bit about the iterate statement in this post. If you don't know what it is, look at the web page behind the hyperlink.

The iterate statement was derived from the FOR statement from PASCAL and BASIC (and their derivatives). I had to generalize it in order to allow it being used with user-defined types instead of just numbers; my intention is to have it support the behavior of 'foreach' in some other languages. So I came up with some scheme to support the use of iterators. I defined some operators that need to be supported by the types used in an iterate statement. For example:

The variable should be initializable by the from-expression. The variable should support increment when using "step ++". The variable must be able to be compared to the to-expression. In an "iterate v : t from x to y step z" the compiler would first compare x and y, to see which one is the largest value. If x <= y then the step would be considered to be an incremental value, and otherwise a decrementing value. And there are operators needed that can decide when the to-value is reached for both cases; so you would need comparisons v <= y (for an incrementing step) and y<= v (for a decrementing step) to be available. But this scheme is not good enough. When I came up with this I assumed the use of a "begin" and "end" iterator, where the "end" iterator should point at the last element of the collection. In C++ the 'end' iterator points one past the last element. I thought that my change would not be a problem, but I forgot to think of what would happen when iterating over an empty collection. Such a collection does not have a first or last element iterator!

So I will have to change the current way of doing things. One possible way is having the 'end' iterator should be done as in C++, and point to one past the last element. This means an iterate will look as follows:

iterate v : c.iterator from c.begin to --c.end
# do something
end

It would require the programmer to remember using a "--" in front of the "end" iterator, because the "end" iterator does not point to a valid element in the collection. The iterator also must support the predecessor operator, but what does it return when used on the "end" iterator in an empty collection?

Another possibility is having iterate extract some other info from the collection before starting the loop. It could first query the iterators for the instance of the collection class they belong to (and both iterators must return the same value) and then ask the collection class whether it's non-empty and skip the loop if it's not. But this would require allowing invalid iterators returned from the collection in order to return their collection object when the collection is empty.

And a third option would be to specify the collection object explicitly in the iterate statement itself. Something like:

iterate i in c
 # do something for each element
end

# - or -

iterate i in c from someStartIterator  # optional "to" or "step" omitted here
 # do something for each element, starting from some given iterator
end

This would need an extra keyword "in" (already silently supported by the latest compilers), and some predefined methods in the collection, required by the iterate statement for determining the non-emptyness of the collection and its start and end values. It would not change the existing iterate behaviour but only extend it.

I don't know yet what I'll choose as the solution. Maybe you'll see the change as it appears in a new compiler release, or maybe I'll write about it before I implement it.