Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
6  
i don't think it is possible. you have to redesign (and rewrite) everything again. –  Bryan Chen Oct 4 '13 at 4:12
18  
-1, this post is biased by the wrong assumption that OOP and functional style are contrary. Those are mostly orthogonal concepts, and IMHO its a myth that they are not. "Functional" is more opposed to "Procedural", and both styles can be used in conjunction with OOP. –  Doc Brown Oct 4 '13 at 5:56
10  
@DocBrown, OOP relies too heavily on a mutable state. Stateless objects do not fit well into the current OOP design practice. –  SK-logic Oct 4 '13 at 8:42
9  
@SK-logic: the key are not stateless objects, but immutable objects. And even when objects are mutable, they can often used in a functional part of the system as long as they are not changed within the given context. Furthermore, I guess you know objects and closures are interchangeable. So this all shows that OOP and "functional" are not contrary. –  Doc Brown Oct 4 '13 at 8:50
11  
@DocBrown: I think the language constructs are orthogonal, while the mindsets tend to clash. OOP people tend to ask "what are the objects and how do they collaborate?"; functional people tend to ask "what is my data, and how do I want to transform it?". Those aren't the same questions, and they lead to different answers. I also think you misread the question. It's not "OOP drools and FP rules, how do I get rid of OOP?", it's "I get OOP and I don't get FP, is there a way to transform an OOP program into a functional one, so I can get some insight?". –  Michael Shaw Oct 4 '13 at 18:30

5 Answers 5

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.

share|improve this answer
    
I appreciate the effort, organization, and clear communication in this answer; but I have to take slight issue with some of the technicals. One of the keys as mentioned near the top is composition of functions, this goes back to why largely encapsulating functions inside of objects does not yield purpose: If a function is inside an object, it must be there to act on that object; and if it acts on that object it must be changing it's internals. Now I'll forgive that not everyone requires referential transparency or immutability, but if it changes the object in place it no longer need return it –  Jimmy Hoffa Oct 16 '13 at 1:26
    
And as soon as a function doesn't return a value, suddenly the function cannot be composed with others, and you lose all the abstraction of functional composition. You could have the function change the object in place and then return the object, but if it's doing this why not just make the function take the object as a parameter and free it from the confines of it's parent object? Freed from the parent object it will be able to work on other types as well, which is another important part of FP you're missing: Type abstraction. your forEachPasenger only works against passengers... –  Jimmy Hoffa Oct 16 '13 at 1:28
1  
The reason you abstract things to map and reduce, and these functions are not bound to containing objects is so that they can be used on a myriad of types through parametric polymorphism. It's the conflagration of these varied abstractions which you don't find in the OOP languages that really defines FP and drives it to have value. It's not that laziness, referential transparency, immutability, or even the HM type system are necessary to create FP, those things are rather side effects of creating languages purposed for functional composition where functions can abstract over types generally –  Jimmy Hoffa Oct 16 '13 at 1:31
    
@JimmyHoffa You made a very fair criticism of my example. I was seduced into mutability by the Java8 Consumer interface. Also, the chouser/fogus definition of FP did not include immutability and I added the Odersky/Spoon/Venners definition later. I left the original example, but added a new, immutable version under a "PS" section at the bottom. It's ugly. But I think it demonstrates functions acting on objects to produce new objects rather than changing the internals of the originals. Great comment! –  GlenPeterson Oct 16 '13 at 13:27
1  
This conversation continues on The Whiteboard: chat.stackexchange.com/transcript/message/11702383#11702383 –  GlenPeterson Oct 16 '13 at 16:05

I have personal experience "accomplishing" this. In the end, I didn't come up with something that's purely functional, but I came up with something that I'm happy with. Here's how I did it:

  • Convert all external state to a parameter of the function. EG: if an object's method modifies x, make it so the method gets passed an x instead of calling this.x.
  • Remove behavior from objects.
    1. Make the data of the object publicly accessible
    2. Convert all methods into functions that the object calls.
    3. Have client code that calls the object call the new function by passing in the object data. EG: Convert x.methodThatModifiesTheFooVar() into fooFn(x.foo)
    4. Remove the original method from the object
  • Replace as many iterative loops as you can with higher order functions like map, reduce, filter, etc.

