Thursday, March 08, 2007

On The Expressive Power of Programming Languages

There are at least three separate proposals recently put forward in the space of "Closures for Java." Among the criteria for evaluating the proposals, I'd like to discuss two: conciseness (possibly phrased as convenience) of code using the construct, and expressiveness. Conciseness is pretty obvious, and you can compare the proposals on this measure by writing snippets of code that do basically the same thing as each other, but written using existing constructs and then each of the proposed constructs. How many characters, or tokens, does it take to write the code? By the measure of conciseness, shorter is better.

Unfortunately, the authors of the various proposals don't appear to be using a common meaning for "expressiveness" or "expressive power." Consequently, we often end up talking at cross-purposes when comparing the proposals. Some people appear to treat "expressiveness" and "conciseness" as synonyms, but to me these have completely different meanings. Expressiveness is a bit harder to measure, but in some ways more important at this stage of the discussion. See Matthias Felleisen's, On the Expressive Power of Programming Languages, 3rd European Symposium on Programming, Copenhagen, Denmark, 1990, http://citeseer.ist.psu.edu/felleisen90expressive.html, for one attempt to formally capture the meaning of expressiveness.

In my mind, a language construct is expressive if it enables you to write (and use) an API that can't be written (and used) without the construct. In the context of the Closures for Java proposed language extension, control abstraction APIs are the kind of thing that don't seem to be supported by the competing proposals. You don't see the proposals compared side-by-side on this measure because this is something only supported by one proposal. Programmers who have become accustomed to programming with closures find them very useful for factoring out common code in ways that are not currently possible in Java. See, for example, http://www.joelonsoftware.com/items/2006/08/01.html, http://ivan.truemesh.com/archives/000637.html, http://www.talios.com/dear_java_i_need_closure.htm, and http://blog.moertel.com/articles/2005/08/30/closures-and-the-professional-programmer. These kinds of uses might not occur to you if you're mainly a Java programmer, because Java doesn't reward you for thinking this way. But this is another example of expressive power.

I'm not particularly attached to one syntax or another for closures. I don't mean to say that syntax isn't important. Anyone who knows the story of variance and wildcards knows how much I value a good surface syntax. Our proposal describes a particular syntax not because we believe it is the best possible syntax, but because it is hard to write a specific proposal without some syntax. Ultimately, I hope the closures issue becomes a JSR and the expert group takes its time to decide what surface syntax is best. But I believe that the expressiveness of the Closures for Java proposal is the most important reason to consider doing anything in this space at all. If it is just a matter of a slightly more concise syntax, I'm not sure it is worth the trouble.

13 comments:

Tom Palmer said...

Mostly agreed. (Although even just making "final" go away would be nice.) Keep up the good work with BGGA/javac.info, and I think even the syntax so far really is mostly fine.

Tom Hawtin said...

If "Closures for Java" had a syntax as verbose and redundant as inner classes, I'm absolutely sure it wouldn't be worth the bother.

axel said...

Closures: great! Syntax: great! type parameters for exceptions: great! final: great!

But taking a close look at the four examples cited: None of them use return, break, continue. This C heritage is the part of the proposal that bothers me: It is most in conflict with the existing OO heritage in the Java language (inner classes) and brings the least benefit to the programmer. A "findFirst" method for collections would solve the standard application of "break", the "continue" statement in its most frequent form corresponds to "return" in an inner method, and a non-local "return" holds unpleasant surprises in the form of runtime exceptions.

Apart from these low-level constructs, the competition does support control abstraction, too (loops, nested locks, timers,...).

Anonymous said...

Almost all languages we use are turing complete, and therefore are computationally/expressively equivalent. You could roll your own closures in java using an insane stack-of-hashtable implementation for symbol management.

It all comes down to "mere" syntactic sugar, or conciseness. That's the magic.

On the other hand, perl sucks. So I'm not sure what to believe.

Cheers,
Carson

Stefan Schulz said...

