Ståle’s weblog

I am an avid reader of The Daily WTF, and recently there was a small challenge posted on the site. It deals with something called Russian multiplication. The explanation on the site is much better to understand than something I could reproduce myself, so I urge you to read the full text there. Basically, in order to multiply 2 numbers, you set them in 2 columns. You then add a row with half and double of the first and second number in the previous row. Keep doing that until you have reached 1. Here is a simple table example for 47*131:

You then add all the numbers in the second column, when the number in the first column is odd, 131 + 262 + 524 + 1048 + 4192 = 6157.

Now to create a small Scala program that can solve this. First, I need a method that just produces the table above. This is rather simple to create:

1
2

def sumParts(a:Int, b:Int): List[(Int,Int)] = 
    if (a==0) List() else (a,b) :: sumParts(a/2, b*2)

Notice the list type here is (Int, Int), which indicates it’s a list of tuples. If you have used scripting languages, you might be aware of tuples already. Tuples in Scala allows us to define a list like type with fixed size, and fixed type for each value. This is a tuple of 2 Ints, and the actual type off the method is a List of tuples, each with 2 Ints. If we send 47,131 as arguments to this method, we will get List((47,131), (23,262), (11,524), (5,1048), (2,2096), (1,4192)) in return. We can now iterate over this list to create a presentable output:

1
2
3
4

val numbers = sumParts(47, 131)
for ((a,b) <- numbers) {
    println("% 8d % 8d %5s" format(a, b, if (a%2==1) "*" else ""))
}

Which produces this output:

      47      131     *
      23      262     *
      11      524     *
       5     1048     *
       2     2096
       1     4192     *

To format the output nicely, I use the format operator on the string. I have used the “%” operator to format stuff extensivly when printing in python, so I was happy to find the same functionality easily available in Scala. It would be nice if they also added a “%” overloaded method for RichString in Scala for this. I also use an if to print out a “*” next to each number that should be included in the addition. Next we need to filter out the numbers we actually need for the addition, and add them together.

1
2
3

val addNums = for ((a,b) <- numbers; if (a%2==1)) yield b
val sum = (0 /: addNums) (_+_)
println("Numbers: %s, ansver: %d" format(addNums mkString(" + "), sum))

To get addNums, we use a for loop, and Scalas powerfull pattern matching. The for syntax is (item <- iterable). Instead of accessing each entry as a tuple, we use the (a,b) pattern to indicate the shape to Scala. The shape of the List ([(Int, Int)]) matches this, and each value in the tuple will be unpacked into a and b. When then filter on values where a is odd, and yield b. We will then have a list of only those numbers that had a corresponding odd number in our original table. Using mkString we can create a presentable String version off those numbers, and using the fold operator we add the numbers together.

It's also possible to create a smaller method for just calculating the sum from the list of parts returned by sumParts:

1

def calc(a: Int, b: Int) = (0 /: (sumParts(a,b) filter(_._1%2==1))) (_+_._2)

Here I fold on the tuples, so I need to use _2 to access the 2nd value off the tuple.

Finally, here is the program in full, accepting 2 numbers on the command line. No error checking and verification is present in this version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

object RussianMultiplication {
    def sumParts(a:Int, b:Int): List[(Int,Int)] =
        if (a==0) List() else (a,b) :: sumParts(a/2, b*2)
 
   def main(args: Array[String]) {
        val numbers = sumParts(args(0) toInt,args(1) toInt)
        for ((a,b) <- numbers) {
            println("% 8d % 8d %5s" format(a, b, if (a%2==1) "*" else ""))
        }
        val addNums = for ((a,b) <- numbers; if (a%2==1)) yield b
        val sum = (0 /: addNums) (_+_)
        println("Numbers: %s, ansver: %d" format(addNums mkString(" + "), sum))
    }
}

Staale Programming, Scala Scala, TheDailyWTF

I have gotten the opportunity to work a bit with GWT likely, which is a technology I really like. And I am happy that I am now able to try it out more, and learn how to use it. One off the things I needed to work, was to request data from a different server, as I integrate with Python Django on the back end. I could create a forwarding servlet to handle the communication to deal with the same origin policy off browsers, but I have instead opted for using a Script tag approach that I found from the GWT faq and elsewhere.

However, I had one job that resulted in over 20 additional request jobs. So I wanted a system that throttled this, and only kept a limited amount of requests live at the same time. So I needed a solution a bit beyond what I had in the examples.

Circumventing the SOP when fetching JSON data

