Articles

A Misconception of Functional Programming?

Recently, I came across an article entitled “Useful Pure Functional Programming” which talks about the advantages of functional programming.  However, something struck me about the way the author thinks about functional programming:

“Living for a long time in the context of an imperative world made me get used to think in a specific sequential way … On the other hand, in the pure functional world, I’m forced to think in a way to transform data.”

The author is arguing that thinking about execution in a sequential notion is somehow inherently connected with imperative languages.  The first “imperative” example given in the article is a simple loop in Java:

int sum(int[] list) {
  int result = 0;
  for (int i : list)
    result += i;
  return result;
}

The thing is, for me, this example could equally be written in a pure functional language.  Sure, it doesn’t look like Haskell code — but then Haskell isn’t the only pure functional language. For example, in Whiley, it would look like this:

int sum([int] list):
    result = 0
    for i in list:
        result = result + i
    return result

This is a pure function in the strongest sense of the word (i.e. it always returns the same result given the same arguments, does not have side effects and, hence, is referentially transparent). This function is pure because, in Whiley, compound data structures (e.g. lists, sets, maps, etc) have value semantics and behave like primitive data (e.g. int) rather than as references to data (like in Java).

Functional Style

Now, I think the author of the original article got confused about the difference between functional languages and functional style (i.e. the use of functions as the primary mechanism for expressing and composing computation).  Sure, the functional style favours (amongst other things) recursion over looping. But, that doesn’t prevent functional languages from including looping constructs.

The key is that many imperative languages support the functional style.  In other words, it’s not something exclusive to functional programming languages (although they perhaps support it better).  We need to try and distinguish these two things better, in my opinion, to avoid too much confusion around the difference between functional and imperative languages.

The thing is, some people don’t like the functional style.  For example, I always prefer to use loops when I can (such as for the sum() example above) because they are clear and easy to understand. But, for some things (e.g. traversing a linked list), I like recursion better.  That’s my style. The problem is that people with an imperative streak, like me, often believe they have to completely change their style to use a functional programming language.  But, that shouldn’t need to be the case.  It’s just a shame mainstream functional languages make imperative-style programming so difficult. If it was easier, then people could migrate slowly without having to rewire their brain from the outset …

Thoughts?

