Are closures considered impure functional style?

Question

Are closures considered impure in functional programming?

It seems one can generally avoid closures by passing values directly to a function. Therefore should closures be avoided where possible?

If they are impure, and I am correct in stating that they can be avoided, why do so many functional programming languages support closures?

One of the criteria for a pure function is that "The function always evaluates the same result value given the same argument value(s)."

Suppose

f: x -> x + y

f(3) will not always give the same result. f(3) depends on the value of y which is not an argument of f. Thus f is not a pure function.

Since all closures rely on values which are not arguments, how is it possible for any closure to be pure? Yes, in theory the closed value could be constant but there is no way of knowing that just by looking that the source code of the function itself.

Where this leads me to is that the same function may be pure in one situation but impure in another. One cannot always determine if a function is pure or not by studying its source code. Rather, one may have to consider it in context of its environment at the point when it is being called before such distinction can be made.

Am I thinking about this correctly?

Answer 1

Purity can be measured by two things:

1. Does the function always return the same output, given the same input; i.e. is it referentially transparent?
2. Does the function modify anything outside of itself, i.e. does it have side-effects?

If the answer to 1 is yes and the answer to 2 is no, then the function is pure. Closures only make a function impure if you modify the closed-over variable.

Answer 2

Others have covered the general question nicely in their answers, so I'll only look at clearing the confusion you signal in your edit.

The closure doesn't become an input of the function, rather it 'goes' into the function body. To be more concrete, a function refers to a value in the outer scope in its body.

You are under the impression that it makes the function impure. That is not the case, in general. In functional programming, the values are immutable most of the time. That applies to the closed-over value as well.

Let's say you have a piece of code like this one:

let make y =
    fun x -> x + y

Calling make 3 and make 4 will give you two functions with closures over make's y argument. One of them will return x + 3, the other x + 4. They are two distinct functions however, and both are pure. They were created using the same make function, but that's it.

Note the most of the time a few paragraphs back.

1. In Haskell, which is pure, you can only close over immutable values. There is no mutable state to close over. You are sure to get a pure function that way.
2. In impure functional languages, like F#, you can close over reference cells and reference types, and get an impure function in effect. You are right in that you have to track the scope within which the function is defined to know if it's pure or not. You can easily tell if a value is mutable in those languages, so it's not much of a problem.
3. In OOP languages that support closures, like C# and JavaScript, the situation is similar to impure functional languages, but tracking the outer scope gets more tricky since variables are mutable by default.

Note that for 2 and 3, those languages don't offer any guarantees about purity. The impurity there is not a property of the closure, but of the language itself. Closures don't change the picture much by themselves.

Answer 3

Closures appear Lambda Calculus, which is the purest form of functional programming possible, so I wouldn't call them "impure"...

Closures are not "impure" because functions in functional languages are first class citizens - that means they can be treated as values.

Imagine this(pseudocode):

foo(x) {
    let y = x + 1
    ...
}

y is a value. It's value depends on x, but x is immutable so y's value is also immutable. We can call foo many times with different arguments which will produce different ys, but those ys all live in different scopes and depend on different xs so purity remains intact.

Now let's change it:

bar(x) {
    let y(z) = x + z
    ....
}

Here we are using a closure(we are closing over x), but it's just the same as in foo - different calls to bar with different arguments create different values of y(remember - functions are values) which are all immutable so purity remains intact.

Also, please note that closures have a very similar effect to currying:

adder(a)(b) {
    return a + b
}
baz(x) {
    let y = adder(x)
    ...
}

baz is not really different than bar - in both we create a function value named y that returns it's argument plus x. In matter of fact, in Lambda Calculus you use closures to create functions with multiple arguments - and it's still not impure.

Answer 4

Normally I'd ask you to clarify your definition of "impure", but in this case it doesn't really matter. Assuming you're contrasting it the term purely functional, the answer is "no", because there's nothing about closures that's inherently destructive. If your language was purely functional without closures, it'd still be purely functional with closures. If instead you mean "not functional", the answer is still "no"; closures facilitate the creation of functions.

It seems one can generally avoid closures by passing data directly to a function.

Yes, but then your function would have one more parameter, and that would change its type. Closures allow you to create functions based on variables without adding parameters. This is useful when you have, say, a function that takes 2 arguments, and you want to create a version of it that only takes 1 argument.

EDIT: With regards to your own edit/example...

Suppose

f: x -> x + y

f(3) will not always give the same result. f(3) depends on the value of y which is not an argument of f. Thus f is not a pure function.

Depends is the wrong choice of word here. Quoting the very same Wikipedia article you did:

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.

Assuming y is immutable (which is usually the case in functional languages), condition 1 is satisfied: for all values of x, the value of f(x) doesn't change. This should be clear from the fact that y is no different from a constant, and x + 3 is pure. It's also clear there's no mutation or I/O going on.

Answer 5

Very quickly: a substitution is "referentially transparent" if "substituting like leads to like" and a function is "pure" if all of its effects are contained in its return value. Both of those can be made precise, but it's vital to note that they are not identical nor even does one imply the other.

Now let's talk about closures.

Boring (mostly pure) "closures"

Closures occur because as we evaluate a lambda term we interpret (bound) variables as environment lookups. Thus, when we return a lambda term as the result of an evaluation the variables inside it will have "closed over" the values they took when it was defined.

In plain lambda calculus this is sort of trivial and the whole notion just vanishes. To demonstrate that, here's a relatively lightweight lambda calculus interpreter:

-- untyped lambda calculus values are functions
data Value = FunVal (Value -> Value)

-- we write expressions where variables take string-based names, but we'll
-- also just assume that nobody ever shadows names to avoid having to do
-- capture-avoiding substitutions

type Name = String

