Friday, September 28, 2007

What is frege (or what will it be)?

Frege is a functional programming language in the spirit of Haskell for the Java Virtual Machine. The language design and a compiler evolved in my spare time over the last few years.

It all began in 2004, when I read the paper Practical type inference for arbitrary-rank types by Simon Peyton Jones. I had always asked myself how compilers for strongly typed languages like Haskell or ML manage to find the type of every expression in a program, so that the programmer does not need to declare types. Now I knew.

The example implementation that comes with the paper was in Haskell, of course. However, being a perl programmer then, I asked myself if it wasn't possible to write a type checker in other languages as well. It took not too long until I had written down the essence of the paper in perl.

Now I had a perl program that could typecheck expressions, albeit expressions in a language that was existent only in imagination. In order to typecheck something, I had to write some perl code that created a syntax tree and handed that over to the typechecker. Clearly, this was inacceptable. The more so, as I was familiar with parser construction for long. Why not write a small parser as frontend for my typechecker?

And so it evolved and grew more and more. The day came when I had a perl program that compiled functional code to perl. (How well perl is suited for functional programming is explained here).

Unfortunately, it turned out that the compiled perl code was very, very slow.
Since the days when PASCAL appeared as a new programming language I had always been strongly convinced that the best test of a compiler was to be written itself in the language it compiled, so it could compile itself. But my compiled perl code was so miserably slow that I soon gave up the idea of a self hosting compiler.

By that time I felt the need to refresh my Java skills. Java 5 was just out, likewise a version of Eclipse that supported it. So, rather than porting my compiler to Frege, I ported it to Java first. I also changed the target language to Java.

This proved to be very successfull, and now, a few months later, for the first time, I could compile the Frege compiler with the intermediate compiler wirtten in Java, compile the same source code with the compiler just compiled, use the result of that compilation to compile the source code again and finally run a diff over the java files produced. When the diff remained silent, the hard work was done.