Fwd: HPCS recap

Not having much time to produce original content, it’s a pleasure to find a post on a subject I was considering to cover, and actually being treated better than I could have hoped to do myself: a post about HPCS on Bartosz Milewski’s blog. Other than the fact that Fortress is not under development but has currently “wound down” (as Guy Steele said in the keynote speech of the JVMLS 2013), the article is up to date. All three approaches resonate with the theme in my post on array processing. I just want to add that both Guy Steele (Fortress) and Vijay Saraswat (X10) have had great influence on me, the former via Common Lisp and Scheme (cf. TinyScheme), the latter via the “Concurrent Constraint Programming” book (cf. my thesis on Concurrent Constraint Logic Programming [Technical Report CERMICS 92-04]). And Fortress intended to tackle the problem of properly dimensioned calculations, which had also been one my favorite subjects.

Even mainstream Java has been oriented towards how to do efficient and practical computing (cf. “Arrays 2.0“).

Enjoy!

Advertisements

Lies, damned lies and methods implementing specialized generic interfaces

You know that I’ve been spoiled by spending years in a land with reified generics. I’ve heard Daniel Spiewak, in an episode of “The Scalawags“, say that he prefers erased generics because they permit more freedom in the typesystem, and Martin Odersky also swears by them, so I’m not ready to condemn them yet. But they can sure tie one in knots.

Here’s a recount of a recent experience of mine, suitably distilled to its essentials. Follows javap disassembly for a completely boring pair of interface and implementation.

Compiled from "Interface.java"
public interface Interface {
  public abstract boolean toBoolean(java.lang.String);
}
Compiled from "Implementation.java"
public class Implementation implements Interface {
  public Implementation();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public boolean toBoolean(java.lang.String);
    Code:
       0: iconst_1
       1: ireturn
}

Surely you must be yawning by now. Let’s spice it up by introducing some Java 8-like base interface. toBoolean looks like Predicate#test, doesn’t it? But this time I’ll also show you the original Java, because you’re in for a surprise.

public interface Predicate<T> {
  public abstract boolean test(T);
}

public interface Interface2 extends Predicate<java.lang.String> {
}

public class Implementation2 implements Interface2 {
 public boolean test(String s) {
  return true;
 }
}
Compiled from "Implementation2.java"
public class Implementation2 implements Interface2 {
  public Implementation2();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public boolean test(java.lang.String);
    Code:
       0: iconst_1
       1: ireturn

  public boolean test(java.lang.Object);
    Code:
       0: aload_0
       1: aload_1
       2: checkcast     #2                  // class java/lang/String
       5: invokevirtual #3                  // Method test:(Ljava/lang/String;)Z
       8: ireturn
}

What the…? Apparently, the mere act of defining Interface2 as a specialization of Predicate, actually specialized the signature of test, so as to allow uses of “real” test(String). But, at the same time, the compiler injected an erased test that calls the specialized one. That’s how I found it. I was creating the implementation with Javassist, and the Javassist compiler did not perform this sleigh-of-hand. Which was OK until I tried to call the method and got an abstract method error. Not a very common sight, is it?

Oh, and you cannot do this explicitly with Java code, because trying to do so gives you an error.

OtherImplementation2b.java:2: error: name clash: test(Object) in OtherImplementation2b and test(T) in Predicate have the same erasure, yet neither overrides the other
 public boolean test(Object o) {
                ^
  where T is a type-variable:
    T extends Object declared in interface Predicate
1 error

boolean test(java.lang.Object) should have been final, but isn’t. Even so, the aforementioned error does not let you override it, anyway. You can only override the specialized method.

Ultimately, it is not just compilers for “other” languages who need to jump into hoops to get around the limitations of Generics. This is a case of the Java compiler itself jumping through hoops. Remember that the Javassist-created class compiled fine and was loaded fine, but the error stroke at runtime. Beware!

UPDATE: These phantom methods are called “bridge” methods, and they are utilized in all places where the typesystem needs to express things the JVM cannot. They sport the ACC_BRIDGE flag.

Intersection of automata, and why should you care

Regular readers of this blog (both of them…) know that I have a propensity to make actual use of basic theory, and this has served me really well, all these years, primarily because most others don’t. After all, you know the saying that, in theory, theory and practice do not differ but, in practice, they do. Well, the point is to know when they do and when they don’t. And I’ll stop being cryptic now and tell you that the theory concerning this post is automata theory.

I first used statemachines as an explicit programming abstraction around 2001, in a system that handled SMS dialogs with mobile subscribers (I say explicit, because, at some level, any system mutating state, transitions between states of an implicitly defined statemachine). Statemachines are a very concise way to model such things, as they have a memory of exactly unit length. You collapse all past history on this one thing, which is the current state. You gain an impoverished but surprisingly sufficient language (a regular grammar) to handle events.

And then, reality intervenes, and things become messy. There are Moore machines, and Mealy machines and statechart diagrams, the UML standard way to model statemachines for software, that encompass both. Because we don’t just care to recognize a series of events, what we want is to act on them, so we need a finite state transducer. I’ll use the Mealy viewpoint (actions linked to transitions) in the sequel. Let me relate some thoughts of mine about how to think about transition guards.

We start with a sample transition, as in the diagram.

Statemachine transition with guard

Statemachine transition with guard

You move from State 1 to State 2 when Event 1 arrives, but only when guard() is true. Supposedly, guard() is a boolean expression on the World. It can be either true or false, or else we wouldn’t bother asking, and, supposedly, the World sometimes makes it true and sometimes makes it false. I’ll come back to this in a moment. Suppose, now, that, the World being in a state of making guard() true, is represented as a real state, in another statemachine.

Two automata

Two automata

We now have two statemachines, and I’ve taken the liberty to make the World statemachine understand the Event 1 transition as well (not doing anything important with it). The reason I did that, was to pave the way to forming the intersection of the two statemachines.

Product of automata

Product of automata

What just happened, is that we got rid of the guard, at the cost of having to maintain a second statemachine, the World one. In a system where transitions in the World statemachine are also done from within the system itself, this amounts to optimizing the guard calculations to happen only when the World changes, and memoizing the result. The main statemachine should also understand (and similarly ignore) the events of the World one, so that the intersection statemachine is well-defined.

Don’t get all worked up about the complexity of all that, because you don’t have to physically form the intersection. All that “understanding” and “ignoring”, you should read it as happening implicitly. In plain words, you can just define transitions in the second machine in response to World-changing events, and transitions in the first machine in response to the main events, but the latter transitions will be defined on product-states, formed from one state from each statemachine.

I’ll be spending more time on statemachines in the immediate future, so you may expect more stuff coming from that direction. I can’t let you in on job-related things, but I’ll be happy to share basic knowledge.