Papers

It's a been a god few months for paper publishing (and I have been a little lax about reporting on it): "Encoding Ownership types in Java" (with James Noble) has been accepted to TOOLS, "Towards a Semantic Model for Java Wildcards" (with Alex Summers, Maraingiola Dezani-Ciancaglini, and Sophia Drossopoulou) has been accepted to FTfJP, and "Tribal Ownership" with James Noble and Tobias Wrigstad has been accepted to OOPSLA. Which all makes me very pleased indeed! I think they are all good work, and I very much enjoyed working on them, learning a lot from my collaborators in the process - thanks guys!

These papers should be appearing shortly on my research page.

Impact

A blog posting day today. This one has been swirling in my mind for a while actually.

Robert O'callahan (Mozilla) gave a talk at Vic recently (blog link), in essence, on the impact of one's work in the world. I missed the talk, but read the slides and had a chat with Rob about this, and it got me thinking. A lot.

What impact does my work have? Well as a theoretical researcher, I'm used to the answer being none. And I've been pretty comfortable with that, I get satisfaction from the intellectual challenge, rather than the real-world impact. If one of my ideas trickles down into something useful one day, then that is a bonus.

But, thinking about this a bit more, impact is like risk - it's a two dimensional idea, in the case of impact, there is magnitude (how many people, how much you impact each person) and 'positivity' (I can't think of a better name, I mean how positive the effect is). I've always thought in terms of magnitude, implicitly assuming I would be making things better, not worse (no intention of doing research for the military, for example). But I think it is important to think in terms of both - one should strive to make one's impact better, as well as bigger.

Not sure what any of this means in practical terms, but it is a musing in the spirit of the blog's name.

UK elections - postscript

So, a dissapointing showing for the lib-dems after predictions of greatness. But a tory-lib-dem coaliation is probably the best result that could be hoped for. Insha'allah, the lib-dems will temper the uglier side of conservative social policy, but the tories will get to fix the economy (whatever that means). On the other hand, it could all fall apart in a few months, time will tell. At least Labour are out of power (if you told me ten years ago that I'd be saying that, I'd have laughed in your face). Hopefully, the kicking will be taken for a comment on the home (civil liberties, "broken Britain" stuff) and foreign (war) policies of the last few years. We should remember that, Labour did a lot of good things for the country too...

Fingers crossed for some good things from the new boys (talking of which, it really is boys, where are all the powerful female ministers?), and hopefully proper voting reform at some stage...

UK Elections

Bit of a departure from the usual, but it's election time, so why not?

Who to vote for - no-one looks conviincing, labour are tired and have made a total mess, plus there is that unpleasent Tony Blair taste left over. The size of the british state is getting ridiculous and the infringements on civil liberties frightening.

