Static typing for warp-widgets
I have been thinking about this for awhile, currently warp-widgets templates are duck typed. I want to make them statically typed (as crazybob encouraged me to). There are two parts to this.
Part #1
@My(name="Jeff") <div>... </div>
@EmbedAs(My.class)
public class MyWidget {
@Inject
public MyWidget(My my) {
assert "Jeff".equals(my.name()); //true
}
}
Part #2
${message}
- writing a specialized statically typed expression language for warp-widgets (would be nice to avoid this!)
- check that the properties/paths exist on classes at template compile time (static duck typing)
- another, harder, option is to perform expression egress type narrowing at template compile time. Which will give us ‘effectively static’ typing (but under the hood we allow MVEL to evaluate the expressions, dynamically)
Filed under: 1 | 2 Comments
Tags: guice, java, type system, type theory
Generics are at once the most welcome, easy to understand and most perplexing feature added to Java since… well ever! I couldn’t imagine life without them, but like anything in type theory they are at times confoundingly opaque. Here are some all-too-common misconceptions about Java Generics and Generic types in general:
- Set<Child> is a subtype of Set<Parent>
This is an unfortunate misapprehension brought on by the rather strange fact that Child[] is a subtype of Parent[].
- Type erasure means there is no real difference between Set<T>, Set or Set<E>
Type erasure means there is no way to enforce the difference between them at runtime.
- Set<?> is equal to Set<?>
This one came up in the Guice list recently: why can’t we declare a variable as Set<?> and then bind it to some implementation that Set<?> accepts?
The answer is that Set<?> is a wildcard type. In other words, it is a query on all types that match Set<?>. Like Set<Object>, Set<Socket>, Set<BuckRogers>, and everything else besides.
Java cannot close over the scope of all possible bindings to any give Set<?>. In other words, because Set<?> can be any Set type, Java cannot assume that it is any one Set type. Therefore you cannot bind Set<?> to any particular Set.
- The same goes for Set<? extends Thing>
This is a special kind of wildcard known as a bounded wildcard. In essence, a wildcard is a closure over the global scope of the program. If such a closure were possible, we could bind wildcards correctly. But this is not doable without the source code to everything (aka global compilation =)
- Type reification would have let us do cool things like new T();
No, it would not.
- Guice can @Inject List<T> if I bind all possible List<T>’s used in my program
Type erasure means that Guice has no idea what the witness of T was, when bound.
Filed under: 1 | 0 Comments
Tags: closures, generics, guice, java, type system, type theory
When consulting with a colleague, recently, I ran into an interesting use case: in order to monitor live performance, we needed to count the number of method invocations on a service (read: EJB/remoted call). Actually, it was a number of such services. The obvious answer was to place an interceptor around each method call, and increment a global counter.
However, here’s the kicker: we don’t know how many services there are, and the system is highly concurrent. What would you use to store service/call count mappings?
- j.u.HashMap - Can’t, it’s not thread-safe
- Hashtable/Collections.synchronizedMap() - Nope, there’s a single lock–all invocations will queue up behind one another and kill performance
- j.u.c.ConcurrentHashMap - Even with a mighty (1:1) lock granularity it’s no good because a single EJB can be invoked concurrently. If there’s a popular EJB you end up with the one-giant-lock problem all over again
So that’s exhausted all obvious solutions. What we needed was a table where:
- a key could be inserted atomically, and
- its counter incremented atomically
…but these two operations are not atomic (together). Here’s roughly what we came up with (credit should mostly go to my colleagues):
public class CountingTable<K> {
private final AtomicReferenceArray<K> keys = new AtomicReferenceArray(CAPACITY);
private final AtomicIntegerArray counters = new AtomicIntegerArray(CAPACITY);
public void count(K key) {
int index = key.hashCode() & (keys.length() - 1);
while(key != keys.get(index) && !keys.compareAndSet(index, null, key)
&& key != keys.get(index))
if (index < keys.length() -1)
index++;
else index = 0; //wrap
counters.incrementAndGet(index);
}
}
What we end up with is a constant-time, fixed-size, lock-free, wait-free, open-addressing hashtable with linear reprobing. =)
How does it work?
- First, we hash into the array somewhere (sparse-array trick); I use & as it’s much faster than %
- Next, we test if the key is already there (if it is, drop out, increment and done)
- If not, we try to insert the key using CAS against null (if slot is empty, insert key, drop out, increment and done)
- If not, we recheck to ensure an interleaving thread didn’t insert our key (if it did, drop out, inc & done)
- If not, we move to the next slot in the array (linear reprobing); rinse, lather and repeat.
Does it really work?
- constant-time complexity - by hashing into an array, I guarantee O(1) puts in the average case
- lock-free - there is absolutely no mutex over the table, a stripe or even a single key!
- wait-free - during a single put, multiple threads can make make progress (even to the same key)
- linear-reprobing - by scanning forward into the array on collisions, we maintain constant time-complexity (degrades to linear in the worst case, i.e. if all keys collide)
- open-addressing - by storing keys and values in the array, we can vastly improve CPU cache performance over a traditional chaining hashtable like j.u.HashMap and j.u.c.ConcurrentHashMap in colliding cases
Send me your thoughts, I suspect this can be improved a lot. (And if you want to see another post on reading from this table =)
With due props to Cliff Click’s ideas on hashtables.
Filed under: 1 | 0 Comments
Tags: concurrent, counting, data structure, hashtable, java, lock-free, threading, wait-free
Thoughts on CICE (closures?)
CICE is a proposal by Doug Lea, Josh Bloch and ‘Crazy’ Bob Lee. It is being touted as a “closures” proposal for Java 7 alongside Neal Gafter’s BGGA (for instance). Here are some thoughts I had after reading their document: So basically, CICE is syntactic sugar for anonymous classes. In Guice parlance, the following: …becomes: Scheme is one of my favorite languages. Scheme basically invented closures, so given this–what are my reactions to CICE? First, this is what I call a closure: A block of statements which retains its lexical context indefinitely. A closure is also a first-class citizen, in that it can be stored in a variable and passed around like an object . In CICE, you don’t implictly close over the wrapping lexical context Uh, sure but what does that mean? It means local variables are not part of the closure’s immediate scope. Even though the appear to be: … won’t work. r only sees x = 1. Local variables are actually copied to the block. By hiding the final keyword it fools you into believing this is not the case. The fix for this is to declare x as public: I thought closures are supposed to prevent such malarkey, not induce it =P Note: The BGGA proposal also added something like this not long ago, but it was an optionaldocumenting annotation @Shared, rather than a language construct (i.e. public keyword). Statement blocks are not anonymous Blocks in almost every language thus far are anonymous (Ruby, Groovy, Python, etc.). A block in CICE is just a contraction of an instance creation step, so you still need to specify its type. The following (anonymous method) is not possible: Statement blocks are too type-restrictive By the same token, statement blocks are restricted to pre-existing types (i.e. single-method interfaces being subclassed). One powerful feature of closures in Scheme (and other dynamic languages) is they are type-neutral at the point of definition. This may seem cribby to you but: …can add two integers, longs, or floats. The function in add is type-neutral. This is *not* to be confused with duck-typing (Scheme is not duck-typed). There is a subtle point here that all functions in Scheme are type-neutral until they execute, but this is not what I am getting at (ignore that Scheme is dynamically typed for the moment). I concede that it is harder to type-check inferred-type methods in a statically-typed language like Java, but CICE makes this impossible without pre-defined generic types: I must declare this type simply in order to use it anonymously. This feels backwards to me. By contrast, this is a Haskell function: add x y = x + y Does add() take Ints? Longs? Floats? We don’t know until it is used. And we don’t care. Haskell functions are quantified over all types. In other words, they are type-polymorphic. Haskell is statically-typed, so this is not an apples-to-oranges comparison either (if you were wondering that it was with Scheme and CICE). The CICE proposal claims this is something that could be improved upon. More on type-neutrality OK, so you sort of grok that a closure is different from a CICE in that you don’t subclass a pre-defined type. But what’s so bad about that? One-method types are easy to create (and most useful ones already exist–example Callable<T> and Future<T>). Without resorting to duck-typing what else could I possibly think type-neutrality provides? “Real” closures possess function types. This essentially boils down to a tuple consisting of [R, A...An] where R is a return type and A…An are argument types. So what? Well–this actually means closures are quantifiable over all types matching the tuple (ANY matching function) and not simply a named type. Consider: As opposed to a real closure: Named types don’t enter into it. The closure’s type is captured over its functional type signature, which effectively gives it the flexibility of structure typing (but without contaminating the structuraltype system itself–unlike scala). Much more powerful indeed. Other stuff For these reasons I believe it is misleading to call CICE a “closures proposal”. It should certainly not be considered in the same vein as BGGA for instance. Note that none of this speaks to the merits of CICE as a code footprint reduction proposal. Nor to BGGA in terms of its merit as a closures proposal. I am not endorsing either proposal, nor condemning CICE as a language feature. I just want to highlight that it is inaccurate to equate CICEs to closures.bind(Service.class).toProvider(new Provider<Service>() {
public Service get() {
return new ServiceImpl();
}
});
bind(Service.class).toProvider(Provider<Service>()
{ return new ServiceImpl; });
public Runnable get() {
int x = 1;
Runnable r = Runnable() { System.out.println(x); };
x = 2;
return r;
}
public Runnable get() {
public int x = 1; //huh?
Runnable r = Runnable()
{ System.out.println(x); };
x = 2;
return r;
}
list.each({ it -> doStuffTo(it); });
(define add (lambda (x y) (+ x y)))
public interface Adder<N> {
N add(N x, N y);
}
public java.lang.Runnable get() {
return my.domain.Runnable()
{ System.out.println("Hi"); }; //error
}
package some.other.domain;
...
public { => void } get(boolean where) {
return where ? { => System.out.println("Hi"); }
: my.domain.Closures.bye() ;
}
Filed under: 1 | 3 Comments
Tags: closures, guice, haskell, lambda, scheme, type system