State of Frege 3.24

[Ingo W.]

Hello all,

I had hoped to be able to complete the new backend so that I would be able to deliver the new version at the start of this year.

However, there were numerous unforeseen difficulties I had to fight with, so I'm a bit late.

Nevertheless, I can already compile the Prelude and the first results are quite promising.

We will probably see substantial speed gains between 20% and 60% and the jar sizes should get cut to 50%.

I will continue to develop this further, but due to the now ending christmas holidays at a slower pace.

Meanwhile, I wish all Frege friends a Happy New Year!

Ingo

[Dierk König]

Great news!

Cheers
Dierk

> --
> You received this message because you are subscribed to the Google Groups "Frege Programming Language" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to frege-programming-l...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Marimuthu Madasamy]

Hi Ingo,

> We will probably see substantial speed gains between 20% and 60% and the jar sizes should get cut to 50%.

This is great! The speed gains, I guess, are because of Java 8 lambdas? Are Frege lambdas now compiled into Java lambdas? If not all, for most of the cases? I am sure that the release notes will have all these details but I am just curious about how this performance gain is achieved in this release :).

Happy new year all!

[Ingo W.]

To tell the truth, it's a mystery to me how exactly the speed differences come about.

The most dramatic change from 3.23 will be that the generated Java code will be fully generic, with the exception of higher rank functions, where the forall type variables are replaced by certain pseudo types. 

This  has a number of interesting consequences ... I'll lay that out in detail in a new "How to call Frege vom Java" later. The idea is that the whole thing should be much easier since your IDE can tell you exactly what type the function has that you are calling. It can tell you also exactly what the result type is.

For example, here is like some well known list functions look like:

final public static <α> boolean elem(PreludeBase.CEq<α> ctx$1f, Lazy<α> arg$1, PreludeBase.TList<α> arg$2) { ... }

final public static <α, β> PreludeBase.TList<α> map(final Func.U<β, α> arg$1, final PreludeBase.TList<β> arg$2) { ... }

final public static <α, β> α fold(Func.U<α, Func.U<β, α>> arg$1, α arg$2, PreludeBase.TList<β> arg$3) { ... }

You get the idea. 

Now, the crucial point seems to be the implementation of the function type (higher order functions will generally appear as unary (curried) function type Func.U). Whereas up to now, every apply() created a thunk (i.e. Delayed), the functions in 3.24 are just nested lambdas, and always return the evaluated value. This, in itself, seems to save lots if intermediate thunks, and the access to the arguments from outer lambdas are maybe faster through closures.

Anyway, it's not the Java8 lambdas themselves! We do actually have 2 different implementations of Func (unfortunately, I tried to avoid it, but there is no way, since for complicated reasons functions must implement the Lazy interface with method call() from Callable. Sure, I can write the default method in the Java8 code, but then it doesn't compile in or for Java7. Likewise, I can write a plain old interface with methods apply() and call(), but then Java8 refuses to accept this as functional interface.) So I have the compiler import either frege.run7.Func or frege.run8.Func, depending on what the target is. And when the target is 1.7, then it simply pretty prints the generated lambda expressions as 

    new Func.U<A,B> { public B apply(Lazy<A> arg) { ...})  --as before,but with generic types

So, I ran some tests based on the same Frege code. The first one compiled with 3.23. The second one compiled with the pre-alpha 3.24 with target 1.7, and the third one with target 1.8. And surprisingly, while the old code is always substantially slower, there is no significant difference between the new java7 code and java8 code!

As always, I learned some interesting things about Java. For example, did you know that you cannot reference a final static member variable from within a lambda expression in its initializer? but with the old fashioned new Func.U() { ... } syntax, you can. (Why in the world is this so?)

 BTW, it should be possible to checkout the gen8 branch and make the compiler. This will then be the old compiler plus some passes (most prominently the code generation) that do the new stuff and get activated with command line flag -experimental.

To run the future compiler, use the following flags:  -prefix xx -sp next/:. -experimental

The prefix makes sure it compiles to build/xxfrege etc. and doesn't overwrite the 3.23  code.

The -sp is needed because of some necessary adaptions to library files, and makes sure the compiler uses the future versions when compiling with -make and also if you just give the module name instead of the file name. Source files that have counterparts below next/ will probably not make it through javac when compiling them with -experimental. 