I agree that sometimes conciseness is mistaken for expressiveness. But I am not sure, if the goal for a language construct should focus on providing as much functionality as possible. I'd still argue that Closures and Control Invocation Syntax are two separate constructs, which may be combined, with the drawback of causing implicit restrictions.
Of course, the resulting functionality should provide more than just shortening existing constructs. It's a nice to have, if shortening effects come automatically with applying the new constructs in specific scenarios.

Neal Gafter said...

@Anonymous: Turing completeness doesn't measure expressiveness. Although Java is Turing-complete, it is not possible to write control abstraction APIs in Java today. See my talk, or the paper "On The Expressive Power of Programming Languages" (link in this blog post) for details.

Axel Rauschmayer said...

Isn't there a slight imbalance between closures and methods? Informally (I'm not sure I got it 100% right), you have the following situation.

Functions:
- anonymous definition: yes
- named definition: NO
- can be typed and referenced as a separate construct: yes

Methods:
- anonymous definition: NO
- named definition: yes
- can be typed and referenced ("method pointers"): NO

I absolutely agree that we need control abstraction APIs. But the Colebourne/Schulz proposal [1] better handles the above mentioned imbalance. In your proposal, closures pose as functions (and I'd still love Java to have first-class generic functions, but am not holding my breath), maybe it makes sense to treat them more like methods as in the C/S proposal. Apart from method pointers, the difference is minor, but it still feels better.

[1] http://jroller.com/page/scolebourne?entry=first_class_methods_java_style

Neal Gafter said...

@Axel: Yes, closures are different from methods. I don't know why you feel there is an "imbalance" that we need to do something about.

Axel Rauschmayer said...

OK, I've thought about it some more and the main difference between BGGA and FCM is that FCM makes the connection to methods: you have method reference literals and can convert them to a closure via currying. Or you can refer to static methods and use them without currying. This is based on what's already there in java.lang.reflect. Furthermore, defining named closures as static methods (as opposed to a class that implements a closure signature in BGGA) pays tribute to their role as functions in current Java.

So, what I would like to have is both BGGA's control abstractions and the above mentioned integration of methods.

Anonymous said...

Axel, that's what I (and others) have been trying to tell Neal: A proposal for method literals (or currying in general) has to be an integral part of the closure proposal, in order to make the proposal more complete, and better showcase its expressive power. Otherwise, that message will be largely lost on the audience who will be instead distracted over syntax related issues. Because without it (the literal support), you get that strange feeling that strange feeling that something is missing.
I do hope that Neal in the next iteration of the proposal will give method literal support some consideration for inclusion.

Mike

axel said...

Here's the other Axel again :-)

Felleisen's paper provides a formal tool for judging whether a language extension is more than just "syntactic sugar", and draws the conjecture that programs in more expressive languages contain less (redundant, repetitive, distracting) programming patterns.

However, as Felleisen points out, expressiveness comes at a price: "an increase in expressive power may destroy semantic properties of the core language that programmers may have become accustomed to."

By Felleisen's measure, "goto" is more expressive than structured control statements. This indicates that expressiveness is not the only criterion for language design!

For a more popular presentation of this idea, see http://weblog.raganwald.com/2007/03/why-why-functional-programming-matters.html

Jochen "blackdrag" Theodorou said...

I think I have another definition for "expressive". For mean I use the term when I am able to make something in a shorter, but still readable way. So it is about to say the same thing with less words without loosing the general understanding. The part of being still readable is very important to me, because I see constructs in other languages, that allow you to express things in a very short way, but 2 months later you have no idea what that thing was doing again. I also think that Java goes the maintainability way a bit to far, but that doesn't mean that explicit syntax is in general wrong.

As for closures... As long as the closures are shorter as inner classes and still easy readable, I think they will be a gain to Java.

Daniel said...

I've looked at a bunch of examples for closures. In every case, the job could be done just as easily with inner classes. The saving in terms of less typing from using closures was minimal. The closure syntax was no clearer - in fact it can be less clear what's going on. The introduction of extra syntax has a definite negative effect on overall clarity of the language, and hurts teaching. So the overall effect is less clear code, and less Java coders. Great.

NB - I write as an ex-Lisp coder. Since switching to Java I have never looked back.