The way you circumvent the SOP in browsers, is to use script tags. You add a script tag to the document with the url for the JSON service, and you also add a parameter for which callback method the service should use. The service then creates the json data, and wraps it in “callback(<json-data>)”, so when the page loads, that method will get invoked, giving you the data. This does of course require the server you are communicating with to support this method of data fetching.

Server side Django views

To ease the creation off the JSON views in Python, I created a decorator that, when applied to a method, would wrap it such that it only needed to return something that could be json encoded. Then encode and send the result. The actual code for this relies on en extension off the DecoratorBase I posted about here, so I will not post it here. Maybe I can update this in a seperate post.

Easy request building

To make it easier to code the requests, I used the builder pattern to create JsonRequestJob objects. The JsonRequrestJob objects are rather simple:

1
2
3
4
5
6
7
8
9
10
11
12

private static class JsonRequestJob<T extends JavaScriptObject> {
    private final String url;
    private final String params;
    private final AsyncDataCallback<T> callback;
 
    public JsonRequestJob(String url, String params, AsyncDataCallback<T> callback) {
        this.url = url;
        this.params = params;
        this.callback = callback;
    }
 
}

And here is the builder:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public static class JsonRequestBuilder {
    private final String url;
    private final StringBuilder params = new StringBuilder();
 
    private JsonRequestBuilder(String url) {
        this.url = url;
    }
 
    public JsonRequestBuilder param(String key, String value) {
        params.append('&').append(key).append('=').append(value);
        return this;
    }
 
    public void exec(AsyncDataCallback<? extends JavaScriptObject> callback) {
        jobs.add(new JsonRequestJob(url, params.toString(), callback));
        dispatchJob();
    }
 
}

To actually create a builder, I have a DataFetcher class (which contains the above 2 classes), and it has a get method for creating a builder. The DataFetcher also need configuration in the form off a base url. This is set up by including a script tag in the root element:

1
2
3
4
5

<script language="javascript">
 
var dataUrlBase = "http://localhost:8000/etc"
 
<script>

And here is the get method. Keep in mind that the function argument here refers to which view/function I am calling on the Python Django side off things:

1
2
3
4
5
6

private static native String getDataUrlBase() /*-{
    return $wnd["dataUrlBase"]
}-*/;
public static JsonRequestBuilder get(String function) {
    return new JsonRequestBuilder(getDataUrlBase()+function+".json?callback=");
}

Finally, the actual DataFetcher needs to have a que for adding and dequing jobs, as well as an implementation that actually creates and inserts the script tag, sets up the callback method to call when data is loaded, as well as ensuring the max number of requests is kept at a minimum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public class DataFetcher {
 
    private static Queue<JsonRequestJob> jobs = new LinkedList<JsonRequestJob>();
    private static final int MAX_JOB_COUNT = 3;
    private static int jobCount = 0;
    private static int requestCount = 0;
 
    private static void dispatchJob() {
        if (jobCount >= MAX_JOB_COUNT || jobs.isEmpty()) {
            return;
        }
        jobCount++;
        final JsonRequestJob job = jobs.poll();
        makeJSONRequest(job.url, job.params, job.callback, requestCount);
        requestCount = (requestCount + 1) % 5000;
    }
 
    private static native <T extends JavaScriptObject> void makeJSONRequest(String url, String params, AsyncDataCallback<T> handler, int requestId) /*-{
    var callback = "callback" + requestId;
 
    var script = document.createElement("script");
    script.setAttribute("src", url+callback+params);
    script.setAttribute("type", "text/javascript");
 
    $wnd[callback] = function(jsonObj) {
        $wnd[callback + "done"] = true;
        @DataFetcher::dispatchJSON(Lcom/google/gwt/core/client/JavaScriptObject;LAsyncDataCallback;)(jsonObj, handler);
    }
 
    setTimeout(function() {
        if (!$wnd[callback + "done"]) {
            @DataFetcher::dispatchJSON(Lcom/google/gwt/core/client/JavaScriptObject;LAsyncDataCallback;)(null, handler);
        }
 
        // cleanup
        $wnd.document.getElementsByTagName("head")[0].removeChild(script);
        delete $wnd[callback];
        delete $wnd[callback + "done"];
    }, 1000);
 
    $wnd.document.getElementsByTagName("head")[0].appendChild(script);
 
    }-*/;
 
    public static <T extends JavaScriptObject> void dispatchJSON(JavaScriptObject jsonObj, AsyncDataCallback<T> handler) {
        jobCount--;
        dispatchJob();
        handler.handleData((T) jsonObj);
    }
 
}

