Skip to content
Print

So Begins the Functional Revolution

19
May
2008

When I started learning Scala, I was convinced that its designers were positively the worst marketers I had ever seen.  The official project page was (and is) peppered with Scala examples of things like quicksort, factoring, prime number sieves and so on.  All of these examples were written in such a way as to be virtually incomprehensible to the average OOP developer.  In fact, they all had a very simple common denominator which really set me off: they were written with a very functional flair.

Functional programming is an ancient and venerable tradition, dating back all the way to the days of Lisp and APL.  In its purest form (ahem: Haskell), functional programming is the absence of side-effects.  Everything in the language is some sort of declarative expression, taking some values and returning a result.  This sweeping restricting has some fairly profound consequences.  Consider the following ML function:

fun search nil _ = false
  | search (hd::tail) x = (hd = x) orelse (search tail x)

For most developers sporting an imperative background, this is probably fairly difficult to read.  If you actually boil it down, all it does is walk through a list, returning true if it finds a certain element (x), otherwise false.  This implementation is a far cry from how we would do it in an imperative language:

public <T> boolean search(List<T> list, T element) {
    for (T hd : list) {
        if (element.equals(hd)) {
            return true;
        }
    }
 
    return false;
}

Arguably, this is harder to read, but it is much more familiar to most people.  Both functions do exactly the same thing, but one of them relies upon mutable state and the side effects imposed by iterators, while the other is completely declarative (in the mathematical sense).  The one critical thing to notice is that the Java version is less constrained.  In ML, you can only have one expression per function, and you certainly can’t have anything mutable floating around.  By contrast, Java offers a far greater sense of freedom in what you can do.  Want to modify an instance field?  Go right ahead; there’s nothing stopping you!  I believe that it is for this reason that imperative languages like C/C++, Java, Ruby and such have really become the dominant force in the industry.

Getting back to my original point though…  I have to admit that I used to be a firm believer in the One True (imperative) way of doing things.  The OOP mothership had landed and I was 100% convinced that it was here to stay.  However, after spending some time getting to know Scala, I’m beginning to sway more to the “academic” way of thinking: functional languages are pretty nice.  Consider the following Scala algorithm which takes a series of integers as its arguments and prints their sum:

object Main {
  def main(args: Array[String]) {
    println(args.map(_.toInt).foldLeft(0)(_ + _))
  }
}

Compare that to the equivalent Java code:

public class Main {
    public static void main(String[] args) {
        int sum = 0;
        for (String arg : args) {
            sum += Integer.parseInt(arg);
        }
 
        System.out.println(sum);
    }
}

Scala’s naturally concise syntax aside, the use of functional concepts definitely contributes to a more expressive solution.  Once you understand what the map and foldLeft methods accomplish, this code becomes startlingly readable.  What’s more, because this code is simpler and more expressive, the potential for subtle bugs and maintenance problems because virtually non-existent.  If something goes wrong in our Scala example and somehow the type checker doesn’t catch it, the problem will still be fairly easy to fix because of how straightforward and consistent the code is.

Contrast this with the Java solution.  It’s easy to imagine subtle errors slipping into the implementation.  Even something as simple as a typo can be difficult to track down.  Consider:

public class Main {
    public static void main(String[] args) {
        int sum = 0;
        for (String arg : args) {
            sum = Integer.parseInt(arg);
        }
 
        System.out.println(sum);
    }
}

Can you spot the error?  I’ll give you a hint, given the input “1 2 3 4 5“, the correct answer is 15.  Our revised Java solution prints “5“.

I can’t even figure out how to trivially break the Scala solution so that it does something bad.  This sort of stability happens time and time again with functional solutions.  You write the code, it’s expressive and elegant, and somehow it manages to do everything you wanted without fuss. 

This isn’t even limited to simple examples.  Somehow, this effect holds even in larger, more complicated systems.  I recently built a modest application in Scala using it’s trademark hyrbrid-functional style.  It’s hard to estimate of course, but judging by my experiences with similar projects in Java, I saved a great deal of time and effort just due to Scala’s functional expressiveness.

