Object-oriented – How to refactor an OO program into a functional one

functional programmingobject-orientedrefactoring

I'm having difficulty finding resources on how to write programs in a functional style. The most advanced topic I could find discussed online was using structural typing to cut down on class hierarchies; most just deal with how to use map/fold/reduce/etc to replace imperative loops.

What I would really like to find is an in-depth discussion of an OOP implementation of a non-trivial program, its limitations, and how to refactor it in a functional style. Not just an algorithm or a data structure, but something with several different roles and aspects – a video game perhaps. By the way I did read Real-World Functional Programming by Tomas Petricek, but I'm left wanting more.

Best Answer

Definition of Functional Programming

The introduction to The Joy of Clojure says the following:

Functional programming is one of those computing terms that has a amorphous definition. If you ask 100 programmers for their definition, you’ll likely receive 100 different answers...

Functional programming concerns and facilitates the application and composition of functions... For a language to be considered functional, its notion of function must be first-class. First-class functions can be stored, passed, and returned just like any other piece of data. Beyond this core concept, [definitions of FP might include] purity, immutability, recursion, laziness, and referential transparency.

Programming in Scala 2nd Edition p. 10 has the following definition:

Functional programming is guided by two main ideas. The first idea is that functions are first-class values... You can pass functions as arguments to other functions, return them as results from functions, or store them in variables...

The second main idea of functional programming is that the operations of a program should map input values to output values rather than change data in place.

If we accept the first definition, then the only thing you need to do to make your code "functional" is to turn your loops inside out. The second definition includes immutability.

First Class Functions

Imagine you currently get a List of Passengers from your Bus object and you iterate over it decreasing each passenger's bank account by the amount of the bus fare. The functional way to perform this same action would be to have a method on Bus, maybe called forEachPassenger that takes a function of one argument. Then Bus would iterate over its passengers however that is best accomplished and your client code that charges the fare for the ride would be put in a function and passed to forEachPassenger. Voila! You're using functional programming.

Imperative:

for (Passenger p : Bus.getPassengers()) {
    p.debit(fare);
}

Functional (using an anonymous function or "lambda" in Scala):

myBus = myBus.forEachPassenger(p:Passenger -> { p.debit(fare) })

More sugary Scala version:

myBus = myBus.forEachPassenger(_.debit(fare))

Non-first-class Functions

If your language does not support first-class functions, this can get very ugly. In Java 7 or earlier, You have to provide a "Functional Object" interface like this:

// Java 8 has java.util.function.Consumer, but in earlier
// versions you have to roll your own:
public interface Consumer<T> {
    public void accept(T t);
}

Then the Bus class provides an internal iterator:

public void forEachPassenger(Consumer<Passenger> c) {
    for (Passenger p : passengers) {
        c.accept(p);
    }
}

Finally, you pass an anonymous function object to the Bus:

