What defines a functional programming language?

I see this question debated hotly in various forums, so I thought that it was worth addressing. Mostly in the name of dispelling some myths, but also to highlight what I feel are the most crucial foundations of functional programming.

And also because I think that definitions are important. They are central to both how we think and how we communicate.

Before giving what I believe is the correct definition, I’d like to highlight some flaws in alternative definitions that I commonly see used:

Flawed Definition 1: A functional programming language is a language which enables programming in a functional style with higher order functions

Any Turing complete language can be made to support a “functional style with higher order functions”, if only by emulating a language with higher order functions. It reminds me of Greenspun’s Tenth Rule:

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

I have personally seen this effect in some particularly over-engineered “enterprise” projects: after piling on several layers of abstraction, business rule definitions and XML-based mini-languages you are probably getting suspiciously close to Turing completeness….

Needless to say this is a pretty unhelpful definition. We already know you can emulate anything you like in a Turing complete programming language. We are interested in finding a definition that helps us categorise and understand programming languages, not in making an academic point about computability theory.

Flawed Definition 2: A functional programming language is a language with first class functions

The idea here is that functional programming language depends on being able to pass functions as parameters to other functions – so the functions are “first class” in the sense of being an entity that can be created, manipulated, stored in a variable etc.

The idea of first class functions is certainly an important idea in functional programming. Without first class functions you would be unable to write code like:

(defn double [x] (* 2 x))

(map double [1 2 3 4 5])
=> (2 4 6 8 10)

However – this isn’t a very useful definition overall, mainly because it includes a large proportion of all languages ever created, including many that nobody would seriously define as “functional programming languages”. For example particular, C has first class functions (function pointers).

Even Java can be considered to have first class functions if you allow the use of an Object to represent a function. You can use techniques such as anonymous inner classes, which ultimately can do everything that first class functions can (albeit with a somewhat convoluted syntax).

Last but not least, having first class functions does not guarantee that you will use them in a “functional” way: probably the most common use for function pointers in languages like C is to construct jump tables as a performance optimisation for regular imperative code.

Flawed Definition 3: A functional programming language is a language with lambdas

This is a refinement on the above definition. A lambda operator implies a couple of extra things in addition to first class functions:

• Syntactic support for creating anonymous first class functions via some form of lambda operator expression. Without this then you are back to simulating lambdas (e.g. Java’s used of anonymous inner classes)
• The ability to close over variables in the surrounding scope (i.e. creation of a closure). This is important as it enables the parametrisation of lambdas returned from a higher order function.

Here’s a bit of Clojure code that demonstrates both these concepts:

;; construct an anonymous function, closing over the parameter y
(defn make-adder [y]
  (fn [x] (+ x y)))

;; apply an newly constructed adder to all elements of a collection
(map (make-adder 10) [1 2 3 4 5])
=> (11 12 13 14 15)

It turns out that having first class lambdas provides most of what you need to code in a pretty decent functional programming style – everything else that we associate with functional programming can effectively be built up from lambdas. Indeed there is an entire branch of computer science theory devoted to this topic – Lambda Calculus.

This definition excludes languages like Java (which doesn’t have any special syntax for lambdas – at least until Java 8) and C (since function pointers can’t close over variables in the local environment).

The definition however still includes many other languages, e.g.:

• Ruby and C# which are predominately object-oriented in approach.  Most coding is done with classes and objects that contain mutable state. Although first class/higher order functions are used, it is most likely in a limited way, e.g. providing a concise syntax for applying a function to all elements of a collection.
• Scala and Common Lisp which are best described as “multi-paradigm” (in the sense that they effectively enable a broad range of programming paradigms without strongly favouring any particular paradigm at the language level). Both integrate functional and object-oriented capabilities in quite sophisticated ways, in addition to offering good support for various other paradigms.

What is wrong with defining these as functional programming languages? I think there are two reasons:

Firstly, it is not useful in helping us distinguish between languages. If all it takes is a lambda operator to make a language functional, then our definition will not distinguish between JavaScript and Haskell. Applying the same logic to OOP we would probably have to call Haskell object oriented because it supports bundling data with functions into an “Object”. And taken to its logical extreme,  we would be forced to classify 90% of languages simultaneously as OOP, Functional, Logic-Based, Declarative, Imperative, Structured, Concatenative and Agent-Oriented just because they implement one or more keys features from each paradigm. Then we have gained….. what exactly?

