Software design is about 3 things: structure, structure and structure. Some may argue it is about anticipating future changes, performance and / or scalability. I politely accept their arguments but then I worry about the three things I still consider most important: structure, structure and structure. In a bit more detail: system structure, data structure and structure of behaviors.
Functional Programming relates to the structure of behaviors. It is one – out of many possible ways - to organize system behavior. What is this “structure of behaviors”? I’ll try to be brief about it – it’s a rather long story otherwise.
System structure details how an entire system is broken down into subsystems and the relationships between these subsystems. Here we could go have an entire conversation on dependencies and how they should be managed. But I’ll try and stick to the topic - although I love digressing. Second on my list is data structure. Its importance derives from the simple fact that bad data structures require complex processing algorithms. If your code is complex,then you’ve got your data structures wrong. Building good, solid data structures that make all code around them simple is not easy. It's worth mentioning here that concepts and methods used by the relational model can be directly applied to building, lets say, correct C data structures. But I’m digressing again. Sorry. Finally, there is structure of behaviors. In OO that is the method to class mapping. In C it would be best described by design of function signatures and their mapping to headers and modules. Etc.
Usually the order of importance is: system structure, data structure and last structure of behaviors. When looking at things from this perspective, both data and behaviors can and should be normalized exactly like normalizing a relational model. That includes methods too. Afterall methods are implemented via pointers to functions and pointers are data; therefore they can be treated as part of the data structures. As simple as that! However, if we change the order of importance to: system structure, structure of behaviors and data structure, then everything becomes a function. Even data is represented by functions. This is key to implementing functional programming in an OO language.
A Simple Interfacepublic interface Expression {
Expression evaluate();
}This is a very powerful tool. When looking closely at this interface you’ll notice the signatures of 2 design patterns. First, there is the command pattern in the evaluate() method. Then, some sort of composite is present here, but it is a composite of behaviors and not data, as one may expect. The evaluate() method of the Expression interface returns an expression. One can build a path of behaviors by writing:
x. evaluate ().evaluate ().evaluate() …The evaluate method returns yet another expression which can be further evaluated. For example if the expression is f(x) = sqrt(x) and x is a number the result is a number which is the square root of x. If the expression is a primitive type, like “abc” string, this should evaluate to self. And if f(x) takes g(y) as a parameter the evaluated form of f(g(y)) should be (f o g )(y).
Primitive and FunctionsPrimitive types are Expressions that evaluate to self / this. Why should we consider them primitive? Because they do not evaluate into anything different then themselves. We can call x.evaluate() as many times as we want and we get the same thing over and over again. They can also serve as out of recursion conditions if writing recursive evaluation code.
public abstract class Primitive implements Expression {
public Primitive() {
super();
}
public Expression evaluate() {
return this;
}
}Functions are Expressions too, but quite the opposite of Primitives. They evaluate into something different than theselves. That can be any other type of expression: function or a primitive.
public abstract class Function implements Expression {
protected Expression x;
public Function() {
super();
}
public Function(Expression x) {
super();
this.x = x;
}
public Expression evaluate() {
return evaluate(x.evaluate());
}
public Expression evaluate(Expression x) {
...
}
}Adding to NumbersAdding two numbers requires a two parameter function (binary function):
public abstract class BinaryFunction extends Function {
public BinaryFunction() {
super();
}
public BinaryFunction(Expression x) {
super(x);
}
@Override
public Expression evaluate(Expression x) {
if (x instanceof Pair) {
Pair p = (Pair) x;
return evaluate(p.getLeft(), p.getRight());
}
throw new CannotEvaluateException("Wrong parameter for binary function: " + x);
}
protected Expression evaluate(Expression left, Expression right) {
// actual implementation here
}
}A binary function is an abstraction for all functions / operators taking 2 parameters (e.g. Add, Multiply, Diff, …). Down below is the Add function
public class Add extends BinaryFunction {
public Add() {
super();
}
public Add(Pair x) {
super(x);
}
public Add(Expression left, Expression right) {
super(new Pair(left, right));
}
protected Expression evaluate(Number left, Number right) {
// … do the actual number addition.
}
protected Expression evaluate(Expression left, Expression right) {
if (left instanceof Number && right instanceof Number) {
return evaluate((Number) left, (Number) right);
}
}
}The calling code looks like:
Number a = new Number(1);
Number b = new Number(2);
Expression c = new Add(a, b).evaluate();
assertEquals("3", c.toString());
In the code above, when calling = new Add(a, b).evaluate(), the Function base evaluates x first and with the result calls evaluate(Expression x). By constructio, x is a Pair and Pair is a Primitive, so it will evaluate to itself. The evaluate(x) in the BinaryFunction class forwards the call to evaluate(Expression left, Expression right). The Add class translates this call again into a call to evaluate(Number left, Number right) which finally does the computation.
Why all this complexity? This question has a simple answer: because we want to add more than just numbers, strings (concatenation), sets (union) or booleans (or). In order to support polymorphically all the flavors of additions we need all this duck typing and complexity. There are also arrays and collections which we can add (as vector operations). Then here is what the class Function may look like:
public abstract class Function implements Expression {
...
public Expression evaluate(Expression x) {
if (x instanceof Array) {
return evaluate((Array) x, this);
} else if (x instanceof Collection) {
return evaluate((Collection) x, this);
} else {
// by default this is the identity function f(x) = x;
return x;
}
}
...
}When called for a parameter which is an Array or Collection, the function iterates through all the elements and applies itself to each element in the Array or Collection.
protected Expression evaluate(final Array right, final Function operator) {
Array result = new Array(right);
for(int i = 0; i < result.length(); i++) {
result.array[i] = operator.evaluate(right.array[i]);
}
return result;
}For example, if the parameter is an array, a function f will return a result array which contains the values of f(x[i]) for i = 0 to array.length(). Basically the function applies itself to every element of the array. Same way, if the parameter is a collection, the function will return as a result a collection (of the same kind with the input one; we use java reflection to create the result collection), which is the image of the input collection through the given function.
public abstract class BinaryFunction extends Function {
...
@Override
public Expression evaluate(Expression x) {
if (x instanceof Pair) {
Pair p = (Pair) x;
return evaluate(p.getLeft(), p.getRight());
} else if ((x instanceof Array) && ((Array) x).length() == 2) {
Array a = (Array) x;
return evaluate(a.get(0), a.get(1));
}
throw new CannotEvaluateException(
"Wrong parameter for binary function: " + x);
}
protected Expression evaluate(Expression left, Expression right) {
if (left instanceof Array && right instanceof Array) {
return evaluate((Array) left, (Array) right, this);
} else if (left instanceof Collection && right instanceof Collection) {
return evaluate((Collection) left, (Collection) right, this);
} else {
throw new CannotEvaluateException(
"Incorrect parameters for binary function.");
}
}
...
}If the function is a binary function, it can take either a Pair or an array of length 2 as an argument. Further on, if the two Expression the BinaryFunction operates over are arrays or collections (with the same length), the result is the image of the array / collection through the binary function.
For example:
int [] va = {1,2,3,4,5};
int [] vb = {3,4,5,6,7};
Array a = new Array(va);
Array b = new Array(vb);
Expression c = new Add(a,b).evaluate();
assertEquals("[4, 6, 8, 10, 12]", c.toString());Finally, the Add binary function can add many things (of the same kind). It can add for example, two Numbers (and numbers can be integers, double, currency or scientific implemented as java doubles, ints, BigIntegers or BigDecimals).
protected Expression evaluate(Number left, Number right) {
Object lObj = left.get();
Object rObj = right.get();
if (lObj instanceof Integer && rObj instanceof Integer) {
return new Number(((Integer) lObj).intValue()
+ ((Integer) rObj).intValue());
} else if (lObj instanceof BigInteger && rObj instanceof BigInteger) {
return new Number(((BigInteger) lObj).add((BigInteger) rObj));
} else if (lObj instanceof BigDecimal && rObj instanceof BigDecimal) {
return new Number(((BigDecimal) lObj).add((BigDecimal) rObj));
} else if (lObj instanceof BigInteger || rObj instanceof BigInteger
|| lObj instanceof BigDecimal
|| rObj instanceof BigDecimal) {
return new Number(new BigDecimal(lObj.toString()).
add(new BigDecimal(rObj.toString())));
} else {
return new Number(java.lang.Double.parseDouble(lObj.toString()) +
java.lang.Double.parseDouble(rObj.toString()),
Number.commonFormat(left, right));
}
}Or it can add two literals. That comes down to concatenating two strings.
protected Expression evaluate(Literal left, Literal right) {
return new Literal(left.toString() + right.toString());
}If the we want to add Booleans, that translates into a logical or.
protected Expression evaluate(Bool left, Bool right) {
return new Bool(left.get() || right.get());
}All the duck casting is implemented by the generic evaluate( Expression, Expression) in the BinaryFunction.
protected Expression evaluate(Expression left, Expression right) {
if (left instanceof Number && right instanceof Number) {
return evaluate((Number) left, (Number) right);
} else if (left instanceof Bool && right instanceof Bool) {
return evaluate((Bool) left, (Bool) right);
} else if (left instanceof Literal && right instanceof Literal) {
return evaluate((Literal) left, (Literal) right);
} else if (left instanceof Array && right instanceof Array) {
return super.evaluate(left, right);
} else if (left instanceof Collection && right instanceof Collection) {
return super.evaluate(left, right);
} else {
return evaluate(new Literal(left.toString()),
new Literal(right.toString()));
}
}Here’s some stuff we can write:
• Adding arrays (see above).
• Adding literals
Literal a = new Literal("a");
Literal b = new Literal("b");
Expression c = new Add(a,b).evaluate();
assertEquals("ab", c.toString());• Adding two lists of numbers:
List a = new List();
List b = new List();
a.add(new Number(1));
a.add(new Number(2));
a.add(new Number(3));
b.add(new Number(1));
b.add(new Number(2));
b.add(new Number(3));
Expression c = new Add(a,b).evaluate();
assertEquals("[2, 4, 6]", c.toString());
• Adding Booleans:
Bool a = new Bool(true);
Bool b = new Bool(false);
Expression c = new Add(a,b).evaluate();
assertEquals("true", c.toString());
• Adding Literals to Numbers or Literal to Boolean
Literal a = new Literal("a");
Number b = new Number(1, Number.integer);
Expression c = new Add(a, b).evaluate();
assertEquals("a1", c.toString());
Literal a = new Literal("a");
Bool b = new Bool(false, Bool.TRUE_FALSE);
Expression c = new Add(a, b).evaluate();
assertEquals("aFALSE", c.toString());• Adding complex functions
Number a = new Number(1);
Number b = new Number(2);
Literal c = new Literal("3");
Number d = new Number(4);
Number e = new Number(5);
Add f1 = new Add(a, b);
Add f2 = new Add(c, d);
Add f3 = new Add(e, f2);
Expression f = new Add(f1, f3).evaluate();
assertEquals("3534", f.toString());
• Creating complex functions
Number a = new Number();
Number b = new Number();
Literal c = new Literal();
Number d = new Number();
Number e = new Number();
Add f1 = new Add(a, b);
Add f2 = new Add(c, d);
Add f3 = new Add(e, f2);
Expression f = new Add(f1, f3);
assertEquals("000", f.evaluate().toString());
After the function has been created, just set the values and evaluate.
a.set(1);
b.set(2);
c.set("3");
d.set(4);
e.set(5);
assertEquals("3534", f.evaluate().toString());
Arrays, Collections and IteratorsIterators are functions that operate over arrays or collections. When an array is iterated, the values in the array are evaluated – they change. See the code down below.
int [] a = { 1, 2, 3, 4 };
int [] b = { 11, 12, 13, 14 };
Iterator iter = new Iterator(new Array(a)) {
@Override
protected Expression evaluate(int idx, Expression e) {
return new Add(e, new Number(10)).evaluate();
}
};
assertEquals(new Array(b), iter.evaluate());After the iterator has been evaluated, the values in the array have increased by 10. This can be avoided by using a ConstArray. See the code below:
String[] a = { "1", "2", "3", "4" };
Iterator iter = new Iterator(new ConstArray(a)) {
@Override
protected Expression evaluate(int idx, Expression e) {
return new Add(e, new Number(0)).evaluate();
}
};
assertEquals("[10, 20, 30, 40]", iter.evaluate().toString());
assertEquals("[1, 2, 3, 4]", Arrays.toString(a));A ConstArray will make a copy of the array and return that as a result. The array itself is not changed. This is also the case for collections.
Functional iterators are a kind of iterators that take a function as a parameter. They iterate a collection or array and apply the function to every element in the collection or array.
The Joel TestSo what can we do with all this? Actually we can do a lot. Here’s how I implemented what Joel suggested in his article
“Can Your Language Do This?” The cook picks up the lobster the water and does the PutInPot function. Then it picks up the chicken, the coconut and does the BoomBoom function. I wrote everything in one expression just to make the point of how far can one line of code go.
Cook sweedishCook = new Cook();
assertEquals("Get the lobster.\nPot lobster.\nPot water.\n",
sweedishCook.evaluate("lobster", "water",
new Function() {
@Override
public Expression evaluate(Expression x) {
return new Literal("Pot " + x.evaluate().toString());
}
}).evaluate().toString());
assertEquals("Get the chiken.\nBoom chiken.\nBoom coconut.\n",
sweedishCook.evaluate("chiken", "coconut",
new Function() {
@Override
public Expression evaluate(Expression x) {
return new Literal("Boom " + x.evaluate().toString());
}
}).evaluate().toString());
The cook class is a function (of course). It can do a bit more than what Joel was trying to do.
class Cook extends Function {
Expression i1, i2;
Function f;
public Cook() {
super();
}
public Cook(String i1, String i2, Function f) {
super();
this.i1 = new Literal(i1);
this.i2 = new Literal(i2);
this.f = f;
}
public Expression evaluate(String i1, String i2, Function f) {
this.i1 = new Literal(i1);
this.i2 = new Literal(i2);
this.f = f;
return evaluate();
}
@Override
public Expression evaluate() {
Expression e1 = i1.evaluate();
Expression e2 = i2.evaluate();
return new Literal("Get the " + e1.toString() + ".\n" +
f.evaluate(e1).toString() + ".\n" +
f.evaluate(e2).toString() + ".\n");
}
@Override
public Expression evaluate(Expression x) {
if(x instanceof MenuItem) {
MenuItem a = (MenuItem) x;
this.i1 = a.i1.evaluate();
this.i2 = a.i2.evaluate();
this.f = (Function) a.f;
return evaluate();
}
return super.evaluate(x);
}
}Not obvious what else? Here is some interesting stuff. First we set a whole sweedish kitchen as an array of sweedish chefs. We give one dish to each cook and then we evaluate the kitchen. The end result is an array of “cooked” dishes.
public void testSweedishKitchen() {
Array sweedishKitchen = new Array(2);
sweedishKitchen.set(0, new Cook("lobster", "water", new Function() {
@Override
public Expression evaluate(Expression x) {
return new Literal("Pot " + x.evaluate().toString());
}
}));
sweedishKitchen.set(1, new Cook("chiken", "coconut", new Function() {
@Override
public Expression evaluate(Expression x) {
return new Literal("Boom " + x.evaluate().toString());
}
}));
assertEquals("[Get the lobster.\nPot lobster.\nPot water.\n, Get the chiken.\nBoom chiken.\nBoom coconut.\n]",
sweedishKitchen.evaluate().toString());
}Or here is another way of cooking. We give an entire menu (as an array of menu items) to the Swedish cook. Then we evaluate the cook with the menu as a parameter. The result is an array of cooked dishes.
public void testSweedishMenu() {
Array menu = new Array(2);
MenuItem menuItem = new MenuItem("lobster", "water", new Function() {
@Override
public Expression evaluate(Expression x) {
return new Literal("Pot " + x.evaluate().toString());
}
});
menu.set(0, menuItem);
menuItem = new MenuItem("chiken", "coconut", new Function() {
@Override
public Expression evaluate(Expression x) {
return new Literal("Boom " + x.evaluate().toString());
}
});
menu.set(1, menuItem);
Cook sweedishCook = new Cook();
assertEquals("[Get the lobster.\nPot lobster.\nPot water.\n, Get the chiken.\nBoom chiken.\nBoom coconut.\n]",
sweedishCook.evaluate(menu).toString());
}Finally here are two ways to implement map reduce. First, I followed Joel’s java script code. Then I re-implemented the same taking full advantage of my design. Obviously, the second approach looks a lot more elegant, but that is by design :)
class MapFunction extends Function {
Function mapper;
MapFunction (Function mapper) {
this.mapper = mapper;
}
@Override
public Expression evaluate(Expression x) {
return mapper.evaluate(x);
}
}
Function square = new Function () {
@Override
public Expression evaluate(Expression x) {
if(x instanceof Number) {
return new Multiply(x,x).evaluate();
}
return super.evaluate(x);
}
};
Function timesTwo = new Function () {
@Override
public Expression evaluate(Expression x) {
if(x instanceof Number) {
return new Multiply(x,new Number(2)).evaluate();
}
return super.evaluate(x);
}
};
Function sum = new Function() {
@Override
public Expression evaluate(Expression x) {
if(x instanceof Array) {
Array a = (Array)x;
Expression sum;
try {
sum = (Expression)a.get(0).getClass().newInstance();
} catch (Exception e) {
throw new CannotPrototypeException(e);
}
for(int i = 0; i < a.length(); i++) {
sum = new Add(sum, a.get(i)).evaluate();
}
return sum;
}
return super.evaluate(x);
}
};
int [] numbers = {1,2,3,4};
String [] strings = {"a", "b", "c", "d"};
MapFunction map = new MapFunction (square);
assertEquals("25", map.evaluate(new Number(5)).toString());
assertEquals("[1, 4, 9, 16]", map.evaluate(new Array(numbers)).toString());
map.mapper = timesTwo;
assertEquals("10", map.evaluate(new Number(5)).toString());
assertEquals("[2, 4, 6, 8]", map.evaluate(new Array(numbers)).toString());
map.mapper = sum;
assertEquals("5", map.evaluate(new Number(5)).toString());
assertEquals("10", map.evaluate(new Array(numbers)).toString());
assertEquals("a", map.evaluate(new Literal("a")).toString());
assertEquals("abcd", map.evaluate(new Array(strings)).toString());Above I implemented a the MapFunction with 3 different mapper functions: square, timesTwo and sum. Have a look at the code and how it works. Sum is a bit more interesting than the others function. It needs to set its initial sum value based on the first element of the array that will be iterated by the MapFunction (that’s a fairly strong assumption to make, but without that map reduce would not work). Other than that, all mappers rely on behavior of the base Function class: when the parameter is a Number they simply calculate and return. When the parameter is an array or collection, that gets iterated.
And finally, the map reduce (just the sum) implemented with iterators this time:
class Sum extends Function {
Expression sum;
Sum(Expression init) {
super();
sum = init.evaluate();
}
public Expression evaluate(Expression x) {
sum = new Add(sum, x).evaluate();
return x;
}
}
int [] numbers = {1,2,3,4};
String [] strings = {"a", "b", "c", "d"};
Sum sum = new Sum(new Number(0));
new FunctionalIterator(new Array(numbers), sum).evaluate();
assertEquals("10", sum.sum.toString());
sum = new Sum(new Literal(""));
new FunctionalIterator(new Array(strings), sum).evaluate();
assertEquals("abcd", sum.sum.toString());As a plus, this can sum whatever is in the array. It will try to convert the sum on a best effort basis (if nothing else works, it makes the sum a string).
ConclusionLanguages like Java or C# or whatnot, give programmer enough firepower to implement exactly what they need for any given problem. For example, and I tried to make this point above, one can do functional programming and "non-functional programming" language. Upon careful examination of the problem, we could find simple and elegant solutions regardless of the language we program in. Elegant code is elegant in any language, even in assembly. If you want to do function programming in Java, C or assembly, rest assured that there is an elegant way to do it. I hope my solution qualifies as such. You may download all the code from
here.
