Friday, October 16, 2009

Scala vs. Scala

One bit of fallout from the JVM Language Summit I attended last month was a resolve to learn Scala.

I've been trying to write an implementation of a game my cousin designed, and I decided to use Scala, because the scope of the project seemed small enough that I could combine it with learning a new language, but large enough that it would exercise a fair amount of that language.

And so far, I'm pretty fond of Scala. The underlying semantics are close to Java's, because the language was conceived to run on the Java Virtual Machine, but the Scala compiler does its utmost to infer anything (like the type of an expression, or whether an identifier is the name of a variable or zero-argument method) that would be obvious to a human reader. The result is a great deal less boilerplate than in Java. Furthermore, Scala traits have fewer arbitrary restrictions on their content than Java interfaces, which makes it easier to compose your code the way you think it, instead of the way the compiler wants it.

In the dispute between functional vs. imperative languages, Scala comes down squarely on both sides. Scala seems to have two ways to do almost everything; consider, for example, the imperative-looking for (obj <- mySet; if isGood(obj)) yield transform(obj) vs. its functional equivalent, mySet.filter(o => isGood(o)).map(o => transform(o)). Which is better? I'm not sure I have enough experience with Scala to give a definitive answer, but I do find myself using both imperative and functional forms in my code, and I think the imperative form is easier to follow when you're doing something complicated, and the functional form easier to read when you're doing something simple. Because the rules for transforming between the two syntaxes are pretty straightforward, having both options in the language doesn't seem to impose as much of a mental burden as I had expected.

By making it clear that the dichotomy between functional and imperative languages is a false one, Scala does us the favor of freeing up our energies to argue about something else. On to the next flame war!

Thursday, September 17, 2009

Unconstructable Token Spotted at JVM Language Summit

I've been attending the JVM Language Summit at Sun's campus in Santa Clara, not because I'm implementing a programming language on the JVM, but in my capacity as programming-language-junkie-at-large. The big fuss this year is over the invokedynamic bytecode instruction, which (unlike the other ways Java bytecode provides for invoking a method) can be retargeted at runtime.

This is (at least potentially) a great efficiency gain for implementors of dynamically dispatched languages. Such languages choose the target of a method invocation based on the runtime rather than the compiletime types of their arguments (or even on the arguments' values), and may choose methods to invoke based on method arguments other than the first (the receiver). Often they also let you modify an object's class at runtime to add or remove methods, which requires a dispatch algorithm that not only differs from Java's, but that can change over time.

The infrastructure around invokedynamic is the java.dyn package proposed for Java 7. Since I hadn't been paying much attention to invokedynamic, it took me all day yesterday to wrap my head around the magic that not only allows it to work, but often to do so very efficiently (if you're lucky enough to have the JVM inline everything that it could).

That magic derives from two sources:
  • MethodHandles, which, in their simplest form, are direct references to method bodies, and which the JVM is smart enough to inline; and
  • MethodHandles.guardWithTest, which composes a new MethdHandle from a test and two alternatives, the result of which the JVM is also smart enough to inline.


In effect, at each call site, you can inline a bunch of code (which you can change later, if you need to) that chooses an invocation target. This code will often look as if it's making a choice based on the runtime types of the method arguments originally given, but in practice, if enough gets inlined, those types will be known to the JVM when it's compiling your target-choosing code—so that the target is known at compiletime, meaning no invocation overhead at all if the target is also inlined.

Ever so sweet, if the JVM is aggressive enough about inlining. Which it sometimes isn't, but that's another topic, perhaps best left to people who know more about how the inlining decisions are made.

Anyway, what I really meant this post to be about was a spotting of the Unconstructable Token pattern in the java.dyn API, specifically in the MethodHandle constructor: this constructor is protected, because you may need to make language-specific subclasses of MethodHandle to keep track of whatever your language needs to keep track of—but you obviously can't let people construct a method handle just anywhere. Hence the Magic Token argument (currently of type sun.dyn.Access, but I assume they'll change the name to something less Sun-specific before release), which ensures that only The Authorities can can create a method handle.

I hadn't originally thought of Unconstructable Token in terms of restricting where user-supplied subclasses of framework classes can be allocated, but this is a fine use of it, and Java modules will do nothing to make this use of the pattern obsolete.

Thursday, September 10, 2009

Immutable, Keyable, Canonical

I've been trying to come up for a while with some general-purpose mechanisms for creating canonicalized classes. I ran into trouble trying to formulate the rules, and I realize now that was because I was trying to conflate three distinct concepts into one.

