Optional Values in Java

If you take some Java code and write psuedocode representing it, you'll probably find that you don't bother with null checks and you don't bother with getters and setters. Sure, in psuedocode you're lazy, but it's more than that - null is usually wrong, so much so that intentional uses of null look like sloppy code.

In fact, if you're writing an API, you probably want to keep null out of your interactions with your users - you want to make sure they realise their mistake if they give you null and you don't want to give them null, lest they forget to check it. But there are actual times when you need some way of representing an optional value.

One particularly popular approach is to use sentinel values - let's say "" for Strings, Double.NaN for doubles, -1 for ints. Now everywhere you read the value you need to check for the sentinel, or be sure that not checking for it won't cause you problems.

Another approach is to use an empty list to represent no value, and a list of 1 element otherwise. Again you need to check whether the list is empty before getting the result out.

You could make a class that might hold a value, that has methods called hasValue() and getValue(). Again, requires a check.

In all these you need to remember to check before you get the value - not much of an improvement over using null directly.

If I categorise some code including null checks (no, not nunchucks), then we'll have something to toy with:

1. foreach

if (x != null) {
 doStuffWith(x);
}

2. map

String s;
if (x == null) {
 s = null;
}
else {
 s = x.toString();
}

3. fold

int length;
if (s == null) {
 length = 0;
}
else {
 length = s.length();
}

Those were some strange names I gave to these categories! Let's tackle foreach first: Think of a value that might be null as a collection containing 0 or 1 elements - foreach would be a loop that runs 0 or 1 times to do something with the value.

map is a mapping from a domain containing null, to a co-domain containing null, - for example, mapping from rectangular coordinates to polar coordinates should probably yield null for a null input, if it doesn't throw an exception.

fold is a more manageable name for a 'catamorphism', which is a transformation that tends to yield a simpler value than the collection it's applied to (which seems the opposite of a fold in origami). In the case of a possibly-null value, the result is simpler because the result is (usually) a not null value.

Being responsible non-repetitive Java programmers, we'd like to encapsulate our possibly-null value plus the checks into an object with three methods, foreach, map and fold, rather than repeating them everywhere:

interface Optional<T> {
 void foreach(Task<T> task);
  R map(Conversion<T,R> conversion);
  R fold(R theDefault, Conversion<T,R> conversion);
}

