10
$\begingroup$

StackOverflow pointed me here, so the question might be a bit in a layman's terms.

Wikipedia defines pure functions as

In computer programming, a function may be described as a pure function if both these statements about the function hold:

  1. The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change as program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices.
  2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

However it does not seem to cite any sources -- so it is hard to say whether this is an accepted definition, or who defined it this way.

When I look at what the languages do when they include a syntax/annotation for "pure" functions, there are quite a few different approaches:

  1. In D the only limitation is non-mutation of global state. "Pure" functions can mutate its arguments.
  2. In GCC there are two types of "pure": pure (no side-effects, but can read global state) and const (stricly pure as per wikipedia definition).
  3. In C#, it is defined as "does not make any visible state changes" (whatever that is).
  4. Haskell follows the Wikipedia definition.

So my question is: is there a canonical definition of pure function?
And if there is, what is its source?

Improve this question
$\endgroup$
2
  • $\begingroup$ Related historical perspective, though no one seems to give any definite or sourced answers. $\endgroup$
    – Guildenstern
    Commented May 5, 2014 at 9:51
  • 1
    $\begingroup$ This isn't worth an answer but here is my definition: if x = y (by it's definition) then f x = f y is true and f causes no externally measurable change in state (i.e. all change in state is internal to x, y, and f). Haskell takes advantage of this. It implements lazy evaluation by mutating thunks and replacing them with functions that return the result immediately. That is if you evaluate (f x) it may actually change f and x under the hood but you can't ever tell. $\endgroup$
    – Jake
    Commented Jul 2, 2014 at 16:07

2 Answers 2

Reset to default
4
$\begingroup$

As noted in this paper Imperative Functional Programming, (1993) by Peyton-Jones and Wadler (among the group of researchers that created Haskell):

We focus on purely-functional solutions, which rule out side effects, for two reasons. Firstly, the absence of side effects permits unrestricted use of equational reasoning and program transformation...

the focus is on absence of side-effects to enable program transformations (i.e compiler optimisations).

What are side-effects? This paper in turn points to Integrating functional and imperative programming (1986) by Gifford and Lucassen, which mentions four types of effect classes: Pure, Function, Observer and Procedure. So, the term "pure function" derives from this paper.

  • a PURE is referentially transparent: it does not cause side-effects, its value is not affected by side-effects, and it returns the same value each time it is evaluated.

Note, however, that Peyton-Jones and Wadler mentioned shortcomings in this approach. Worth noticing, they say, is the programming language Clean that uses linear types to introduce side-effects in a safe manner (i.e. safe for the compiler). Basically, it threads the World as a variable in all I/O related functions, including the main entry point.

With that, it is possible to have a pure functional language interacting with the world and having side-effects (I/O, the OS, the Windowing system, etc), contradicting partially your wikipedia definition. One can in fact say that Haskell has Clean as one of its influencers; although it departs from linear types and uses another type-level construct (monads) to guarantee linearity, i.e. a single-reference at all times.

Improve this answer
$\endgroup$
5
  • $\begingroup$ "Basically, it threads the World as a variable ...". Do you actually mean "threads". Is there an informal account of this on the web? $\endgroup$
    – babou
    Commented Jul 2, 2014 at 21:58
  • $\begingroup$ I used "threading" as a metaphor. It means, you have to pass the World variable from one function to another. And linear typing means that such World variable is not used more than once. It implies, for example that to open a file inside a function you would do like (f_handle, world2) = fopen file_name, world (pseudocode) and a next call will have to use world2. In essence programs are seen as operating on the the Universe as a whole. Put other way, there are no side effects when you are operating on the Universe :-) $\endgroup$
    – carlosayam
    Commented Jul 2, 2014 at 23:51
  • $\begingroup$ Threading the World, as you say, seems to be the standard way (as I recall) to deal with the environment in denotational semantics. So the key point must be linearity. But then, denotational semantics (DS) is supposed to be purely functional, without any linearity constraint. I guess DS is a mathematical abstraction and has no qualms about juggling many Worlds. Computing is physical, and linearity allows for world evolution, but only one World can exists at one time (which probably sequentialises evaluation). What is the semantics of 2 Clean programs run concurrently :-)? $\endgroup$
    – babou
    Commented Jul 3, 2014 at 10:45
  • $\begingroup$ Is the Gifford and Lucassen paper accessible on the web? $\endgroup$
    – babou
    Commented Jul 3, 2014 at 21:38
  • $\begingroup$ I got access through the Uni. $\endgroup$
    – carlosayam
    Commented Jul 4, 2014 at 4:43
-1
$\begingroup$

Wikipedia's definition is canonical. The crucial two requirements are:

  • The return value and behavior of the function is a deterministic function of the arguments that were explicitly passed to the function.

  • An invocation of the function has no observable side effects.

Strictly speaking, D and gcc shouldn't be using the word "pure" the way they do; it's an abuse of standard terminology.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.