And finally, the -experimental flag selects the new code generator.

But please don't open any issues regarding this. There are certain problematic constructs that can't be compiled yet. Likewise, -inline or -O doesn't seem to work at all currently. It's just still "experimental". 

Regards, Ingo

[Marimuthu Madasamy]

Thank you Ingo for the detailed reply.

> generated Java code will be fully generic

Surprised that Java generics is even capable of representing Frege types (even basic ones). I remember you telling us before that with Java generics, the Java compiler failed to compile even valid code with Java 6 which I hope now is not an issue with latest versions.

> So I have the compiler import either frege.run7.Func or frege.run8.Func, depending on what the target is. And when the target is 1.7, then it simply pretty prints the generated lambda expressions

Nice! so the lot of new work happening on 'gen8' branch could actually be used with Java 7 also. I thought the 'gen8' branch is specifically targeted for Java 8 so that is not the case which is great! I periodically check out the commits on this branch to see what is going on even though I don't understand much of the change :)

> And surprisingly, while the old code is always substantially slower, there is no significant difference between the new java7 code and java8 code!

surprise indeed! I would've thought that the Java 8 code would be substantially greater in performance.

> For example, did you know that you cannot reference a final static member variable from within a lambda expression in its initializer?

Not sure I understand this. The following actually works which I think is not what you describe:

public static final List<Integer> xs = asList(1, 2, 3);

public static final Function<Integer, Boolean> f = n -> xs.contains(n);

> it should be possible to checkout the gen8 branch and make the compiler. 

Great! I will try it out some time.

[Ingo W.]

Am Dienstag, 5. Januar 2016 07:22:56 UTC+1 schrieb Marimuthu Madasamy:

Thank you Ingo for the detailed reply.

> generated Java code will be fully generic

Surprised that Java generics is even capable of representing Frege types (even basic ones). I remember you telling us before that with Java generics, the Java compiler failed to compile even valid code with Java 6 which I hope now is not an issue with latest versions.

Yes, it was a fault in the Java6 compiler who failed to recognize even mildly complex generic type expressions. This is now apparently working. 

However, most funnily, the generated program code consists of endlessly long type expressions.

But most importantly, I've found a way to represent higher kinded types, look at frege.run.Kind.

Granted, there are some casts and type coercions needed at times, when the Java type language is not powerful enough. For example, I cannot say that, for all A it is the case that TList<A> and Kind.U<TList<?>,A> are simply the same type. I can only say that List<A> extends Kind.U<List<?>, A>. 

> So I have the compiler import either frege.run7.Func or frege.run8.Func, depending on what the target is. And when the target is 1.7, then it simply pretty prints the generated lambda expressions

Nice! so the lot of new work happening on 'gen8' branch could actually be used with Java 7 also. I thought the 'gen8' branch is specifically targeted for Java 8 so that is not the case which is great! I periodically check out the commits on this branch to see what is going on even though I don't understand much of the change :)

Yes, but as said before, you can either have it as java7 or java8. You can't, for example, compile Module A with target 1.7 and module B with target 1.8 and use them together, because the Func types used are simply not the same.

> And surprisingly, while the old code is always substantially slower, there is no significant difference between the new java7 code and java8 code!

surprise indeed! I would've thought that the Java 8 code would be substantially greater in performance.

No, it isn't.

 

> For example, did you know that you cannot reference a final static member variable from within a lambda expression in its initializer?

Not sure I understand this. The following actually works which I think is not what you describe:

public static final List<Integer> xs = asList(1, 2, 3);

public static final Function<Integer, Boolean> f = n -> xs.contains(n);

No, think of the following top level definition:

    a = 1:a

Now, the compiler is smart enough to see that a is self-referential and arranges for this being a thunk, as before, for example, currently it does:

final public static frege.runtime.Lazy a = 

  new frege.runtime.Delayed() {

    final public frege.runtime.Lazy eval() {

      return PreludeBase.TList.DCons.mk(1, Console.a);

    }

  }

;

Now, you would think that we could replace the new Delayed() ... with a Lambda (supposing that Delayed was a Functional Interface), but it doesn't work. It would complain about the mentioning of Console.a inside the Lambda. Hence, in that case, we simple use the old syntax.

    

    

