Sunday, November 9, 2014

Specialized Scala


I've been playing with the maths library, Breeze (a good introduction is here). It's written in Scala and uses a cunning stunt to avoid boilerplate code.

The problem with writing an efficient library in Java is autoboxing is horribly inefficient for sufficiently complicated mathematical operations. The solution is typically to make the code less generic and use primitives (as I did in my pet project, jMathematics).

Scala has a neat trick to avoid this. It uses the @specialized annotation. So, one of Breeze's implementations of a matrix looks like this:

final class DenseMatrix[@specialized(Int, Float, Double) V](...
                                                            val data: Array[V],
                                                            ...)

This results in the compiler creating methods that use these 3 primitives as well as the more generic types. This leads to quite a lot of classes:

henryp@phillsdell:~/Code/Scala/Maths/breeze$ find ./target/scala-2.10/classes/ -name DenseMatrix* | wc -l
350

but this Scala code:

  def valueAt(row: Int, col: Int) = apply(row,col)

(where apply ultimately reads from data: Array[V] in the constructor above) is compiled into this:

henryp@phillsdell:~/Code/Scala/Maths/breeze$ for FILE in `find ./target/scala-2.10/classes/ -name DenseMatrix*` ; do { javap "$FILE" | grep "valueAt(int, int" ; } done
  public int valueAt(int, int);
  public java.lang.Object valueAt(int, int);
  public float valueAt(int, int);
  public java.lang.Object valueAt(int, int);
  public double valueAt(int, int);
  public java.lang.Object valueAt(int, int);
  public V valueAt(int, int);

Great, so a generic Object return value plus methods for our three specialized primitives. What could possibly go wrong? Well careless use can lead to literally megabytes of code being generated. That's why it's so rare in the standard Scala libraries.

However, this is a big win for mathematics library writers.

Saturday, November 8, 2014

More on Java 8 Lambdas


Using the code found on this tutorial of Java 8's new Optional class, I started playing with the syntax of the new lambdas.

First let's instantiate a simple data structure using POJOs:

        Computer computer = new Computer(new Soundcard(new USB("3.0")));

and wrap it in a fairly straightforward object that's new to Java 8's functional packages:

        Optional<Computer> option = Optional.of(computer);

Now comes the more interesting code. Say Computer has a method thus:

    public Optional<Soundcard> getSoundcard() { ... }

we can flatMap so:

        Optional<Soundcard> flatMapped = option.flatMap(Computer::getSoundcard);

What interesting syntax. 

There's three curious points about this line.


Computer::getSoundcard

We call this a method reference. It's the function we call on all the elements we flatMap over. It's type can be seen by refactoring it out:

        Function<Computer, Optional<Soundcard>> asFunction = Computer::getSoundcard;

Using this newly refactored code, the flatMap line above is equivalent to:

        Optional<Soundcard> flatMapped = option.flatMap(asFunc);


Alternative syntax

We could just have easily used the Lambda Expression Syntax and the flatMap would have looked like this:

        Optional<Soundcard> flatMapped = option.flatMap( (Computer aComputer) -> aComputer.getSoundcard() );

or, equivalently, using the more verbose block form:

        Optional<Soundcard> flatMapped = option.flatMap( (Computer aComputer) -> {
            return aComputer.getSoundcard();
        } );

Again, refactoring this expression out into an isolated function shows us its type:

        Function<Computer, Optional<Soundcard>> asFunction = (Computer aComputer) -> aComputer.getSoundcard();


Map versus FlatMap

Note that the flatMap method was used rather than the map method. There is a very good reason for this.

The flatMap method signature looks like this:

    public<U> Optional<U> flatMap(Function<? super T, Optional<U>> mapper)

while the map method looks like this:

    public<U> Optional<U> map(Function<? super T, ? extends U> mapper)

(where T is the type that this Optional contains in both cases).

If we call map on this Optional, look at the return type:

        Optional<Optional<Soundcard>> mapped = option.map((Computer aComputer) -> aComputer.getSoundcard());

An Optional in an Optional is returned. Looking back at the signatures, the reason for this is clear. 

The method flatMap takes a function that returns an Optional<Soundcard> and this is exactly what the flatMap method returns.

But map's method signature says it takes a function that returns a type U and wraps that U in an Optional and returns it. Since we can pass the method reference Computer::getSoundcard to map and that obviously returns Optional<Soundcard> (because that's what getSoundcard() says it returns), the type U is Optional<Soundcard>. So, U is wrapped in an Optional and U is an Optional. Therefore, an Optional wrapped in an Optional is returned.


Monads

It may seem odd that we map and flatMap on an Optional. Perhaps you're more used to calling these methods on Collections. But Lists and Sets share properties with Optionals in that they're all monads - something I'm only just getting my head around...


Further reading