(you might really want to make Optional Iterable so that you get Java's foreach loop, rather than providing foreach, as an implementation detail).

In the same way that java.util.Collections.sort can take a Comparator, each of these methods takes in an object that has a method that gets called if and when it needs to be.

interface Task<T> { void execute(T value); }
interface Conversion<T,R> { R convert(T value); }

Let's look at how we can convert the earlier null-using code to code using Optional.

1. foreach

x.foreach(doStuff);

2. map

String s=x.map(toString);

3. fold

int length=x.fold(0,length);

Of course, the likelihood is that you're not lucky enough to already have doStuff stored as a Task, toString stored as a Conversion and length stored as a Conversion, so perhaps you'd use an anonymous class to provide those. Unfortunately the syntax for anonymous classes bloats the code too much to be readable in a blog (or an IDE).

It would be useful to have good syntax for using foreach, map and fold in Java, so that there was at last an attractive alternative to null. For now we'll have to settle for attractive semantics rather than attractive syntax though.

I think this is beautiful because it provides a level of abstraction that gets you further from a potential source of bugs, makes your code more expressive about what it accepts, and lets you do in objects what otherwise would be repetitive.

A complete implementation of Optional is available in Functional Java under the name Option. There, Task is called E, and Conversion is called F. Option is most widely known as Maybe, from Haskell.

May your nulls rest in peace.

Designing an Object

If there may exist an object with a method that is not appropriate at all points in the existence of the object, then the object or the method are flawed.

A class encapsulating a compile phase in an IDE might have a blocking or non-blocking execute() method, plus a getErrorMessages(). There is an obvious protocol in using this class - instantiate, call execute(), call getErrorMessages(). It's not particularly hard to use, though it's also not hard to get wrong. Even if you decide not to help those users who don't bother to learn the protocol, it's worth thinking about whether that protocol should even exist, and what the alternative is.

Many readers would probably, when prompted at least, make execute() return the error messages (or a Future for them), which solves the problem quite well. If you wouldn't, keep adding phases plus methods only appropriate for each phase, to one class that grows and grows, until you end up agreeing or changing career :) Anyway, in this case it's clear that the object was flawed by doing two things one after the other - executing the compile phase and delivering results.

I bet most people could train themselves to spot this flaw and remove it, and if anyone only goes that far as a result of reading this post I'll be happy. But most people are probably quite happy with another flaw, java.util.Iterator.next(), which is only allowed when hasNext() returns true, in most Iterator implementations. But moving next() or hasNext() onto another object doesn't really work for Iterator. For a long time I was unhappy with Iterator, but didn't really have a solution, despite trying a couple of things out.

The biggest use of Iterator directly in Java for many years was in what has since been replaced by a foreach loop. There are some detractors of, well, anything new, but generally the foreach loop was really well received by the Java community. It provides a higher-level interface than the Iterator gives us. We can write a lot of code using the foreach loop that would have been more verbose and awkward to get right using Iterator directly. But foreach is only one abstraction; there are some more that are higher still than it, and don't (but can) depend on Iterator. If you don't know what those abstractions are I really think you should take the time to learn about map, filter and reduce, and the more general but less usable parent of those, fold. But this isn't a post about those, so I'll return to the topic at hand.

Iterator has been shown to be flawed, though flawed in a way that is acceptable to most of us and in a way we're used to, and in a way that seems non-trivial to solve (without knowing about map, filter, reduce and fold!). You might not be in a position to, or even want to, replace Iterator, but at least you should know not to copy its design, or bind yourself unnecessarily to it. You're now either armed with a simple way of deciding between two API designs, or you're about to tell me why I'm wrong.

Happy coding.

Programming in a natural order

Whenever I'm doing the same thing over and over, a little background thread in my brain starts to wonder if there's a better way. Sometimes I tell it to shut up and let me code, other times I listen. In this case it took me a long time to listen, so it must have been pretty persistent. The first time I noticed it was while writing some lisp. Here goes the usual overly trivial example:

I write (+ 3 4) then realise I want to multiply the result by 5. I have to go back to the start of the expression and change it to (* (+ 3 4) 5). I could easily blame lisp's prefix syntax and maybe define some reader macro so I can write something like (+ 3 4) >> (* 5). But that would solve one case and not really fix the overall problem. Here's the obligatory less trivial example:

I write (+ 3 x) then realise that x needs to be a lambda parameter, so I go back and write (lambda (x) (+ 3 x)). I think it's difficult to make the above >> reader macro work with this.
(+ 3 x) >> (lambda (x)) might work, but it's starting to get hard to read. It doesn't seem as natural as it did for the previous case.

But, as I said, it took me a long time to take notice of this background thread, and in fact when I did I was writing Scala, not lisp. When in lisp I just wrote the code anyway, and it didn't harm me noticably. I never wrote the above reader macro, and as I've never written one, chances are it's unwritable anyway.

The case when writing Scala was where I was looking at an expression, then realised that one of its inputs would be a collection, not a single value. A closer-to-reality example - you have a Client, and a Client has a manager, the contact there that you speak with. So you have:
def sendSpam(client: Client) = emailer.send(marketingTripe, client.manager.emailAddress). Then later you change Client.manager to Client.managers, and change its type from Manager to Iterable[Manager]. Now the emailer protests (at compile time), so you have some options:

1. Change the emailer to make it accept an Iterable[Client]. This is actually quite reasonable, and what I did in the real code this mimics.

2. Change the code to:
client.managers foreach (manager => emailer.send(marketingTripe, manager.emailAddress)).

3. Listen to the background thread in your brain, and blog about an automatic transform from the original version to option 2. Today I'm choosing option 3, as you can tell. To avoid ambiguity, I'll introduce some syntax to put around 'managers':
emailer.send(marketingTripe, ^(managers).emailAddress) will be transformed to the code from option 2 above (though perhaps without a real variable name).

At this point, you might be seriously glad that I am not a committer on the compiler for the language that you use every day. But I think the above might actually be a good idea, and might even be a better syntax for a map with a lambda than what we're used to. The reasoning is: it's preferable to write code in a natural order, rather than the order that the language forces you to.

A Cross-Language Generics Trick - Java, Scala and C#

Given a Pair<T, U> type in Java, Scala or C#, such as Map.Entry, Tuple2 or KeyValuePair respectively, you can construct type-checked variadic heterogenous containers that you can write general methods to operate on.

Let's write a Pair interface for Java and C#:

interface Pair<T, U> {
 T _1();
 U _2(); }

For Scala we'll use Tuple2, which has _1 and _2 as well. You could use Map.Entry and KeyValuePair in Java and C# respectively, but they seem to have extra semantic information in their names. I know some readers will be crying out for more semantic information than _1 and _2, but I hope they bear with me a moment.

Eliding the implementation, one could have a line of code like the following easily:

Java: Pair<String, Integer> pair = Pairs.pair("hello", 5);
Scala: val pair=("hello", 5)
C#: val pair = Pairs.Pair("hello", 5);

I expect that's fine with most people. For C# you'd probably change 'pair' to 'Pair' for the method name. Then, to start introducing the trick:

Java: Pair<Double, Pair<String, Integer>> withDouble = Pairs.pair(3.0, pair);
Scala: val withDouble = (3.0, pair)
C#: var withDouble = Pairs.Pair(3.0, pair);

You can see that the type in the Java code starts to look a little messy; this is no accident. Explicit static typing makes us more likely to choose less expressive types. Anyway, we can add a method 'prepend' to the Pair type, which doesn't modify anything, but returns a new Pair consisting of a data item on the left and the original Pair on the right. So we get:

Java: Pair<Double, Pair<String, Integer>> pair = Pairs.pair("hello", 5).prepend(3.0);
Scala: val pair = Pairs.pair("hello", 5) prepend 3.0
C#: var pair = Pairs.Pair("hello", 5).Prepend(3.0);

So prepend must be an interesting method, because it looks like you can use it to add more type parameters to something. Clearly you can't, I'm just chaining Pairs, but it makes a nice effect. So far not very useful; I'll get to that. First let's implement prepend:

Java:
 public class Pair<T, U> { ...
  public <V> Pair<V, Pair<T, U>> prepend(V v) {
   return pair(v, this); } }
Scala:
 implicit def Tuple2WithPrepend[T, U](tuple: (T, U)) = new {
  def prepend[V](v: V) = (v, tuple) }
C#:
 public class Pair<T, U> { ...
  public Pair<V, Pair<T, U>> Prepend<V>(V v) {
   return pair(v, this); } }

The nice part about this way of building up Pairs is that you can write methods to handle them instead of writing one per Pair arity. Specifically, you could gather up parameters for an immutable class then instantiate it in one go. In fact, that's what I do in a prototype for a JDBC wrapper. To wet the tastebuds (sorry, only Java for this one):

List<QuestionInfo> questions=select(conn).asString("question").asString("correct").asString("wrong").as(question).from("questions").toList();

The idea is that the above runs the SQL query: select question, correct, wrong from questions and constructs a QuestionInfo for each result, putting the result into a list.

The surprising thing is probably that there's no reflection or casting going on at all. Each asString (well, after the first one really) builds up more in a chain of generic types, then the .as(question) deconstructs them again. question is actually an F<Pair<String, Pair<String, String>>, QuestionInfo>, which means it's a function that takes 3 Strings and returns a QuestionInfo, roughly.

The above code comes from a working test case I published here.

It turns out that someone else had this idea way way way before I did, and made something professional out of it, though only some of that appears to be statically type-checked.

I hope that what I've showed here proves useful to you, and if you are my team leader and I pointed you at this page, remember that you saw it on the Internet, it's real, so you have to let me write it in our project.

So You Like For Loops? Zip It Up!

I've written this little for loop many a time, it finds all duplicates in a sorted list of integers:

List<Integer> nums=Arrays.asList(1,2,2,3,4,6,6,7,8,8);

List<Integer> dups=new ArrayList<Integer>();
int prev=nums.get(0);
for (Integer i: nums.subList(1))
{
    if (prev==i)
        dups.add(i);
    prev=i;
}

Now go and read your email or something, and come back to read just the for loop (and the line above it). You have to trace through time in your head to work out what it does. The code doesn't say what it means, but that's ok, right, because it works.. hmm.

Let's make up a type called Pair<X,Y>, and quickly imagine that List now has this nice method, zip. Here's the above list, zipped with a sublist of it starting from 1.

System.out.println(nums.zip(nums.subList(1)));
output: ArrayList((1,2),(2,2),(2,3),(3,4),(4,6),(6,6),(6,7),(7,8),(8,8));

Can you see how that relates to the original list? I hope so. Given this data, how would you find duplicates? Well, you'd look for any Pairs where the X and Y value are the same, easy. We'll call that zipped list 'zipped', of type List<Pair<Integer, Integer>>:

List<Integer> dups=new ArrayList<Integer>();
for (Pair<Integer, Integer> pair: zipped)
    if (pair.x().equals(pair.y()))
        dups.add(pair.x());

This for loop is a common pattern now, it's a 'collector'. At each iteration we have a/the list of dups, and the current pair. If the current pair has equal elements we modify the list of dups to make it have one more. Really, it seems like it should be a general operation, filter:

List<Integer> dups=zipped.filter(new Predicate<Pair<Integer, Integer>>()
{
    public boolean invoke(Pair<Integer, Integer> pair)
    {
        return pair.x().equals(pair.y());
    }
}).map(new Function<Pair<Integer,Integer>,Integer>()
{
    public Integer invoke(Pair<Integer, Integer> pair)
    {
        return pair.x();
    }
});

It's kind of better but the syntax is getting in the way. Hold up your closure glasses to the screen, or if you don't have any, I've kindly repeated the code but using the proposed Java 7 closures syntax:

List<Integer> dups=zipped.filter( { Pair<Integer, Integer> pair => pair.x().equals(pair.y()) } ).map( { Pair<Integer, Integer> pair => pair.x() } );

I hope that helped you read the previous code. Let's go one step further with these glasses, they are now magically type inference glasses. We don't need to specify the type of 'pair' because it's blindingly obvious from the type of zipped. We don't need to specify the type of dups because it's blindingly obvious from the return type of filter:

val dups=zipped.filter( { pair => pair.x().equals(pair.y()) } ).map( { pair => pair.x() } );

It looks to me like the braces in there are a bit redundant, the () after x and y are just annoying, and .equals is a Java design error that our glasses can correct:

val dups=nums.zip(nums.tail).filter(pair => pair.x==pair.y).map(pair => pair.x)

Und viz zis Scala zee transfurmaschun vill be complete! (parody of a parody)

Update: Thanks to David MacIver, who spotted a mistake, I had to add 'map' to each of the non-for-loop examples, and in updating it, I've stopped short of what might be the Scala norm - in a closure such as (x => x+2), where the closure parameter is only used once, you can write (_+2). So above you'd write blahblahblah.map(_.x) instead of blahblahblah.map(pair => pair.x).

Implementing OOP in Java

Object-Oriented Programming is all about late binding. Java has some support for it via polymorphism, but it is not as late as it could be. Java makes some attempt to guarantee things statically, e.g., method calls are guaranteed to correspond to an actual method at runtime. This has a couple of implications:

1. Some of the dynamism that languages like Smalltalk, Python, Ruby and Groovy have is lost.

2. In attempting to reach that dynamism, programmers end up doing things like: throw new UnsupportedOperationException, because their interfaces are too big, and having smaller interfaces would increase the number, and hence perceived complexity, of APIs (yes, this really is the reason java.util has 'optional methods' in interfaces).

Static typing, particularly when it's done really well, is incredibly useful. So useful that it can replace lots of unit tests, or even make unit testing even easier to write. It's actually possible to guarantee that code cannot have a runtime error, if you write it with that in mind. However, some code really needs to be dynamic, at least temporarily, because it's being written by an amateur, or needs to be swapped in or out at runtime, or is an idea that might not match up with your language's typesystem just yet. In that kind of code, guaranteeing that there are no errors is actually an anti-goal.

So, let's implement this idea of OOP, in Java. Some languages have a symbol type that is quite appropriate for this, but Java doesn't, so we'll use strings. To avoid annoying namespace collisions, we'll call our Object type Dyn, short for Dynamic. I chose this short name to not distract from the meaning of Dyn-using code. A Dyn is an object that has a method, ap, that takes a String and zero or more Dyns as parameters, and returns a Dyn. (Some conversion methods to Java's static types might be useful too)

public abstract class Dyn
{
    public abstract Dyn ap(String name,Dyn... args);
}

And an implementation, just enough to try it out:

public static final Dyn identity=new Dyn()
{
    public Dyn ap(String name,Dyn... args)
    {
        return this;
    }
};

The above Dyn is a bit silly, whatever message you send to it, it returns itself, and that's all. Here's one that holds a Java int and when the message "sqr" is passed to it, returns a Dyn holding the square of that int:

public static final Dyn squarer(final int i)
{
    return new Dyn()
    {
        public Dyn ap(String name,Dyn... args)
        {
            return name.equals("sqr") ? squarer(i*i) : identity;
        }
    };
}

Here I'm using the identity object to represent an error/missing method, which seems broken, but right now we can't actually observe that because there's no way to print a Dyn or convert it back to a Java object, so it doesn't really matter. I could add a toString() to the implementation to be able to see the results. I could write Rails for it, with all the method_missing goodness involved.

My question to you who have read this far is, if Dyn was made more a part of a static language instead of a clumsily-added library as shown here, would you be tempted away from Ruby et al? Let's, for this post, reserve the [] brackets to say 'in here be dynamic code'; any time we don't want the typechecker to look at our code, we put it in there, so we might write something like: Animal animal=new Dog(); [ animal.woof(); ] You could write all your code between [ and ], and gradually move it outside when you know how to make it type check, hence incrementally getting better reliability and performance (but reduced flexibility).

Note that this isn't the same thing as adding explicit static types to a dynamic program. Good static typing doesn't need explicit types everywhere, thanks to type inference.

Would this be an attractive option? Does such a language already exist?

When would you choose to repeat types?

I was surprised to see that some developers would prefer to repeat code with different
names rather than using abstractions.

In other words they name types by the way they're used instead of what they are.

I always like to consider the extremes of always applying a rule or never applying it.
If we made every use its own type we'd have lots of conversion functions to write
to avoid code duplication (but of course those functions would be duplicates).

The other extreme would be only naming a type by what it is so you'd never have
NameAndAge and AddressAndYear, you'd only have StringAndInt (or Tuple[String, Int])
and the meaning would only be shown by the use.

Tony Morris generally seems to agree, but he would give names to types when the
typesystem cannot express important things about the type, such as associativity.

AssocF[Int] instead of F[Int, Int, Int]

I've seen people prefer names for types in all cases, so they would never want
tuples or function types in their languages.

I think these programmers have a fear of abstraction. What do you think?

A Trivial Display of How Scala's Type System Beats Java's

This article shows that Scala lets you add methods to objects, depending on their generic types. In Scheme, and other lisps and languages influenced by lisp, there is a construct called a cons, which is a pair of values. Linked lists can be built up by 'consing' pairs together. The first part of a cons can be called the 'car' (if used as a list, this is the head), and the second the 'cdr' (if used as a list, this is the tail). So if you have a cons with a cons as its second element, you can think of that as a compound data structure with three elements. E.g.:

(cons 1 (cons 2 3))

The first value of the second part of that, 2, the head of the tail, the car of the cdr, is known as the cadr. Let's write a Cons class in Java and Scala and then look at how to add the cadr.

Consider this Java code:

class Cons<A,D>
{
    public final A car;
    public final D cdr;

    public Cons(A car,D cdr)
    {
        this.car=car;
        this.cdr=cdr;
    }
}

equivalent to this Scala:

case class Cons[A,D](car: A,cdr: D)

(yes, that's all)

Now let's think about cadr. If a Cons has a car of type A and a cdr of type D, what type is the cadr? It's the type of the car of the cdr, which we haven't got a type parameter for. We could try this:

class Cons<A,D extends Cons<E,F>> but there's a recursion problem here -- F must extend Cons<E,F>>, not going to work. Plus, even if that worked, we could no longer use Cons for simple pairs.

We can make a static method elsewhere:

public static <A,D,E> D cadr(Cons<A,Cons<D,E>> cons)
{
    return cons.cdr.car;
}

That works fine, but it makes cadr somewhat a second-class citizen. It's a shame we can't do pair.cadr. In steps Scala.

implicit def addCadr[A,D,E](cons: Cons[A,Cons[D,E]])=new { def cadr=cons.cdr.car }

Cons(1,Cons(2,3)).cadr gives 2

addCadr, when in scope (it can be imported if it's not written where we need it) defines an implicit conversion from Cons[A,Cons[D,E]] to an anonymous class that implements cadr. So any time we ask for cadr the compiler (not the runtime) looks at our Cons type, doesn't see cadr and looks for any implicit conversions that result in a type that implements cadr. In this case it finds one.

The above is probably not a very practical use, let's think of some. You can make a List[Char] have the same methods as a String, for convenience. You can make a List[Double] have a total method.

(The worst thing about Java generics is how annoying they are to type in blogger!)

In Defence of (0/:l)(_+_) in Scala

A few days ago, Doug posted a rather angry-sounding exit note about Scala, based on two and a half months of 'an in-depth look at the Scala language'. He pointed out some code as an example of how write-only Scala is:

(0/:l)(_+_)

I had no clue what this meant (the first part anyway) at first. Zero Slash Colon One? Is that a new band? I typed it into my Scala interpreter, and while I was typing it, I realised that the One was an Ell. Let's change the name now. l is a bad name. Call it x, xs, or kiwiFruit, but not l:

(0/:list)(_+_)

I then had a bit more of a clue. From the Scala book, I remember reading that operator names that end with a colon are right-associative. In other words, a+b is shorthand for a.+(b), but a+:b is shorthand for b.+:(a). So the above code can be rewritten as:

(list./:(0))(_+_)

This doesn't look a lot clearer, but we can now look up the /: method in the Scaladocs. It's not on List, it's on one of List's traits, Iterable. It's a fold. Here's a longer way of writing the code (and in a way I'd have understood immediately):

list.foldLeft(0)(_+_)

If you're still left bewildered by this version, let's go a bit further.

(_+_) is an anonymous function that takes two values and adds them with the + operator. Let's make up two names and roll them into place. x gets rolled into the first _, y into the second:

list.foldLeft(0)(x, y => x+y)

And if anyone's still not following, what this does is to sum all the elements of list. If the list is List(2,3,4) it looks like 0+2+3+4. Some languages/tools call it reduce (notably MapReduce/Hadoop), some call it inject (Ruby. Any others?). Some languages make you use a for loop, which I assume must be to stop you from getting too cocky about how good your code looks.

So, 1 minute after not understanding the original code, I understood it. The blog in question got mentioned on the Scala mailing list, and Martin Odersky, Scala's inventor, apologised, kind of:

That was my fault. I included it because I liked it, and that for two reasons:

1. (z /: xs) (op) looks like an abbreviation of a left leaning tree
with a `z' on the lower left end (at least to me). I.e. something like

      op
    /    \
   op    x1
  /  \
 z   x0

That's the tree I always draw when I explain fold left.

2. (z /: xs) has the operands in the ``right'' order.

I can see both points, and I'll still use foldLeft. I would not balk at someone else's code using /:. It took me 1 minute to understand, and now I can happily read folds written that way.

In discussions with other Scala programmers, I tried to say that the time taken to learn things isn't as important as how useful they are once learned, but I couldn't find a good way to say it. David MacIver, in an unrelated post to the mailing list, said what I intended to, but much better:

"Optimising your notation to not confuse people in the first 10 minutes of seeing it but to hinder readability ever after is a really bad mistake."

If only I could get him to stop arguing with Ian Clarke and write stuff I want to read!

If I used folds a lot, and perhaps I will someday, I would quite happily use the /: operator. Once I've internalised its meaning I can just get on with reading the names that I chose for things, rather than reading what the language forces me to have. Of course, to most of us, myself included, I'm not that used to folds, but if I considered folding to be just as primitive as +, I'd much rather write /: than foldLeft, just as I'd rather write + than plus.

The rest of Doug's blog really surprised me; I don't know how two people can spend the same amount of time in a programming language's community and get such different results.

My only explanation is that I am comfortable with Haskell, and a long-time Java programmer, so I probably have an advantage when it comes to Scala, which is largely Java minus some bad things, plus some good things from Haskell and many other places.

And while it's in my text buffer:

Don't assume that Scala is only useful for writing web apps, desktop apps, object orientated programming, functional programming, scripting, encoding mathematical properties and concurrency just because that's all that's been discussed on the mailing list this week.

Make Scala Your Language for 2008

Scala's a statically-typed language based on Java, but with features that make it comparable to Ruby, Groovy, Haskell, Python, Erlang and Smalltalk. It's pronounced "Skah-la", rather than "Skay-la", it has closures, gets rid of Java's controversial checked exceptions, and is almost perfectly interoperable with Java APIs.

There's an official book nearing completion (available now in PDF form), and some very clever people are using Scala (and some not so clever ones, like me). One of the core developers is called Lex Spoon, which has to be a plus for any language. Scala's been cooking, and by the time you finish reading this and procrastinating about whether to use it, it'll be ready.

It is one of those languages where boilerplate isn't welcome, yet is statically typed and supports both OOP and functional programming without blinking. Scala programs can use Java APIs effortlessly, and Scala turns out to be better than Java for testing Java code (despite some integration concerns raised by Ola Bini)!

So how can you use it? Obviously, install it, then you can launch its interpreter (you can use it as a scripting language or a regular compile-to-bytecode JVM language [though the difference is an elaborate illusion]). Here I'll launch the interpreter with the Google Translator API on the classpath:

$ wget -q http://google-api-translate-java.googlecode.com/files/google-api-transla
te-java-0.26.jar
$ scala -classpath google-api-translate-java-0.26.jar
Welcome to Scala version 2.6.0-final.
Type in expressions to have them evaluated.
Type :help for more information.

scala> import com.google.api.translate.{Language,Translate}
import com.google.api.translate.{Language, Translate}

scala> import Translate.translate
import Translate.translate

scala> import Language.{ENGLISH,SPANISH}
import Language.{ENGLISH, SPANISH}

scala> translate("bastante facil",SPANISH,ENGLISH)
res0: java.lang.String = Fairly easy

So it's pretty handy for trying out APIs, even built-in ones. Let's look at replacing all backslashes in a String with forward slashes, presumably to insert the resulting code into our Java program.

scala> "blah\\blah\\".replaceAll("\\","/")
java.util.regex.PatternSyntaxException: Unexpected internal error near index 1
\
 ^
        at java.util.regex.Pattern.error(Pattern.java:1700)
        at java.util.regex.Pattern.compile(Pattern.java:1453)
        at java.util.regex.Pattern.(Pattern.java:1130)
        at java.util.regex.Pattern.compile(Pattern.java:822)
        at java.lang.String.replaceAll(String.java:2190)
        at .(:4)
        at...
scala> "blah\\blah\\".replaceAll("\\\\","/")
res2: java.lang.String = blah/blah/

As you can see it's useful for prototyping little bits of Java too. But Scala in this case has a better way, too. Strings delimited with """ do not need any escaping (and can be multiline):

scala> """blah\blah\""".replaceAll("""\\""","/")
res4: java.lang.String = blah/blah/

Now the only escaping necessary is what Java's regex implementation requires.

Scala's method call syntax can be used without punctuation in some cases. x.y(z) can be written x y z, and x.y() can be written x.y. It also has implicit conversions, so if you define a conversion from type X to type Y, it looks as though X has all Y's methods. The type Int has a conversion to RichInt, and RichInt has a to(Int) method, so I can do:

scala> 1.to(10)
res0: Range = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

or even better:

scala> 1 to 10
res1: Range = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

The lack of punctuation makes some things really attractive:

scala> (1 to 10) ++ (20 to 30) map (_.doubleValue) map Math.sqrt filter (x => x-
x.intValue>0.5) map (x => x*x) map Math.round
res60: Seq[Long] = Array(3, 7, 8, 21, 22, 23, 24)

This code takes the range 1 to 10, the range 20 to 30, and concatenates them together, then gives another range with the same values as the first but as doubles, then another with the same values as the second, but square rooted, then it gives another range with only those square roots whose fractional parts are greater than 0.5, then another range with the remaining values squared, then another with rounded values of those.

You can read the code pretty much like a bash pipeline. Here's the same thing how I imagine a bash programmer would like it:

concat $(range 1 10) $(range 20 30) | map doubleValue | map Math.sqrt | filter x-x.intValue>0.5 | map x*x | map Math.round

As with bash, each new Range does not stomp over the memory of the previous one.

Let's insert the punctuation again to see how it looks with Java-style punctuation:

scala> 1.to(10).++(20.to(30)).map((_.doubleValue)).map(Math.sqrt).filter((x =>
 x-x.intValue>0.5)).map((x => x*x)).map(Math.round)

Eek! I think it's safe to say we wouldn't write such elegant code so often if we had to write (and read) the punctuation!

This use of methods as if they were infix operators is really powerful; so powerful that it is used for what we normally call infix operators. 3+4 is just 3.+(4) (operator precedence rules are preserved though).

That's enough for now.

A Functional Way of Testing OOP Programs

A message in OOP implies effects on entities[1], rather than mathematical functions. If you use mathematical functions in your code, how often they're evaluated isn't important:

    print cos 0*cos 0 is equivalent to:
    let x=cos 0 in print x*x

If you instead say that cos 0 is a message you send to an object, then you can't make that optimisation without knowing how the code you're calling works, because you'd be eliminating a message. cos 0 as a message may cause effects that you can't easily see as a caller; collapsing two messages to one can introduce different behaviour.

However, most of the time that you send an object a message it doesn't appear to perform an action, it just returns you some value. I'll name a method called for its value a function, and a method called for its effects simply a method.

If you can intercept effects that methods cause, then the method no longer causes effects, but describes them. In other words, if you notice an action and control whether it really happens, you've made the method appear to be a function, and you've made it easier to test, because you can observe all the actions that happen.

Such an interceptor, a body of code that intercepts effects as described could use metaprogramming of some sort, perhaps by changing classes directly at runtime, perhaps through compile-time techniques such as macros. However implemented, it would apply an automated transformation to the innards of methods. Let's see what we'd want that to generate, by writing the result of the transformation ourselves.

The interceptors in the following code vet, log or reject effects. I've made an interceptor return an interceptor on each call so that interceptors themselves can be implemented using return values rather than state changes. The code in this article is something a bit like Java, so that implementation details of a particular language don't get in the way.

public Interceptor writeSomeTextToFile(interceptor,text,file)
{
    (interceptor,val out)=interceptor.new FileStream(file)
    interceptor=interceptor.write(out,text)
    return interceptor.close(out)
}

It looks doable, but pretty ugly. One part of it can be improved. If we change Interceptor so that it can has a type parameter, we can get rid of the tuple return that interceptor.create gave:

public Interceptor[Nothing] writeSomeTextToFile
    (Interceptor[Nothing] interceptor,text,file)
{
    Interceptor[FileStream] out=interceptor.new FileStream(file)
    Interceptor[Nothing] two=out.write(text)
    return two.close(out)
}

It's really up to the Interceptor now what it does with that code. It could run the effects there and then, store them and never execute them, and our code would be none the wiser, because we haven't seen any mechanism for getting values out of the Interceptor.

The code processor to add interceptors would be pretty handy. Let's say we have an annotation that instructs some build tool or macro to do that, so now our source code looks like:

@WithInterceptor
public void writeSomeTextToFile(text,file)
{
    val out=new FileStream(file)
    out.write(text)
    out.close()
}

Our unit test can look like:

val passed={
    val ceptor=new LoggingInterceptor()

    return ceptor.invoke(writeSomeTextToFile,"hello","/etc/passwd")
                 .matches(list(creating(FileStream,"/etc/passwd"),
                               writing(FileStream,"hello"),
                               closing(FileStream)))
}

It's now clearly far easier to reason about and test the method, because you can trivially observe all of its side-effects. You could even decide which ones to allow, externally to the code, to implement a sandbox. In the usual case that you want to execute the effects immediately, you can still do that.

This is a very long-winded way of showing that methods are functions in disguise. Allowing methods to have difficult-to-notice side-effects makes them harder to reason about. It's harder to write tests for them, it's harder to think about them.

This interceptor technique could be applied to existing code, to compare the effects that a 1,000 line method has, to the effects that a refactored version of it has, in the same way we often write unit tests that compare returned values. It seems to make such a good regression test framework that I'd be very surprised if it didn't already exist for most mainstream languages.

The interceptor technique is very heavily based on monads (and may even just be a monad). Haskell programmers, the biggest monad users today, even have special syntax for the interceptor chaining; the translation I mentioned is built into their compiler. In fact, they can do all the things OO programmers do, but they make it harder to have unwanted side effects. To my knowledge though, Haskell's IO monad is largely implemented as a compiler hack, so it's hard to write the same tests for side effects that I've showed in this article.

[1] "in object-oriented programming languages such as Smalltalk or Java, a message is sent to an object, specifying a request for action." -- http://en.wikipedia.org/wiki/Message

Java 7 Example - Writing Your Own Foreach

One of the promises of closures was that if Java 5 had closures instead of foreach, you could have implemented foreach as a method. Let's put that to the test with the Java 7 prototype.

Firstly, the 'control invocation syntax', which is a little subjective, hasn't been implemented in the prototype, so anything I show here is certainly less than foreach could be with closures.

Here's a simple attempt:

public static <T> void foreach(T[] ts,{T=>void} block)
{
    for (int a=0;a<ts.length;a++)
        block.invoke(ts[a]);
}

I can call this like so:

foreach(new String[]{"hello","world"},{String s=>System.out.println(s);});

I found that I kept repeating one error in testing out this prototype, namely forgetting the ; for a statement in a {something=>void} closure.

Anyway, the above doesn't work with continue, break or return. Those are not bound yet by the closures prototype. No matter, let's roll our own (ignoring return; I don't know of a way to apply the following technique to return).

Not only can we pass a closure to a method, but the method can pass a closure to our closure! No, I've not yet gone mad:

public static <T> void foreach(T[] ts,{T,{=>void},{=>void}=>void} block)

Perhaps the T,{=>void},{=>void} is better abstracted into a ForeachControl class or something. Imagining that it was, the T field would be called 't', the first {=>void} would be called 'brake' (as in break, but avoiding collisions with the keyword), and the second {=>void} would be called 'cont' (as in continue).

For now, I'm quite happy to use the above. I'll just reiterate it:

{T,{=>void},{=>void}=>void} is a function type that takes a T, and two {=>void}s and has no return value. A {=>void} is a function type that takes nothing and returns nothing, analogous to Runnable. Here's some example usage:

String[] input={"fish","print","fingers","don't print"};

foreach(input,{String s,{=>void} cont,{=>void} brake=>
        if (s.startsWith("fish"))
                cont.invoke();

        System.out.println(s);

        if (s.startsWith("fingers"))
                brake.invoke();
});

Ok, that kind of looks like a foreach statement now, plus some baggage for loop control. Actually that's as far as I can go in the current prototype. Let's implement foreach then.

cont and brake both need to 'send a message' to the foreach method, without allowing the closure to finish. Without convoluting the usage code above, I can do that by making cont and brake throw exceptions, which is very similar to how continue and break are planned to be supported in closures, except I'm doing it in-language.

public static <T> void foreach(T[] ts,{T,{=>void},{=>void}=>void} block)
{
    class Continue extends RuntimeException { }
    class Break extends RuntimeException { }

    for (int a=0;a<ts.length;a++)
    {
        try
        {
            block.invoke(ts[a],{=>throw new Continue();},{=>throw new Break();});
        }
        catch (Continue c)
        {
            continue;
        }
        catch (Break b)
        {
            break;
        }
    }
}

Look at the block.invoke line. I'm passing two closures to block.invoke - one that throws a Continue and one that throws a Break. Other than that, this method is pretty simple.

As I've said elsewhere, even when/if the control invocation syntax appears, you won't be able to implement foreach exactly as in Java 5, because int cannot be a type parameter, and the closures spec doesn't specify any boxing between int and Integer for type parameters.

Even if you never use this code (I won't!), you can see at a small scale the power of thinking in closures, especially for implementing language features. This is one of the reasons why Smalltalk was such a small language - you could implement much of what Java programmers think of as language as library methods. Lisp and FORTH are small languages (at least conceptually - ignore Common Lisp!) for similar reasons. Java 7 is aiming in the same direction.

Java 7 Example - Pattern Matching

One way you can measure a programming language is by taking a feature, either one that it has, or not, and seeing how close you can get to implementing that feature without writing your own parser, etc. Let's take a look at (and copy!) one of Scala's (and many other languages') features; pattern matching:

animal match {
    case Dog() => "woof"
    case Cat() => "meow"
}

It's very similar to a switch statement, and the above really doesn't show how flexible pattern matching is, but it will suffice for now. The usual way of writing the above code in Java would be with some nested instanceof checks and casts, or by adding a speak() method to the Animal type hierarchy.

It's not always practical to add methods to types directly in Java.. e.g., if you're dealing with classes you don't control. And instanceof is fallible - you don't want to have: if (animal instanceof Car) pass compile-time checks, but it does. So let's see how close we can get to the above pattern matching using the Java 7 prototype. I hope you can do better than me!

Here's what I'd ideally want in Java:

Animal animal=Math.random()<0.33 ? new Cat() : Math.random()<0.5 ? new Dog() : new Horse();

System.out.println(match(animal,
                        {Cat c=>"meow"},
                        {Dog d=>d.name+" says woof"},
                        {Horse h=>"neigh"}));

What type would match take as parameters? For now, let's imagine that we're always dealing with Animals, and always returning Strings.

public String match(Animal animal,{? extends Animal=>String}... cases)

That's not legal - {? is an "illegal start of type" according to the compiler. Neal said that because the things on the left hand side of a closure automatically have ? super in their types, I can't also have ? extends. If I replace it with the interface that javac generates it compiles fine:

public String match(Animal animal,OO<? extends Animal,String,null>... cases)

(the null part there specifies the exception types that may be thrown - in a function type you can omit that)

We can't actually call that method without getting at least a warning from the compiler, thanks to varargs using arrays instead of generics. I'm sure that must have made sense to someone at the time. If I convert it to List<OO<? extends Animal,String,null>> cases, I still have a problem. Inside match, I don't know what type ? is, so I can't do anything with it. Next trick then:

class Case<T>
{
    public final Class<T> clazz;
    public final {T=>String} function;

    public Case(Class<T> clazz,{T=>String} function)
    {
        this.clazz=clazz;
        this.function=function;
    }
}

Now I could have List<Case<? extends Animal>> as the parameter type. Here's some sample usage then:

System.out.println(match(animal,
                         new ArrayList<Case<? extends Animal>>(){{
                             add(new Case<Cat>(Cat.class,{Cat c=>"meow"}));
                             add(new Case<Dog>(Dog.class,{Dog d=>"woof"}));
                             add(new Case<Horse>(Horse.class,{h=>"neigh"}));
                         }}));

Note that I'm taking advantage of a little trick for creating lists inline by creating an anonymous subclass of ArrayList and providing a static initialiser. Verbose? Yes. Ugly? Yes. But enough about me. That code will be gone in a moment.

Look at each line. I've got Cat three times in the same line. Ugh. In fact if I make match generic, so that it can return something other than String, then I'll have to add a type parameter to Case for that, and then those lines become even worse. There must be a better way.

I can use a fluent interface/embedded DSL, or, erm, in real words, "readable code" by making match(animal) return a matcher, and putting a method on it, add, that has a type parameter, U, and takes a Class<U> and a U=>String. In fact, let's go the whole generic hog and make it take a Class<U> and a U=>R, where R is the return type we want. When we've finished adding cases, we call done(), which returns R.

Usage:

System.out.println(match(animal)
        .add(Cat.class,{Cat c=>"meow"})
        .add(Dog.class,{Dog d=>"woof"})
        .add(Horse.class,{Horse h=>"neigh"})
        .done());

One step at a time then. match is a simple wrapper method around a type called Matcher, that lets us avoid writing new Matcher<Animal,String>:

public static <T,R> Matcher<T,R> match(T t)
{
    return new Matcher<T,R>(t);
}

Matcher is a class that stores the T passed into its constructor, and an R to return, which is initially null. It has a method, add, that has a type parameter, U, which extends T. Having U extends T guarantees I don't add an invalid case, such as one that tests whether an animal is a Car.

class Matcher<T,R>
{
    public final T t;
    public R r;

    public Matcher(T t)
    {
        this.t=t;
    }

    public <U extends T> Matcher<T,R> add(Class<U> aCase,{U=>R} f)
    {
        if (aCase.isInstance(t))
            r=f.invoke(aCase.cast(t));

        return this;
    }

    public R done()
    {
        return r;
    }
}

The type parameter U is declared to extend T so that you cannot add a case that is impossible, e.g., .add(Car.class,{Car c=>"beep"}) (which makes no sense unless a Car is an Animal).

Get this code, as one compilable/runnable file.

Java 7 Prototype - Surprises and Expectations

In my first week of testing the prototype, I found quite a lot of bugs, and some more subjective defects.

Neal Gafter seems amazingly fast at fixing bugs, so there's probably not much point reporting any bugs on this blog. I'll run through some surprises instead. If you want to see the bugs I found, take a look in the test/ directory in the prototype. Neal put some of my bug reports in as Clarkson2.java etc. It looks like he uses some automated testing on those, so if he breaks one he should know before I report it again!

If there's anything in this code that you don't understand, just ask. I mainly wrote it to test the prototype, so I wasn't overly concerned with writing good code. Most of these code samples are from bigger programs that I chopped down whenever I found a bug.

And now to the meat.

1. Definite assignment rules make it difficult to write recursive closures.

(1)
{int=>int} factorial={int x=>x<2 ? x : x*factorial.invoke(x-1)};

The above only works if factorial is a field, not a local variable, because factorial is not 'definitely assigned' on the right hand side of the =. I've been playing with Scala a bit recently (which has given me some good fuel for testing this prototype with), and it doesn't have this restriction. After a conversation with David MacIver, a Scala programmer rather than a dabbler like myself, we came to the conclusion that it's possible to cause a NullPointerException in similar code to the above in Scala.

Lo and behold, Neal replied with much the same argument - if the definite assignment rules were relaxed, the following code could fail, or even do undefined things:

(2) {int=>int} factorial=f({int x=>x<2 ? x : x*factorial.invoke(x-1)});

If f() invoked the closure, then factorial would be accessed before it had been assigned a value. In Scala that is guaranteed to give a NullPointerException, because all variables are assigned to null/0/false before being assigned their real value. In Java, the verifier would not load the code, because it would possibly use values that had been in memory before.

However, for the actual case above (not (2), (1)), it's easy to see that the closure is not invoked before factorial has been assigned a value. I think this idiom is useful enough to make a special case for, but then I'm not involved in writing either the code or the specification so I can't really estimate that task.

The obvious workaround would be:

{int=>int} factorial=null;
factorial={int x=>x<2 ? x : x*factorial.invoke(x-1)};

..except that local variable capture is not supported yet. The current workaround is to make factorial a field instead of a local variable.

If I ever get my head around combinators properly I think I'll have a better workaround.

2. Java 5's foreach statement cannot take a closure.

This code fails:

for (final String s2: {=>asList(args).iterator()});

This code works:

Iterable it={=>asList(args).iterator()};
for (final String s2: it);

The only difference is that I explicitly made closure conversion happen. Typecasting would not fix it (ClassCastException). This is apparently as specified, as a foreach is only specified to take an Iterable or an array. It's not a huge issue, and I can't think of any use cases, but it's still a surprise.

3. Autoboxing doesn't apply to function types.

{Integer=>Integer} f={int x=>x*2}; is a compile error.
{int=>int} g={Integer x=>x*2}; is a compile error. This doesn't look insane on its own, but because generic type parameters cannot be primitive types, it has repercussions. I can't write a generic map function and use it like this:

Iterable<Integer> mapped=map(asList(1,5,11,26),{int x=>x*x});

I have to use the more verbose and more indirect-looking {Integer x=>x*x}.

There's no way of writing a single generic method that converts a primitive function to a wrapper function, again because generic type parameters cannot be primitive types. I could write 8 individual methods, e.g.:

public static {Integer=>Integer} lift({int=>int} f)
{
 return {Integer i=>f.invoke(i)};
}

etc.

However, there's again no way of generalising those to make them work with {int,int=>int}, etc. There is no subtyping relationship between different function types, except the covariance and contravariance rules, quickly demonstrated here:

{Number=>Number} f={Object o=>5};

The above compiles because any Number input is obviously also an Object, and because the output, 5, is obviously a Number (autoboxing taken for granted).

The lack of autoboxing also means that sometimes you'll have to explicitly supply the generic types. Here's an example:

class Main
{
        public static void main(String[] args)
        {
                int i=id().invoke(5);
        }

        public static <T> {T=>T} id()
        {
                return {T t=>t};
        }
}

This code won't compile, because the compiler judges the <T> in the call to id() from main to be int, which cannot be a type parameter. Neal says this isn't a bug. This version compiles:

class Main
{
        public static void main(String[] args)
        {
                int i=Main.<Integer>id().invoke(5);
        }

        public static <T> {T=>T} id()
        {
                return {T t=>t};
        }
}

I think this is a bug; it seems that inference should pick Integer instead of int in the first case.

Another implication of the lack of autoboxing is that when the closure invocation syntax arrives, that Neal promised would let you reimplement the foreach loop yourself as a method, you won't be able to. I expect this will work, if you write your own foreach method:

foreach(Integer i: asList(3,4,5))
 System.out.println(i*i);

but this won't:

foreach(int i: asList(3,4,5))
 System.out.println(i*i);

4. Closures cannot implement generic methods.

This one is much easier to describe in code than words. Given:

interface Identity
{
 <T> T id(T t);
}

..it is impossible to implement this with a closure. I think Haskell allows something like this. Scala doesn't. A use for this would be in implementing some kind of Either type, where an Either<X,Y> may hold an X or a Y, and you don't want to actually have to test which it is, just call a method in Either, supplying a function to run if it holds an X, and a function to run if it holds a Y. The return type of that method should be generic.

Stay tuned for some examples that actually do work with the prototype, at least one of which is actually interesting!

Life in the old Java yet - Closures Prototype

I get home from eating some overpriced underportioned seafood, and drinking a few stouts, phone my girlfriend and check my email. Nothing out of the ordinary, nothing interesting.. but wait! An email from Neal Gafter with a closures prototype! Wow!

So I download it, follow the instructions and it fails. Hmm. I'll try on Linux. javac -version works. I write my first working Java program with closures. I write my second! I mention it in an IRC channel or two, excitedly! I remember that I'm still on the phone and have no idea what she said for the past 5 minutes, so I lower my laptop lid. I get off the phone as quickly as possible, which is to say we talk for another half hour, which is to say she talks for another half hour.

An hour or two after that I send Neal a list of about 5 or 6 problems with the prototype, but go to bed happy, especially having drunk a Spitfire. A beer, not a WWII aeroplane.

First thing in the morning, he's fixed the problems, so I download again. The same problems are there. Hmm. Oh, right, the filename included the date. What's today's date (it was 2am today that I sent the emails)? 2007-10-22. But Neal's in America, and they're backward, so 2007-10-21. Ok, got the right file now. Still fails in Windows, and at least one of my reported failures still fails but for a different reason. I start playing again, and some more code fails for the same reason as the first, so I give up for now.

There's much more fun in breaking a prototype compiler than a production one!

Ok, new day, and I'm at my girlfriend's house for the evening. Neal's just sent another prototype, and it still doesn't work in Cygwin. I can't get my laptop online to connect to Eugene Ciurana's Linux box that I was testing on, so I start looking at the bin/javac script. I see and fix the not-on-Windows problem. It's passing a full path to lib/javac.jar to javac, and that includes /cygdrive/c, Cygwin paths, which Java doesn't know about. I find a fresh batch of bugs and surprises. After finding the same bug twice from unrelated pieces of code (and getting pestered to watch a film) I stop trying. Neal confirms the bugs, but nothing new arrives the next day.

Over the next few days I find more and more bugs, and Neal fixes them all. There are a few bugs that turn out to be features; they're actually in the spec that way.

Now that I have a fresh set of bugs waiting to be emailed to Neal, he's just published the closures prototype. You can find it over at his blog.

I'll shortly publish some surprises from playing with the prototype, then some examples of what you can (and can't) do with it. In a less commentative style..

IDEA 7 - A Release Too Early?

I downloaded the new IDEA 7 release today, and pondered buying the upgrade licence, but went with the 30 day trial first. Here's a little video I made of an editing bug that I noticed immediately.

(If anybody can figure out how to get a .swf into a blogger page, please tell me how. Blogger just mangled any HTML I used to do it.)

Another niggle is that, including the milestone releases, the inspections that use @Nullable and @NotNull seem not to be present, and with no mention of why. Hopefully they're now just in some plugin that I don't happen to have installed. That's a bit of a show-stopper for me, I changed my coding style to use those annotations. I'd have to convert to FindBugs' equivalent to continue using that coding style.

Why Java Needs Closures (It Already Has Them)

Some bloggers and people I've talked with think of closures in Java as something unnecessary - e.g., "why must we copy C#?". As it happens, most languages have closures, including Java.

A closure is an executable block of code that can refer to free variables from the enclosing scope. Here's an example in Java:

public void example()
{
        final double use=Math.random()*10000;

        SwingUtilities.invokeLater(new Runnable()
        {
                public void run()
                {
                        System.out.println(use);
                }
        });
}

It's not a great example of how closures are useful. The instance of that anonymous class can reference the variable 'use'. In fact, there's a leak in the implementation that gets into the language - 'use' has to be final. That doesn't stop the anonymous class from being a closure. Let's consider how life would be if Java didn't have closures:

public void example()
{
        double use=Math.random()*1000;

        class MyRunnable implements Runnable
        {
                private double use;

                public MyRunnable(double use)
                {
                        this.use=use;
                }

                public void run()
                {
                        System.out.println(use);
                }
        }

        SwingUtilities.invokeLater(new MyRunnable(use));
}

In fact, that's not far off what the first code sample gets compiled to. In Java 1.0, inner/nested/local/anonymous classes didn't exist, so you'd have to take the above MyRunnable, and put it in a separate file, but the code would be the same otherwise. If you were going to complain about Java getting closures, Java 1.1 was the time to do it!

The above two code samples work in today's Java, and some of you might even favour the second, because it's more explicit - it matches the bytecode more closely.

The way I think is that you should, at least as a thought experiment, take anything like "favour explicit code over abstract code" to an extreme, to test it out. The most explicit you can be in programming is to write assembly code, and none of us wants to do that. Let's flip it around. The most abstract you can be in programming is to write in Lisp, and none of us wants to do that. Both of those statements have holes in them, of course, there are some people who love writing assembly, and there are some who love writing in Lisp. I'm one of the latter.

As it turns out, abstraction is so prevalent in programming that most of us program in languages that are closer to Lisp than they are to assembly. C is the lowest-level programming language that I know, and even it has huge abstractions over the underlying assembly.

Java programmers are already programming on an abstraction, the Java Virtual Machine, before they even worry about syntax. It seems that we already favour abstract code over explicit code. Abstract doesn't mean imprecise, or vague, it's another way of saying "general". We can use abstractions to stop repetition.

Consider the above code samples as templates of some kind:

        final $TYPE $VAR=$VAL;

        SwingUtilities.invokeLater(new Runnable()
        {
                public void run()
                {
                        $ACTION($VAR);
                }
        });

and

        $TYPE $VAR=$VAL;

        class $BLAH implements Runnable
        {
                private $TYPE $VAR;

                public MyRunnable($TYPE $VAR)
                {
                        this.$VAR=$VAR;
                }

                public void run()
                {
                        $ACTION($VAR);
                }
        }

        SwingUtilities.invokeLater(new $BLAH($VAR));

The first template has 4 parameters, $TYPE, $VAR, $VAL, $ACTION. It mentions $VAR twice, the others once each.

The second has 5 parameters, $TYPE, $VAR, $VAL, $ACTION, $BLAH. It mentions $TYPE 3 times, $VAR 6 times, $VAL once and $ACTION once. We're always taught not to repeat ourselves in programming, and we can easily see that the second template is more repetitive than the first. A less well-known rule is to avoid unnecessary names. MyRunnable is a name that's defined once and used once - a bad sign.

Extra repetition means extra scope for errors. You might change 'use' between calling invokeLater and invokeLater actually happening - now you've got a sync problem. This is because you had to copy your variables yourself. Admittedly, thanks to the 'final' restriction, Java doesn't help much there, but at least it stops broken code from compiling.

Let's briefly return to the restriction that the local variables that anonymous classes capture must be final. Does that stop anonymous classes from being closures? Changing the values of variables is kind of an optional feature in programming languages. Mathematics seems to have managed without x++ for many years. Java's anonymous classes place some restrictions on what kind of variables are considered free, but that doesn't stop them from being closures. Haskell definitely has closures, and definitely doesn't have mutable variables.

Ok, with all that out of the way, we now know that Java has closures, and they aren't disappearing anytime soon. Let's take a moment to laugh at the blog posts (actually most of them are anonymous comments on blogs) saying that Java doesn't need closures.

There. Now let's briefly examine why Java needs better closures, by returning to our template. This time we're going to read it with boilerplate glasses:

        boilerplate double use=Math.random()*10000;
        SwingUtilities.invokeLater(boilerplate System.out.println(use));

What we'd like to do now is to make that boilerplate disappear. Scala has an interesting way of doing that:

        val use=Math.random*10000
        invokeLater(System.out.println(use))

Scala methods can have lazy parameters, that is, parameters that are not evaluated at call time, but are evaluated when the method wants to. You can use that to write your own if method, e.g.:

        myIf(Math.random<5,System.out.println("Still here"),System.exit(0))

Of course, myIf is just an interesting result, and not actually useful, but in the case of invokeLater it is useful; it gets rid of a lot of our boilerplate.

Java 7 closures let us do pretty much the same thing:

        double use=Math.random()*10000;

        SwingUtilities.invokeLater({=> System.out.println(use));

There is another syntax for the last line:

        SwingUtilities.invokeLater()
        {
                System.out.println(use);
        }

We still have a little boilerplate with both these syntaxes, but not enough to need the boilerplate glasses. Sadly, despite it being technically possible for IDEs to become boilerplate glasses, they haven't done so. Folding an anonymous class in IDEA looks like:

        new Runnable(){...}

They've folded the wrong thing. Duh. It should look more like:

        new ...{System.out.println(use);}

Some people think that Java doesn't need better closures because Java as a language is already broken in many ways. Often Scala is quoted as the next Java. I've tried Scala out - it's very impressive, and similar enough to Java to not have too many surprises. So in one sense I agree, but I also think that Java should have better closures to move the status quo of programmers up a notch. Programmers should consciously favour abstraction over boilerplate, instead of the current situation, where many use abstractions all the time but are reluctant to invent their own.

Being free of boilerplate lets you think in different ways. My post on point-free programming shows one route you could take - there are many others.

Point-free Programming in Java 7 - Beyond Closures

Here is an introduction to point-free programming, using Haskell, Scheme, Java 5 and the proposed Java 7 for examples, and a couple of ideas for how the Java 7 proposal could improve to make point-free programming more practical.

I've grown quite accustomed to programming in lambda style now, in Common Lisp, Scheme and Haskell. Here's a quick example of how that looks:

Scheme: (lambda (x y) (+ x y))
Haskell: \x y -> x+y
Java 5:

new FunctionIII()
{
    public int invoke(int x,int y)
    {
        return x+y;
    }
}

Java 7: {int x,int y => x+y} Not too bad. You could use this to fold (or reduce) across a list. To fold is to apply a function on a starting number and an element of a list, and then to apply the same function on the returned value and the next element of the list, until the end of the list. You could use this to compute the sum of all the elements of a list:

Scheme: (foldl (lambda (x y) (+ x y)) 0 (list 3 4 5 6 7))
Haskell: foldl (\x y -> x+y) 0 [3,4,5,6,7]
Java 5:

foldl(new FunctionIII()
{
    public int invoke(int x,int y)
    {
        return x+y;
    }
},0,asList(3,4,5,6,7));

Java 7: foldl({int x,int y => x+y},0,asList(3,4,5,6,7));

One point to note here is that you could, in Scheme, write this as (+ 3 4 5 6 7), because Scheme's + function takes any number of arguments, even 0 (whereupon it returns 0). So this is a contrived example using non-optimal code.

It's not idiomatic Haskell either. For a start, you can write sum [3,4,5,6,7], and avoid foldl altogether. Bear with me for a moment though. In Haskell, you can shorten \x y -> x+y to simply (+), which means 'the function called +'. In Scheme you don't even need the parentheses. +, used in a 'value position', which is anything other than the first in a list, refers to the function +, rather than calling it. So you can do:

Scheme: (foldl + 0 '(3 4 5 6 7))
Haskell: foldl (+) 0 [3,4,5,6,7]

This is the simplest example I can think of of pointfree style, which is where you remove lambda expressions but without introducing mutable variables. Here's a better example:

I want to multiply all elements of a list by 2. Here's the lambda style:

Scheme: (map (lambda (x) (* x 2)) (list 3 4 5 6 7))
Haskell: map (\x -> x*2) [3,4,5,6,7]
Java 5:

map(new FunctionII()
{
    public int invoke(int x)
    {
        return x*2;
    }
},asList(3,4,5,6,7));

Java 7: map({int x => x*2},asList(3,4,5,6,7));

But these lambda expressions don't really express my intent that well. I want to map the function 2* across the list. Haskell has a convenient syntax for this:

Haskell: map (2*) [3,4,5,6,7]

What I've done there is to specify the * function, with its first argument filled in. This works because all functions in Haskell are automatically curried. If I type this at the REPL:

:type (*)
Output: (*) :: (Num a) => a -> a -> a

This looks a bit confusing if you're not familiar with it. What it means is that (*) is a function with a type parameter, a, which in Java terms would look like <a extends Number>. It takes one parameter of type a, and returns a function that (takes one parameter of type a, and returns a value of type a). Parentheses used for disambiguation there, this turns out to be hard to write in English.

:type (2*)
Output: (2*) :: (Num t) => t -> t

That means that (2*) is a function with a type parameter, t, which is an instance of the Num typeclass (the same as 'a' in the first example). It takes one parameter of type t, and returns a value of type t.

So I can call (2*) as an ordinary function, adding a value (this is called taking a section, and is a way of partially applying a function). The following expressions all have the same output, 8:

(2*) 4
(*2) 4
(*) 2 4
((*) 2) 4

This seems like an interesting but not-so-useful result of automatic currying at first, but you can actually rewrite any lambda expression in this style. Sometimes the code will be easier to read than a lambda expression, sometimes not. Here's a more complex example:map ((+10) . (*2)) [3..6]

The . operator means function composition, like in mathematics - f(g(x)) would be written as (f . g) x. You can compose functions before you have the values to give them, so f . g has a meaning. Read ((+10) . (*2)) as: "multiply by 2 then add 10". Look ma, no variables!

Scheme doesn't have any support for this, as its procedures are not automatically curried, but you can make something similar happen:

(map (compose (plus 10) (multiply-by 2)) (list 3 4 5 6))

plus and multiply-by need defining in an odd way:

(define plus
    (lambda (x)
      (lambda (y)
        (+ x y))))

(define multiply-by (lambda (x) (lambda (y) (* x y))))

You can write a general curry procedure in Scheme, but as there's no portable way of discovering how many args a procedure takes, you have to supply the arity. Plus, some procedures are of variable arity.

(curry 2 +) would return a procedure that takes a value, and returns a procedure that takes a value and returns the sum of the two values, used like this:

(((curry 2 +) 4) 5) ;; output: 9

Java 5:

public static final FunctionIO<FunctionII> plus=new FunctionIO<FunctionII>()
{
    public FunctionII invoke(final int x)
    {
        return new FunctionII()
        {
            public int invoke(int y)
            {
                return x+y;
            }
        };
    }
};

For brevity I'll leave multiply-by out.. it's the same but with + changed to *!

Java 7:

public static final {int => {int => int}} plus={int x => {int y => x+y}};
public static final {int => {int => int}} multiplyBy={int x => {int y => x*y}};

map(compose(plus.invoke(10),multiplyBy.invoke(2)),asList(3,4,5,6));

Because both Scheme and Java make you curry explicitly, they discourage point-free programming (although it's still possible, and quite useful). I'd like to see all function types in Java 7 be automatically curried. In other words:

{int,int => int} should be the same as {int => {int => int}}.

This doesn't have to have any negative impacts at runtime, as demonstrated by Haskell's great performance.

To make it really useful, it should also be applicable to operators, so that #+ gives a {int,int => int} and #+.invoke(2) gives a {int => int}. (where #+ is a possible syntax for taking a reference to +).

Sometimes you'll want to provide the second argument rather than the first. Haskell's solution to this is a function called flip:

(flip (/)) 3 6 -- gives 2, the result of 6/3. I could use it in this possible future of Java with #/:

flip(#/).invoke(3) would return a {int => int}, that, when you pass it a number, it returns that number divided by 3. Equivalent to Haskell's (/3).

As you do more and more in point-free style, you get more and more used to it, as one would expect, and some constructs that seem unnatural at first seem normal later. I'm still a novice, but I'm having fun.

Stop Sitting On The Type Fence

Static typing is not just about preventing simple bugs, and dynamic typing is not just about writing millions of tests that you wouldn't have to write with static typing.

Programmers of languages like Java, C#, C, C++, etc., middle-of-the-road statically typed languages with some dynamic features, have some intuitions, built up from years of experience at getting the best out of their language, but don't often stop to see what contortions their language makes them go through, or that they are limited in what their compiler tells them about their code.

They often think that rigorous static typing is about preventing bugs that a few unit tests would solve, or that dynamic typing is about writing tests that static typing would solve.

Static Typing is Not About Low-Hanging Bugs

Many years back, clever mathematicians proved that functions express types. If you have an expressive enough type system, you only need to give the input and output types for a function, and you have its implementation. Consider the identity function, written in Scheme like this:

    (lambda (x) x)

Don't worry if lambdas are unfamiliar to you. No, actually, do worry. Lambdas underpin most of computer science and certainly all of programming, even if that's not obvious. If, as I did, you gained a Computer Science degree without ever hearing about lambdas, ask for your money back, and spend it on a copy of The Structure and Interpretation of Computer Programs (SICP) for you, all your friends and family. It's also available in PDF form for no money, in case you're unsuccessful in getting your money back from your University.

Anyway, a lambda expression is analogous to an anonymous function in many languages, and even an anonymous class (with one method) in Java. The particular lambda expression above is a function that takes a value, and returns that same value.

In Haskell, the syntax isn't much different:

    \x -> x

The \ is Haskell's approximation to the Greek letter lambda, the bit before -> is the parameter list, and the bit after it is the result. Scheme doesn't care about telling you the types of things, but Haskell does. The type of \x -> x is t -> t, which means it's a function that takes a t (which can be anything) and returns a t (which is the same as the first t). All fairly obvious.

Given the above, there's only one logical implementation of t -> t, and that's \x -> x. You could make silly ones, where you store x in a local variable, and then return it later, but they're all equivalent. Or perhaps the implementation could look up the type of x, and grab something similarly-typed from a cache. All a bit silly though. Perhaps if all types in a language had a clone function, then you could provide a different implementation, but without that, or something similar,

What you can see from this is that, at least for simple functions, you only need the types to derive the implementation. Does this scale up to things like \x y -> x/y, etc.? Yes, as it happens, though you then need the concept of dependent types, which is types that depend on runtime values. They can still be checked at compile time. In other words, types and values are isomorphic to each other (isomorphic is a mathematical way of saying 'equivalent').

What does the Java version of the identity function look like? Oddly, it depends on whether you write it how Scheme works, or how Haskell works. In Scheme there are no compile time types (or you can say there is exactly one), and the closest that Java comes to that is Object:

    public static Object identity(Object x)
    {
            return x;
    }

If you write it like Haskell, then you need to make sure that the return type is the same as the input type, with no silent upcasting (to Object):

    public static <T> T identity(T x)
    {
            return x;
    }

There is quite a difference between the two pieces of code, which is particularly disturbing, because the Haskell and Scheme versions look so similar to each other. In fact, there's a project called Liskell, which gives Haskell lispy syntax. There, the two would probably be the same. This is a first hint that Java gets in the way of thinking about static typing, by making it very verbose, in particular by making untyped code look different to typed code.

Haskell is also guilty of this, partly by design, and partly because of some deficiencies in its type system. That's the reason that the side of the fence I sit on is the dynamically typed one, but I keep my eye on the static typing people, because they come up with great ideas, and secretly I'd like to be able to use their type systems on some of my code.

So static typing isn't just about making sure that you don't add two credit card numbers together, it's about expressing code as close as possibly to mathematics. Mathematicians tend to be very good at reducing problems to their smallest representations, and coming up with very general solutions, so there can be no doubt that this approach will (and already has) produced amazing results.

Haskell's type system is certainly imperfect, and so are its programmers - this is clear because of the presence of its unit testing system, QuickCheck. If the type system was perfect, and the programmers using it never took shortcuts, there would be no need to run unit tests. It would be evident by the compiler succeeding, that the code could not crash, or produce any results outside the expected range.

If you look for more and more sophisticated type systems, you will probably come across Coq at some point, which is a proof engine that can generate executable code. There you deal with logic, with set theory, all things that are the pinnacle of static typing, and which my Computer Science degree, and probably yours, did not cover.

Go there. Have a look. Even if you decide that static typing is not for you, or that you'll get by with a lesser static typing system such as Haskell's or Java's, you can learn a very general way of thinking that will apply across a lot of programming, in the same way that understanding lambdas will help you when you see C# delegates, JavaScript's anonymous functions, etc.

Dynamic Typing is Not Just About Writing Tests

Many static typing proponents, even Haskellers, have the opinion that while Lisp, Python, Ruby, JavaScript, et al, might have some nice syntax, the fact that they are devoid of static types makes them ultimately useless. You can't easily get the compiler to tell you if you try to do something stupid. For example, 3/"hello world" will be accepted by the language despite it being obvious (read: provable) that a runtime problem will occur.

Many Java programmers assume that you have to guess at the types being used in a dynamic program, or provide excessive documentation. The greater point is that what will work will work. Dynamic languages get out of your way so that you can explore a problem. Whereas in a statically typed language you have to make the solution consistent before you can try it out, you can try out an incomplete function very easily in dynamically-typed languages.

    (lambda (x)
      (if (< x 0)
          (do-this x)
          (do-that x)))

I can call the above lambda on negative numbers, even if do-that hasn't been written yet (assuming do-this has). The runtime doesn't generally complain unless it has to.

Once you have explored a problem, and you understand it, you probably have a nearly-working program, so you're pretty close to having a working one. You get no guarantees that the program will work for all possible inputs, and there isn't even a general way of restricting inputs (other than adding checks at runtime).

Dynamic programmers tend to think in the language they are using - that is, they write code while they're thinking, and test functions out to see whether they work for the cases they're interested in. If I write a function that adds two numbers together, I'm not even remotely interested in what happens if someone passes strings to it, because I'm not writing it for that use case.

This way of thinking keeps the code focused on the task in hand. If the code starts to get hard to read, or repetitive, the programmer will come up with an abstraction. E.g., beginner Java programmers often try this:

    if (x==3 || 5 || 10)

which doesn't compile, because the compiler sees 3 expressions that should all be booleans, and the 2nd and 3rd are ints instead. The programmer gets told they're wrong, and they should fix it to be:

    if (x==3 || x==5 || x==10)

That's clearly garbage, because x== is repeated. The programmer has just adopted a poorer way of thinking to suit a language, instead of adapting the language.

    if (x in (3,5,10))

would be great, as would:

    if ((3,5,10) contains x)

, or even, as valid Java:

    if (asList(3,5,10).contains(x))

Of course, this latter example is a little ugly. Translated directly to Scheme:

    (if (contains (list 3 5 10) x)

If this was used a lot, a Scheme programmer might write:

    (if (in? x 3 5 10)

A Java programmer could do that too, but they would need to know more of the language to be able to do it. Therefore, the Java programmer is 'corrected', instead of shown how to write their idiom in Java.

Because the language gets out of the way, this kind of code is easy to write. That brings about the worry that because you can write code to be as good as you like, you can also write incredibly bad code, and this is completely true.

The remarkable thing is that the language doesn't try to judge whether your code is good or bad - it just runs the code. That's great, because it lets you learn from your own mistakes, and even better, it lets you come up with things that the language designers didn't think of.

It's become quite clear in recent years that Object-Orientated Programming as Java and C++ do it is not the pinnacle of software engineering - but you can't escape Java's OO system. You can't really implement multiple dispatch for two separate codebases in one central place unless you go outside the language (e.g., reflection, bytecode weaving). If it turns out that Haskell's typeclasses aren't the best way of expressing things, you can't remove them from the language, because existing code depends on them - the compiler always needs to understand them - and probably you will still have to use them because the language's central concepts depend on them.

By the language not telling you that you're wrong, it lets you be right in ways that the language designer might not have envisaged. For example, the code snippet (+ "hello" "world") looks wrong, because + is not defined on strings. But in a language like Scheme, + is only a variable, so I can write:

    (let ((+ string-append))
      (+ "hello" "world"))

and it's no longer wrong (arguably a bit stupid though).

So how about those tests? Well, if you look at Java code:

    public Integer add(Integer a,Integer b)
    {
        return a+b;
    }

Both a and b can possibly be null, so what happens if null is passed? Er, you get a NullPointerException. Some programmers will specify that in documentation for the method, or just write that null is not allowed. The same method in Scheme would be callable with any values at all, though it would fail. That changes the attitude of calling programmers. Instead of looking at the half-hearted type signature, and seeing that null is a possible value, the programmer is more likely to look at the implementation.

In the first half of this entry, I said that types imply implementations - well, the reverse is true! Implementations imply types. You don't need a type signature to see what values can be passed to (lambda (a b) (+ a b)), you can infer the type signature from the implementation. In this case, you can pass anything to that lambda that you can pass to the primitive + procedure, whose type signature actually depends on the implementation of Scheme you're using, but it accepts at least those types in the specification.

So Scheme programmers aren't likely to write tests to see what happens if you pass credit cards to a function expecting addresses, because that's never going to be a use case. They informally restrict the inputs. They're emulating what a static type checker does, but mentally. That lets them organically approach a solution to a problem, instead of having to design it beforehand.

It's certainly true that this mental processing is error-prone, and bugs get into source code because of this. Then, many programmers are tempted to write swathes of tests, in an informal attempt to prove that their code is correct.

The bad part of this is that they aren't benefitting from the static typing camp's results now. They have a solution, but they can't use the machine to prove it. They'll end up writing the same kinds of tests over and over.

All this is why I think that, despite him talking about middle-of-the-road type checkers like Java's, Gilad Bracha was on the ball with his presentation about adding pluggable type checkers to dynamic languages. I thoroughly expect that it will be some time before a great one exists, and largely because too many people are sitting on the fence, instead of knocking it down.

If you ignore mediocre languages, there isn't a great deal of difference between how statically typed programmers think and how dynamically typed programmers think. We all like lambdas, we all like side-effect free code, we all dislike crashing programs. So the next time you see a proposal to add static typing to your favourite language, or to add some new dynamic feature to your static language (including 'get-out' clauses like Haskell's unsafePerformIO), bear in mind that you're just witnessing a step on the road to convergence.

If the next big language has a mandatory static type system, then it will either be a crap one, or Computer Science degrees will suddenly contain a lot more mathematics. That won't happen. The next big language will be crap, or dynamic.

Objects To Functions 1 - Stateless Classes

Before I had really heard of functional programming, I had started to notice that it made a lot of sense to make certain objects 'value objects', i.e., create them with all the data they need and then never change them, which lets you pass them around without worrying about who changes them. This sounds like low-hanging fruit, I mean, of course you can easily keep track of changes, just like C++ programmers always manage to track who frees an object.. Ah. You probably see where I'm going now. So, if I don't mutate an object, I can pass it around without thinking about the consequences. That's why it turns out to be better to share Strings rather than StringBuffers in Java. Of course, you can treat a StringBuffer as an immutable value, just by never mutating it, but as it is intended to be mutated, you generally don't share it, at least not without thinking very carefully. Let's look at a very simple stateful class:

public final class Point
{
    public double x,y;
}

I'm sure some readers will be complaining about the lack of get/set methods now - I'll happily explain why I don't use them if you ask in a comment. Others may complain about final, I'll happily explain that too. If you instantiate a Point and pass it around, some programmers will see that it's intended to be mutable, and store a copy of it (or take pains never to store it, but just use its values once), and other programmers will take the attitude of, well, if you're giving out a mutable object you'd damn well better expect it to be mutated*. The latter sounds like an unreasonable attitude, but it's why IDEA places warnings on methods that return the values of fields that hold arrays and collections. IDEA puts the onus on the class giving out the mutable object, rather than on the user of that object - it assumes that the latter programmer is the most likely one. * this latter programmer often also has the attitude that while it's ok for him to mutate the object, nobody else should! It's quite easy to make Point immutable, you can provide a constructor that sets x and y, and then make x and y final. You don't absolutely have to do this - all it really takes to stop a data structure from being modified is to stop modifying it - you don't have to put up barriers to modification to do that. Still, in Java modifying things is the norm, so it might be a good idea for now. If you get to a stage where mutation is only done with great care then you might not need the barrier.

public final class Point
{
    public final double x,y;

    public Point(double x,double y)
    {
       this.x=x;
       this.y=y;
    }
}

So, how does this relate to functions? A Point is now a function, as in mathematics. If you create a Point, it will always give you the same value for x and the same value for y. You can think about it as a function that takes the symbol x or the symbol y and always gives the same result. That is, objects can be or represent functions just as well as methods can. Math.abs represents a function, because it always gives the same output for the same input, and so does point.x. Now I can treat a Point as a long-lived value and never worry whether it will be mutated, just as I don't worry about it being garbage collected. In effect, I've taken time out of its semantics. You might be thinking that Point is crying out to be an interface, because programming to the implementation is inflexible. However, I'd like all clients of Point to be able to rely on .x and .y returning the same thing, forever, and not have to worry about different implementations doing strange things. Instead I would suggest that if you wanted a different implementation, you don't call it Point, and don't try to make it extend or implement Point. Clearly it would be of a different type, e.g., MutablePoint, or DebuggablePoint, Quaternion, etc. - and you wouldn't want to use it in places that expect a Point. There are cases that make this way of programming tricky, and solutions to each: 1. Collections. It would be pretty expensive to copy a collection instead of changing it, so in many cases you may as well change it in place, which loses you the time-independence, and stops the collection from behaving as a function. There are some concessions you could make - e.g., only allowing adds, not removes (then any successful accesses will always succeed - you won't break assumptions). For the more general case, there is one kind of collection in particular that works well as a function - a linked list. Java's LinkedList class doesn't give you access to the individual nodes of the list, which is what we need for this to work, so you'd need to write your own.

class Link<T>
{
    public final T item;
    public final Link<T> next;

    public Link(T item,Link<T> next)
    {
        this.item=item;
        this.next=next;
    }
}

Link<String> list=new Link<String>("hello",null);

If you feel the need to add to the list, you don't need to change anything, just call new Link<String>("world",list) and use that value instead from now on. Then each list retains its properties as a function - it will always return the same value if you ask it the same question. If you want to iterate over such a linked list and do something, say, finding the maximum of a Link<Integer>, you could do it like so:

public int max(Link<Integer> list)
{
    int max=Integer.MIN_VALUE;

    while (list!=null)
    {
        max=Math.max(max,list.item);
        list=list.next;
    }

    return list;
}

This works, and from the outside you can't see any problem, but on the inside you can see that time is important. That is, the list objects always work as functions, but because the variables list and max change values, they don't work as functions - you have to think about time whenever you think of them. It would be easier if you only had to look at the method parameters to see the values, instead of having to trace changes in your head. This is a small-scale version of the bigger problems caused by things that change. We can probably deal with this version with no real problems, but let's follow through and see what happens when we apply the large-scale thinking to the small scale. Because a list is a recursive data structure, it turns out to be quite easy to rewrite max as a recursive method:

public int max(Link<Integer> list)
{
    return new Object()
    {
        public int max(Link<Integer> remaining,int current)
        {
            return remaining==null ? current : max(remaining,Math.max(current,remaining.item));
        }
    }.max(list,Integer.MIN_VALUE);
}

Woah! I'm abusing inner classes or something! What's going on? Java doesn't let you define a method inside a method, but it lets you define a method inside a class, and a class inside a method, so that's what I've done. If I was going to write it in more idiomatic Java, I'd do this:

public int max(Link<Integer> list)
{
    return maxImpl(list,Integer.MIN_VALUE);
}

private int maxImpl(Link<Integer> remaining,int current)
{
    return remaining==null ? current : maxImpl(remaining.next,Math.max(current,remaining.item));
}

Now that you've understood that these two idioms are actually equivalent to each other, you can read the first one without any confusion. Just understand that if I could declare a method inside a method directly, I would have done. There is a problem with this code, in that it throws a StackOverflowError for medium-sized collections, on the Sun JVM, but not IBM's, so I am only using it as an intermediate case for this blog post, before reaching a final conclusion. Anyway, let's move on and create a similar method that gives the minimum for a collection.

public int min(Link<Integer> list)
{
    return new Object()
    {
        public int min(Link<Integer> remaining,int current)
        {
            return remaining==null ? current : min(remaining,Math.min(current,remaining.item));
        }
    }.min(list,Integer.MAX_VALUE);
}

I copied and pasted the code, then changed it, which is a good sign that there's some thinking left to be done. I can make more of it the same by renaming the method inside the anonymous class to 'invoke' or something equally generic. I can move the starting value to the method header - it might not make sense to everyone that the minimum of an empty list is Integer.MAX_VALUE, let's allow the user to decide what value that should be:

public int min(Link<Integer> list,int minimum)
{
    return new Object()
    {
        public int invoke(Link<Integer> remaining,int current)
        {
            return remaining==null ? current : invoke(remaining.next,Math.min(current,remaining.item));
        }
    }.invoke(list,current);
}

There's no reason now not to use the outer method as the target for recursion instead of creating an inner one, so if the anonymous class annoyed you, it goes away now:

public int min(Link<Integer> list,int minimum)
{
    return list==null ? minimum : min(list.next,Math.min(current,remaining.item));
}

Wow, that's short. It's also fairly simple. It says, for an empty list, return the given minimum. For a non-empty list, return ourselves invoked with a smaller list, giving the new invocation a different minimum. Notice that nowhere here have we changed any variables. Still, this throws a StackOverflowError too. Two more steps and we'll get rid of it. The only parts that are specific to minima now are the name of the method, and Math.min. A more general version of what we're doing here is reducing a list to a single value. There are lots and lots of reasons we might do that. Asking whether a list contains a certain item is a reduction.

interface Reducer<T,R>
{
    R reduce(T left,R right);
}

public <T,R> R reduce(Link<T> list,R accumulator,Reducer<T,R> reducer)
{
    return list==null ? accumulator : reduce(list.next,reducer.reduce(accumulator,list.item),reducer);
}

A Reducer is something that knows how to reduce 2 values to one. It doesn't necessarily have to mean two items from the list, just an accumulator and one item from the list. Let's have some imaginary syntax meaning that if I type Math.min with no parentheses, I get a Reducer<Integer,Integer>: int min=reduce(list,0,Math.min); That says find me the minimum value in that list, using Math.min to do so. Unfortunately, Java doesn't support such syntax, so this is what you really end up with:

int min=reduce(list,0,new Reducer<Integer,Integer>()
{
    public Integer reduce(Integer left,Integer right)
    {
        return Math.min(left,right);
    }
});

Unfortunately, this is pretty annoying - so annoying that if you use it more than once, you'll want to wrap the reducer up in a static field or method somewhere, so you end up with: int min=reduce(list,0,Maths.minRef); I'm English, we say Maths instead of Math, which turns out to be a handy conflict resolution here. We still have the StackOverflowError problem, but we can resolve it by rewriting reduce in the 'old' way, with changes to variables. Note that StackOverflowError is really a fault with Java, because at the point where reduce calls itself, there is no need to retain any of reduce's data on the stack. Java could make it work so that reduce overwrites its own parameters and then does a goto to get to the top. Unfortunately, it doesn't, so we have to do that ourselves (except the goto is some loop or other):

public <T,R> R reduce(Link<T> list,R accumulator,Reducer<T,R> reducer)
{
    while (list!=null)
    {
        accumulator=reducer.reduce(accumulator,list.item);
        list=list.next;
    }

    return accumulator;
}

So even though we've ultimately had to make a concession for the technical problems of being in a JVM, we've got something pretty reusable out of the thought experiment. Of course this is nothing new. I actually wouldn't at this time recommend using linked lists in this way in Java, but closures in Java 7 and a solution to the problem of tail-call elimination might make this much more attractive. 2. Cyclic data. If class A needs to hold a B, and B needs to hold an A, there's no way to instantiate them both at the same time. There are clever tricks that make them nearly instantiated at the same time, but you can't make the respective fields final in each. A common solution is to get rid of the cycle by creating a third object, C, that holds A and B, supplying the instances of each other as necessary. Unfortunately, the name for C is often hard to think of, which is a reasonable sign (I'm contradicting another of my blog posts here) that C is a bad thing to have at all. I'd suggest looking at the individual case and deciding what to do. Sometimes it's just that A and B should be merged, or that some functionality should be moved from one class to another. In other cases, it might turn out that some methods can be made static, in which case there's no need to hold an instance. 3. Data that will change over time. Essentially a philosophical question, it is possible to argue that something that is different before a certain time than after it hasn't changed, that there are actually two objects. Monads are a way of treating immutable objects as if they can change, by making the new value replace the old value seamlessly, which effectively solves the philosophical question by letting you write code nearly the same way regardless of the answer. Using Java, though, I'd probably suggest that if data changes over time, you may as well use mutable data. Perhaps Java 7 will make monads more attractive.