Can Your Brain Think This Way?

Reposted from: Caterpillar’s Blog

One day you’re browsing your own code and you notice two large chunks that are almost identical. In fact they are identical, except that one is about “Spaghetti” and the other about “Chocolate Moose”.

System.out.println("I'd like some Spaghetti!");
System.out.println("I'd like some Chocolate Moose!");

This looks like Java, but even if you don’t know Java you can tell what’s going on. Duplicated code is a problem. So you create a method:

static void swedishChef(String food) {
    println("I'd like some " + food + "!");
}

static void println(Object obj) {
    System.out.println(obj);
}

swedishChef("Spaghetti!");
swedishChef("Chocolate Moose!");

Fine, this example is a classic, but can you think of a deeper one? The advantages of this code are the ones you’ve heard a thousand times: maintainability, readability, abstraction = good!

Now you notice two other chunks of code that are identical, except that one repeatedly calls a method called boomBoom and the other repeatedly calls one called putInPot. Apart from that, the two chunks really are twins.

println("get the lobster");
putInPot("lobster");
putInPot("water");

println("get the chicken");
boomBoom("chicken");
boomBoom("coconut");

Now you need a way to substitute one flow of control for another inside a method. That’s an important idea, because it makes it easier to keep commonly used code inside a method.

interface Block<P> {
    void apply(P p);
}

static void cook(String food1, String food2, Block cooker) {
    println("get the " + food1);
    cooker.apply(food1);
    cooker.apply(food2);
}

cook("lobster", "water", new Block<String>() {
    public void apply(String food) {
        putInPot(food);
    }
});

cook("chicken", "coconut", new Block<String>() {
    public void apply(String food) {
        boomBoom(food);
    }
});

Look at that — we successfully substituted the flow of control. Can your brain think this way?

Wait. Suppose you haven’t defined methods like putInPot or boomBoom — just implement them directly inside apply. Also, calling cook looks a bit ugly; using variables properly reads better than cramming it all into one line.

Block<String> putInPot = new Block<String>() {
    public void apply(String food) {
        println("pot " + food);
    }
};

Block<String> boomBoom = new Block<String>() {
    public void apply(String food) {
        println("boom " + food);
    }
};

cook("lobster", "water", putInPot);
cook("chicken", "coconut", boomBoom);

Calling cook is much clearer now. When you create an anonymous class instance on the fly, you can name it sensibly and then pass it into a method.

Once you start thinking about anonymous class instances as parameters, you’ll probably think of code that does the same thing to every element of a List.

List<Integer> numbers = asList(1, 2, 3);

List<Integer> multipliedWith2 = new ArrayList<>();
for (Integer number : numbers) {
    multipliedWith2.add(number * 2);
}

You often need to do the same thing to every element in a List, so you can write a method to help:

interface Mapper<P, R> {
    R apply(P p);
}

static <T, R> List<R> map(List<T> lt, Mapper<T, R> mapper) {
    List<R> mapped = new ArrayList<>();
    for (T elem : lt) {
        mapped.add(mapper.apply(elem));
    }
    return mapped;
}

Now you can write the above as:

Mapper<Integer, Integer> multiply2 = new Mapper<Integer, Integer>() {
    public Integer apply(Integer number) {
        return number * 2;
    }
};

List<Integer> multipliedBy2 = map(numbers, multiply2);

Another common job is combining all the elements in a List in some way:

static Integer sum(List<Integer> numbers) {
    Integer sum = 0;
    for (Integer number : numbers) {
        sum += number;
    }
    return sum;
}

static String join(List<String> strs) {
    String joined = "";
    for (String str : strs) {
        joined += str;
    }
    return joined;
}

println(sum(asList(1, 2, 3)));
println(join(asList("a", "b", "c")));

sum and join look a lot alike, so you might want to abstract them into a generic method that combines all elements of a List in some way:

interface Reducer<R, P> {
    R apply(R r, P p);
}

static <T, R> R reduce(List<T> lt, Reducer<R, T> reducer, R init) {
    R r = init;
    for (T elem : lt) {
        r = reducer.apply(r, elem);
    }
    return r;
}