[Ingo W.]

Meanwhile, the work was delayed again by the low quality of the java8 compiler. I tried various versions from Oracle and OpenJDK, but it's always the same.

 

The point is that it either aborts with NullPointerExceptions (note the irony), or it produces bytecode that doesn't pass the byte code verifier. I can't really tell which one is worse. At least the VerifyError form the JVM gives an indication where the problem might be, whereas the NullPointerException just prints the stack trace, and that was it then. Go figure for yourself what the problem is in a source file with 1000s of LOC!

To be sure, the VerifyError is especially mean, since it doesn't occur before the affected class is loaded. This means your program could run for hours, and then, suddenly BOOM, CRASH.

The eclipse compiler also aborts on the same files where javac8 aborts. I haven't checked if the code it produces for the files where it doesn't abort leads to VerifyError.

I've lost almost two weeks now in attempts to work around this by generating code that is better suited for javac8, but it's hopeless.

Today I tried with an early access version of Java9, and, ohh wonders! It turned out to work, and I could roll back all changes I had made so far in order not to  displease javac8. Hence it also turned out that the code I produced was and is 100% correct in terms of Java. And it runs with a JVM 8, which seems to be slightly faster than the JVM9 at this time.

So we will have two options:

a) generate java7 code. Everything can be done with a JDK-7 or higher.

b) generate java8 code. You need a JDK-9 to do this (or at least a javac9), but you can run the result with JRE-8.

I do not really hope for a corrected javac8 in the remaining year before java9 comes out. So developers will probably have to live with jdk9 early access tools, unless they decide to develop in and for java7 only.

The difference between the java7 and the java8 code is that the latter uses Java lambdas where the former uses instances of anonymous classes. In fact, the abstract Java code generated for both is the same, it's just printed differently. It turns out that the speed of both versions is the same. The code size, however, is quite different. For the compiler itself it is about 6 times higher for the java7 version. This is due to the numerous class files created for the anonymous class creation expressions.

Here are the numbers for the compiled compiler comparing 3.23 (old) code, new java8, new java7: 

Size on file system:  77M 22M 122M

Number of class files: 16633 2129 27499

Size as JAR: 17M 5,7M 28M

[Dierk König]

ok, that kind of means that we have to prevent Frege users from accidentally generating Java 8 code with javac8, right?

Does that mean that we have some kind of decision in the compiler itself
or do we distribute two different compilers such that
javac7, javac8 -> generate Java 7 code
javac9 -> generate Java 8 code
?

Will that still work when people have mixed codebases built from different compilers?

cheers
Dierk

[Ingo W.]

Am Samstag, 16. Januar 2016 10:24:43 UTC+1 schrieb Dierk Koenig:

ok, that kind of means that we have to prevent Frege users from accidentally generating Java 8 code with javac8, right?

Yes. Not sure yet how to do this, though.

 

Does that mean that we have some kind of decision in the compiler itself
or do we distribute two different compilers such that
javac7, javac8 -> generate Java 7 code
javac9 -> generate Java 8 code ? 

We will indeed have two different artifacts.

Though both of them do the same thing.

When you use the compiler, you can specify the -target environment to produce code for.

It defaults to the java version of the JVM the compiler is running in.  

Will that still work when people have mixed codebases built from different compilers?

The critical point here is lambda support or not. You can't compile a module with -target 1.7 and then import it in a compiler run with -target 1.8. It also doesn't work the other way around. Yet with 1.8 and 9 this is no problem.

The fundamental reason for this is that the very basic interfaces used in the compiled code (Lazy and Func) are different, depending on the support in the java compiler for lambdas, functional interfaces and default interface methods.

The implication is that you need to decide on your target platform (one with or without lambda support) and depending on that, select the frege compiler and the JDK you use. As far as Frege source code is concerned, this decision can be reverted any time, by recompiling everything with another frege compiler and/or JDK.

[Hilco Wijbenga]

Have you thought of using RetroLambda (see [1]) and perhaps Animal
Sniffer (see [2]), specifically its Java signatures (see [3])?

[1] https://github.com/orfjackal/retrolambda
[2] http://www.mojohaus.org/animal-sniffer/animal-sniffer-maven-plugin/
[3] http://www.mojohaus.org/animal-sniffer/animal-sniffer-maven-plugin/examples/generating-java-signatures.html

