Truly understanding the difference between procedural and functional

I'm really having a hard time understanding the difference between procedural and functional programming paradigms.

Here are the first two paragraphs from the Wikipedia entry 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. It > emphasizes the application of > functions, in contrast to the > imperative programming style, which > emphasizes changes in state. > Functional programming has its roots > in lambda calculus, a formal system > developed in the 1930s to investigate > function definition, function > application, and recursion. Many > functional programming languages can > be viewed as elaborations on the > lambda calculus. > > 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, > changing the value of program state. > Because of this they lack referential > transparency, i.e. the same language > expression can result in different > values at different times depending on > the state of the executing program. > Conversely, in functional code, the > output value of a function depends > only on the arguments that are input > to the function, so calling a function > f twice with the same value for an > argument x will produce the same > result f(x) both times. Eliminating > side effects can make it much easier > to understand and predict the behavior > of a program, which is one of the key > motivations for the development of > functional programming.

In paragraph 2 where it says

> Conversely, in functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function f twice with the same value for an argument x will produce the same result f(x) both times.

Isn't that the same exact case for procedural programming?

What should one look for in procedural vs functional that stand out?

Functional Programming

Functional programming refers to the ability to treat functions as values.

Let's consider an analogy with "regular" values. We can take two integer values and combine them using the + operator to obtain a new integer. Or we can multiply an integer by a floating point number to get a floating point number.

In functional programming, we can combine two function values to produce a new function value using operators like compose or lift. Or we can combine a function value and a data value to produce a new data value using operators like map or fold.

Note that many languages have functional programming capabilities -- even languages that are not usually thought of as functional languages. Even Grandfather FORTRAN supported function values, although it did not offer much in the way of function-combining operators. For a language to be called "functional", it needs to embrace functional programming capabilities in a big way.

Procedural Programming

Procedural programming refers to the ability to encapsulate a common sequence of instructions into a procedure so that those instructions can be invoked from many places without resorting to copy-and-paste. As procedures were a very early development in programming, the capability is almost invariably linked with the style of programming demanded by machine- or assembly-language programming: a style that emphasizes the notion of storage locations and instructions that move data between those locations.

Contrast

The two styles are not really opposites -- they are just different from one another. There are languages that fully embrace both styles (LISP, for example). The following scenario may give a sense of some differences in the two styles. Let's write some code for a nonsense requirement where we want to determine if all of the words in a list have an odd number of characters. First, procedural style:

function allOdd(words) {
  var result = true;
  for (var i = 0; i < length(words); ++i) {
    var len = length(words[i]);
    if (!odd(len)) {
      result = false;
      break;
    }
  }
  return result;
}

I'll take it as a given that this example is comprehensible. Now, functional style:

function allOdd(words) {
  return apply(and, map(compose(odd, length), words));
}

Working from the inside out, this definition does the following things:

1. compose(odd, length) combines the odd and length functions to produce a new function that determines whether the length of a string is odd.
2. map(..., words) calls that new function for each element in words, ultimately returning a new list of boolean values, each indicating whether the corresponding word has an odd number of characters.
3. apply(and, ...) applies the "and" operator to the resulting list, and-ing all of the booleans together to yield the final result.

You can see from these examples that procedural programming is very concerned with moving values around in variables and explicitly describing the operations needed to produce the final result. In contrast, the functional style emphasizes the combination of functions required to transform the initial input to the final output.

The example also shows the typical relative sizes of procedural versus functional code. Furthermore, it demonstrates that the performance characteristics of procedural code might be easier to see than that of functional code. Consider: do the functions compute the lengths of all of the words in the list, or does each stop immediately after finding the first even length word? On the other hand, the functional code permits a high-quality implementation to perform some pretty serious optimization since it primarily expresses intent rather than an explicit algorithm.

Further Reading

This question comes up a lot... see, for example:

• What is the difference between procedural programming and functional programming?
• Can someone give me examples of functional programming vs imperative/procedural programming?
• OOP vs Functional Programming vs Procedural

John Backus' Turing award lecture spells out the motivations for functional programming in great detail:

Can Programming Be Liberated from the von Neumann Style?

I really shouldn't mention that paper in the present context because it gets pretty technical, pretty quickly. I just couldn't resist because I think it is truly foundational.

---

Addendum - 2013

Commentators point out that popular contemporary languages offer other styles of programming over and above procedural and functional. Such languages often offer one or more of the following programming styles:

• query (e.g. list comprehensions, language-integrated query)
• dataflow (e.g. implicit iteration, bulk operations)
• object-oriented (e.g. encapsulated data and methods)
• language-oriented (e.g. application-specific syntax, macros)

See the comments below for examples of how the pseudo-code examples in this response can benefit from some of the facilities available from those other styles. In particular, the procedural example will benefit from the application of virtually any higher-level construct.

The exhibited examples deliberately avoid mixing in these other programming styles in order to emphasize the distinction between the two styles under discussion.

The real difference between functional and imperative programming is the mindset - imperative programmers are thinking of variables and blocks of memory, whereas functional programmers are thinking, "How can I transform my input data into my output data" - your "program" is the pipeline and set of transforms on the data to take it from the Input to the Output. That's the interesting part IMO, not the "Thou shalt not use variables" bit.