static Integer sum(List<Integer> numbers) {
    Reducer<Integer, Integer> sumUp = new Reducer<Integer, Integer>() {
        public Integer apply(Integer sum, Integer number) {
            return sum + number;
        }
    };
    return reduce(numbers, sumUp, 0);
}

static String join(List<String> strs) {
    Reducer<String, String> joinAll = new Reducer<String, String>() {
        public String apply(String all, String str) {
            return all + str;
        }
    };
    return reduce(strs, joinAll, "");
}

In a language with first-class functions, like JavaScript, you can do these things more simply. Many older languages can’t do this at all. Some allow it but make it painful (C has function pointers, but you have to declare and define the function elsewhere). Object-oriented languages, meanwhile, take the view that you shouldn’t be allowed to use functions — as demonstrated by the Java here.

If you want to treat functions as first-class objects, Java requires you to create an object with a single method, called a Functor. On top of that, many object-oriented languages require you to create a separate file per class, which ends up not exactly fast (klunky fast). If your programming language requires Functors, you can’t fully enjoy the benefits of a modern programming environment. See if you can return it and get some money back.

So — if you use a language with first-class functions, can you write this out? Not having first-class functions is more of a nuisance, but the point is whether you went through the thinking process above. Hmm? But how much benefit do you really get from writing those tiny methods that just do something to every element in a List?

Let’s go back to the map function. When you do something to every element in a List, you probably don’t care which element goes first. Whether you start from the first or the last element, the result is the same — right? If you have two CPUs, you can write code so each handles half the elements, and map becomes twice as fast.

Or suppose you have thousands of servers around the world (just hypothetical), and a very, very large List holding the contents of the entire internet (also hypothetical). Now you can run map across those servers, each handling just a small part of the problem.

So here’s another example: writing code that searches the entire internet extremely fast is actually simple — just call a map method with a basic string searcher as its parameter.

There’s a genuinely interesting thing to notice here: once you think of map and reduce as methods everyone can use — and everyone does use them — then if some super-genius writes code that runs map and reduce across a globally distributed massively parallel array of computers, all the old code that worked fine as a single loop still works, but now it’s tens of millions of times faster, which means it can be used to solve huge problems instantly.

Let me repeat that point. It abstracts out the basic concept of a loop; you can implement the loop any way you want, including implementations that take proper advantage of extra hardware.

Now you understand what I’m asking: are you the kind of programmer who can’t write anything without first-class functions?

Without understanding functional programming you can’t invent MapReduce, the algorithm behind Google’s extraordinary scalability. The terms Map and Reduce come from Lisp and functional programming. In hindsight, MapReduce is obvious to anyone who understands functional programming: pure functional code has no side effects, so it parallelizes easily.

I hope you now see that, yes, a language with first-class functions lets you find more opportunities for abstraction — your code gets smaller and tighter — but even without first-class functions you can still have the same ideas and write code that’s reusable and scales better. Countless Google applications use MapReduce, so whenever someone improves its efficiency or fixes a bug, all of them benefit.

Every time, I’m a little puzzled by the question of whether a productive programming environment really is one that makes it easier to work at different levels of abstraction. Ancient GW-BASIC didn’t let you write functions. C has function pointers, but they’re horribly ugly and can’t be anonymous — you must implement them elsewhere, not inline where they’re used. Java makes you use Functors, which are even uglier. As Steve Yegge put it, Java is a kingdom of nouns.

So what? Does that mean you can’t write object-oriented code in C? Does having a powerful tool like first-class functions automatically level you up? JDK 8 will have lambdas; if in earlier JDK versions you already handled things the way shown above, you’ll get much more out of JDK 8’s lambdas:

static Integer sum(List<Integer> numbers) {
    return reduce(numbers, (sum, number) -> sum + number, 0);
}

static String join(List<String> strs) {
    return reduce(strs, (all, str) -> all + str, "");
}

If your brain can’t think this way, the most likely outcome is that you’ll treat JDK 8’s lambdas as mere syntactic sugar for anonymous classes. And there’s no reason to think that using a dynamic language with first-class functions will automatically upgrade your brain. Don’t forget how much Java code out there isn’t object-oriented in the slightest.