The Day Functional Programming Became Pure

The definition of "functional programming" changed slowly over the last 20 years, as expressed on the Wikipedia page on Functional Programming. Perhaps the process started even earlier with John Backus's famous Turing Award lecture Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs. [Note, I have revised this to put the quotations in chronological order and add a new paragraph on the end]

Before 14 August 2003, the page described functional programming as a style that emphasized the use of functions. For example on 14 October 2001‎ the entire page was 220 words long, and began:
Functional programming is a style of programming that emphasizes the evaluation of functional expressions, rather than execution of commands. The expressions in these languages are formed by using functions to combine basic values.  
A functional programming language is a language that supports and encourages functional programming. The oldest example is LISP. More recent examples include Scheme, ML, Haskell, Erlang, Clean.
Lisp is identified as the first functional language, and Schema, ML and Haskell are on equal footing.

The changes started on On 14 August 2003 when the pages from Nupedia, which had a structured and peer reviewed model for content production, were integrated into Wikipedia by Luxor to create a page with 1,640 words:
Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. In contrast to imperative programming, functional programming emphasizes the evaluation of functional expressions, rather than execution of commands. The expressions in these languages are formed by using functions to combine basic values.  

At this point functional programming is not about emphasizing use of functions. Instead it means programming with mathematical functions. Implicit in this definition is that such functions are pure, but because it is not explicit the implications were not clear. This description was elaborated until 29 May 2006, when the page read:
Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. Functional programming emphasizes the definition of functions rather than the implementation of state machines, in contrast to procedural programming, which emphasizes the execution of sequential commands. A purely functional program does not modify state to produce values (as is done in imperative programming), it constructs new values from (but does not overwrite) existing values. 
There is no uniform agreement on what constitutes functional programming or a functional programming language. Often considered important are higher-order and first-class functions, closures, and recursion. Other common features of functional programming languages are continuations, Hindley-Milner type inference systems, non-strict evaluation (i.e. "laziness"), and monads.
There is still a distinction between (ordinary) functional programming and the "pure" form of functional programming, which avoids the use of mutable state. At this point there was a small but significant change, in the middle of the night, with no fanfare, by an unknown person. At 01:07 on 29 May 2006 it was changed to read:
Functional programming is a programming style that treats computation as the evaluation of mathematical functions and avoids state and mutable data. Functional programming emphasizes the definition of functions, in contrast to procedural programming, which emphasizes the execution of sequential commands. 
Functional programming relies on concepts from the lambda calculus, Lisp, and more recently Haskell. Frequently mentioned are the avoidance of state and side-effects (which provides for referential transparency), higher order functions, recursion, and closures. 
At a stroke, the author made explicit the requirement for purity and added it to the definition of functional programming. This requirement had been implicit in the description of functional programming, as computation with mathematical functions. This author also resolved the uncertainty about how functional programming should be defined. Prior pages said there is no agreement, but the new definition was stated without such doubts.

The change was made by ideogram, whose real-world identity is not disclosed. This account was created a few days before the active editing of the Functional Programming page started. Since then the account has been banned numerous times for unacceptable behavior (trolling) but this seems to be urelated to the editing of the Functional Programming page.

They didn't leave a revision comment. On the other hand, there is some discussion about the issues on the Functional Programming Talk page. There have been edits since this point, which have restored some of the previous language, but they are later removed. Currently (July 14, 2012) the page reads:
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.[1] 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.[1] 
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.
[1] Paul Hudak. 1989. Conception, evolution, and application of functional programming languages. ACM Computing Surveys volume 21, issue 3 (September 1989).
What are the implications of this? How did this change come about? Are we in the midst of a (small) scientific revolution? Who is behind this?


According to the new definition ML and Lisp are no longer functional languages. It is possible to write some some in a functional subset of these languages. The first requirement is avoiding the use of "ref" types in ML, or the use of assignment and structural mutation in Lisp languages. However, this is not enough, because many of the standard libraries for ML and Lisp languages have side-effects. This is especially true of any libraries for IO. As a result, the range of program that can be conveniently written in a functional style is fairly limited.

11 comments:

Anonymous said...

Who really cares what Wikipedia has to say? It's just a bunch of random, unattributed, uncurated prose. Some of it is right, some of it is wrong. Even elementary school teachers don't consider it authoritative.

William R Cook said...

I see Wikipedia as a reflection of the community. It is not the authoritative answer, but it is a sign of what the community thinks. Especially for a page like this, which is widely debated and read.

Rob said...

Beyond generally agreeing with Anonymous ("the community"? what community?) I think you're reading the phrase "and avoids state and mutable data" pretty narrowly. Functional programming does avoid the use of state and mutable data, which is not to say that it excludes it.

Furthermore, the definition is about state and not effects. This definition leaves open the possibility that it's possible to program non-functionally in a "purely functional" language that provides a monadic interface to state and mutable data.

William R Cook said...

I prefer to read the phrase "treats computation as the evaluation of mathematical functions" literally. Once you say that, the definition is clear, and must exclude implicit side effects. The rest of the definition goes on to clarify this, especially in the last (current) version. If you look up the meaning of "avoids" it is fairly strong. Of course monadic interfaces are perfectly acceptable in a functional program, because the program computes a "command" value which is then executed by the top-level runtime to perform the desired effects.

