Thursday, December 22, 2011

Frege meets Eclipse

In this last post of 2011, I want to talk about my work on the upcoming Eclipse plugin for Frege -- codename fregIDE.
Update Jan 15, 2012:  fregIDE is meanwhile available for download, for details see the tutorial.

As I wrote in the previous post, I am using the IDE Meta Tooling Platform (IMP) and it looks like this was a fair choice. The  approach of IMP is very appealing (to me, anyway), here is a quote from their web page:
IMP lets you focus on your language, not Eclipse componentry.
IMP interfaces keep you focused on the stuff you know best: your language, and your models. Almost all of the complexities of Eclipse are hidden from you.
Although the last sentence is a bit of an exaggeration, it was indeed easy to get an editor with syntax coloring and error marking working. The most work to do here was on the Frege scanner. The scanner used to record line number and column for each token, but the syntax coloring mechanism requires source code offsets.

It turned out that I would need to keep the list of tokens to accommodate the way the Eclipse/IMP editor works: when there are any changes in the text (like when one types a character), it calls the component one has to supply called the Parser, which has to return a reference to something that is supposed to be an abstract syntax tree. Yet this value is never inspected or interpreted by IMP itself. Rather, it is given to other user supplied classes,  like the syntax coloring class. For example, IMP gives the value it got from the parser to the syntax colorer and says: I've got this from the parser, could you extract from this a token iterator for me? And later on, it calls a method that is supposed to color a single token and passes one of the tokens extracted from the iterator, where the type of the tokens is also opaque to the framework.

This approach is quite different from other frameworks I researched. For example, XText requires one to write the language from scratch with their own supplied tools. This may be nice when developing a small DSL that should forever live within the Eclipse world, but is completely inappropriate if one already has a compiler. IDEA apparently requires that one fits the language one wants to have supported in a Procrustean bed of interfaces they supply.  And so on.

Conversely, because the Frege compiler is essentially a computation in a state monad, it was too easy to fulfill the needs of the IMP. Just add a new field to the compiler state for the token list (that up to now used to get passed to the parser right away and then was forgotten), write a small helper class that implements the Iterator<T> interface and iterates over Frege lists and that was that. The abstract syntax tree is, of course, nothing but the compiler state. The IMP Frege parser (i.e. compiler driver written in java) does in essence nothing more than what the batch compiler driver does: it goes down the list of compiler passes and executes one after the other.

In short, I had to do only very small changes on existing compiler passes (with the exception of the scanner, see above). I just separated the concerns of compiler passes and compiler driver a bit clearer. For example, instead of just printing error messages to standard error, the messages are now collected and the compiler driver decides what to do with them. The batch compiler driver still writes them to standard error, while the fregIDE compiler driver creates error annotations in the source code editor.

This looks all very promising and I hope to provide the community with a basic version of the fregIDE early next year, which will then get enriched with features over time. The initial version will have project and preferences management, the editor with syntax coloring and live error markers and last but not least an incremental project builder. Support for run configurations will come for free because a Frege Project can only be established on top of a Java Project.

Sunday, November 20, 2011

Frege Release 3.18.0 available

As announced earlier, code generation has been completely rewritten. The results are
  • Fewer classes are being generated. For example, the distribution used to include 14.000 classes, now there are about 9000. As a consequence, the Frege jar is now noticeable smaller.
  • All known bugs that caused generation of  Java code the Java compiler would complain about are fixed. I strongly urge anybody who encounters errors of any kind and particularly errors that show up in the Java compilation stage to inform me about it, preferably by posting an issue.
Please visit the download page to grab the latest release. Note that because there have been substantial changes in the run time system, you cannot run Frege code compiled with earlier versions. Please recompile all you have.

The focus in the coming weeks will be on experimentation with IDE support. I'll explore how far I can get with the Eclipse IMP technology. As far as I can see at the moment, this will require quite some adaptions in the compiler. I'm really curious to see how this will turn out.

Thursday, October 20, 2011

Frege and Java Generics

Early on in the development of the Frege compiler, I decided that the compiler would produce Java source code, which would be compiled subsequently by a Java compiler fired up with Runtime.exec().