Canonicalization (also called “interning”) is a well-known design pattern; see, for example, the Wikipedia article on interning of strings. A canonical object must have a well-defined immutable identity (which I am calling the object's “key”, by analogy with the use of the term “primary key” in referring to relational databases), and an object with a given identity is stored just once. Canonicalization is useful for simplifying comparisons between objects (their references can be compared, instead of their contents) and also for saving space in applications where many identical objects might otherwise be allocated.

My realization was that I had been confusing the idea of an immutable object with the idea of an object with an immutable identity. Besides being candidates for canonicalization, objects with an immutable identity are also suitable as map keys, because two such objects, when equal, always look up the same value in a map. However, an object with an immutable identity need not be completely immutable. Consider, for example, this class:


final class C {

private final String s;

private int n;


C (String s) {
assert s != null;
this.s = s;
}


public boolean equals (Object o) {
if (o == this)
return true;
if (! (o instanceof C))
return false;
return ((C) o).s.equals(s);
}


public int hashCode () {
return s.hashCode();
}


public String toString () {
return s;
}


public synchronized int n () {
return n;
}


public synchronized void n (int n) {
this.n = n;
}

}


This class has an immutable identity, specified by the value of the final variable s: s is the only field examined by equals and hashCode, and so instances of this class are perfectly suitable for use as map keys. Nonetheless, this class also contains some mutable state, in the form of the variable i.

I'm not the only one to mix up the notions of immutable object and immutable identity. The javadoc for java.util.Map says:


Note: great care must be exercised if mutable objects are used as map keys....


the implication being that only completely immutable objects are suitable keys. The paragraph in question does go on to mention the equals and hashCode methods specifically, so the documentation is not incorrect; still, many other authors have carelessly used “immutable object” and “suitable for use as a map key” as synonymous.

In this post, then, I want to come up with usable definitions of these three concepts:


  • Immutable: Applied to an object, it means that all instance variables of the object are final, and all the object's instance variables of reference type are null or references to immutable objects; or, the object is an instance of a system class known to be immutable, like String.

    An immutable class is a class all of whose instances are known to be immutable; specifically, it is either a system class known to be immutable, or:


    • All instance variables of the class are final; and

    • All instance variables of the class are of an immutable type, where an immutable type is a primitive type or a reference to an immutable class; and

    • All subclasses of the class are also immutable.


    A possibly immutable class is a class that might have both mutable and immutable instances (because even though all its instance variables are declared final and of possibly immutable types, the class, or the class of a reference reachable through one of its instance variables, might have a subclass with non-final variables).

    Note that these definitions do not permit an array to be considered immutable, because Java does not have a way to declare an array element final.

  • Keyable: Applied to an object, it means that the object meets the usual Java criteria for a suitable key in a hashed data structure. Specifically, the object may be an instance of a system class known to be keyable, such as String; but if it is not an instance of such a class, then, for an instance a of class C and some subset K (the “key fields”) of C's instance variables, a is keyable if and only if:


    • a.equals(b) returns false if b is null or of a class other than C. Otherwise, it returns true if and only if all corresponding variables in K are equal.

    • a.hashCode() returns a deterministic value based only on the values of a's instance variables in K (the value returned is not affected by the values of instance variables of any other object, or of any class's static variables).

    • All variables in K are final, and if of a reference type, either are null or refer to keyable objects.


    A class C is a keyable class if every instance of the class is guranteed to be a keyable object. This requires that:


    • C's equals and hashCode behave as described above for keyable objects; and

    • All subclasses of C be keyable classes; and

    • All of C's key fields be final and of a keyable type, where a keyable type is a primitive type or a reference to a keyable class.


    A possibly keyable class is a class that might have both keyable and nonkeyable instances.

  • Canonical: Applied to a class, it means that the class is keyable and that some mechanism is used to avoid creating (except perhaps transiently) more than one instance of the class with the same key.

    An instance of a canonical class is called a canonical object. A canonical object a is necessarily the only one with its key, meaning that a.equals(b) is equivalent to a == b for any possible b.


The discussion above doesn't mention static variables, which clearly are not part of an individual object's state, and so can be ignored when deciding whether an object meets any of the above definitions. More problematic are transient variables—although these are treated for the most part as ordinary instance variables, they are not serialized and so are not part of an object's state when it is saved and restored (possibly in another process). I am inclined now to exclude transient variables from consideration when applying the above definitions to the facilities I'm working on.

Thursday, September 3, 2009

Reflecting Darkly on Generics

Although you can do reflection on generic types in Java, the information available from java.lang.Class and the java.lang.reflect classes is pretty raw.

I came across a situation the other day where I had something like:


interface I<T> {
T foo ();
}

abstract class C implements I<String> {
}


and I wanted to ask: what does C.foo() return? The answer, obvious to a human reader, is String, but deducing this using reflection requires traversing C's ancestry and explicitly resolving the type variable T.

