Sunday, April 14, 2013

Scala and the price of not being purely functional

A functional programming language (e.g. Scala or SQL for that matter) encourages one to think in the problem domain and write solutions that are declarative and accurate (provably so indeed). However, that is usually a lie! After coming up with a solution, one then has to worry about performance and see how to tweak it. And to be able to do so one has to know how the language works - which contradicts the whole premise of being declarative in the first place.
With something like SQL, we have query optimizers and I believe they do a pretty good job.
Now the same could be true in a pure functional language like Haskell, which, is free to reorder all our expressions as long as the dependencies are maintained. However, with Scala, expressions are allowed to have side effects (of course one should strive to not have those) and thus in general reordering of expressions is something the compiler probably won't do for us. And thus we have (lazy) val v def. E.g.
abstract class MyList[T] {
    def size(): Int
    def head: T
    def tail: MyList[T]
}

class MyEmptyList[T] extends MyList[T] {
    val size = 0
    def head = throw new NoSuchElementException
    def tail = throw new NoSuchElementException
}

class MyNonEmptyList[T](val head: T, val tail: MyList[T]) extends MyList[T] {
    def size = {
        println("MyNonEmptyList.size()")
        1 + tail.size
    }
}

object Main extends App {
  val list:MyList[Int] = new MyNonEmptyList(7, new MyEmptyList);
  list.size
  list.size
}

This outputs:

MyNonEmptyList.size()
MyNonEmptyList.size()

If MyNonEmptyList#size was declared val instead, the output would be:

MyNonEmptyList.size()

However memoization of methods that have input parameters is not supported, e.g.

class MyClass {
    def get(in:Int):Int = {
        println("MyClass.get()")
        in * 2
    }
}

object Main extends App {
  val x  = new MyClass
  x.get(5)
  x.get(5)
}
The output:

MyClass.get()
MyClass.get()

If we wanted to memoize "get", we can't declare it as val but instead we'd have to keep a map ourselves.