The reasons for this decision were manyfold:

  1. I could save a huge amount of work by not programming byte code generation, even if there exist excellent libraries for this nowadays.
  2. The Java compiler would check whether the code produced by Frege code generation made sense.
  3. If it did not make sense, one could easily see it, by just looking at the java code, which, incidentally, contains also the desugared Frege code in the form of comments.
  4. Last but not least, for an old-fashioned UNIX hacker like me, it felt like the most natural way to do.
But it turned out, that I stretched the second point  too far, when my ambition was not only to generate correct Java code, but to generate type safe (in java terms, that is) java code. I had not considered that java generic types are not  powerful enough to reflect higher ranked, higher kinded polymorphic types like they occur in Frege programs.

A first warning came early, when the Java 6 compiler complained about syntax errors. It turned out that this was instead a Java compiler bug. Astonishing, a few years after introduction of generics in the language! Worse, the bug would only get fixed with JDK7. See my stackoverflow post for details.
Fortunately, at this time the JDK7 preview was already available, so I downloaded that and continued with JDK7.

Some days later I discovered that I could not express the type of a class method of a constructor type class, like this:

Here, the type variable f stands not for a type, but for a partially applied type, like Maybe or [], and the variables a and b are like the element types.
As I had to learn this way, Java has not the slightest idea of how to apply a type variable to a type. I wasted a week or so trying with something like
but other difficulties arose I can't recall exactly, but they were insurmountable.

Not enough that type applications would not work with variables, partially applied types would not work either.  Don't ask what I experienced with higher ranked function types like

Yet, my desire to see Frege compiled code run finally, and, when this was achieved, the aversion against throwing everything away and starting anew, seduced me to write one workaround after the other, every time in the hope it would be the last one. For example, I introduced methods like this:

that are called at various places to "instantiate" polymorphic functions at the required type just to make javac happy. This made the code even uglier, but finally seemed to work.

Until recently, when one of the committers of the Frege project found a number of bugs, and two or three of them were of the sort where the Java compiler flags type errors. Today, he sent me another error report with the following compiler message:

.\test\ <?,?>w(test.Test.tMaybe<?>,frege.rt.Lazy<frege.rt.Fun<?,t
est.Test.tMaybe<?>>>) in test.Test.iMonad_Maybe._gt_gt_eq cannot be applied to <
     return iMonad_Maybe._gt_gt_eq.<Fun<?, ?>, ?>w(_arg1, _â2805_27)._e();

Yes, it can be applied, I just can't prove it in Java!
Time for a new code generation without generics, but with unavoidable explicit casts in the right places! This will mostly be a matter of stripping the generic overhead of maybe 30% to 40% off the current code generator.

Saturday, October 15, 2011

Improved import declarations, plans for future developent

With Revision 202, the functionality of import declarations has been extended.

  • Items in data and class namespaces can be selected by name. 
  • It is now possible to re-export imported items. 
  • Everything that can be imported can be aliased for use in the current package.
Taken together, this will make it possible to create packages that provide an interface to some library consisting of arbitrary many sub-packages, so that implementation details remain hidden and full functionality of many modules can be imported with a single import.
Unfortunately, changes in some module of a library that are not merely additions will continue to break binary backwards compatibility of the client modules that are compiled against an earlier version. This is due to limitations of the JVM, where all classes, methods and so on have only one name.
The new features are documented in chapter 5 of the language reference.

Next steps in development will be:

  • Apply the new import features to the Prelude (which will be just an interface to some most basic modules) and evolve a standard library that should cover most of Haskell's, where applicable and desirable.
  • Explore the possibilities of Java7 method handles. I see 3 areas where they could be useful: 1) better performance for higher order functions and partial function applications - some measurements suggest that programs may spend 25% or more of their time constructing and evaluating thunks  2) great reduction of the number of class files resulting from compilation of a Frege module - currently, every function is compiled to a class 3) as a technical means an interpreter could employ in interpreting user input that contains references to already compiled code such as library functions.
  • Compiler support for import of whole Java classes along with their methods and static values. This will not only save typing, but also promote a canonical way how to map Java APIs in Frege. 
  • Type system support for some basic subtyping relationships - for example, one should be able to pass a BufferedReader as argument to a native function that takes a Reader.