data Expr
  = Var Name
  | App Expr Expr
  | Abs Name Expr

-- We model the environment as function from strings to values, 
-- notably ignoring any kind of smooth lookup failures
type Env = Name -> Value

-- The empty environment
env0 :: Env
env0 _ = error "Nope!"

-- Augmenting the environment with a value, "closing over" it!
addEnv :: Name -> Value -> Env -> Env
addEnv nm v e nm' | nm' == nm = v
                  | otherwise = e nm

-- And finally the interpreter itself
interp :: Env -> Expr -> Value
interp e (Var name) = e name          -- variable lookup in the env
interp e (App ef ex) =
  let FunVal f = interp e ef
      x        = interp e ex
  in f x                              -- application to lambda terms
interp e (Abs name expr) =
  -- augmentation of a local (lexical) environment
  FunVal (\value -> interp (addEnv name value e) expr)

The important part to notice is in addEnv when we augment the environment with a new name. This function gets called only "inside" of the interpreted Abstraction term (lambda term). The environment gets "looked up" whenever we evaluate a Var term and so those Vars resolve to whatever the Name referred to in the Env which got captured by the Abstraction containing the Var.

Now, again, in plain LC terms this is boring. It means that bound variables are just constants as far as anyone cares. They get evaluated directly and immediately as the values they denote in the environment as lexically scoped up to that point.

This is also (almost) pure. The only meaning of any term in our lambda calculus is determined by its return value. The only exception is the side-effect of non-termination which is embodied by the Omega term:

-- in simple LC syntax:
--
-- (\x -> (x x)) (\x -> (x x))
omega :: Expr
omega = App (Abs "x" (App (Var "x") 
                          (Var "x")))
            (Abs "x" (App (Var "x") 
                          (Var "x")))

Interesting (impure) closures

Now to certain backgrounds the closures described in plain LC above are boring because there's no notion of being able to interact with the variables we've closed over. In particular, the word "closure" tends to invoke code like the following Javascript

> function mk_counter() {
  var n = 0;
  return function incr() {
    return n += 1;
  }
}
undefined

> var c = mk_counter()
undefined
> c()
1
> c()
2
> c()
3

This demonstrates that we've closed over the n variable in the inner function incr and calling incr meaningfully interacts with that variable. mk_counter is pure, but incr is decidedly impure (and not referentially transparent either).

What differs between these two instances?

Notions of "variable"

If we look at what substitution and abstraction mean in the plain LC sense we notice that they are decidedly plain. Variables are literally nothing more than immediate environment lookups. Lambda abstraction is literally nothing more than creating an augmented environment to evaluate the inner expression. There is no room in this model for the kind of behavior we saw with mk_counter/incr because there's no variation allowed.

To many this is the heart of what "variable" means—variation. However, semanticists like to distinguish between the kind of variable used in LC and the kind of "variable" used in Javascript. To do so, they tend to call the latter a "mutable cell" or "slot".

This nomenclature follows the long historical usage of "variable" in mathematics where it meant something more like "unknown": the (mathematical) expression "x + x" does not allow for x to vary over time, it instead is meant to have meaning regardless of the (single, constant) value x takes.

Thus, we say "slot" to emphasize the ability to put values into a slot and to take them out.

To add further to the confusion, in Javascript these "slots" look the same as variables: we write

var x;

to create one and then when we write

x;

it indicates us looking up the value currently stored in that slot. To make this more clear, pure languages tend to think of slots as taking names as (mathematical, lambda calculus) names. In this case we must explicitly label when we get or put from a slot. Such notation tends to look like

-- create a fresh, empty slot and name it `x` in the context of the 
-- expression E
let x = newSlot in E

-- look up the value stored in the named slot named `x`, return that value
get x

-- store a new value, `v`, in the slot named `x`, return the slot
put x v

The advantage of this notation is that we now have a firm distinction between mathematical variables and mutable slots. Variables may take slots as their values, but the particular slot named by a variable is constant throughout its scope.

Using this notation we can rewrite the mk_counter example (this time in a Haskell-like syntax, though decidedly un-Haskell-like semantics):

mkCounter = 
  let x = newSlot 
  in (\() -> let old = get x 
             in get (put x (old + 1)))

In this case we're using procedures which manipulate this mutable slot. In order to implement it we'd need to close over not only a constant environment of names like x but also a mutable environment containing all of the needed slots. This is closer to the common notion of "closure" people love so much.

Again, mkCounter is very impure. It's also very referentially opaque. But notice that the side-effects do not arise from the name capture or closure but instead the capture of the mutable cell and the side-effecting operations on it like get and put.

Ultimately, I think this is the final answer to your question: purity is not affected by (mathematical) variable capture but instead by side-effecting operations performed on mutable slots named by captured variables.

It's only that in languages which do not attempt to be close to LC or do not attempt to maintain purity that these two concepts are so often conflated leading to confusion.

Answer 6

No, closures do not cause a function to be impure, as long as the closed value is constant (neither changed by the closure nor other code), which is the usual case in functional programming.

Note that while you can always pass in a value as an argument instead, usually you can't do so without a considerable amount of difficulty. For example (coffeescript):

closedValue = 42
return (arg) -> console.log "#{closedValue} #{arg}"

By your suggestion, you could just return:

return (arg, closedValue) -> console.log "#{closedValue} #{arg}"

This function isn't being called at this point, just defined, so you'd have to find some way to pass your desired value for closedValue to the point at which the function is actually being called. At best this creates a lot of coupling. At worst, you don't control the code at the calling point, so it's effectively impossible.

Event libraries in languages that don't support closures usually provide some other way to pass arbitrary data back to the callback, but it's not pretty, and creates a lot of complexity both for the library maintainer and the library users.