19 comments to A Misconception of Functional Programming?

  • noraguta

    Functional means functional.eg. Programming with functions and without mutables.But your example is still imperative.

  • Martijn Hoekstra

    Thoughts: Scala! It is a hybrid functional/imperative language that promotes a functional style, but doesn’t demand it. It allows the above loop in functional or in imperative style:

    You could do imperatively:

    def sum(ints : Seq[Int]) = {
    var result = 0
    for (nextint total + next)
    }

  • Hi noraguta,

    I think that functional programming means quite a lot of things. Look at the first sentence from the Wikipedia article on functional programming:

    In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data.

    My sum() implementation in Whiley is a mathematical function which does not mutate any global state. Yes, you can argue that it does mutate state local to the function — but is this really against the spirit of functional programming?

    The second paragraph of that Wikipedia article begins with this:

    In practice, the difference between a mathematical function and the notion of a function used in imperative programming is that imperative functions can have side effects that may change the value of program state.

    So, whilst my Whiley code may have imperative style, I argue that it is functional in this sense.

  • Martijn Hoekstra

    hrm, that didn’t come out looking any good, and it’s missing the functional one:

    def sum(ints: Seq[Int]) = {
    ints.foldleft(0)((total, next) => total + next)
    }

  • alex

    @noraguta I think you missed the point pretty hard.

  • Hi Martijn,

    Yes, I agree — Scala is a good example. To a lesser extent, so is D.

  • Neel Krishnaswami

    ML (both SML and OCaml) actually has full support for imperative programming — sequencing, references, while-loops, the works. However, most people don’t use them. The reason is that their type systems, like most, only track the flow of values, and so the inconsistency-checking you get from typechecking is of most value for programs in a value-oriented functional style.

    The pain of going from usefully precise type error messages to incomprehensible runtime errors because some dynamic data structure containing a bunch of functions of type unit -> unit called them in the wrong order creates a very strong selective pressure against imperative programming.

    You really need something like extended static checking to reduce the pain from imperative programming. I’d also expect you’d want the checker to say something about aliasing, too (a la separation logic). What’s Whiley’s story on aliased data?

  • Hi Neel,

    Well, in the case of pure functions like in my example, there is no possibility of aliased data. However, Whiley does support impure functions (called methods) where you can have true object references. At this stage, I don’t really have a story on the verification side of that — I’m mostly concentrating on verification of pure functions.

    Regarding the issue of typing you talk about, I think flow typing is one possible answer there [correct me if i'm wrong].

  • Yes, the difference is largely in how many side effects you’re willing to tolerate in your code. You can do all kinds of amazing things if you start by writing side effect-free code, and lambdas can help you do that. For example, making a habit of using a lambda and map instead of a for loop, whenever possible, will bring you far along the path of being able to do incredible optimizations, such as automatic, behind the scenes parallelization.

    http://www.yellosoft.us/parallel-processing-with-haskell

  • The article is called Useful Pure Functional Programming, you quoted the name of the blog

  • Hi Iopq,

    Oops, will correct — thanks!

  • John

    I think what you’re struggling against is the impracticality of a truly pure “functional language”. In mathematics, when I declare that f(x) = x + 1, I am not describing a process. I am describing a relationship. Given a value of x, the value of the function f will be x + 1. There is no “computing” this value so to speak. The function f simply maps a value from one number space to a different number space.

    Now, we can certainly simulate this on a computer by creating a “function” f that receives a numeric input and returns a numeric output that is one more than the input. The “function” itself can then be used in the same fashion as a mathematical function. As long as we don’t expose the behind-the-scenes implementation, it will behave almost identical to a mathematical function.

    One of the big problems, though, is that in mathematics the functions are mapping across number spaces. These number spaces can be conceptualized as imaginary viewers. Viewer 1, sitting in “normal” number space views the value of some point labeled x at position 1. Viewer 2, sitting in the “f” number space views the same value of some point labeled x at position 2. The important part is that the point is just a single point, looked at by two viewers.

    In programming, a language that applies this concept would treat variables and functions such that one could do the following.

    f = lambda x: x + 1
    a = value(1)
    b = a: f(a)
    print(a) => 1
    print(b) => 2

    a becomes a value in normal number space, and b becomes a reference to a, such that the “getter” always returns a + 1. This gets us a little closer to a simulating a functional paradigm. That said, a formal functional “program” would be nothing more than a series of transformation of data to the desired number space, or more generically the desired view-space since we don’t necessarily have to be talking about a number space.

    One critical distinction to be a “purely functional” program, though, is that the state/data of said program never changes. We could not, for instance, do either of the following assuming we’ve already written the above code:

    a = a + 1
    a = value(2)

    In either case we change the state of a, and have thus violated the functional paradigm. If you give yourself the thought exercise, you might also conclude that there are a number of other computationally common activities that violate the paradigm, too. Input (user or system) technically violates the paradigm too. It boils down to such programs, and hence the languages that define them, would be limited to closed systems that only ever do the exact same thing every time they are invoked.

    The bottom line is that computers by their very nature operate in an imperative paradigm at the hardware/assembly level. At best we can only come close to simulating a functional paradigm on top of imperative implementations. In lieu of the limited capabilities of a purely functional paradigm, practicality dictates that most “functional” languages will be fundamentally imperative with some degree of functional paradigm restrictions implemented on top. To suggest anything different is misleading.

  • Michael Sloan

    I think that the distinction is pedantry – functional languages are valuable because they enable functional style – so there’s no reason to hold everyone to the standard of being careful about the distinction.

    You do bring up a very good point, though. Haskell, in particular has a very “fix the world” attitude, and doesn’t make using it very possible to use it in ignorance of functional style. The learning curve is very steep, especially if you expect it to be similar to any (non-functional) language you knew before.

    An interesting way to fix this problem might be to write a DSL / language that desugars to Haskell, and looks like some popular imperative language. Python, for example, with some libraries that re-implement some of the standard functions in terms of Haskell libraries. Even better would be if this de-sugaring process worked in a series of steps, where the user can write code that targets each stage, and each getting more Haskell-ey, to ease the user into it.

    Most Haskellers will dislike this approach for its impurity and the influx of people writing extraordinarily non-idiomatic code, but it really would help the overall avoidance of success at all costs thing.

  • Erik E

    Well spoken Dave. If we were trained to think functional from the very start, perhaps programming purely in a functional style would work. For me though having programmed in imperative style for so long it is not worth going functional all the way. I use functional style a lot more now than before. I love closures, and higher order functions. But I still prefer looping most of the time over recursion. Recursion makes sense for traversing lists and trees though.

    If you are into graphics and game development like me then avoiding state changes does not make sense either. E.g. I think it is fine to manipulate the data in a buffer you get passed to a function. But you should avoid changing things that the user of your function did not see go into the function through arguments.

    Haskell is probably great for bright people. But I doubt a language like that could ever go mainstream. It is just to difficult to grasp for your average Joe programmer. Having said that, though I am not all cynical. I think in principle everybody could write in LISP or Scheme. That it isn’t so, I think is more about historical conicidences than about issues with the language itself.

  • Timothy Pratley

    Sequence operators are a huge win. Loops are something everyone understands well. But each loop is different. You have to understand each loop individually as you encounter it to figure out what it does. Sequential operators give you a bunch of abstract loops. “Map” is a loop that uses each element to calculate something new. “Reduce” is a loop that accumulates a result. “Take” is a loop that terminates early. “Filter” is a loop that only calculates when a predicate is met… and so on. Functional languages often have dozens of abstractions to help with sequential calculation. This gives you as a programmer a bigger vocabulary. Yes you have to know more abstractions. But with a bigger vocabulary you don’t have to write a new loop for every sequential problem you encounter. This is a much more robust and reliable approach once you learn the vocabulary. Take LINQ for example… it provides exactly this sequential vocabulary to C#. Now you can write very clear operations without making mistakes like forgetting to increment a counter.

    I encourage you to accept the challenge of thinking about sequential operations as transformations because doing so avoids errors and is more concise. It isn’t a question of style, but vocabulary :)

  • Timothy Pratley

    ;; easier if you know what ‘reduce’ means
    (defn sum [list]
    (reduce + list))

    ;; easier if you don’t, but more moving parts
    int sum([int] list):
    result = 0
    for i in list:
    result = result + i
    return result

  • Looking at the first and the second function in the post, I realize that both of them are ugly. If you want true functional programming, then take a look at this example (on LISP):

    (reduce #’+ ‘(1 2 3 4 5))

    Which returns 15. Now that’s an excellent language that maybe the world is still not ready for.

  • Splinter of Chaos

    I think the wording of the wiki article is very interesting.

    “avoids state and mutable data.”

    There is a big difference between avoiding and disallowing. The section, “Comparison to imperitive programming” makes the difference more clear.

    “Functional programming is very different from imperative programming. The most significant differences stem from the fact that functional programming avoids side effects, which are used in imperative programming to implement state and I/O. Pure functional programming disallows side effects completely and so provides referential transparency, which makes it easier to verify, optimize, and parallelize programs, and easier to write automated tools to perform those tasks.”

    Functional languages avoid state. Pure languages disallow it. This makes me think that “functional style” isn’t a sufficient term. How aboud “pure style” or “functionally pure”?

    Erik E: “If you are into graphics and game development like me then avoiding state changes does not make sense either… Haskell is probably great for bright people. But… It is just to difficult to grasp for your average Joe programmer.”

    Some people think more concretely, and others think more abstractly. Some think randomly, some sequentially. Some people will find Haskell easier and some will find C++ easier, regardless of intelligence. Though, if you go through a Haskell-OpenGL tutorial, you’ll see there IS state changing (IORef, for one), it’s just a real pain to use.

    The problem I have with Haskell is not that it’s for bright people, or that it avoids state, but that it’s a single-paradigm language–the only one I have ever used. Most languages let you choose what paradigm to use at any one time, for any one problem or sub-problem. Those concerned too much with purity would seem to forget every idea in computer science outside of their clique.

  • Jonathan Fischoff

    Focusing on value semantics is a better way to explain Haskell I think because symbols can be rebound, which is surprising when purity is defined as a variable can’t change it’s value.

    I think the best and much more advanced way to understand Haskell is by meditating on non strict system F omega. This is a major difference between Haskell and almost another programming language. Haskell can be (almost) desugared to a formal logical system.

Leave a Reply

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>