What defines a functional programming language?

Posted: August 27, 2012 in Uncategorized
Tags: ,

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

About these ads
Comments
  1. Joe Vijay says:

    I always thought your “Right Definition” combined with the four flawed definitions (mentioned in your article) were qualities of a Functional programming language. Thanks for clearing that up.

  2. Hugo Estrada says:

    Great article. Having clear definitions is a necessary component to understand an programming paradigm. It doesn’t matter if they change with time. Each definition at a certain point in time is like a flagpost that let us know where we were and what lies ahead.

    This is something that I find lacking and frustrating with OOP. Just getting a clear definition of what exactly OOP is is a hard exercise, and one ends up having to guess what it is supposed to be. I rather have previously bad definitions than none at all, which is close to what the situation is today.

  3. “Functional programming” is like “object-oriented programming”: it usually refers not to a single concept but to a social movement which espouses several unrelated concepts. One is high-order functions (your definitions 1-3); another is functions that return results; a third is the elimination of state (your definition 4). Trying to define functional programming in terms of its single root concept doesn’t work, because there isn’t one. This is often confusing.

    • mikera7 says:

      Good point – and I totally agree that functional programming (like other programming paradigms) is a complex idea that includes human factors and multiple underlying concepts. I just think that this is still compatible with having a good clear definition – it just means that your definition is going to be a little more “fuzzy” than rather than a strict rule, and that the boundaries might move a little over time as human understanding develops. I think it is analogous to how historians / political scientists are able to usefully define terms like “liberalism”.

      I like the linked article by the way, but see its conclusion as supporting my viewpoint – i.e. having a good definition is important and worth doing if you intend to have meaningful discussions around a topic.

  4. Phil says:

    This is a nice and clear article, and I agree with the definitions provided. However, given that there’s so much debate and confusion surrounding the term “functional programming language”, I’m inclined to simply avoid it entirely if possible. I would argue that “functional” is a property of programs rather than languages.

    It may be more helpful to think solely in terms of levels of support for writing functional programs: 0) functional programs are possible to write, if awkwardly, (CL, Ruby, JS) 1) functional programs are encouraged and idiomatic, (OCaml, Clojure) and 2) functional programs are required. (Haskell, Coq)

  5. Johan Tibell says:

    > By exploiting lazy evaluation, the program effectively defines a sequence of sequentially dependent IO interactions that can be executed by the runtime.

    I’m not sure what to make of this. Operationally it’s definitely not the case that the program generates a (lazy) sequence of actions that’s later interpreted.

    You also don’t write programs as-if that was the case. The imperative parts of Haskell programs are written just like the imperative parts of e.g. Java and have the same semantics with respect to side effects (i.e. they are hard to reason about in both languages).

    > 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.

    Monads actually allow us to talk about state an external interactions in our programs in a more principled way. The easy way out is to not have a notion for side effects in your language. This is what ML did and what Haskell explicitly avoided.

    The whole point of this exercise is that we want to reason in terms of pure functions as much as possible. That gets harder if you don’t know whether a function is pure or not. Not having a type system for keeping pure and impure functions separate puts the responsibility on the programmer.

    Checking whether a function is pure or not requires non-local reasoning (i.e. you might have to check every function you call, every function it calls, etc.) The whole point with functional programming was to avoid this non-local reasoning.

    • mikera7 says:

      Hi Johan,

      I’m sure from your answer that your knowledge of Haskell is better than mine. :-)

      Regarding the IO monad, I’m going off my understanding which mirrors the description in the Wikipedia entry at http://en.wikipedia.org/wiki/Monad_(functional_programming)#The_I.2FO_monad

      “In a purely functional language, such as Haskell, functions cannot have any externally visible side effects. Although a function cannot directly cause a side effect, it can construct a value describing a desired side effect, that the caller should apply at a convenient time.”

      That’s what I mean by “effectively defines a sequence of sequentially dependent IO interactions that can be executed by the runtime”. My point is that the Haskell program itself is still a pure function, and it is the responsibility of the runtime to actually execute the IO interaction(s) that the program defines. Maybe I can find a way to express this more clearly (I always find writing about Monads tricky!)

      • Johan Tibell says:

        Hi,

        Unfortunately the description you link to isn’t a very good one (which is of course not your fault). While you could look at the IO monad that way, it’s not a very useful. Every function is pure if you consider its input and output the whole world (which is the semantic trick people who claim IO actions are pure in Haskell is). The problem is of course that its hard for us to reason about functions that take the whole world as input and output and this is indeed what non-pure functions do (i.e. they could potentially access or change anything in the world). Actions in the Haskell IO monad are no easier to reason about that say Java functions.

        Here’s the rub, since side effecting things in functional language are no easier to reason about side effecting thing elsewhere, we don’t want them to infect our whole program, making the whole thing hard to reason about. This is what the (Haskell) type system helps us do. It says: over here are the pure functions, you can reason about them using these rules, and over here we have the impure “functions”, be careful when you reason about those, as that’s much harder.

        Without this distinction you must always assume that any function might have a side effect.

        That being said, having a culture that prefers pure functions will help you avoid bugs due to side effects, but it’s not the same as eliminating them by construction.

  6. [...] What defines a functional programming language?. Article très sympa à lire qui cherche à définir l'essence d'un langage fonctionnel. Après avoir éliminé les définitions classiques (présence de fonctions de première classe, lambdas, …), la définition retenue (que j'apprécie) est : A functional programming language is a language that emphasises programming with pure functions and immutable data. [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s