As a consequence of this mindset, FP programs typically describe what will happen, instead of the specific mechanism of how it will happen - this is powerful because if we can clearly state what "Select" and "Where" and "Aggregate" means, we are free to swap out their implementations, just like we do with AsParallel() and suddenly our single-threaded app scales out to n cores.

     Isn't that the same exact case for procedural programming?

No, because procedural code can have side-effects. For example, it can store state between calls.

That said, it is possible to write code that satisfies this constraint in languages considered procedural. And it is also possible to write code that breaks this constraint in some languages considered functional.

I disagree with WReach's answer. Let's deconstruct his answer a bit to see where the disagreement comes from.

First, his code:

function allOdd(words) {
  var result = true;
  for (var i = 0; i < length(words); ++i) {
    var len = length(words[i]);
    if (!odd(len)) {
      result = false;
      break;
    }
  }
  return result;
}

and

function allOdd(words) {
  return apply(and, map(compose(odd, length), words));
}

The first thing to note is that he is conflating:

• Functional
• Expression oriented and
• Iterator centric

programming, and missing the ability for iterative style programming to have more explicit control flow than a typical functional style.

Let's quickly talk about these.

Expression-centric style is one where things, as much as possible, evaluate to things. Although functional languages are famed for their love of expressions, it's actually possible to have a functional language without composable expressions. I'm going to make one up, where there are no expressions, merely statements.

lengths: map words length
each_odd: map lengths odd
all_odd: reduce each_odd and

This is pretty much the same as given before, except functions are chained purely through chains of statements and bindings.

An iterator centric programming style might be one taken by Python. Let's use a purely iterative, iterator-centric style:

def all_odd(words):
    lengths = (len(word) for word in words)
    each_odd = (odd(length) for length in lengths)
    return all(each_odd)

This is not functional, because each clause is an iterative process, and they are bound together by explicit pause and resumption of the stack frames. The syntax may be inspired partially from a functional language, but it is applied to a completely iterative embodiment of it.

Of course, you can compress this:

def all_odd(words):
    return all(odd(len(word)) for word in words)

Imperative doesn't look so bad now, eh? :)

The final point was about more explicit control flow. Let's rewrite the original code to make use of this:

function allOdd(words) {
    for (var i = 0; i < length(words); ++i) {
        if (!odd(length(words[i]))) {
            return false;
        }
    }
    return true;
}

Using iterators you can have:

function allOdd(words) {
    for (word : words) { if (!odd(length(word))) { return false; } }
    return true;
}

---

So what is the point of a functional language if the difference is between:

return all(odd(len(word)) for word in words)

return apply(and, map(compose(odd, length), words))

for (word : words) { if (!odd(length(word))) { return false; } }
return true;

The main definitive feature of a functional programming language is that it removes mutation as part of the typical programming model. People often take this to mean that a functional programming language does not have statements or uses expressions, but these are simplifications. A functional language replaces explicit computation with a declaration of behaviour, which the language then performs a reduction on.

Restricting yourself to this subset of functionality allows you to have more guarantees about your programs' behaviours, and this allows you to compose them more freely.

When you have a functional language, making new functions is generally as simple as composing closely-related functions.

all = partial(apply, and)

This is not simple, or perhaps even not possible, if you haven't explicitly controlled global dependencies of a function. The best feature of functional programming is that you can consistently create more generic abstractions and trust that they can be combined into a greater whole.

In procedural paradigm (shall I say "structured programming" instead?), you have shared mutable memory and instructions which read/write it in some sequence (one after the other).

In functional paradigm, you have variables and functions (in the mathematical sense: variables do not vary over time, functions can only compute something based on their inputs).

(This is oversimplified, e.g., FPLs typically have facilities for working with mutable memory whereas procedural languages can often support higher-order procedures so things are not as clear-cut; but this should give you an idea)

The Charming Python: Functional programming in Python from IBM Developerworks really helped me to understand the difference.

Especially for someone who knows Python a bit, the code examples in this article in which doing different things functionally and procedurally are contrasted, can clarify the difference between procedural and functional programming.

In functional programming in order to reason about the meaning of a symbol (variable or function name) you only really need to know 2 things -- current scope and the name of the symbol. If you have a purely functional language with immutability both of these are "static" (sorry for badly overloaded name) concepts, meaning you can see both -- the current scope and the name -- just by looking at the source code.

In procedural programming if you want to answer the question what's the value behind x you also need to know how you got there, the scope and name alone are not enough. And this is what I would see as the biggest challenge because this execution path is a "runtime" property and can depend on so many different things, that most people learn to just debug it and not to try and recover the execution path.

I've recently been thinking of the difference in terms of the Expression Problem. Phil Wadler's description is oft-cited, but the accepted answer to this question is probably easier to follow. Basically, it seems that imperative languages tend to choose one approach to the problem, while functional languages tend to choose the other.

One clear difference between the two programming paradigms is state.

In Functional Programming, state is avoided. Simply put, there will be no variable that is assigned a value.

Example:

def double(x):
    return x * 2

def doubleLst(lst):
    return list(map(double, action))

However, Procedural Programming uses state.

Example:

def doubleLst(lst):
    for i in range(len(lst)):
        lst[i] = lst[i] * 2  # assigning of value i.e. mutation of state
    return lst