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