Link to wealthfront.com

Fork me on GitHub

Tuesday, May 4, 2010

A Better Option for Java

If you are somewhat familiar with Scala or Haskell, you are probably used to Option[T] or Maybe a, the neat way to pass around "partial values" - values that may be missing. Maybe a in Haskell represents either Nothing or Just x for some x of type a. In Scala Option[T] is either Nothing or Some(x) where x is of type T.

Due to pattern matching in both Haskell and Scala, it is easy to use Maybe/Option in case statements, switching the execution depending on whether there is a value or it is just nothing.

We can easily define class Option<T with two subclasses returned by factories, Some<T>(T x) and Nothing - but this does not help us in dealing with the code inconveniences. If we use conditionals, like
Option<T> result = myMethod();
if (result.hasValue()) {
  return deliverable(result.getValue());
} else {
  return excuse("no data, no action");
}

How is it better than the following?
T result = myMethod();
if (result != null) {
  return deliverable(result);
} else {
  return excuse("no data, no action");
}

In Java, it is not. So, a Java Programmer would suggest to drop the whole weird idea of Option and continue using null as a token of no-data, or NullObject pattern from Effective Java book.

null has been around forever, and forever we've been fighting NPE, NullPointerException. And if we ask a Java Programmer to suggest a solution to make sure there's no NPE, the only answer would be to check parameters for null... and then what? Throw an NPE, most probably. Bad luck!

How can Option help? If we look at the piece of code above, checking hasValue() and acting accordingly, it seems like it does not help much. Well, of course, since it is not just a reference, but an Option, it is harder to omit null checking. But still, Java compiler does not help us.

In Scala and in Haskell we can use pattern matching to disambiguate:
Scala:
def option2array(opt: Option[Int]): Array[Int] = {
  opt match {
    case Some(n) => Array(n)
    case None => Array()
  }
}

Haskell:
maybe2list :: Maybe a → [a]
maybe2list m =case m of
  Just x  → [x]
  Nothing → []

If we omit case None => Array() or Nothing ? [], we will have an incomplete or a non-exhaustive pattern matching; and a compiler will issue a warning. Why a warning, not an error? Well, because we want to allow partial functions.

There is no way to do the same in Java, without pattern matching.

One solution to enforce case handling could be this: class Option hides its contents from the client code, but accepts a delegate, let's call it, awkwardly, OptionVisitor, something like this:
interface Visitor<T, S> { // member interface of class Option 
  S onSome(T x);
  S onNothing();
}

To use it, we will need to implement a method accept(Visitor<T,S> visitor) in Some and Nothing.

We are safe now. We could even apply the same trick to our Scala code, say, when we decide to migrate from Java to Scala.

The problem with visitors, though, is that the code readability deteriorates: Java still, in 2010, does not have delegates, and one has to wtite too much boilerplate code.

But in Scala there is another solution, which has been known for years, see, e.g., David Pollack's posting "The Scala Option class and how lift uses it", [1]. Quoting:
for (val x <- data-blogger-escaped-br="" data-blogger-escaped-some="">     val y <- data-blogger-escaped-br="" data-blogger-escaped-some="" data-blogger-escaped-x="" data-blogger-escaped-y="" data-blogger-escaped-yield="">

In essence, if your class, any class, has a method called map, you can use that class as a "source" in a "for comprehension loop". The example above uses yield; alternatively, we can write
Option[T] result = myMethod()
for (x: T <- data-blogger-escaped-br="" data-blogger-escaped-result="">  return deliverable(x) 
}
return excuse("no data, no action")
This looks pretty much like a monad. Option is a monad.How can it help us, humble Java programmers? Here's the trick. If we make our Option<T> implement Iterable<T> we too, in Java, can use it in loop form:
Option<T> dataProvider() {...}
...
for (T x : dataProvider()) {
  return doSomethingWith(x);
}
return doSomethingWithNothing();

We are getting two advantages here: first, we have safe code; second, we have a reasonable (for Java) amount of boilerplate.The other, conceptual, advantage of this form is that it stresses its applicability when we do not perceive our logic as necessarily Boolean; it does not stress a dichotomy (either Some or Nothing, and is still good in an arbitrary intuitionistic logic (e.g. temporal logic).

References:
  1.  David Pollack, The Scala Option class and How Lift Uses It:
    http://blog.lostlake.org/index.php?/archives/50-The-Scala-Option-class-and-how-lift-uses-it.html

  2. Tony Morris, Maybe in Java:
    http://blog.tmorris.net/maybe-in-java/

  3. Executive summary of this entry: powerpoint slides

Below is the source code of Option<T>. It contains interface Visitor; you probably won't need it, it was included here for illustration.

import java.util.Iterator;
import java.util.NoSuchElementException;

public abstract class Option<T> implements Iterable<T>
{
    interface Visitor<T, S> {
        S onSome(T x);
        S onNothing();
    }
    
    public abstract <S> S accept(Visitor<T, S> visitor);

    private static abstract class ImmutableIterator<T> 
     implements Iterator<T> {
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    private static class Nothing<T> extends Option<T> {
        Iterator<T> EMPTY = new ImmutableIterator<T>() {
            public boolean hasNext() { return false; }

            public T next() {
                throw new NoSuchElementException();
            }
        };
        
        public Iterator<T> iterator() { return EMPTY; }

        @Override
        public <S> S accept(Option.Visitor<T, S> visitor)
        {
            return visitor.onNothing();
        }
    }
    
    private static Nothing<Object> nothing = new Nothing<Object>();
    
    private static class Some<T> extends Option<T> {
        private T value;
        
        Some(T value) {
            this.value = value;
        }
        
        public boolean equals(Object o) {
            return o instanceof Some<?> &&
              (((Some<?>) o).value).equals(value);
        }

        public int hashCode() {
            return value.hashCode();
        }
        
        public Iterator<T> iterator()
        {
            return new ImmutableIterator<T>() {
                boolean hasNext = true;

                public boolean hasNext() {
                    return hasNext;
                }

                public T next()
                {
                    if (!hasNext) throw new NoSuchElementException();
                    hasNext = false;
                    return value;
                }
            };
        }

        @Override
        public <S> S accept(Option.Visitor<T, S> visitor)
        {
            return visitor.onSome(value);
        }
    }
    
    static <T> Option<T> some(Option<T> value) {
        return value == null ? Option.<T> nothing() : value;
    }

    @SuppressWarnings("unchecked")
    static <T> Option<T> some(T value) {
        return value == null              ? Option.<T> nothing() : 
               value instanceof Option<?> ? (Option<T>) value    : 
                                             new Some(value);
    }
    
    @SuppressWarnings("unchecked")
    static <T> Option<T> nothing() {
        return (Nothing<T>) nothing;
    }
}