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've spent about 20-40 hours developing part of a game using JavaScript and HTML5 canvas. When I started I had no idea what I was doing. So it started as a proof of concept and is coming along nicely now, but it has no automated tests. The game is starting to become complex enough that it could benefit from some automated testing, but it seems tough to do because the code depends on mutating global state.

I'd like to refactor the whole thing using Underscore.js, a functional programming library for JavaScript. Part of me thinks I should just start from scratch using a Functional Programming style and testing. But, I think refactoring the imperative code into declarative code might be a better learning experience and a safer way to get to my current state of functionality.

Problem is, I know what I want my code to look like in the end, but I don't know how to turn my current code into it. I'm hoping some people here could give me some tips a la the Refactoring book and Working Effectively With Legacy Code.


For example, as a first step I'm thinking about "banning" global state. Take every function that uses a global variable and pass it in as a parameter instead.

Next step may be to "ban" mutation, and to always return a new object.

Any advice would be appreciated. I've never taken OO code and refactored it into Functional code before.

share|improve this question
1  
"Next step may be to "ban" mutation, and to always return a new object.": IMO you do not need to ban mutation completely: referential transparency is what counts. You can use destructive updates as an optimization technique provided you preserve referential transparency. –  Giorgio Jun 24 '13 at 22:40
    
@Giorgio good to know. I'd prefer to "ban" mutation first and optimize second, though. –  tieTYT Jun 24 '13 at 22:41
1  
I think your first two steps are a great idea! I would be honored if you'd take a look at a functional JS library I wrote (tiny) for making monadically composed chains of functions, it may help; it passes state along through the chain of functions but never mutating; each function you chain with it will ensure values are cloned to return a new value rather than the value handed to it. github.com/JimmyHoffa/Machinad The lib itself is pretty complex if you're not familiar with monads, but look at the example and you should see it's very easy to use; it was just complex to implement. –  Jimmy Hoffa Jun 25 '13 at 3:12
1  
If you want to do things in a functional style one thing I would make sure you wash out of your code is inheritance if it's even there at all. force yourself to compose functions and use what javascript is great at: lexical scope to make facilities available where you need instead of hierarchy trees. Define your data structures as just those, only add functions to them to aid fluent style where the function would be just as good taking the data structure as a first parameter. In OO this would be an anemic model; but we're talking FP, composition is the key to avoiding those drawbacks. –  Jimmy Hoffa Jun 25 '13 at 3:24
    
@tieTYT: Of course I agree with you, we all know that premature optimization is bad. –  Giorgio Jun 25 '13 at 6:11
add comment

1 Answer

Having authored several projects in functional style JavaScript, allow me to share my experience. I will focus on high level considerations, not specific implementation concerns. Remember, there are no silver bullets, do what works best for your specific situation.

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.
share|improve this answer
    
Thanks a lot for taking the time to write this up. Some examples would be greatly appreciated (and personal projects don't help with this because they show the "after", they don't show how to get there from "before"). This would be most useful in your section titled "Functional Style Interfaces". –  tieTYT Jun 28 '13 at 0:05
    
I added a simple example. Finding a larger example demonstrating the conversion process will be hard, so I highly recommend trying to start working with real world code as soon as possible. It really is a very project specific process and actually working though the code will teach you a great deal. Maybe the first pass isn't great, but keep iterating and learning until you are happy with the result. And there are plenty of excellent examples of functional design online for other languages (I personally find scheme and clojure to be the best starting points for many topics). –  Matt Bierner Jun 28 '13 at 5:01
    
I wish this answer were split into several so I could upvote each part –  paul Jun 28 '13 at 18:10
add comment

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.