Wednesday, December 19, 2007

Scala: Tail-Recursive Higher-Order Function

Last time I showed a simple handbook tail recursion solution. Digging deeper into Scala and functional programming, I've bumped into more interesting stuff. Introduce some new terminology:

1. A higher-order function is a function which takes other functions as parameters or returns another function. For example

def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f, a + 1, b)

defines a higher-order function which takes a function f plus two integers, and returns the sum of every f(x) in the interval (a, b).

2. An anonymous function is simply a function with no name. It's really just syntactic sugar but comes in handy when fiddling with higher-order functions, see:

sum(x => x * x, 10, 20)

is a call to the above-defined function, with the (unnamed) square-function as the first argument.
Watch how the compiler automagically infers the type of x here.

3. Currying is another interesting concept, nicely described here. Currying lets you decompose argument lists arbitrarily, hence serving a nice ground to refactoring. Taking the sum example, we could rewrite it in a way that we factor out the interval-parameters from it's argument-list, and make it just pass back another function, which in turn deals with the intervals. Like so:

def sum(f: Int => Int): (Int, Int) => Int = {
def sumF(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sumF(a + 1, b)

Try it out:

sum(x => x*x)(10, 20)
def s = sum(x => x*x)

Putting it in a more concise form, we are currying:

def sum(f: Int => Int)(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f)(a + 1, b)

This is just a more compact form, but means the same as the previous one, you can still go

sum(x => x*x)(10, 20)
def s = sum(x => x*x) _ // note the underscore!

To wrap it all up, take exercise 5.2.1 from Scala By Example: rewrite sum (the curried version) to use tail-recursion.
Converting linear recursion to tail-recursion shouldn't be too hard: instead of recursively calling your method and then applying the iterating function in every step, you accumulate and recursively call on the partial results. Looking at the previous solution you would find it's really easy, and it goes like this:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
def sum1(a: Int, result: Int): Int = {
if (a > b) result
else sum1(a + 1, f(a) + result)
sum1(a, 0)

Tuesday, December 18, 2007

Scala: Tail-Recursive Factorial

Scala By Example has a smallish exercise (4.6.1) to desing the tail-recursive version of the following function:

def fact(n: Int): Int = if (n == 0) 1 else n * fact(n - 1)

Tail-recursion means that the recursive call is the last call in the body of the function. In other words, the last operation computed is a recursive function application. In this cited example, the last expression is a multiplication, which renders the body non-tail-recursive.

To make the implementation more efficient, we have to turn the body inside-out and accumulate each step's result of the multiplication. This can be nicely done with the great nested function feature, see:

def fact(n: Int) = {
def fact1(n: Int, acc: Int): Int = {
if (n == 0) acc
else fact1(n - 1, n * acc)
fact1(n, 1)

Notice how in this version I didn't mention the return type. The compiler can infer it, but I would consider it good practice to explicitly declare the intended type. However, recursive methods must always declare their return type (you get a neat compiler error should your forget it).

Monday, December 17, 2007

Shale, Struts, Spring, Tapesty, Stripes, Wicket, Whatever, Rails

I believe I've stated my dislike regarding web applications before. And again. I'm not being Luddite here. I like interesting and exciting stuff, as I told.

But taking J2EE and Java as an example, well, web development really can be painful. There are a helluva lot of frameworks, and you really have to learn a stack of stuff before you even can start working. And you really have to figure out the best way to go. As for me, I wish I hadn't gone with Core J2EE Patterns: Best Practices first, but J2EE Best Practices instead -- or better yet, with J2EE Design Patterns. Those worked out the best in may case, at last. For the learning part. As for the Getting The Job Done part, well, I'm still not convinced I went for the best route. I had to create a very simple web app: very little functionality, no persistence, very lean state-machine. KISS being one of my two main principles I've gone with implementing all of it on top of JSP/JSTL: no frameworks attached. DRY being the other principle I came to the conclusion I had to implement the Composite View pattern. Dug up the aforementioned (and a lot of other) books, read everything back and forth, and never got it.

And that's when I realized why we see a ploriferation of opensource Java web application frameworks: Because nobody ever understood what the fuck people were talking about when describing the J2EE patterns, so newcomers had to roll their own framework. Then they had to identify some design considerations in the new framework, so they just simply invented some new patterns, and which started everything all over again. As long as there is no general mindset about which framework(s) to use, people are doomed to the framework-boom. This is why Rails being the de facto web-framework for Ruby is doing so good for the Ruby community.

Event handling in C# for the Java developer

For months now I've been working on a C# WinForms project. Things are supposed to be easy for me, cause C# is just a copy of Java, right? Well sure, ok, I'm using C# 2.0, so I'm not supposed to see so much divergence from Java. True enough. There are grave differences however in a lot of areas, generics and events for example. Right this time, I've to delve into the latter.

Event-based programming is a powerful mechanism to enable two-way and multiplexed communication between interested parties. Event-based programming is main usage of the Observer pattern. Events are used extensively in GUI programming. That's why in Java, the events-mechanism is part of the AWT package of the standard library. In .Net world however, it's part of the core framework, which makes it a tad harder to comprehend -- although it allows for more diverse usage of them. For advanced examples check the very useful Pro C# 2005 and the .NET 2.0 Platform, Third Edition book from Apress. For a simple, Java-C# side-by-side comparison see Dare's post.

Sunday, December 9, 2007

Why 3-tier is easier than 2-tier?

I really hate webapps. I'm not talking about fun and hip things like JRuby on Rails or (more) exotic and interesting things like Seaside. Pure "enterprise" pretty-graphical-decorations-over-a-relational-database class of stuff makes me cringe really. It's repetitive, unexciting, dull. I hate the way AJAX tries to reinvent the wheel, by relaying logic to the client, once again. More on this later.
There is one strong benefit on theserverside tho: web architecture forces you to use some kind of layering. However good you might be in mingling presentation logic with business logic, you will be always given contextual boundaries between the DB the webserver and your client. You can't just grab something from a backend, parse it into an object, and drag it around your 2-tier app as long as the user turns off her machine before Winter Holidays. Endulging yourself into saving a few hours by not caring about immutability, proper encapsulation et al. Not good.
Take your webdeveloper hat and present users a real interface.

Saturday, December 8, 2007


Hi everybody. My name is... Umm. Nevermind. I'm In-House Developer #342 (out of 900) at ABigCompany Inc., or maybe just Developer #1 (out of 1) at StillBornStartup Co., nevermind.
I'm the bottom 99.9801% and proud of it. Well, not really. Do I represent a population? Maybe. We're the ones who get their hands dirty, because we are tied to clumsy technologies, struggle with dated software, fight bad managing decisions, dump through ex-coworkers' shitty code every day, and still we get the job done. And we admire the big guys, 'cause boy, they're oh so exciting to read. And we don't even have time to consider beating the averages, 'cause you know, we are them.
But still, we get the job done, and sometimes it feels like we have some bragging rights, too.
Or sometimes we just must take a quick note, and publish it.
And this is perfectly my duty here, to put us on the map --
-- You're welcome.