Short-Circuit Evaluation for Free

Virtually all modern programming languages employ short-circuit evaluation of Boolean expressions. This means that the second operand of a Boolean expression is evaluated only if necessary to determine the value of the whole expression.

• In the expression x && y, y is evaluated only if x is True. If x is False, then the whole expression x && y is False no matter the value of y, so there is no need to evaluate y.

• In the expression x || y, y is evaluated only if x is False. If x is True, then the whole expression x || y is True no matter the value of y, so there is no need to evaluate y.

If one of the two operands is more costly to evaluate, then it helps performance to make it the second operand. Whenever the first operand is enough to determine the value of the whole expression, we save the cost of evaluating the second operand.

Short-circuit evaluation also helps with making our code more elegant. Here's a common example in C:

if (ptr != NULL && *ptr > 10) {
    ...
} else {
    ...
}

Clearly, it is safe to dereference ptr only if it is not NULL. By checking first whether ptr != NULL, we make sure that the second operand *ptr > 10 is evaluated only if this is safe, if ptr != NULL. Without short-circuit evaluation, we would have to write this more tediously:

if (ptr != NULL) {
    if (*ptr > 10) {
        ...
    } else {
        ...
    }
} else {
    ...
}

In particular, the else-branch is repeated twice now. There are ways to avoid this duplication, but none of them are as elegant as using short-circuit evaluation.

In languages with applicative order evaluation of function arguments, short-circuit evaluation requires that the compiler treats Boolean expressions differently from other expressions. Otherwise, it would first evaluate both operands x and y in x && y or x || y before determining the value of the whole expression.

In Haskell, lazy evaluation gives us short-circuiting "for free". What I mean by that is that we can implement x && y and x || y in standard Haskell, without special support for these operations in the compiler, and they short-circuit as in any other language.

Let's test short-circuiting in Haskell. To this end, the following little helper will be useful:

undefined :: a

There exists an undefined value of any type a, and as the name suggests, this value is undefined. We really shouldn't ask for its value. If we do, we get a runtime error:¹

GHCi

>>> undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:75:14 in base:GHC.Err
  undefined, called at <interactive>:18:1 in interactive:Ghci8

Now try this:

GHCi

>>> True || undefined
True

or

GHCi

>>> False && undefined
False

Clearly, we're never asking for the value of the undefined second operand if the first operand determines the value of the whole expression. So, (||) and (&&) short-circuit as expected.

Here are the implementations that achieve this:

(&&), (||) :: Bool -> Bool -> Bool
False && _ = False
_     && y = y
True  || _ = True
_     || y = y

To evaluate the expression x || y, we need to decide whether to apply the first or second equation of (||). The first equation applies if x is True. Thus, we need to evaluate x to decide whether this equation applies. If x is True, then the first equation says that x || y is True no matter the value of y. We use a wildcard in place of y, so we really don't care about its value. Thus, x || y short-circuits. If x is False, then the first equation does not apply, so we need to know the value of y if we want to know the value of x || y.

The logic of the implementation of x && y is analogous. It may be a good exercise for you to verify yourself that y is evaluated only if x is False.

---

1. Apart from its use to demonstrate lazy evaluation, why does there exist an expression that we should never evaluate? I'm not sure, but I do know that undefined is a useful tool for top-down programming.

   When programming, we usually divide the problem we want to solve into subproblems. They get divided into smaller subproblems, and so on until we obtain really simple problems for which we can write a trivial function. The problem is that we usually don't know what these really simple problems look like until we are done breaking our problem into pieces. This makes bottom-up programming hard, where we build up solutions to bigger problems from solutions to smaller problems. It's much easier to say that I know how to solve problem A if I know how to solve problems B, C, and D. I write a function that solves A by calling functions that solve B, C, and D. I don't have functions for B, C, and D yet, but I know their type, I know what arguments I pass to these functions and what they are supposed to return.

   I can now write down the type signatures of the functions that solve B, C, and D, and I can define them to be undefined at this point. I should not try to run my code because it involves undefined functions, but I can still compile it, to see that as far as types are concerned, the bits and pieces I have implemented so far fit together nicely. If I use Haskell's type system effectively, these type checks go a long way to rule out the most idiotic errors.

   Next I implement each of the functions for B, C, and D in turn, and I do it the same way. I figure out how to solve B if I have solutions to simpler problems E and F. Again, I implement my solution to B using functions that solve E and F, and I provide the type signatures of the latter along with undefined implementations. Again, I will check that my types check out at this point by trying to compile my code.

   The consequence of all this is that undefined is a useful tool to drive top-down development, which starts with the problem I try to solve and breaks it into smaller subproblems instead of synthesizing the solution bottom-up. This way, we never have to guess what the building blocks are from which to build our whole program: our decomposition process leads us to the right subproblems. ↩