Ståle’s weblog

The 2nd project Euler problem is also rather trivial:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Creating a fibonacci method in Scala is trivial:

1

def fib(n: Int):Int = if (n <= 2) 1 else fib(n-2)+fib(n-1)

Since this is a recursive function, we need to explicitly declare the return type, as Scala can’t infer it from the method body alone. The method is however badly recursive. Scala does support tail recursion, that is recursion when the last statement off the method calls itself. However here the method calls itself before the end, so tail recursion can’t be used. This causes an exponential row off calls. Rewriting the method so it employs tail recursion, it looks like this:

1
2

def fib(n:Int, a:Int, b:Int):Int = if (n==0) a else fib(n-1, b, a+b)
def fib(n:Int):Int = fib(n, 1, 0)

The 2nd method here is just a shorthand for the first. We recursivly call ourselves with decreasing n until n reaches 0, in which case argument a will hold the correct answer. Since this is a tail recursive call, Scala is able to rewrite it into a loop instead, thus avoiding deep stack frames and StackOverflow exceptions.

However, calculating increasing fibonacci numbers until we reach the max of 4 million is not effective. We keep throwing away the calculations from each step even though we could use it for the next number. What we need instead is a method for iterating over all the fibonacci numbers. In python this would be a generator functions, but atm. I don’t know the equivalent in Scala. Instead I went for a method creating a list of Fibonacci numbers:

1
2
3
4
5

def fib(max: Int, a: Int, b: Int):List[Int] = {
    if (a+b < max) a+b :: fib(max, b, a+b)
    else List()
}
def fib(max: Int):List[Int] = fib(max, 0, 1)

The 2nd method is the one we will normally call, which calls to the first to do the actual work. Here we use the List concatenation operation in scala, ::. This will prepend the expression on the left (a+b) to the list on the right (fib(max, b, a+b)). This is because the default Lists in Scala are immutable LinkedLists, so adding to the start is a cheap operation.

With the method for generating fibonacci numbers in hand, it’s easy to calculate the sum off all even fibonacci numbers below 4 million. We just need to filter out the even numbers, then appply a reduce function:

1

println(fib(4000000) filter(_%2==0) reduceRight(_+_))

The full program then becomes:

1
2
3
4
5
6
7
8
9

object Euler002 extends Application {
    def fib(max: Int, a: Int, b: Int):List[Int] = {
        if (a+b < max) a+b :: fib(max, b, a+b)
        else List()
    }
    def fib(max: Int):List[Int] = fib(max, 0, 1)
 
    println(fib(4000000) filter(_%2==0) reduceRight(_+_))   
}

A note of caution here. All my methods use Int, which will overflow quickly for fibonacci numbers. If larger numbers are needed, use Long or BigInt. BigInt has all the common math operations overloaded, so it’s just as easy to use as Int in the above code.

Staale Euler, Scala Euler, 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

This post is rather overdue. It’s over a week now since I returned home from the roundup. I should have posted earlier, but I blame jet lag and busy days. Though the reality is closer to a bit of laziness.

The main thing I took away

What I primarily got out off the roundup was Scala and JavaFX. Although the roundup in general is a lot about our profession, the stuff outside the sessions focused more on the fun bits, ie. programming. I have heard about Scala before, especially since it’s basically mentioned in every JavaPosse podcast. I have also looked at some Scala code. But during the Roundup I got to see a lot more code, and learn more about the language. I even went online to Amazon during the roundup to order my own copy off the Scala book, only to later hear that Bill Venners brought some for us all to buy. I guess I should have checked with him. I’ll probably post more about Scala as I learn more.

JavaFX I also found interesting. This is also something I have played a bit with on my own. It’s really interesting to look at a language that is designed with a specific use-case in mind, rather than being more general like the languages  I usually use. The bind stuff is awesome, and having keywords such as tween and duration literals seems really nice. In a normal language these would be too special case to have as language constructs. But in a language dealing with animation they fit right in.

The sessions

