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.