2010-06-02

java dead?

I don't think Java's dead


it's just dead boring

I can't not submit

There are times when I'm not allowed to submit.

I wish I'd made a branch to begin with

so I'm going to run my own subversion server on my local development machine.

visual SVN server

tortoise svn client

2010-06-01

Can you balance space and time?

The balance between space and time is still relevant:

http://blog.tmorris.net/you-lazy-thunk/

In scala, there's the lazy keyword which will make an assignment lazy.
But I didn't know of anything that would trade space for time, ie caching.

I was reading about clojure (lisp on the java) programming-clojure ,
and they mentioned the built in memoization http://en.wikipedia.org/wiki/Memoization

So I decided to do my own implementation of memoization in scala.
 
    def mem[A,R](func: A=>R) : A=>R = {
        var cache = Map[A,R]()

        (a:A) => {
            if (cache.contains(a)) {
                cache(a)
            } else {
                val result = func(a)
                cache += a -> result
                result
            }
        }
    }


    val double = (x:Int) => {

        println("double "+x)
        x*2 
    }

    double(2)
    double(2)

    val memDouble = mem(double)
   
memDouble(2)
   
memDouble(2)
   
memDouble(4)
   
memDouble(4)

when you run this in the repl you get:

scala> double(2)
double 2
res13: Int = 4

scala> double(2)
double 2
res13: Int = 4

scala> memDouble(2)
double 2
res9: Int = 4


scala> memDouble(2)
res10: Int = 4


scala> memDouble(2)
res10: Int = 4


scala> memDouble(4)
double 4
res11: Int = 8


scala> memDouble(4)
res12: Int = 8


as you can see from the repl output;
When you call double, it executes the body everytime you execute the function. ie it prints double 2 each time.
The memDouble function is different however, the first time you call the memDouble function, it prints, but the second time (with the same arguments), it just gives you the value.

Using this mem function, we can automagically cache the results of any function that takes a single argument.
In order for it to work with functions of any arity (number of arguments), we need to implement different versions for each arity.
We can then wrap those functions up in a singleton object, to hide the arity details.
Here I've done it for 1 and 2 argument functions, it's pretty easy to extrapolate. The key to the cache map becomes a tuple of the arguments.


object Mem {
    def mem1[A,R](func: A=>R) : A=>R = {
        var cache = Map[A,R]()
        (a:A) => {
            if (cache.contains(a)) {
                cache(a)
            } else {
                val result = func(a)
                cache += a -> result
                result
            }
        }
    }

    def mem2[A,B,R](func:(A,B)=>R) : (A,B)=>R = {
        var cache = Map[(A,B),R]()
        (a:A,b:B) => {
            if (cache.contains((a,b))) {
                cache((a,b))
            } else {
                val result = func(a,b)
                cache += (a,b) -> result
                result
            }
        }
    }
    ...

  
    def apply[A,R](func:A=>R) = mem1(func)
    def apply[A,B,R](func:(A,B)=>R) = mem2(func)

    ...
}

object Test extends Application {
    val mult = (x:Int,y:Int) => { println("mult"); x*y }
    val double = (x:Int) => { println("double"); mult(x,2) }
    val hello = (x:String) => { println("hello"); "hello "+x }
   
    val memDouble = Mem(double)
    memDouble(2)
    memDouble(2)
    memDouble(4)
    memDouble(4)
    memDouble(4)
   
    val memMult = Mem(mult)
    memMult(2,3)
    memMult(2,3)
    memMult(4,4)
    memMult(4,4)
   
    val memHello = Mem(hello)
    memHello("me")
    memHello("me")
   
    case class MyObj(val value:Int) {
        def multiply(x:Int) = x*value
    }
   
    val memMyTriple = Mem(MyObj(3).multiply(_:Int))
   
memMyTriple(2)
   
memMyTriple(2)
}


As you can see, it's not just for basic functions, it also works with methods on objects as well.

I've found these functional concepts fairly straightforward to implement in scala, the only issue being with different function arities.

This is an effective way to use space in order to save time, while leaving your source code relatively unaffected.