Voting Tory would be like selling one's soul to Satan (remember the '80s?), plus Cameron looks like Blair 2.0. The liberal democrats have some good policies (civil liberties, imigration) and actually have a chance of getting some votes this year, but have some stupid policies too (abolishing tuition fees, no nuclear power, etc.). Perhaps a lib-dem/tory coalition might work. What we really need is a proper liberal party - in both economic and social terms. And one with the guts to radically reform the health service (take power away from the GMC, reform doctor training and the doctor's/GMC monopoly) and education (let universities charge what they like, abandon the stupid target of getting stupid people through universities, fix primary/secondary schools a bit (although God knows how to do that)).

So The Economist is probably right, as repulsive as it seems, the tories are probably the best bet for a vote. Now that is a sorry state of affairs, glad I don't actually live in the UK right now.

You wait months for a good seminar...

...and then three come along at once!

Following Monday's seminar Robert was scheduled to talk again on tuesday, this time at the NZCSRSC (student research conference). It sounded like an interesting talk - "How to change the world" is not a modest title. And having perused the slides I am very disappointed not to have attended - it looks like there were a lot of good things, and thinking about your work in terms of impact is an interesting perspective, and one which I have not thought of since working in PLT.

Anyway, I couldn't attend because I was attending another seminar, this one from Rusten Leino on the Dafny language/verifier and other verifcation stuff going on at Microsoft research. It was a very interesting seminar with a very good demo of verification in action. Pretty impressive amount of bugs caught and all proofs done automatically - it was kind of like magic! Really solved the problem I have with a lot of these things, which is that no-one wants to prove their programs. The annotation overhead is still quite high, and I think only a minority of programmers will be able to write the specifications. But, with a little practice, I can imagine writing code with specs in Dafny in a practical way.

Rusten also summarised some of the other verification efforts he is associated with and they have acheived some pretty cool stuff.

"Dynamic framing" sounds cool, and I should try and understand it better.

Overall, I got the feeling that right there was the future of 'safe' programming languages, or at least a sneak peak of it. And, since it's at Microsoft, it actually has a fighting chance of making it into the real world!

Who would have thought...

...that a talk about standards would be interesting? But it was! Robert O'Callahan (Mozilla) just gave a talk about web standards. Standards are dull, and people who care about them tend to be even duller, but this was not a dull talk! It was interesting! Lots of interesting things about the web.

One nice thing is that short interations seem to work better for standards too, just like software. I think this is one of those fundamental computer science truths, kind of like "you can solve any problem with an extra indirection", for any task, shorter iterations are better.

Also, interesting parsing problem - "herebedragons", its obvious what is intended, but how should you parse it? And make a tree that can be manipulated by Javascript etc. And we all thought syntax had been solved thirty years ago. In fact, the web seems to be a whole new world of interesting computer science problems (see the post on Javascript VMs). Now what would be an interesting research topic?

VM talks and assembly language

Google are currently developing two (at least only two are public) VMs: Dalvik and V8. Dalvik is a Java VM (but not a "JVM" - it doesn't run Java byte code) targeted at mobile devices (part of Android), V8 is a Javascript interpreter and part of the Chrome browser. There are talks on both:

Dalvik: http://www.youtube.com/watch?v=ptjedOZEXPM

V8: http://www.youtube.com/watch?v=lZnaaUoHPhs

I recommend you watch both, they are both good, the V8 one in particular really got my juices going (man, I'm such a geek).

I think it is interesting to compare the two as the tackle a similar problem in very different ways. Obviously the source languages are different, in particular, V8 does lots of interesting stuff to optimise Javascript out of the dynamic language tar pit. The goals are different: Dalvik's main goal is to minimise space (also, time, but mainly space) and battery life; V8 is a pure speed machine. Dalvik doesn't do any JITing, V8 is (as I understand it) all JITed. Dalvik is optimised by using a new set of byte codes and a more compressed file format and some neat tricks on internal libraries etc. V8 is optimised by using classes and caching call sites. There's tons more on both VMs in the talks, and lots more stuff for an interesting comparison.

All of this machine hackery inspired me to look again at x86 assembly and architecture (and maybe I'll look at ARM next). I used to think x86 assembly was a big scary mess and best shyed away from. I've always output JVM or MIPS assembly in compilers etc. for this reason. Bu actually, x86 is not too bad! There's a few more instructions that do some pretty interesting things, but it really isn't much worse than other assembly languages. And I find it really interesting finding out how the processor works; maybe there's a closet bit-jockey in me after all.

A rant - empirical analysis

Having typed up my ECOOP notes and gone through the proceedings a bit, I have actually got a little bit angry about the state of affairs concerning empirical analysis.

A few years ago it seemed that any kind of empirical analysis was a bonus and as long as you had a problem and a solution and a soundness proof you were good to go. The obvious problem is that there is nothing to say that your solution addresses the problem, that the problem is serious, or that the solution is practical.

Bit by bit reviewers have started asking for some empirical evidence to answer these questions. Can someone tell me why this fashion started?

I don't have too much of a problem with this, except that we are doing research here, and some of these crazy ideas which aren't practical and don't really solve any problem lead to solutions that are and do. If you press too hard for practicality you lose the paradigm shifting ideas that only seem practical in ten years time.

What has made me angry, is that the pendulum seems to have swung too far: it now seems really hard to get something published without empirical analysis, which makes it hard to be productive unless you have an army of students and constrains some good, but not immediately practical, ideas. Furthermore, there seem to be a few papers published at ECOOP which seem to be half a paper - just the evaluation or motivation section of a decent paper, without any real idea. These seem to have been published on the strength of the empirical analysis alone, without having asked how much of a contribution this analysis actually is.

I agree there is a need for analysing existing work, but some just seems unnecessary and, frankly, boring.

I count four papers at ECOOP that I would reject for being pointless (there is at least one paper (probably more, but I can't be bothered to look through the proceedings again) that is pure analysis and I think is useful). No names, obviously.

I'd be very interested to here othe peoples views on this, cheers!

ECOOP day 3

Tobias gave the first technical talk and was surprisingly bright-eyed; apparently that's what being Swedish does for you. The paper is entitled Loci: Simple Thread-Locality for Java. There is a very simple ownership system (two annotations - shared and thread) where threads own their thread local data and the system restricts references accordingly, thus data is kept thread-local. It's all enforced statically, and they have a compiler. Their empirical evaluation found that most classes could be made thread-local.

Next was Failboxes: Provably Safe Exception Handling presented by Bart Jacobs the younger. These are essentially a safer version of exceptions (although they are layered on top of exceptions, they're not a replacement). The problem with standard exceptions is that side effects made inside a try block will remain even if the try block fails and an exception is thrown. Fail boxes allow non-lexical scoping of expressions and so failure can prevent execution of dependent expressions which are outside the try block.

Weirdest talk of the conference award goes to Yossi Gil presenting "Are we ready for a Safer Construction Environment". The idea is small but sweet and is a restriction on the way objects can be constructed. The problem is that during object construction, objects are 'half-baked' that is, construction has not finished, fields may not have been initialised, and invariants may not have been established. They propose restricting construction to their hard-hat model, which means that means no virtual method calls and no exposure of this to external methods.

Now, whilst this is a solution, it's not very clever, it seems to be along the lines of "if you do nothing, you won't get hurt" and to me seems like it should be a paragraph in a 'how to program' textbook, not a full paper in a PL conference. But, they have done loads of corpus analysis to confirm the obvious, and since that seems to be in fashion now (why? Can someone please tell me why?!), it has got published. Having said that it is something that I would bear in mind if I were making a system where invariants at construction was important, so I guess it should be published somehow...

Christian Haack then talked about Type-Based Object Immutability with Flexible Initialisation. This seems like a lightweight ownership system for immutability. I think the key of it is that you enforce owners-as-dominators (or something like it) during initialisation to ensure an object is initialised 'privately' and then enforce a kind of owners-as-modifiers (it's not total immutability) afterwards. Which is nice as far as it goes. But I feel there is a sweet spot with the immutability/uniqueness/ownership combination which has not quite been hit, although this and other papers are getting close.

Finally, Ali Ibrahim (I think) talked about Remote Batch Invocation for Compositional Object Services. This is an optimisation of RMI so that remote calls are batched together for the sake of efficiency. They introduce a batch keyword to the language, and within the batch scope, the order of execution can be changed so that remote calls are batched. It's all bit cleverer than that, for example, they do 're-forestation' of data structures to improve batching of loops. They have an implementation and plenty of empirical analysis.

ECOOP day 2

Today's invited talk was by Dave Ungar and it felt more like a self-help tutorial than an academic talk. In fact all three of the talks I attended had a whiff of esteem boosting and soul searching about them: are we academics really that insecure in our endeavours or about out role in computer science?

Anyway, Dave still seemed pretty bitter about the lack of success of Self and the way it was handled at Sun, which might well be justified, but didn't fit into the therapeutic tone of the rest of the talk. The points I took from the talk were: interpreters are better than compilers (and this needs technologies such as JIT to realise), design languages on principles rather than examples, and simplicity is better than expressiveness.

The first technical talk of the day was Adding State and Visibility Control to Traits Using Lexical Nesting. The authors seem to back off the founding principles of traits by adding stateful traits (which are now exactly like classes or maybe mixins?) and nesting of objects to give visibility control. Composition is achieved by delegation and delegate methods are automatically generated. Of course, with state you then get back all the old multiple inheritance problems, which are addressed to some extent. So although nice ideas and well-thought out it seems to go completely against Dave Ungar's maxims of simplicity before expressivity and principles before examples.

I liked Modular Visitor Components:..., although I'm not sure if it's even close to practical. This is a possible solution to an extension of the expression problem - the expression families problem. I wasn't quite clear what this was or to what extent previous solutions address it, in particular where virtual classes fall down. The solution was implemented in Scala using a collection of quite terrifying PL technologies - higher order type parameters, variance, traits, and self types. The result is a suitably complex type system that is nicely expressive.

The other joint-best paper of the conference was Debugging Method Names. They find bugs in names such as getString not returning a value or not returning something of type String or setting something etc. They do all this automatically by analysing a whole bunch of programs, which is certainly clever but didn't really seem like a programming languages problem, or even that hard from the talk, maybe the paper better identifies the problems.