Saturday, October 1, 2011

Bug fixing

As people start playing with Frege some errors in the compiler are exposed. Some of them are merely usability issues, while others are more critical.

For example, somebody tried the following:

fib n = case n of -> n  -> n
    _ -> ....

I had not anticpated this possibility, so the compiler treated this like:

fib n = case n of
    z -> n
    o  -> n
    _ -> ....

and only complained about unreachable case alternatives. Of course, fib degenerated to another identity function this way. The right thing in this case was to refuse the program on the ground that pattern bound variables must not be qualified.

As I strive to correct errors as soon as possible, we had around 7 new versions of the frege*.jar in the last 14 days. I am sorry for that, but I hope error corrections will occur on a slower and slower pace. When one looks at the source code commits one sees also that almost all corrections are but small fixes. Nothing required fundamental changes up to this day.

I appreciate very much your feedback, even if it takes the form of an error report. As mentioned on the project home page there are now the following ways to communicate:

  1. use, make sure to label your question with the "frege" tag.
  2. send an email to me (Ingo.Wechsung, I am using the mail service offered by
  3. Create an issue on the project page. (But consider to try the previous options first.)

Thank you all for your contributions in finding errors and  for your patience with runtime/compiler downloads that are updated often.

Thursday, September 22, 2011

Frege supports now Haskell style comments

From the feedback I received so far I learned that it would probably be a good idea to make porting Haskell code  to Frege as easy as possible. Which means, not harder than unavoidable.

One of the maybe most annoying differences on the lexical level has been the Java-ish comment syntax. This has been fixed today, and from now on Frege recognizes only Haskell style comments anymore.

Yes, this is a backward-incompatible change. I did it under the assumption that there is not much Frege code around there yet.

For those of you who have already written lots of well-documented Frege code there is a tool to convert old comments  to new ones in files specified on the command line. Conversions may be incomplete if one has identifiers with an odd number of apostrophes at the end, as I had to note during conversion of the compiler sources.

Monday, September 19, 2011

Parallelism in Frege employing the fork/join Java API

Yesterday I implemented some experimental support for the fork/join API that comes with JDK 7.

The base operation from a Frege point of view is par. An expression like

a `par` b

arranges for evaluation of a in another thread and returns b, like in Haskell.
For example, a parallel map can be implemented like this

pmap f [] = []
pmap f (x:xs) = a `par` as `par` (a:as) 
        a  = f x
        as = pmap f xs

Unlike the ordinary map, pmap works only on finite lists, because construction of the tail implies immediate construction of the tail of the tail and so forth.

There is an example program in the distribution that implements different algorithms for computing the number of solutions to the n queens puzzle. I added a parallel version of the list based solution and measured the resulting run times. The parallel version constructs n different start out positions where the first queen is placed on a different column of the first row each time, and computes the solutions for the n start out positions in parallel. Then it adds the results.

I have a computer with 2 "hyperthreaded" cores. The JVM deduced from this that the parallelism must be 4 and starts 4 worker threads. During program execution, I saw a CPU utilization of around 75%. This already saved 50% of the run time in medium sized problems (up to n=13).

I then arranged it so that 2 threads will be created for every "CPU", and noticed an overall CPU utilization of 95%. The savings in run time tend to manifest themselves better the  greater the problem is and seem to approximate  2/3. But this numbers will most likely depend on the hardware and maybe the OS.

In small problems that take less than a second in the sequential version (i.e. n=8), the run time differences are barely noticeable.

There is also the possibility to prohibit the Frege run time from actually executing anything in parallel by passing a system property -Dfrege.parallel=false in the command line. The par operator will then effectively behave like

a `par` b =  snd (a,b)

The feature is included in the frege3.17.152.jar available from the download area.

Thursday, September 15, 2011

Friendly Reception

Last weekend, a person unknown to me announced our project on reddit:::haskell. There were about 40 comments, the most of them were positive, interested or even excited.

To answer questions and, most importantly, combat the impression that the project is not active anymore, Wulf and me decided to get us a reddit account (voxfrege).

One topic discussed more extensively was that small differences between Frege and Haskell are  considered annoying for Haskell programmers. Paradoxically, those differences seem to be the more annoying the more "like Haskell" Frege is.

One key example for this is the comment syntax. I am willing to reconsider this and other topics like this as soon as possible (while there is not much code out there yet). Indeed, the opinion expressed that Frege is most interesting to "weekend/would-be Haskell programmers" who are locked with the JVM in their daily jobs, seems to be confirmed by the fact that the same announcement linked to reddit::java did not get a single comment up to now!

Saturday, August 20, 2011

Frege runs with JDK7

As promised, Frege now runs with the JDK7.

Actually there is currently nothing (like library dependencies) that would require JDK7, were it not for the buggy JDK6 compiler.

It is well possible that one may compile all stuff with another compiler. Even a JDK5 compiler could do, if it gets the java syntax right.

Sunday, May 15, 2011

Going public

Today I have published all I have on Google Code. Hence, I'll use the cloud as SVN repository from now on.

A preliminary version of the compiler and (incomplete) documentation can be downloaded from there.

Any feedback, criticism, etc. is welcome. When you leave a comment I'll get an email and will come back to you.

Friday, April 22, 2011

Compiler successfully compiles itself

In the last weeks I was busy to complete the compiler, and now the hard work is done. The compiler compiles itself, then the compiled compiler compiles itself, then that compiled compiler compiles itself and so forth.

Hence, I am now in a position to get rid of the old Frege2 compiler and have a self sustained Frege3 environment. I have also successfully ported QuickCheck

Next steps:
  • clean up the code so it has no warnings
  • get rid of code that was needed to be backwards compatible with Frege2.
  • write properties for Prelude functions
  • make a comprehensive list of differences to Haskell, while doing this adjust Frege to be as close on Haskell as possible.
  • complete documentation
  • evolve library slowly
  • ....

Wednesday, January 12, 2011

Revision 100

On December 16th, I checked the code into a new SVN repository. I had previously used CVS, but even for me some things are too old-fashioned.

And today, I committed revision 100. Some revisions are only 1 or 2 line bug fixes, others are dozens of added lines.

Major achievements since I last posted are:
  • exporting of meta data in the form of java annotations (for the Prelude with its many classes, types and instances some 8000 lines of annotations are written, which causes the compiler to spend  1 or 2 CPU seconds in the pretty printer alone)
  • import of the java compiled meta data from class files. This takes only a few milliseconds.
  • Type checker infers and validates class constraints more or less correct.
The day is not so far anymore when the first real java code line will be written! Up to now, it's only annotations followed by an empty placeholder class.

Incidentally, with revision 100 the compiler can parse and type check its own grammar, which is currently 35798 lines or  225832 tokens. This takes 90 seconds, which is quite long compared to 80 seconds with the old compiler especially when one takes into account that we have no strictness checking and code generation yet.

Apparently, the unoptimized monadic style has its costs. No wonder, as it is essentially a series of tail calls, which are currently implemented with two runtime functions tcLoop and tcGoto that throw and catch TailCallExceptions. It looks like the JIT can't do a very good job in the presence of exceptions.
Hopefully, the new code and runtime will be better suited for tail call intensive code.

Sunday, January 2, 2011

Milestone: Type Checking Works

I implemented type checking over the past days and today I was able to type check the frege/ successfully. These are about 2600 lines of Frege code with the most basic definitions - basic types, list operations, common classes and instances for various types - hence almost all language features are used here.

At the moment, the type checker ignores class constraints. The constraint handling will be very different from version 2, so I will perhaps need lots of tracing while implementing it. I want to avoid doing the tests on the Prelude itself  because the tons of trace output I would get then are not easily manageable.

Therefore, I must be able to compile small test programs that import the Prelude. To import something, I must first generate the meta data (which are custom Java annotations) and compile them to a class file.

Thus, the next milestone will be the GenMeta pass. This will be new territory also. In version 2 I exploited the fact that the javac of Java 5 had a bug that made it let pass recursive annotations, although they are forbidden.
It comes down basically to replacing all recursive fields in patterns, expressions and types with indices into appropriate arrays that hold the atomic elements.