Secondly and most importantly, I believe that  programming paradigms are defined subtractively by what they take away rather than what they add. Uncle Bob Martin gave a great talk in London that covers this topic extensively (while sharing many anecdotes about the history of programming languages).

In some sense – assembler is the ultimate multi-paradigm language as it allows you to do anything that is possible with your machine, and any other paradigm can only offer a subset of what is available in assembler.

The advance that functional programming represents is taking away mutation. Functions are used in the sense of mathematical functions that compute a result but do not have any other side effects, nor do they mutate their inputs. It would be an inconvenient bug in the universe if addition altered the value of zero.

Following this logic, it is not helpful to describe an OOP or multi-paradigm language that encourages mutation as a functional programming language. Even if the language allows a functional style through lambdas, much of the time it will not be used in a functional way. So ultimately this definition is also flawed.

Flawed definition 4: A functional programming language is a language where you program only with pure functions and immutable data (no side effects)

This definition is appealing and actually pretty close to what we want. It builds upon the idea that functional programming is about taking away mutation (since a side effect is either the alteration of some mutable state within the program, or an interaction with the outside world which can be viewed as a mutation of the external environment).

However this definition suffers from being too strict. Most useful programs must be able to effect change in the world – very can be expressed completely as a pure function which takes some input and produces some output and does nothing else.

In order to write code that interacts with the outside world but which is still a pure function, you have no option but to take an approach similar to Haskell. In Haskell the interaction with the outside world is achieved by running the program within a runtime that performs the actions specified by the program via the IO monad. By exploiting lazy evaluation, the program effectively defines a sequence of sequentially dependent IO interactions that can be executed by the runtime. It’s a beautiful and elegant solution that enables programs with side effects to be transformed and expressed as a pure function in a way that is consistent with Haskell’s type system. Ultimately however it dodges the issue of state and external interactions – these problems are just shunted out to the runtime.

There are ways that you can do functional programming that allow mutable state and external interactions, and a long tradition of languages that permit side effects while still emphasizing a style of coding dominated by pure functions. Ocaml and Clojure are two such examples.

So this definition is ultimately too strict. It is a good definition for pure functional programming languages, but we also need to account for impure functional programming languages.

Right definition: A functional programming language is a language that emphasises programming with pure functions and immutable data

This is, I believe, the right definition for a functional programming language (and, I’m pleased to say after a quick check, seems consistent with the current definition in Wikipedia)

It is good because it captures the important aspects of FP:

• The removal of mutability via the focus on pure functions and immutable data
• The importance of functions as the primary programming construct (which by implication must be first class)
• It excludes languages that emphasise other paradigms, even if they have functional features.

At the same time, the definition is sufficiently broad that it allows for both pure and impure functional programming languages, which is a useful sub-division.

Impure languages can provide support for mutability and side effects in various ways, providing that this is controlled in a way that does not contradict the overall emphasis on pure functions and immutable data. A good example of reconciling these things is Clojure’s approach to identity and state as articulated by Rich Hickey.

There is also some flexibility for mutability during construction – this is actually essential as an implementation detail since memory must be mutated in order to construct an immutable object. But it also applies at a higher level – Clojure’s transients for example allow for data structures to be mutable during construction. I rather like the quote:

If a tree falls in the woods, does it make a sound?

If a pure function mutates some local data in order to produce an immutable return value, is that ok?

I think that is OK – the important point is that once the construction is complete, you have an immutable object and it doesn’t affect your ability to go on to use the object in pure functions in a classic functional style.

Conclusion

So that’s it – an emphasis on pure functions and immutable data is my definition for a functional programming language (with an allowance for impurity so that functional languages can implement practically important things like side effects, object construction and mutability in a controlled way)

Of course this is only my opinion: I’m sure this won’t end the debate on the definition of functional programming languages :-)

But I hope it gives some good food for thought!

If you are interested in this topic more generally, I can recommend another excellent keynote presentation video by Rich Hickey – The Value of Values