// Java 8 has syntactic sugar to make this look more like
// the Scala solution, but earlier versions require manually
// instantiating a "Function Object," in this case, a
// Consumer:
Bus.forEachPassenger(new Consumer<Passenger>() {
    @Override
    public void accept(final Passenger p) {
        p.debit(fare);
    }
}

Java 8 allows local variables to be captured the scope of an anonymous function, but in earlier versions, any such varibales must be declared final. To get around this you may need to make a MutableReference wrapper class. Here's an integer-specific class that lets you add a loop counter to the above code:

public static class MutableIntWrapper {
    private int i;
    private MutableIntWrapper(int in) { i = in; }
    public static MutableIntWrapper ofZero() {
        return new MutableIntWrapper(0);
    }
    public int value() { return i; }
    public void increment() { i++; }
}

final MutableIntWrapper count = MutableIntWrapper.ofZero();
Bus.forEachPassenger(new Consumer<Passenger>() {
    @Override
    public void accept(final Passenger p) {
        p.debit(fare);
        count.increment();
    }
}

System.out.println(count.value());

Even with this ugliness, it is sometimes beneficial to eliminate complicated and repeated logic from loops spread throughout your program by providing an internal iterator.

This ugliness has been fixed in Java 8, but handling checked exceptions inside a first class function is still really ugly and Java still carries the assumption of mutability in all its collections. Which brings us to the other goals often associated with FP:

Immutability

Josh Bloch's Item 13 is "Prefer Immutability." Despite common trash talk to the contrary, OOP can be done with immutable objects, and doing so makes it much better. For instance, String in Java is immutable. StringBuffer, OTOH needs to be mutable in order to build an immutable String. Some tasks, like working with buffers inherently require mutability.

Purity

Each function should at least be memoizable - if you give it the same input parameters (and it should have no input besides its actual arguments), it should produce the same output every time without causing "side effects" like changing global state, performing I/O, or throwing exceptions.

It has been said that in Functional Programming, "some evil is usually required in order to get work done." 100% purity is generally not the goal. Minimizing side effects is.

Conclusion

Really, of all the ideas above, immutability has been the biggest single win in terms of practical applications for simplifying my code - whether OOP, or FP. Passing functions to iterators is the second biggest win. The Java 8 Lambdas documentation has the best explanation of why. Recursion is great for processing trees. Laziness allows you to work with infinite collections.

If you like the JVM, I recommend you take a look at Scala and Clojure. Both are insightful interpretations of Functional Programming. Scala is type-safe with somewhat C-like syntax, though it really has as much syntax in common with Haskell as with C. Clojure is not type-safe and it is a Lisp. I recently posted a comparison of Java, Scala and Clojure with regard to one specific refactoring problem. Logan Campbell's comparison using the Game of Life includes Haskell and typed Clojure as well.

PS

Jimmy Hoffa pointed out that my Bus class is mutable. Rather than fix the original, I think this will demonstrate exactly the kind of refactoring this question is about. This can be fixed by making each method on Bus a factory to produce a new Bus, each method on Passenger a factory to produce a new Passenger. Thus I've added a return type to everything which means I'll copy Java 8's java.util.function.Function instead of Consumer interface:

public interface Function<T,R> {
    public R apply(T t);
    // Note: I'm leaving out Java 8's compose() method here for simplicity
}

Then on Bus:

public Bus mapPassengers(Function<Passenger,Passenger> c) {
    // I have to use a mutable collection internally because Java
    // does not have immutable collections that return modified copies
    // of themselves the way the Clojure and Scala collections do.
    List<Passenger> newPassengers = new ArrayList(passengers.size());
    for (Passenger p : passengers) {
        newPassengers.add(c.apply(p));
    }
    return Bus.of(driver, Collections.unmodifiableList(passengers));
}

Finally, the anonymous function object returns the modified state of things (a new bus with new passengers). This assumes that p.debit() now returns a new immutable Passenger with less money than the original:

Bus b = b.mapPassengers(new Function<Passenger,Passenger>() {
    @Override
    public Passenger apply(final Passenger p) {
        return p.debit(fare);
    }
}

Hopefully you can now make your own decision about how functional you want to make your imperative language, and decide whether it would be better to redesign your project using a functional language. In Scala or Clojure, the collections and other APIs are designed to make functional programming easy. Both have very good Java interop, so you can mix and match languages. In fact, for Java interoperability, Scala compiles its first class functions to anonymous classes that are almost compatible with the Java 8 functional interfaces. You can read about the details in Scala in Depth sect. 1.3.2.

Pure Functional vs Functional Style

Consider what you want to gain from this functional refactoring. Do you really want a pure functional implementation, or just some of the benefits a functional programming style can bring, such as referential transparency.

I have found the latter approach, what I call functional style, to mesh well with JavaScript and is usually what I want. It also allows selective non functional concepts to be carefully used in code where they make sense.

Writing code in a more purely functional style is also possible in JavaScript, but is not always the most appropriate solution. And Javascript can never be purely functional.

Functional Style Interfaces

In functional style Javascript, the most important consideration is the boundary between functional and the imperative code. Clearly understanding and defining this boundary is essential.

I organize my code around functional style interfaces. These are collections of logic that behave in a functional style, ranging from individual functions to entire modules. The conceptual separation of interface and implementation is important, a functional style interface may be implemented imperatively, as long as the imperative implementation does not leak across the boundary.

Unfortunately in Javascript, the burden of enforcing functional style interfaces falls entirely on the developer. Also, language features, such as exceptions, make a truly clean separation impossible.

Since you will be refactoring an existing codebase, start by identifying existing logical interfaces in your code that can be cleanly moved to a functional style. A surprising amount of code may already be functional style. Good starting points are small interfaces with few imperative dependencies. Everytime you move over code, existing imperative dependencies are eliminated and more code can be moved over.

Keep iterating, gradually working outwards to push large parts of your project onto the functional side of the boundary, until you are happy with the results. This incremental approach allows testing individual changes and makes identifying and enforcing the boundary easier.

Rethink Algorithms, Data Structures, and Design

Imperative solutions and design patterns often don't make sense in functional style. Especially for data structures, direct ports of imperative code to functional style can be ugly and slow. A simple example: would you rather copy every element of a list for a prepend or cons the element onto the existing list?

Research and evaluate existing functional approaches to problems. Functional programming is more than just a programming technique, it is a different way of thinking about and solving problems. Projects written in the more traditional functional programming languages, such as lisp or haskell, are great resources in this regard.

Understand the Language and Builtins

This is an important part of understanding the functional imperative boundary and will effect interface design. Understand what features can be safely used in functional style code and which can not. Everything from which builtins may throw exceptions and which, like [].push, mutate objects, to objects being passed by reference and how prototype chains work. A similar understanding of any other libraries you consume in your project is also required.

Such knowledge allows making informed design decisions, like how to handle bad input and exceptions, or what happens if a callback function does something unexpected? Some of this can be enforced in code, but some just requires documentation on the proper usage.

Another point is how strict your implementation should be. Do you really want to try enforcing the correct behavior on maximum call stack errors or when the user redefines some builtin function?

Using Non Functional Concepts Where Appropriate

Functional approaches are not always appropriate, especially in a language like JavaScript. The recursive solution may be elegant until you start getting maximum call stack exceptions for larger inputs, so perhaps an iterative approach would be better. Similarly, I use inheritance for code organization, assignment in constructors, and immutable objects where they make sense.

As long as the functional interfaces are not violated, do what makes sense and what will be easiest to test and maintain.

Example

Here is an example of converting some very simple real code to functional style. I don't have a very good large example of the process, but this small one touches on a number of interesting points.

This code builds a trie from a string. Ill start with some code based on the top section of John Resig's trie-js build-trie module. Many simplifications / formatting changes have been made and my intent is not to comment on the quality of original code (There are much clearer and cleaner ways to build a trie, so why this c style code comes up first in google is interesting. Here's a quick implementation that uses reduce).

I like this example because I don't have to take it all the way to a true functional implementation, just to functional interfaces. Here is the starting point:

var txt = SOME_USER_STRING,
    words = txt.replace(/\n/g, "").split(" "),
    trie = {};

for (var i = 0, l = words.length; i < l; i++) {
    var word = words[i], letters = word.split(""), cur = trie;
    for (var j = 0; j < letters.length; j++) {
        var letter = letters[j];
        if (!cur.hasOwnProperty(letter))
            cur[letter] = {};
        cur = cur[ letter ];
    }
    cur['$'] = true;
}

// Output for text = 'a ab f abc abf'
trie = {
    "a": {
        "$":true,
        "b":{
            "$":true,
            "c":{"$":true}
        "f":{"$":true}}},
    "f":{"$":true}};

Let's pretend this is the entire program. This program does two things: convert a string to a list of words and build a trie from the list of words. These are the existing interfaces in the program. Here is our program with the interfaces more clearly expressed:

var _get_words = function(txt) {
    return txt.replace(/\n/g, "").split(" ");
};

var _build_trie_from_list = function(words, trie) {
    for (var i = 0, l = words.length; i < l; i++) {
        var word = words[i], letters = word.split(""), cur = trie;
        for (var j = 0; j < letters.length; j++) {
            var letter = letters[j];
            if (!cur.hasOwnProperty(letter))
                cur[letter] = {};
            cur = cur[ letter ];
        }
        cur['$'] = true;
    }
};

// The 'public' interface
var build_trie = function(txt) { 
    var words = _get_words(txt), trie = {};
    _build_trie_from_list(words, trie);
    return trie;
};

Just by defining our interfaces, we can move _get_words to the functional style side of the boundary. Neither replace or split modifies the original string. And our public interface build_trie is functional style too, even though it interacts with some very imperative code. In fact, this is a fine stopping point in most cases. More code would get overwhelming, so let me overview a few other changes.

First, make all the interfaces functional style. This is trivial in this case, just have _build_trie_from_list return an object instead of mutating one.

Handling Bad input

Consider what happens if we call build_trie with an array of characters, build_trie(['a', ' ', 'a', 'b', 'c', ' ', 'f']). The caller assumed this would behave in a functional style, but instead it throws an exception when .replace is called on the array. This may be the intended behavior. Or we could do explicit type checks and make sure the inputs are as we expected. But I prefer duck typing.

Strings are just arrays of characters and arrays are just objects with a length property and non-negative integers as keys. So if we refactored and wrote new replace and split methods that operates on array-like objects of strings, they don't even have to be strings, our code could just do the right thing. (String.prototype.* will not work here, it converts the output to a string). Duck typing is a totally separate from functional programming, but the larger point is that bad input should always be considered.

Fundamental redesign

There are also more fundamental considerations. Assume that we want to build the trie in functional style as well. In the imperative code, the approach was to construct the trie one word at a time. A direct port would have us copy the entire trie every time we need to make an insertion to avoid mutating objects. Clearly that is not going to work. Instead, the trie could be constructed node by node, from the bottom up, so that once a node is completed, it never has to be touched again. Or another approach entirely may be better, a quick search shows many existing functional implementations of tries.

Hope the example clarified things a bit.

Overall, I find writing functional style code in Javascript is a worthwhile and fun endeavor. Javascript is a surprisingly capable functional language, albeit too verbose in its default state.

Good luck with your project.

A few personal projects written in functional style Javascript:

parse.js - Parser Combinators
Nu - Lazy streams
Atum - Javascript interpreter written in functional style Javascript.
Khepri - Prototype programming language I use for functional Javascript development. Implemented in functional style Javascript.