[Ingo W.]

For what purpose, exactly?

[Hilco Wijbenga]

On 16 January 2016 at 14:34, Ingo W. <ingo.w...@gmail.com> wrote:
> For what purpose, exactly?

To perhaps be able to compile with a higher version compiler but end
up with Java7 class files? You could use, say, lambdas but at runtime
you would still be able to use Java 7. It might allow you to
(partially?) work around the problems you are having?

I just wanted to make sure you were aware of RetroLambda since I have
found it very useful to keep supporting Java6 while using Java8
features. But if it is of no help for Frege, then forget I mentioned
it. :-)

[Ingo W.]

Hi Hilco,

Am Sonntag, 17. Januar 2016 01:13:29 UTC+1 schrieb Hilco Wijbenga:

On 16 January 2016 at 14:34, Ingo W.  wrote:
> For what purpose, exactly?

To perhaps be able to compile with a higher version compiler but end
up with Java7 class files?

We can do that already. The problem we're currently having is that javac8 is broken, as explained.

Regards, Ingo

[Russel Winder]

Is there a big report that can be made?

If things are still the same, Oracle disallow bug reports by the
general public on the OpenJDK bug reporter. This has been a bone of
contention for a while. If it is still the case, i.e. you cannot submit
a bug report to OpenJDK, then I can escalate this through LJC to the
JCP EC. I just need a genuine reproducible bug report to work with.
 
--
Russel.
=============================================================================
Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel...@ekiga.net
41 Buckmaster Road m: +44 7770 465 077 xmpp: rus...@winder.org.uk
London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder

[Ingo W.]

Hi Russell,

I did report the bug, it even has got a review ID:

> We are evaluating this report and have assigned it a Review ID: JI-9028460. 

Despite this I have little hope that this will lead anywhere, since I didn't submit a code example. I think it would need several days to come up with a minimal example that exhibits the error.

Apparently, this is an old bug that wasn't ever fixed thoroughly, and yet (or because of) the javac8 works well in most cases.

However, the code generated by Frege is nothing like anything a human would ever write: for example, static variables initialized with a lambda

that contains a nested class, which has final members that are initialized with a lambda that contains another nested class, and so forth, many levels deep.

The null pointer exception in the compiler happens, apparently, when you access an item from one of the enclosing inner classes from somewhere inside a lambda some levels deeper. It must be stressed, however, that the code is legal.

If anyone wants to reproduce it, here's how to do it:

- from the releases, get https://github.com/Frege/frege/releases/download/3.23.288/frege3.23.24a.jar 

- check out gen8 and copy/move the jar to the working dir under the name fregec.jar

- make runtime compiler

- java8 -cp build -Xss4m frege.compiler.Main -d build -prefix xx -sp next/:. -experimental -make frege.compiler.Classes

(where java8 means the java executable from some jdk-8).

The java compilation will abort on build/xxfrege/compiler/Classes.java.

At this time, several thousands of lines of java code are already generated and all but the failing one are compiled.

I'm not sure that makes for a nice "smallest example". :)

To convince yourself that the generated code is correct, do 

- mv build/xxfrege build/xx8frege

- java9 -cp build -Xss4m frege.compiler.Main -d build -prefix xx -sp next/:. -experimental -make frege.compiler.Classes

and it will compile nicely till the end. There should be no differences in the java files generated from the two runs, except for a line containing the time stamp of the compilation time (1 line per file).

I didn't file a bug report for the issue with the VerifyError. This one is, according to recherches in the internets, also well known, but apparently doesn't happen often enough to fix it.

Regards, Ingo

[Mark Derricutt]

On 18 Jan 2016, at 8:08, Ingo W. wrote:

> Despite this I have little hope that this will lead anywhere, since I didn't submit a code example. I think it would need several days to come up with a minimal example that exhibits the error.

I see 8u72 was released this morning - are any of the fixes in there resolving any of the issues you have here?

mark


--
Mark Derricutt
http://www.theoryinpractice.net
http://www.chaliceofblood.net
http://plus.google.com/+MarkDerricutt
http://twitter.com/talios
http://facebook.com/mderricutt

[Ingo W.]

No, it's still the same.