I couldn't get rid of mutable state. It was just too non-idiomatic in my language (JavaScript). But, by making all state passed in and/or returned, every function is possible to test. This is different from OOP where setting up the state would take too long or separating dependencies often requires modifying production code first.

Also, I could be wrong about the definition, but I think my functions are referentially transparent: My functions will have the same effect given the same input.

Edit

As you can see here, it's not possible to create a truly immutable object in JavaScript. If you're diligent and in control of who calls your code, you can do it by always creating a new object instead of mutating the current one. It wasn't worth the effort to me.

But if you're using Java you can use these techniques to make your classes immutable.

share|improve this answer
    
+1 Depending on just what exactly you are trying to do, this is probably as far as you can really go without making design changes that would go waaaay beyond just "refactoring". –  Evicatos Oct 15 '13 at 22:32
    
@Evicatos: I dunno, if JavaScript had better support for immutable state, I think my solution would be as functional as you'd get in a dynamic functional language like Clojure. What's an example of something that would require something beyond just refactoring? –  Daniel Kaplan Oct 15 '13 at 22:35
    
I think getting rid of the mutable state would qualify. I don't think it's just a question of better support in the language, I think going from mutable to immutable will basically always require fundamental architectural changes that essentially constitute a rewrite. Ymmv depending on your definition of refactoring though. –  Evicatos Oct 15 '13 at 23:04
    
@Evicatos see my edit –  Daniel Kaplan Oct 16 '13 at 0:35
1  
@tieTYT yes, that's sad about JS being so mutable, but at least Clojure can compile to JavaScript: github.com/clojure/clojurescript –  GlenPeterson Oct 22 '13 at 23:45

I don't think it's really possible to refactor the program completely - you would have to redesign and reimplement in the correct paradigm.

I've seen code refactoring defined as a "disciplined technique for restructuring an existing body of code, altering its internal structure without changing its external behavior".

You could make certain things more functional, but at its core you still have an object oriented program. You can't just change small bits and pieces to adapt it to a different paradigm.

share|improve this answer
    
I'd add that a good first mark is to strive for referential transparency. Once you have this you get ~50% of the benefits of functional programming. –  jozefg Oct 4 '13 at 20:20

You would probably have to turn all your code inside out since OOP and FP have two opposite approaches to organizing code.

OOP organizes code around types (classes): different classes can implement the same operation (a method with the same signature). As a result, OOP is more appropriate when the set of operations does not change much while new types can be added very often. For example, consider a GUI library in which each widget has a fixed set of methods (hide(), show(), paint(), move(), and so on) but new widgets could be added as the library is extended. In OOP it is easy to add a new type (for a given interface): you only need to add a new class and implement all its methods (local code change). On the other hand, adding a new operation (method) to an interface may require changing all the classes that implement that interface (even though inheritance can reduce the amount of work).

FP organizes code around operations (functions): each function implements some operation that can treat different types in different ways. This is usually achieved by dispatching on the type via pattern matching or some other mechanism. As a consequence, FP is more appropriate when the set of types is stable and new operations are added more often. Take for example a fixed set of image formats (GIF, JPEG, etc) and some algorithms that you want to implement. Each algorithm can be implemented by a function that behaves differently according to the type of the image. Adding a new algorithm is easy because you only need to implement a new function (local code change). Adding a new format (type) requires modifying all the functions you have implemented so far to support it (non-local change).

Bottom line: OOP and FP are fundamentally different in the way they organize code, and changing an OOP design into a FP design would involve changing all your code to reflect this. It can be an interesting exercise, though. See also these lecture notes to the SICP book cited by mikemay, in particular slides 13.1.5 through 13.1.10.

share|improve this answer

I think this series of articles is exactly what you want:

Purely Functional Retrogames

http://prog21.dadgum.com/23.html Part 1

http://prog21.dadgum.com/24.html Part 2

http://prog21.dadgum.com/25.html Part 3

http://prog21.dadgum.com/26.html Part 4

http://prog21.dadgum.com/37.html Follow-up

The summary is:

The author suggests a main loop with side effects (side effects must happen somewhere, right?) and most functions return small immutable records detailing how they changed the state of the game.

Of course when writing a real-world program you will mix and match several programming styles, using each one where it helps most. However it's a good learning experience to try writing a program in the most functional/immutable way and also writing it in the most spaghetti way, using only global variables :-) (do it as an experiment, not in production, please)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.