Homework for Closures
I’ve long been an advocate of outside-in API design. This reflects my interest in user-interface principles in API design. When designing a GUI it is customary to mock it up on paper and then with prototyping tools before implementing the internal code. This helps the interface reflect the user’s goals and expectations rather than the internal data structures of the program. In API design, this means the class becomes more easily usable by decoupled client code.
It occurs to me that the same principles apply in language design. In particular we should try writing some code with proposed new features before we implement the features. This has several advantages:
- Ensures we get what we need, rather than what the proposal supports
- Helps us understand exactly what is being proposed
- Shows the strengths and weaknesses of each proposal
- Avoids unnecessary features that don’t support a real use case
Consequently herewith are some challenges for the proposers of the various closure proposals. I’ve tried to make them as simple as possible so that the closure issues will be focused on.
Single Method EventListener
Write a Swing applet containing a single button which pops up a JOptionPane containing the message “Hello closures” when pressed.
Solutions
Single Method EventListener, Part 2
I’m still playing with this idea, but I suspect we should try passing in some data from both fields and local variables to be displayed in the JOptionPane. Let’s try passing in a value from a param tag.
Solutions
MultiMethod EventListener
Write an applet such as this very old one that reports all mouse and key events, except for mouse moved events. Thus you’re likely using two event listener interfaces: KeyListener and MouseListener.
(This is a weak problem. There may be a better one, if anyone cares to suggest. The idea though is to set up a well known interface that has more than one method which must be implemented.)
Multithreaded? Server
Write a network server which receives a single String on a line as input. Parse this string as an int. Assuming this is a non-negative integer, return the nth Fibonacci number as a string. Then close the connection.
Do not assume either the output is within the range of an int, long, or double. (I.e. you have to use BigInteger.)
Because Fibonacci numbers grow like O(n^2) and because you have to use BigInteger, you cannot serialize the requests. That is, you cannot process them in sequence and wait for one to be calculated before serving the next. I suspect you need multiple threads to make this work, but it’s just possible someone clever enough could avoid that.
On the other hand, I’d prefer you not to store a humongous lookup table in a file or database somewhere. Yes, that would be sensible; but the specific goal here is to test cases where the server has to do a lot of work for each connection and still process a lot of simultaneous connections.
Solutions
Multithreaded Program
Write a program that makes efficient use of potentially dozens or hundreds of CPUs to multiply two large matrixes containing doubles. Essentially we’re looking for a reasonable implementation of this method:
public static double[][] multiply (double[][] a, double[][] b)
Throw an IllegalArgumentException if the dimensions don’t match up, but the interesting case is when they do.
You can parameterize the number of CPUs if you like.
You can remove the static keyword if you must, but I’d be much more impressed if you don’t have to do that.
Solutions
- Java 1.4 (Needs some work)
Sorting #1
Write a program which sorts two arbitrary lists, using a user-supplied comparison function. You do not have to use the Java Collections API, though you may if you like.
Solutions
It turns out the Collections API handles almost all of this:
- Java 1.4 (Demo’d as a JUnit test case)
Sorting #2
Write a program which sorts a double[] array using a user supplied sort function.
Iteration
Write a class which calculates the average of a java.util.List using a user-supplied average function.
Demonstrate the use of this class with three different average functions–mean, median, and mode–on three different types: java.lang.Double, java.lang.String, and autoboxed ints.
Error Handling
Write a program to write the first 25 Fibonacci numbers into the file named “fibonacci.txt” in the current working directory, which may or may not already exist, may or may not be writable, and must be closed on program completion. (I don’t care whether you write text or binary numbers.)
Solutions
Synchronization
This one’s from Neal Gafter, and I’m still trying to make more fully understand it, but I think the problem statement is along the lines, “Given a CandidatePool extends Collection<Candidate>” which is shared between multiple threads, find a candidate in the pool that meets the requirements, remove it from the pool, and return it. The Candidate interface/class has methods such that the following makes sense
class Main {
/** Find a candidate that meets the requirements */
Candidate recruit(CandidatePool candidates,
Set requirements) {
for (Candidate c : candidates) {
if (c.qualifications().containsAll(requirements)) {
candidates.remove(c);
return c;
}
}
return recruitForeign(requirements);
}
/** Find a candidate meeting the requirements from another pool. */
static Candidate recruitForeign(Set requirements) {
return null; // placeholder implementation
}
} This version is not thread-safe. Making it thread-safe is part of the problem.
According to Gafter, you must also "properly use the Lock API instead of the language's synchronized statement." That requirement sounds suspicious to me, but he knows much more about threads than I do, so presumably there's some reason to prefer the Lock API to mere synchronization.
Fairness
Now take this same problem, and make it not just thread-safe but fair among threads. That may be where the Lock API comes in. I'm still trying to grok this problem.
Have I missed anything?
I'm not sure any of these problems require access to local variables, non-final local variables, or instance fields and methods from the enclosing class. Since those are major sticking points for the various proposals that help distinguish between them, that may be a problem. Then again maybe I shouldn't be focused on that at all, only on the real use case. If we don't have any use cases that need that, maybe that just isn't so important.
Personally I'm beginning to wonder if we need anything more than mere function pointers. Why not just allow a.doSomething, this.doSomething, and Class.doSomething to be passed to methods, and define a syntax for invoking these things within the methods they're passed to? This is close to the Colebourne proposal, but eliminates anonymous inner methods. I don't see why we need to define functions inline inside other functions. In fact, I think I'd prefer we didn't. This would neatly avoid all the questions about this, and local variables in scope being final or not. Hmm, I may have to write some sample code myself, to see if this idea holds water. 🙂
Submitted Solutions
- BGGA: Pending
- CICE: Pending
- First-class methods: Pending
- Harold (Function pointers only, no inline methods): Pending
- Java 1.4: Pending
- Java 5: Pending
- Java 6: Pending
Once the problems are fleshed out a bit more, and I've incorporated feedback, I'll probably do a table mapping solutions to proposals.
Thoughts
I think these are all pretty basic problems that shouldn't take too long for any of the minds working on closure proposals. However, seeing and comparing the solutions should give the rest of us a much better way of judging and evaluating the relative merits of the different proposals.
I request that each proposer publish a page showing the detailed code to implement each of the following problems. Furthermore if anyone wants to solve these just using Java 1.4, 5, or 6 feel free. I'll link to solution sets as they become available. And please do suggest other use cases since I'm sure I haven't hit all of them. If any of the problems are insufficiently clear, let me know and I'll try to elaborate. And if you disagree with any of the use cases, comment about that too.
Gentlemen, start your editors.
Caveat
I am a little worried that these problems are too small and too focused on exactly what closures do. While this may help us compare proposals, it doesn't really help us decide if any proposal is worth the cost compared to doing nothing. This is like optimization: you don't want to spend a huge effort speeding up part of your program where it only spends a tenth of a percent of its time. We don't want a huge increase in language complexity to organize a piece of the language most programmers never see.
While all the use cases mentioned here certainly arise in Java code, I don't know that they're truly the pain points Java programmers face, or the most frequent ones. Some criteria any new language feature must pass should include:
- Does it let us do anything we can't do now?
- Does it make the code we are writing now easier to write?
- Does it make the code we are writing now easier to read?
The most I'm willing to answer for closures on each of those so far is maybe. On the third, I'm tempted to answer no.
March 1st, 2007 at 3:37 pm
The Fibonacci sequence grows like O(phi^n), not O(n^2). Also, you can calculate it in time O(log n) using the BigDecimal class, so it’s entirely reasonable to answer requests as they come in… You need a harder problem such as factoring.
March 2nd, 2007 at 9:12 am
I think that this is a good approach to comparing the proposals (I tried a couple of comparisons in my most recent blog). However, I’m concerned that each proposal writer is going to have to spend a lot of time working out the unimportant parts of the examples above, like the Fibonacci, fairness or synchronization. I would prefer to have the Java 6 code already written, and then customize the closure proposal from that. I think it would make them easier to compare too.
Also, three other ideas – (a) iterating around a map, with easy access to the key/value. (b) iterating around a collection and removing items that match some criteria. (c) Accessing a file, and ensuring it is closed afterwards.
March 2nd, 2007 at 11:07 am
I’m working on Java 1.4 versions myself. I’ll start posting them as soon as I get a minute. That should handle the Fibonacci details. And if anyone else would like to contribute, please drop me a line. I’m afraid I can’t work on this full time just yet, and probably not till next month.
March 4th, 2007 at 1:02 pm
The essence of a closure is that it captures, or closes over, the local variables in the code that lexically surrounds the closure. These variables then survive the method’s exit and are still available whenever the closure is invoked. Note that this means that if two closures are created by a single invocation of a method, they share access to the same set of variables, but a second call of the same method will create entirely new local variables and new closures with access to them.
Currently, objects of (non-
static) inner classes aren’t quite closures: they capture the values of local variables, but not the variables themselves, because an inner-class object can only seefinalvariables, which can be copied freely since they cannot be mutated.Examples that don’t exercise the power of capturing local variables (and it’s a power you probably don’t feel the lack of because you’ve never had it) aren’t really examples of closures at all; they are just syntactic sugar.
March 4th, 2007 at 2:25 pm
That may be the essence of a closure, but to my mind it’s an open question whether that’s necessary. I’m about 90% convinced something is necessary, but I suspect function pointers alone might be enough. What I hope to accomplish with these exercises is to see if that’s true.
Please feel free to suggest practical problems that you feel might demonstrate the need for full closures as opposed to merely function pointers. They jey, though, is that they have to be phrased in terms of what we want to calculate/do rather than the algorith/technique by which we calculate/do that.
A lot of the examples I’ve seen essentially bake the answer straight into the question. They’re more of the form, “How do you drive a Ford Escort with standard transmission from Detroit to New York?” than “How do you travel from Detroit to New York?”
March 4th, 2007 at 8:31 pm
Some people still wonder if having support for structured programming, and subroutine calls is necessary. After all, GOTOs might be enough. And they don’t have to learn anything new to use GOTOs… always a hassle in old age.
March 5th, 2007 at 10:34 pm
A while back I proposed another alternative, Clear, Consistent, and Concise Syntax (C3S) for Java (http://www.artima.com/weblogs/viewpost.jsp?thread=182412). It is closer to CICE than BGGA, in that it is based around inner classes with short syntax. An example in my proposed syntax is:
final list = Collections.sort inList, method( str1, str2 ) {
__str1.length – str2.length
};
Contrast this with Java 5+:
final Collection list = Collections.sort( inList, new Comparable() {
__public int compare( final String str1, final String str2 ) {
____return str1.length() – str2.length();
__}
});
The essence of the C3S proposal is, as the name suggests, to provide Clear, Consistent, and Concise Syntax in that order of priority. In particular Clarity and Consistency are not sacrificed in the name of conciseness. Part of the consistency aspect is not only syntax that is familiar, in particular it uses un-abbreviated keywords, but also it builds upon features already in the language, e.g. inner classes, rather than adding new features, i.e. closures with subtly different semantics than inner classes.
I would be happy to code some of your examples in my proposal, but Java 5+ versions would be easier to work with than 4.
March 6th, 2007 at 3:05 am
A typical example of function argument usage is traversing some data structure and returning the first occurrence (or many) matching the supplied predicate, like find-if in Common Lisp. This does not in itself require closures, only function pointers. However, almost any sensible usage of functions like find-if will use closures. E.g. write a method findNamedElement that takes a String name and returns the first object in a List that matches that name, using List’s built-in findIf method. In Common Lisp that would be something like
(defun find-named-element (name list)
(find-if #'(lambda (obj) (equal (get-name obj) name)) list)
)
In this case you need to close over the name argument, so while you don’t (in this case) need heap allocated stack frames that survive the invocation of find-named-element, you need more than function pointers. Anyone having used this style of programming can tell you that. In my experience, this style mixes well with object-oriented programming. I keep reinventing interfaces for this purpose all the time, while dreaming of a future where Java has closures…
Pick up a book on functional programming (e.g. using Common Lisp) and find exercises there. There’s no need to cook up new ones.
March 6th, 2007 at 6:11 am
Closure (and continuation) in plain old Java 1.4:
class TestContinuation {
class Closure {
private Object state = null;
public Closure(Object state) {this.state = state;}
public Object call() {return state;}
}
public void continued(Closure continuation) {
continuation.call();
}
public void main (String[] args) {
continued(new Closure(null));
}
}
If you really need the convenience of a concise syntax and the dynamism of an interpreter, use something else than Java.
I suggest CPython but you can have your way with JRuby too 😉
Or wait for Java 1.7, although that could be a long time …
Kind regards,
March 6th, 2007 at 10:33 pm
[…] Closures continue to be a hot topic in the Java world. Last week Stephen Colebourne posted the new FCM proposal and he followed it up this week with two posts of comparison examples across the different proposals. Also in that spirit, Elliotte Rusty Harold posted on some homework we should do before deciding on a closure spec and Neal Gafter posted a closure MouseListener example. Finally, Andrew C. Oliver posted on replacing AOP with closures in some cases. […]
April 12th, 2007 at 6:57 pm
I have posted a feature based comparison of the different closure proposals, C3s, FCM, CICE, & BGGA, at:
http://www.artima.com/weblogs/viewpost.jsp?thread=202004
This comparison, hopefully, lets you choose which features are important to you and demonstrates that the proposals, other than CICE, are really a collection of features that includes new syntax for inner classes/closures.