I doubt that the industry is going to change overnight, but it’s hard to deny the benefits of the FP approach.  Functional languages are on the rise; Scala is only the tip of the iceberg.  Languages like Erlang and F# are also gaining popularity as developers begin to recognize how expressive they can be.  It may take some time, but I predict that within a decade or so, the dominant paradigm in the industry will be functional, or more likely some hybrid thereof.  Welcome the revolution!

Comments

  1. Actually, your Java example it´s pretty bad, because the “subtle mistake” you are showing it´s not actually a consequence of a syntatic problem, but an IQ one. Only an idiot could to something like that.

    Henrique Lobo W Monday, May 19, 2008 at 4:43 am
  2. I find it rather amusing that most functional examples are not about a business domain but about … functions. And people deduce from there that functional languages are better suited to express functions. Doh! Who would have guessed.

    Peace
    -stephan

    Stephan Schmidt Monday, May 19, 2008 at 4:59 am
  3. Stephan, I’ve never seen business logic nor data manipulation in enterprise apps, either. More seriously, I’m not sure a functional revolution is coming, but it’s subtlely working its way into the mainstream through C#, JavaScript, and even Java a bit. (And there’s even SQL which has some functional feel to it.) This in addition to the more focused functional languages. I’m not completely sold on Scala, but I think it’s got more value than you imagine.

    Tom Monday, May 19, 2008 at 8:55 am
  4. It is sort of hard to show the benefits of a paradigm in a trivial example without producing *some* flaws. :-) While it is true that the benefits of FP are less obvious when doing something like a Swing UI, they are still very much present. Closures instead of anonymous inner classes being a nice example, but there are also other tasks which must be performed during UI setup that are much cleaner when done functionally.

    Incidentally, the “subtle mistake” is subtle because it’s an easy typo to make and a fairly hard error to detect when you’re not looking for it. If you imagine something like this embedded in a non-trivial algorithm, things can get pretty ugly pretty fast. I’m certain that all of us have done similar things at one point or another (I know I have).

    Daniel Spiewak Monday, May 19, 2008 at 9:37 am
  5. Hi Daniel,

    I think you fell in the exact same trap that you denounce by providing an example of functional programming with a feature which, in my opinion, is hardly ever used and not that useful overall (folding).

    Your point resonates with me, though: I’m a bit tired of reading small snippets of tail recursions about mundane stuff like calculating prime numbers or implementing quicksort. The only way to drag Scala, and functional programming in general, out of the obscurity is to rise above this and start tackling problems that Java programmers face every day (web programming, ORM, etc…).

    The Artima book is a good start, but there is definitely an opportunity for another book there…


    Cedric

    Cedric Monday, May 19, 2008 at 9:47 am
  6. I’ve actually been surprised by how often I use folds in my code. Reduce is sometimes more useful (especially in String joining), but fold is more general (it works in the empty case). It does take a bit of getting used to, but once you start using fold you’ll never look back.

    Daniel Spiewak Monday, May 19, 2008 at 10:00 am
  7. “…hardly ever used and not that useful overall (folding).”

    Hey Daniel, ignorance is bliss ain’t it? ;)
    Keep up the good work mate.

    Tony Morris Monday, May 19, 2008 at 5:47 pm
  8. What bugs me is when people use known, solved problems as examples of ‘instances FP can give a cleaner solution: replacing inner classes with closures, UI setup. IMO, the seductive power of Scala is: trying to think outside my own box and consider problems I never considered before because they are so ingrained in how I work: how about coroutines to develop web applications? The state would be maintained in the code, not in a cookie/session. That’s my .02…

    Mark Monday, May 19, 2008 at 5:51 pm
  9. @Mark

    That’s a good point. I know what you’re talking about too (with Scala pushing us to think outside the box). I’ll have to stay on the lookout for a good example of this in my daily coding, something condensable into a blog post. This really is the strength of Scala, more than just its functional nature or its amenability to DSLs, but rather the way it encourages you to approach problems in a remarkably unique fashion.

    Daniel Spiewak Monday, May 19, 2008 at 7:03 pm
  10. @Stephan

    Google is in the business domain, they produced MapReduce for a real business problem, and they are now reaping huge benefit. MapReduce *is* functional thinking. The issue isn’t whether an imperative or functional implementation of quicksort is better; it’s whether you can employ critical thinking to help solve real problems. I enjoy learning and thinking in different programming paradigms. The best way to think outside the box is to never climb in.

    Paul

    Paul Rogers Monday, May 19, 2008 at 10:41 pm
  11. Hi Daniel,

    I recently started learning Scala to and have started my first project with it, a visual interpreter that uses a Swing based interface instead of the command line (http://code.google.com/p/scalide/). I agree with what you are saying when I first started I would use a lot of while and for loops. Now I find myself thinking about how to write a combination of calls to filter / map / fold etc… and find them easier to read than imperative loops in several cases.

    The pattern matching, actors library, type inference, and drive to keep data immutable are really nice too.

    Ben

    Ben Jackman Monday, May 19, 2008 at 11:51 pm
  12. Various cool features developed in academic languages like ML and lisp have made it into mainstream languages, but it’s pretty unlikely that a functional language will ever make it mainstream, and here’s why

    Functional programming is not additive, it is subtractive. It removes operations , i.e. operations with side effects. In practice all nontrivial programs really *do* need side effects and *very often* this means that almost all functional languages aren’t *really* functional languages, they just make manipulating state more *annoying*, not impossible.

    In a real functional language, you *could not* implement a quick sort. I’ve seen quite a few FP advocates claim to write quicksort, and compare it to a C implementation of quicksort. However, invariably the C implementation is real quicksort, whereas the fp implementation is *mergesort*. Quicksort requires a mutable vector to get its performance boost. I would *assume* that everyone can tell the difference between two totally different sorting algorithms with different complexity, but the examples stay out there for some reason anyway…

    Also, while quicksort is not *asymptotically* worse than mergesort (quite the opposite, just quicker for the common in memory and cache case), there are plenty of algorithms where a pure functional implementation is necessarily some higher order polynomial running time than the case possible with mutable state (think dynamic programming). I think everyone can agree that’s the sort of performance decrease that isn’t acceptable just to get a nicer looking language.

    Really the nice things about scala, ml, lisp, etc are features that can and probably *will* be implemented in more mainstream languages. C already has always had first class functions. Closures are planned for c++ sometime in 2009. However, those things are not functional programming. What makes a FP language an FP language is that it makes writing procedural code either impossible, or in the case of an *impure* functional language, just really difficult, like how Ocaml supports procedural and OO programming, but makes the syntax ugly intentionally.

    Brendan Miller Tuesday, May 20, 2008 at 2:56 am
  13. The Scala code for summing the argument first constructs an array of ints which the typical equivalent Java code does not.

    You could do:

    println(“sum = ” + args.foldLeft(0)(_.toInt + _.toInt))

    Is there a way to lazily map the toInt over the array to prevent repeating the call to toInt above?

    Steven Shaw Wednesday, May 21, 2008 at 9:51 am
  14. No need for laziness, this works just as well:

    println(”sum = ” + args.foldLeft(0)(_ + _.toInt))

    It is a lot more concise, and I thought about doing it this way, but I wanted to use the map(…) function, something which has taken almost as much flack as fold.

    Daniel Spiewak Wednesday, May 21, 2008 at 9:53 am
  15. Of course! Thanks :)

    Steven Shaw Wednesday, May 21, 2008 at 10:12 am
  16. You can also use
    println(args.projection.map(_.toInt).foldLeft(0)(_ + _))

    This will not create the intermediate array, but will calculate the mapped element when needed (if I understand it correctly). Of course there are tradeoffs for both versions.

    Asd Thursday, May 22, 2008 at 5:27 am
  17. Brendan, you make several errors in your post

    >Functional programming is not additive, it is subtractive. It removes operations ,

    In the impure sense of the word functional it’s additive. It adds functional composition, closures, etc. You mention ML, lisp, and Scala in your post – all of these languages allow mutable state and IO side effects. Scala in particular makes it just as trivially easy to do as Java. Some lisps do, too.

    >IHowever, invariably the C implementation is real quicksort, whereas the fp implementation is *mergesort*

    Factually incorrect. The functional sort you are seeing is the non-in place form of quicksort. It has the same time complexity as in-place quicksort – O(n^2) worst case – but a different space complexity. Mergesort, on the other hand, has the better worst case time complexity – O(n log n). And, believe it or not, there’s an imperative form of mergesort on linked lists with O(1) additional space complexity.

    > Also, while quicksort is not *asymptotically* worse than mergesort

    Absolutely it is asymptotically worse. See above about O(n^2) vs O(n log n). Quicksort has many advantages, though, so for most reasonably sized, somewhat randomly ordered data sets in mutable arrays, quicksort is in practice faster. But I will say this again, if you are about asymptotic time analysis then quicksort is worse.

    >Really the nice things about scala, ml, lisp, etc are features that can and probably *will* be implemented in more mainstream languages.

    How ’bout a general expression orientation as opposed to a statement orientation? Why do we need both “if” and the ternary operator in all the C offspring? Will that kind of thinking come in a mainstream language? Yup – when a mainstream language is functional (even if impurely so).

    > C already has always had first class functions.

    C’s functions are not first class unless by “first class” you mean “distinctly second class.” Function pointers mean that top-level functions can be treated as values, true, but, unlike truly first class types of values like integers, you cannot create a new C function at runtime by say combining two other functions.

    > What makes a FP language an FP language is that it makes writing procedural code either impossible, or in the case of an *impure* functional language, just really difficult,

    Not so. Where is it written that an impure functional language must make its imperative side more difficult? A functional language does make writing side effect free code easy – but that doesn’t mean side effecting code need be any harder. Again, check out Scala. The syntax for doing side effecting stuff is pretty similar to Java’s – e.g incrementing x by 100 is just “x = x + 100″ or even “x += 100″.

    Also, imperative programming languages only have native support for one kind of side effect (destructively changing the state of the world) whereas a bit of monadic sugar allows a language like Scala or Haskell to cleanly deal with things that a imperative programmer wouldn’t even understand as side effects. But that’s a discussion for another time and place.

    James Iry Thursday, May 22, 2008 at 5:48 pm
  18. Stephan,

    Same old tired stuff. “Your example code doesn’t solve my business problem so it’s worthless.”

    >I find it rather amusing that most functional examples are not about a business domain but about … functions. And people deduce from there that functional languages are better suited to express functions. Doh! Who would have guessed.

    What business domain does not have lists and sets of things? What business never needs to search, sort, sum, fold, spindle, and mutilate those collections? If nothing else functional programming already brings a nice win for this important bit. But hey, if most of your business domain is better modeled with OO style objects and imperative code, no problem – Common Lisp, OCaml, and Scala can do that too.

    James Iry Thursday, May 22, 2008 at 6:10 pm
  19. All the business problems I have worked on in the finance industry over the last 8 years would have been much much simpler had we been using a language like scala that blends functional and OO concepts. The apps I’ve worked on all required complex aggregation, sorting, filtering, rules, etc., on complex models. In desperation we ended up writing a library in Java to help us (http://jedi.codehaus.org/).

    Languages like scala are ideal for business applications in my experience at least. Unfortunately, I cannot show you these real world business examples :-)

    Channing Walton Friday, May 23, 2008 at 1:28 pm

Post a Comment

Comments are automatically formatted. Markup are either stripped or will cause large blocks of text to be eaten, depending on the phase of the moon. Code snippets should be wrapped in <pre>...</pre> tags. Indentation within pre tags will be preserved, and most instances of "<" and ">" will work without a problem.

Please note that first-time commenters are moderated, so don't panic if your comment doesn't appear immediately.

*
*