It would be nice if there were some general-purpose facilities built into Java to answer questions like:


  • If a given Method m is invoked on an object declared to be of type T, what are the type bounds on the returned value?

  • If a given Method m that takes n arguments is invoked an object declared to be of type T with arguments of specified types Ui, but omitting one argument k, so that 0 ≤ i < k and k < i < n, what are the type bounds on argument k?


Without having made any attempt to write any such facilities myself, I can't say exactly how hard they would be to write, but my feeling is that they would not be easy.

But, if that's not bad enough, they might be impossible to write in a definitive way consistent with the Java language specification—see, for example, this article, which says that the Java generic type inference algorithm is underspecified.

Friday, August 14, 2009

Live from Second Life

“Live from Second Life!” That's how people who are broadcasting over Internet radio while logged into Second Life tend to announce themselves. Which, given the immersive nature of the medium, feels entirely natural until you think about it. Of course, they're actually broadcasting from wherever they are in Real Life. But since whatever they're saying usually concerns the people whose avatars they see in the vicinity of their own avatars, the feel of addressing an intimate gathering is inescapable.

But this weekend I'm blogging live from Second Life in an entirely different sense. I'm attending the Second Life Community Convention in San Francisco. The first sessions of the convention began yesterday afternoon.

I was afraid the convention might be a little dry—lots of people with Real Life or Second Life businesses nattering on about Synergies and Leveraging Brands and other buzzword-laden nebulosities—but it's been a lot more fun than that. I crashed a couple of Art track sessions yesterday. I know zip about art, but I had a blast: artists can be just as creative in conversation as on the metaphorical canvas. The high point of the afternoon was a few short scenes from plays prepared by Z. Sharon Glantz (Lailu Loon in Second Life), who had us read the scenes and then discuss how we'd stage them in Second Life. These were classic brainstorming sessions where wild ideas flew thick and fast. Lailu's stated focus was on how to make Second Life drama that would be accessible to people who weren't familiar with Second Life, but I'm afraid I kept coming up with ways to incorporate Second Life in-jokes into the scenes (are jokes actually funnier when only your friends get them?).

Making virtual worlds accessible to people who aren't familiar with them is a theme of several conversations I've had so far. I was talking with a Belgian journalist last night (whose name I failed to catch) and he was complaining about the number of job applicants he encounters—people in their 20s—who aren't familiar with new media. He says he asks them in interviews, Do you play World of Warcraft? Do you blog? Journalism isn't quite the manual-typewriter-in-an-exotic-location profession it used to be.

This morning's keynote address was from Ray Kurzweil, appearing to us from Second Life, projected on a screen at the front of the room. His presentation focused on the exponential growth of various technologies, including, in recent years, the use of virtual worlds. His contention that within 20 years or so many people will have neural implants that let them interface directly with virtual worlds seemed a little early to me—I'm not sure that many people will move into brain hacking that quickly—but it's clear to me that enough people find virtual worlds compelling that people will keep looking for lower-friction ways to inhabit them.

Sunday, August 9, 2009

Unconstructable Token

Here's a story about a problem, and about a pattern that solves the problem. Both the problem and the solution are specific to Java, because they involve Java's visibility rules.

I wrote a Java method m as part of a project at work. It was an implementation-detail method, not to be called by the client applications of the project, that needed to be called only in a certain context. I provided a public method p that set up the context and called m—but as happens so often, the project had evolved to have a structure more organic than organized, and p was in a different package from m, which meant that m had to be declared public.

My coworker, writing a client application of my project, wanted to invoke the operation that p performed, but didn't recall the name of the method he wanted to use. So, using his helpful IDE, he searched. Well, I had given m and p similar names—no, I didn't really call them m and p, but gave them names describing what they did—and so my coworker's IDE found m, and he wrote a call to m in his code. Since he didn't call p, the context required for m to work properly was not set up, and m blew up when he called it, and he wasted some time trying to figure out why before he came to me and I told him he should have called p instead.

In my defense, I had clearly stated in the Javadoc for m that it was to be called only from p, not from the client application. Unfortunately, my coworker searched for just an identifier in his IDE, and the IDE didn't know enough to read the caveats I had put in the Javadoc and wave red flags in front of my coworker when he called the wrong method.

(OK, I know what you're thinking. I shouldn't have set up my system so that m and p were in different packages in the first place. This kind of setup—a publicly visible method not meant to be invoked by the public—is one that should have been caught in the design phase, or been solved by something like the export controls in the eternally-not-quite-ready-for-prime-time Java Module System, JSR 277. And in this case, you're probably right, at least in a perfect world. But this problem can also occur where refactoring and modularity don't work, as I show below; so for now, please just accept the problem as legitimate.)