There where quite a few good sessions to attend to. I really enjoyed the one on Developer Communication, and I hope it gets out soon so I can share it with others at work, and management. The session on Code Generation was also interesting. I am basically opposed to it. But the session started off mostly looking at cases where code generation is useful. And it’s mostly in adaptor patterns. I think the ideal here is that the generator just creates an interface that is used together with a framework in your application. Then the framework deals with translating calls to the interface to the underlying architecture, say web services.

Another good session was on dynamic vs static languages. Since Python is the language I work in now, I was hoping to come to some defence off the dynamic languages at least. Typically in a room off static language users, the bias is towards static languages. I am sure the reverse would be true at a python conference. I do see a tendency though for newer static languages to borrow useful principles from dynamic languages. Here again Scala and JavaFX are good examples of how static languages don’t need to be overly verbose. I also think dynamic languages sometimes benefit from stealing from static languages. Pythons module system and strong typing is examples off this.

All in all, the conference was great. There are proabably stuff I missed here, but they will all appear as the podcasts off the sessions get out. I am really hopefull that I can attend the roundup again next year.

Staale JavaPosse Roundup 2009 JavaPosseRoundup2009

The 2 first days of the roundup are done, and I am eager to start on the third. The first 2 days was just packed with information and discussion, a lot of viewpoints to take in and stuff to learn.

The trip over was rather long. It took me about 28 hours from getting out of bed until arriving at the Lupine house in Crested Butte. Worst part was not being able to sleep on the trip across the Atlantic, which took nearly 9 hours. And it was also frustrating to be really tired yet not getting to sleep properly through the night. The jet lag is still bad, but improving.

The first day was the alternative languages day, which I attended a session on Scala. There was a lot to take in, as it did not really start at the most basic level, but instead dived right into how to doing LINQ in Scala. It was pretty interesting still, as there where a lot of questions and I learned about the more advanced features of Scala. We also looked at Bill Venners scalatest code, and it looked like a nice concept for expressing tests. Dick Wall showed us some code from Navagenics which was useful for looking at more basic Scala code.

I went over to the chestnut house next to see if I help on anything on Bill Venners scalatest project, but I spent the entire time trying to get it to compile with the fast scala compiler, which for some reason doesn´t work properly on my computer. And the project doesn´t compile on the normal scala compiler either, due to high memory demands. So that was a bit off a miss. I should have brought my Linux laptop instead, because I really don´t feel home enough with the Mac for development.

Day 2 I attended a session on Developer Productivity and Technical Dept. The Developer Productivity explored many facets off what makes a developer productive, as well as how you measure productivity. It´s not really an easy problem to solve other than through peer review, as there generally are no good metrics to use. And any metric you implement is bound to get gamed by the developers anyways, to the detriment off the project.

Next we had the Technical Dept session, which was also really interesting. Here we also got into how you would measure it and how it relates to monetary debt. Technical debt we defined as code or architecture that limited and slowed down developer productivity. Each time the suboptimal code had to be touched or used, you pay interest on it through increased time use. However, you don´t always need to pay off you technical debt like normal debt. If the code is seldom used or changed, it just sits there and work, it´s not necessarily that efficient to fix the problems.

After this a bunch of us went out cross country skiing, which for my part involved a lot of falling down. I haven´t really done cross country before, but have done some downhill recently. But the principles I have learned from downhill really didn´t really translate to going down hills on cross country skis.

In the evening we went out for some great Thai food before attending the lightning talks. There was a bunch of interesting ones here as well, touching on a variety of topics, including Relativity Theory vs Quantum Theory and how we suck at seeing the color Blue.

After the lightning talks, Jet lag started to hit again, so I ended up back at the Lupine house and went to bed around 2300.

Staale JavaPosse Roundup 2009 JavaPosseRoundup2009

Well, I am all packed for my trip to Crested Butte for JavaPosse Roundup 2009. I still need to pack some off my hand lugage (like my laptop), and I am still encoding some movies and Family Guy episodes to bring along on my PSP.

I am really exited about this trip, but right now I am not looking forward to getting up at 4 in the morning, and travel for over 24 hours to get to Crested Butte. I have my laptop, lots of games and fun for my PSP, some podcasts and music on my iPod, and a book to read on my way. And of course I have my laptop with development tools should I get the urge to program.

Staale JavaPosse Roundup 2009 JavaPosseRoundup2009