Side effects as constraints on orderings

April 28th, 2017

Standard disclaimer

Expected reading time: 7 minutes (at 180 words per minute)

A source of confusion

Pure functions are often defined as functions without "side effects". Most posts I see about pure functions are from people who are enthusiastic about pure functional programming, so side effects tend to be handwaved to the layperson as "bad things". Among other handwaves, I've seen:

(That last one was mostly a joke.)

I've never found any of these definitions to be very useful because they're not very precise. It's hard to tell what is and isn't a side effect, which makes these definitions pretty unintuitive.

I often see another approach, where we instead define pure functions and then say that side effects are things that pure functions do not do. This is precise, but not concrete. Again, not very useful.

Luckily, the definition of functional purity at least seems straightforward:

Definition 1. A function f is pure if and only if:
  1. Running f for any given set of inputs x always returns the same output.
  2. Running f does not mutate the external world (for example, by printing to the console or transmitting over the network).

The first part of this definition describes idempotency. The second part describes side effects.

Unfortunately, the second part also raises a lot of questions:

It seems as if there are two intertwined concerns here: firstly, whether an action affects the "external" world; secondly, whether that action "changes" the external world. It's not clear whether these two concerns are orthogonal, or how we can tell whether an arbitrary function meets these requirements.

A clearer definition

Once you write enough pure functional code, these confusions go away with time. With enough code, you'll gradually develop an intuition for what is or is not a side effect.

Unfortunately, the learning curve for this is rather steep. I think this indicates that our definition is not intuitive enough.

Here is an alternative definition:

Definition 2. A function f is pure if and only if:
  1. Running f for any given set of inputs x always returns the same output.
  2. For all programs containing f, changing the order of when f runs relative to other parts of the program will never change the output produced by the program (including all effects on the external world).
  3. For all programs containing f, changing how many times f runs for any particular set of inputs x will never change the output produced by the program (including all effects on the external world).

I think this definition is clearer because it changes the focus of our requirements for purity.

In particular, the description of side effects in definition (1) had two components we had to think about. Firstly, what is "external" in our world? Secondly, what does it mean to "change" or "mutate" or "observe" this world? With our alternative definition, it becomes clear that whether an effect is "changing" the external world is irrelevant. We care about all effects. Instead, we focus only on defining what it means to be "external".

This depends on the particular program. Effect tracking is a tool, and tools are used in the context of a problem. Depending on the program, we may wish to track different effects, and thus may consider different things "external". In a program with strict requirements for memory usage, we might want to track each memory allocation as an external effect (this is in the spirit of what Rust does). In programs where we don't care about the details of memory allocation, we might not consider that as a side effect (this is what Haskell does). In those programs, we might instead care only about how our program interacts with other programs and with users (in Haskell, this is embodied in the IO monad).

This definition also immediately gives us a good rule-of-thumb for how to judge whether a function has side effects. It doesn't concern us with judging whether the state accessed by a function is "hidden" or whether anything is "mutated". Instead, all that matters is whether the program's behavior changes when the function is run many times or at different locations. This captures many use cases: local variable mutation turns out to be pure (e.g. via the State monad), global RNGs turn out to be impure, and it becomes obvious that doing IO causes impurity (e.g. reading the network at different times may give different results).

What does this imply?

The other thing I really like about this definition is its focus on ordering. This definition makes two things obvious:

  1. Pure functions do not care about their ordering within a program.
  2. Impure functions do care about their ordering within a program.

This captures an intuitive difference between pure functions that we are familiar with from math (e.g. the sine function, which doesn't care about how often it's evaluated or at what time) versus impure functions that we see in computer science (e.g. writing to output, which will change the program's end result if it's done at a different time or a different number of times).

It also suggests a way to structure our programs as we keep track of these effects in order to separate our impure from our pure code. Specifically, impure code must capture two notions:

  1. Ordering (running A then B is distinct from running B then A)
  2. Repetition (running A once is distinct from running A twice)

As it turns out, this is exactly what monads are useful for.

Go back