Now for the pattern I adopted to solve the problem. I haven't seen any discussion of a general solution to this problem elsewhere, so I'm going to take the initiative and name the pattern: Unconstructable Token.

In Unconstructable Token, a method m that is declared public but should be invoked only from a particular context takes a parameter of a type T that can be constructed only in that context. m verifies that the T is not null, and gives a sensible error message if it is null—a runtime enforcement of m's restricted visibility that is admittedly inferior to a compiletime enforcement, but the best that can be managed if m must be declared public. (In practice, this is almost as good as compiletime enforcement, because programmers are unlikely to try to pass null as a method argument without explicit permission.)

A schematic example:


package p1;

import p2.C2.T;

public class C1 {

public void m (C2.T token) {
if (token == null)
throw new IllegalStateException(
"Cannot call C1.m directly; call C2.p");
do something useful
}

}


package p2;

import p1.C1;

public class C2 {

public class T {

T () {
// constructor is *not* public, so can only be
// called from package p2
}

}

// The token doesn't have to be a singleton, but is here:
final T t = new T();

public void p (C1 c1) {
set something up
c1.m(t);
finish up
}

}


The example shows a token with no functionality of its own, but it is often convenient for C2 to place some of the data or actions needed to coordinate between m and p in the token itself.

The hoped-for result is that your documentation-ignoring coworkers will quickly realize they can't get a hold of a T, and so can't call m; and therefore they keep searching and stumble on p, which they should call. If they are so bold as to call m(null), they'll get an error message at runtime that points them in the right direction.

Of course this pattern is Java-specific. In C++, you wouldn't declare m public, but instead declare p to be a friend of m, and you'd be done. But the Java folks don't seem inclined to take the language in the direction of friend, so that's unlikely ever to be an option for Java.

Anyway, are you sold yet, or is Unconstructable Token more antipattern than pattern? I think that depends on context. In the distant, shining world of JSR 277, this system could be a single module that publishes C2, but not C1 or T. m would still be declared public, but because it's in a module that doesn't export it, it's not visible to the client application. But in the real world of deadlines and pointy-haired bosses, we can't wait for Java 7 (which will surely include an implementation of the module system—won't it?), and we don't necessarily have the luxury of refactoring the system to put all the relevant mechanism into one package (if that even makes sense), and we probably don't want to get bogged down in something as heavyweight as OSGi (which is an existing module framework specification, but more oriented towards modules that may be added and removed during execution).

I may be displaying undue favoritism because I invented Unconstructable Token, but I think it's not so ugly that you need to be ashamed of using it, especially if you document that you're doing so.

Now, as promised, a situation where Unconstructable Token can be indispensable: the case of synthesized code. If you are writing a class loader that modifies or generates code to implement the rules of some framework, you may want the generated code to call methods in the framework (ordinary methods that you write as part of the framework, not generated methods). However, even though the framework methods may perform actions that don't make sense except when called from the generated code, you must make them public in Java—otherwise, you won't be able to call them from code loaded by your class loader.

If you invoke the generated code in question directly from the framework, you can just pass an Unconstructable Token to the generated code, and the generated code can pass it back when it calls back into the framework.

The solution is more complicated if your framework methods can be called from arbitrary places in the generated code. I haven't dealt with such a situation in practice, but it seems to me you could add some generated code to each class to wind up putting the Unconstructable Token in a private variable in each class containing generated code. Since I'm too lazy to figure out whether this really works, or how to do it tidily, I'm going to decree this an Exercise for the Reader. At least, until such time as I need to do it myself.

Note that neither refactoring nor modularity gets us anywhere in the case of generated code. Assuming your framework doesn't load itself, the generated code you load with your class loader will necessarily be in a different package from any of the framework packages (because they have different class loaders). And how would you write a module so that it exported a method to the generated code, but not handwritten code in the same package? I'm not familiar enough with the module system proposals to say definitively that it's impossible, but it doesn't sound easy.

Saturday, August 8, 2009

The JSR 308 Story

OK, after a little reading, I think I've figured out what JSR 308 does and does not do.

Although there is a bit of speculative language scattered in the JSR 308 materials about runtime enforcement of the rules associated with various annotations, no enforcement mechanism is currently available. That is, JSR 308 (at least in its current incarnation) is all about compiletime, and not about runtime.

Besides the immutability-related annotations of Javari, the JSR 308 kit includes an alternative immutabilty checker, IGJ, and some other annotations for checking:
  • Nullness: @NonNull and @Nullable
  • Interning (whether two objects of which equals is true may be distinct instances): @Interned
  • Locks: @GuardedBy and @Holding
as well as a clunky-looking mechanism for subtyping by annotation, the Basic checker.