Thankfully, JavaScript client side is singlethreaded, so we don’t have to worry about race conditions or synchronizations. If we needed to do that, this could could obviously break, as it has race conditions in relation to the increment/decrement and checking off the jobCount variable. Also notice that there is a timeout added that checks that the page is loaded within 1 second. If it doesn’t, null is sent to the callback, and the actual callback method is removed from the page.

The code is not entirely complete. The AsyncDataCallback interface is missing (but it’s tiny and easy to implement).

Staale Programming, Python Django, GWT, Java, Python

I have been using BerkeleyDBs JDP on and off a bit, just experementing with it to see how it works. BerkeleyDB is basically a B-Tree with transaction support. You store key/value pairs, both being byte arrays. JDP – Java Direct Persistence – is a layer that is built on top off this using annotations. It provides you with JPA like architecture for storing objects. Except there is no underlying SQL, just pure key lookups. This means you can’t write complex queries to select data, you will have to use code instead. But imho. this also means the complexity off what you are doing becomes more apparent.

I have fiddled around a bit with this, and I wanted to create a clean way off configuring environments. When you are using BerkeleyDB, you need to set up an Environment first:

1

Environment(File envHome, EnvironmentConfig configuration)

The EnvironmentConfig in return is set up using a setters:

1
2
3
4

EnvironmentConfig envConfig = new EnvironmentConfig();
envConfig.setTransactional(true);
envConfig.setAllowCreate(true);
envConfig.setCacheSize(1000000);

However, for Scala I wanted to use chaining to set up the environment config. The base implementation does not return this in the setters, so you can’t chain the statements. My first idea was to use implicit to convert the EnvironmentConfig to a richer version, that simply returned itself, so you could chain it.

1
2
3
4

class RichEnvConfig(val config: EnvironmentConfig) {
    def transactional() = {config.setTransactional(true); this}
    def allowCreate() = {config.setAllowCreate(true); this}
}

However I didn’t get it to work properly. I also thought about using operators to chain together traits. But then it occured to me that using traits themselves might make things clearer. So I created the following class:

1
2
3
4
5
6
7
8

object EnvConfig {
    implicit det unwrap(envCfg: EnvConfig) = envCfg.config
}
class EnvConfig {
    val config = new EnvironmentConfig()
    trait Transactional { config.setTransactional(true) }
    trait AllowCreate { config.setTransactional(true) }
}

Now I could more easily create EnvironmentConfigs and use them in code:

1
2

val config = new EnvConfig with Transactional with AllowCreate
val env = new Environment(new File("."), config)

I do however want to use the loan pattern with the Environment, as the Environment requires you to call close on it after use. So I thought instead off having a class for EnvironmentConfig, I could use have one for Environment itself, with an apply method. The Environment wouldn’t be created until it was required in apply, and using traits you could configure the Environment. Pretty happy with myself with the final solution for the Environment part:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Env(val path:File) {
    trait Transactional extends Env { config.setTransactional(true) }
    trait AllowCreate extends Env { config.setAllowCreate(true) }
 
    val config = new EnvironmentConfig()
    def apply[T](f:(Environment) => T) = {
        val env = new Environment(path, config)
        try { f(env) } finally { env.close() }
 
    }
}
 
object EnvTest extends Application {
    val env = new Env(new File(".")) with Transactional with AllowCreate
    env { e =>
        println(e)
    }
}

Some handy links to BerkeleyDB Java Edition:

• BerkeleyDB Java Edition
• Getting started guide
• BerkeleyDB JavaDoc

Staale Programming, Scala BerkeleyDB, JDP, Scala

I have a project at work where in Python, where I use decorators to wrap functionality for views. I hit on a snag when I used 2 decorators on 1 function. I like using class decorators, I read some recommendations regarding that, and it fits better with my Java upbringing . The 2 decorators I needed to apply to the same function looked like this (__call__ method omitted for brevity):

1
2
3
4
5
6
7
8
9

class AutoTemplate(object):
    def __init__(self, func):
        self.func = func
        pathElems = func.__module__.split(".")[:-1]+["%s.html"%func.__name__]
        self.template = os.path.join(* pathElems)
 
class AccessRequired(object):
    def __init__(self, func):
        self.func = func

In addition, I used the functions actual name in the urls.py file to generate the url tuple:

1
2
3

def createUrl(method):
    name = method.func.func_name
    return (r'^%s.html$'%name, method, {}, name)

