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\Test.java:1051: <?,?>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 <
frege.rt.Fun<?,?>,?>(test.Test.tMaybe<frege.rt.Fun<?,?>>,â2805_27<frege.rt.Boxed
<java.lang.Void>>)
     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.





No comments:

Post a Comment

Comments will be censored by me as I see fit, most likely if they contain insults or propaganda for ideologies I do not like. Comments that are on topic will not be censored. If I leave a comment uncensored this does not imply that I agree with the opinions expressed therein.