Given this definition, and the standard libraries for ML and Scheme, I would say that these languages do not support functional programming.

You seem to be suggesting that "functional" is a spectrum, so that you can discuss the degree of functional programming in a given program. This is the degree to which side effects are avoided. How could we have precise criteria to measure this quantity? Even worse, how could we measure the degree to which a language is functional? I prefer a precise, binary definition.

The old definition was also precise and binary. If the language supported first-class functions and used higher-order functions, then it was functional. Smalltalk 80 has first-class functions, and it's libraries have widely used, robust notions of map and fold. Other derivative languages (including Java) have or are adding such features. According to the old definition, wouldn't Smalltalk be a functional language? I think the old definition of "functional programming" has lost its relevance, as all languages now satisfy it. At this point PHP is functional. Given this, and other reasons, we are now seeing "functional" used mean "pure functional".

Some people might say that functional programming also requires algebraic data types and pattern matching. However, this seems completely orthogonal issue of data abstraction, not related to the computational model.

Sukant Hajra said...

For what it's worth, I prefer the new definition of FP. In a world where all languages are getting first-class support for functions, the former definition lacks utility. Retooling the definition to meet modern times is appropriate (as with OO).

Regardless of wikipedia's authority or non-authority on the matter, it's true from my perspective all-the-same. The old voices like Paul Graham are being overshadowed by ones coming from more pure camps (and I don't mind it).

rpg said...

aIn my view, the phrase "treats computation as the evaluation of mathematical functions" is nonsense. Mathematical functions exist in the realm of ideas, and all we can do regarding them is think about them / prove statements about them. Whoever wrote this gubbish clearly intends it as shorthand for a complex statement about mapping / representation etc.

Tony Morris said...

The definition of functional programming has never changed. It had always been about programming with functions. There is no such thing as "a function with side-effects." The amount of academic literature supporting this over many decades is overwhelming. You really should check some of it out.

Nobody cares if someone wrote some garbled nonsense on wikipedia once or twice. It is unpersuasive.

Rob said...

I'm fine with searching for precise definitions (though I suspect it's a hopeless exercise in the end). The definition means that large swaths of ML or Scheme programs can be functional, but the whole program rarely is. (So I guess I'm talking about parts of a program being functional, not about a program being on a functional spectrum.)

I don't really understand the line you draw from "this is a style of programming" and "looking at the standard libraries and deciding whether this is a language that supports this style of programming." That's the part of your argument that seems restrictive and needlessly controversial (not to mention that, in the case of Standard ML, it's possible to write a version of the standard library that uses an IO monad to encapsulate all effects). As an understanding/consistency check, is it accurate to say that Java doesn't support object-oriented programming because the standard libraries treat many classes as final? Unless I'm mistaken, this interferes with their ability to used polymorphically (for the object-oriented variant of the word "polymorphic," obviously).

William R Cook said...

Rob, I see now that it is better to talk about parts of a program being functional, rather than trying to define a spectrum. This approach works well for programs, and it can also be applied to languages. Thus we can say "the standard libraries in Scheme and ML are not functional". This is also true of Smalltalk, which includes a functional subset but whose standard libraries are imperative.

The reason "object-oriented" and "functional" are different is that the first is defined by what it supports while the other is defined by what it avoids. As a result, an object-oriented program/language can include techniques that are not object-oriented. On the other hand, a functional program/language cannot must avoid mutable state everywhere.

Paul Hudak discussed this in his excellent introduction to Conception, Evolution, and Application of Functional Programming:

"This discussion suggests that what is important is the functional programming style, in which the above features are manifest and in which side effects are strongly discouraged but not necessarily eliminated. This is the viewpoint taken, for example, by the ML community and to some extent the Scheme community. On the other hand, there is a very large contingency of purists in the functional programming community who believe that purely functional languages are not only sufficient for general computing needs but are also better because of their “purity”. "

Sukant Hajra said...

This idea of definition by constraint is interesting to me. Roy Fielding's PhD thesis on REST got me thinking about this when he went through his enumeration of various distributed architectures. His entire taxonomy was defined by constraints. In fact, the "null" architecture by his terms is a system with no constraints.

Although Fielding's taxonomy is a bit rough and inexact, this idea that true architectures are really just a system of constraints resonates very strongly with me. Constraints lead to strong system invariants, which our software solutions are in dire need of. By pursuing software more as a process of construction than constraint, we often end up with the integration of a lot of little systems that as a whole don't do any one thing very well. Our production systems are frighteningly "null" architected.

The phrase "functional style" is somewhat ubiquitous now, but in its purer form it's a lot more than style. I try to say "functional architecture" instead, although it's not as idiomatically graceful. Referential transparency as a constraint leads to very powerful and pragmatic system invariants.

So when it comes to cleaning up the definition of OO, I'd frankly prefer if it were defined through constraint.

Shredder said...

You hit the point I wanted to make. This is another reason I don't like Haskell. It's based on a flawed world-view.

You can write pure functions in C and assembly too. Actually pure functions in C are more "pure" than Haskell.

You may like my post:

http://yinwang0.wordpress.com/2013/03/31/purely-functional