So the finished product after decorators where applied needed to work for that. Because the decorators resulted in a class rather than a function being assigned to the the view, this didn’t work properly.

With a little help from Stackoverflow however, I came upon a good solution, that makes it really transparent that a function is actually decorated:

1
2
3
4
5
6
7
8

class DecoratorBase(object):
    def __init__(self, func):
        self.func = func
        for n in set(dir(func)) - set(dir(self)):
            setattr(self, n, getattr(func, n))
 
class AutoTemplate(DecoratorBase): pass
class AccessRequired(DecoratorBase): pass

This does not work for decorators requiring parameters, I will see if I can find a solution for that if I need it.

Staale Programming, Python Decorators, Python

The first problem in project Euler is trivial:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This can be solved quite easily mathematically. By using the formulas for calculating the sum of all numbers up to a given number. However, since I am working on learning Scala, I think it’s a nice problem to start the language at.

Let’s first try and solve it in a traditional Java way in scala

1
2
3
4
5
6
7
8
9
10
11

object Euler001 {
    def main(args:Array[String]) {
        var i=1
        var sum=0
        while (i<1000) {
            if (i%3 == 0 || i%5 ==0) sum += i
            i += 1
        }
        println(sum)
    }
}

Now, anyone that has done functional programming will cringe at this. There are several problems with this program. First, it’s too verbose, we can express the same in less code. Additionally we are using var instead of val. In Scala, we prefix variables with var or val. For Java comparison, val means the variable is final and not reassignable, var means it is. We don’t need to say the types here, as that’s inferred.

But, I don’t want to drone on too much about language details, you can learn those other places for Scala. I will first make an example that is more compact, and introduces things that are different from Java.

1
2
3
4
5
6
7

object Euler001 extends Application {
    var sum = 0
    for (i <- 1 to 999) {
        if (i%3 == 0 || i%5 ==0) sum += i    
    }
    println(sum)
}

Now we still have a var variable here, but the iteration part looks much nicer. The thing to note here is the 1 to 999 construct. This actually is a 1.to(999) call. Numbers are true objects in Scala, with methods on them. However, the dots can be replaced with spaces for a more natural language. In addition, methods that take just 1 argument, we don’t have to include (), so this makes for a nicer to read syntax. We also changed the object to extend Application, which means we don’t need to declare the main method.

I have also not really explained how object works in Scala. They are like static methods in Java classes, but you can extend them. So you can add methods from another class in your static context by simply extending a class.

Still, we can do better. Functional languages focus on immutable values, and extracting information from expressions. The reality is that every expression in Scala results in a value, the value from the last statement in the expression.
So we could actually write:

1

    sum += if (i%3 == 0 || i%5 ==0) i else 0

But functional languages are more about immutability, so we should get rid of the last var, sum. Instead we should construct expressions that results in final parts off the process:

1
2
3
4
5

object Euler001 extends Application {
    val numbers = 1 to 1000 filter((x)=>x%3 == 0 || x%5==0)
    val sum = numbers reduceLeft(_+_)
    println(sum)
}

Here I introduce even more unfamiliar constructs for Java programmers. 1 to 999 produces a sequence of the numbers 1 to 999, the filter method applies a method to this sequence. The expression (X)=> means that we are creating a function that takes x. The code following could be a block in {}, but since it’s a simple statement we just include it directly. This method will actually get inferred by the compiler to have type (x:Int):Boolean – because it’s a method taking and Int (Scala wrapper for the integer primitive) and returns a boolean. The Int type is inferred from the type of the sequence, Int. And the return type is inferred from the result off our expression. The filter method also requires the return type to be boolean, so anything else would have been a compiler error.

The next piece of the magic is the reduceLeft on numbers. This method, basing on the previous line, should have looked something like (a,b)=>a+b. But in Scala there is a shorthand for such expressions, called partial functions. The underscore serves as a placeholder, and the first underscore will take the value off the first method parameter, and the second will take the second parameter and so on. The reduceLeft method takes a 2 argument functions, and returns another value off the same type. This is applied to all elements in the sequence, and the final reduced value is returned, which is the sum.

I might have gotten some terminology and concepts wrong in the text, but all the above code works in Scala. I hope to do more posts on Scala in the future, possibly solving some harder Euler problems. The above problem can of course also be solved by simple math:

(Add every 3rd number to 999 to every 5th number to 999 and subtract every 15th number, as we count those twice otherwise)

Staale Programming, Scala Euler, Programming, Scala