# Normal Forms

Haskell uses call-by-need (i.e. “laziness”) as its evaluation strategy. There’s no shortage of voices bellowing out “use strict data types, use lazy functions (or lazy ‘spines’);” “laziness by default was a mistake;” “laziness makes it hard to reason about performance.” Meanwhile, some Haskellers have shown concretely that strictness isn’t always the right default and that laziness is necessary to achieve good performance in some cases.

Laziness frees the programmer from ugly operational semantics hacks like
“iterators,” allows for user-defined short-circuiting operations (versus strict
languages, where boolean operators must use built-in magic^{1}), and enables
higher-order functions to be used ergonomically without
performance sacrifices.
However, there is one pitfall that is the source of all complaints about lazy
evaluation:

Lazy programs will have live heap objects that are not in normal form.

What is “normal form?”

## Normalization is Evaluation

GHCi has a command called `:sprint`

(that’s read like “s-print” and not
“sprint”^{2}) that allows one to observe values as they are, without
performing any evaluation. We can define a list that has all of the natural
numbers:

`>>> nats = [0..] :: [Integer]`

But no evaluation has happened yet. `:sprint`

will show a
not-yet-evaluated-thing (a “thunk”) with `_`

:

```
>>> :sprint nats
nats = _
```

We can cause part of the `nats`

value to be evaluated by asking GHCi to print
some:

```
>>> take 3 nats
[0,1,2]
```

And `:sprint`

shows that just enough of the structure of `nats`

was evaluated
for GHCi to show what we asked for:

```
>>> :sprint nats
nats = 0 : 1 : 2 : _
```

Here we see that a constructor with multiple arguments can be in a state on the
heap where some of the constructor’s arguments have been fully evaluated, and
some have not. In the case of `2 : _`

, we have a list cons cell whose contained
element is fully evaluated, but whose next part of the list is not. It’s
possible to end up with `:`

values in the opposite situation, where the next
part of the list is known but the contained element is not. Suppose we have a
list of all of the Fibonacci numbers:

`>>> fibs = 0 : 1 : zipWith (+) fibs (tail fibs) :: [Integer]`

Along with a predicate that checks whether or not a list of any type of element has a length of at least three; note that we don’t care about what the list elements are at all:

```
>>> :{
... atLeastThree :: [a] -> Bool
... atLeastThree (_:_:_:_) = True
... atLeastThree _ = False
... :}
>>> atLeastThree [1, 2]
False
>>> atLeastThree [1, 2, 3]
True
```

Now let’s ask GHCi if \(\infty \ge 3\):

```
>>> atLeastThree fibs
True
```

Let’s see what evaluation had to take place to evaluate `atLeastThree fibs`

:

```
>>> :sprint fibs
fibs = 0 : 1 : _ : _
```

Here we have a value with a mix of “fully evaluated” constructors (e.g. the
literals `0`

and `1`

we provided), constructors in which some of the arguments
are known (`1 : _`

), constructors in which no arguments are known (`_ : _`

), and
values about which nothing at all is known, even the “top-level” constructor
(`_`

). Note that GHCi does not parenthesize this value very clearly;
`0 : (1 : (_ : _))`

is more clear.^{3}

“Normalization” refers to the process of applying an abstract rewriting system’s
rules (e.g. the evaluation rules of the lambda calculus) to transform terms. In
this setting, a term in “normal form” is a term which cannot be transformed by
the rules any further; it is, intuitively speaking, “fully evaluated.” When it
comes to Haskell, we can define “normalization” by analogy as “turning thunks
(e.g. `_`

) into concrete values by doing evaluation”. By extension, we can say
that a Haskell value is in “normal form.^{4}” if there are no thunks left in
its structure, meaning that there’s no more evaluation that can be done.

What precisely is a “concrete value?” Rather than simply saying that it’s a value on which no more evaluation can be done, we can use the following set of rules for determining whether or not a value is in normal form:

- The value’s constructor is determined, e.g.
`:sprint`

shows us something other than a single`_`

, like it did in our very first`:sprint nats`

invocation above. - The constructor’s arguments, if any, are not thunks. For example,
`_ : _`

doesn’t obey this rule, since both its arguments are thunks. - The constructor’s arguments are in normal form. In other words, these rules must apply to all constructor arguments recursively.

In the case of the infinite values `nats`

and `fibs`

used in the definition
above, we can actually *never* reach normal form, because we’d have to evaluate
forever to do so. In this example, we’ll use a value that we can evaluate to
normal form:

```
>>> x = (1 + 1, 2 * 2) :: (Integer, Integer)
>>> :sprint x
x = (_,_)
>>> -- Not in normal form yet.
>>> fst x
2
>>> :sprint x
x = (2,_)
>>> -- Still not in normal form yet.
>>> snd x
4
>>> :sprint x
x = (2,4)
>>> -- How it's in normal form.
```

## Weak Head Normal Form

Rather than causing evaluation to occur by having GHCi print values, `base`

provides a function called `seq :: a -> b -> b`

that can be used “force”
evaluation. This is a useful intuition, but “forcing” evaluation isn’t exactly
what `seq`

does, as the documentation explains:

The value of

`seq a b`

is bottom if`a`

is bottom, and otherwise equal to`b`

. In other words, it evaluates the first argument`a`

to weak head normal form (WHNF).`seq`

is usually introduced to improve performance by avoiding unneeded laziness.

Here, “bottom” just means some “divergent” computation, e.g. something that
would take infinite time to evaluate (`f x = f x`

) or would throw an exception
(`error "slain!"`

). This definition is a bit hand-wavy, but is sufficient to
explain what `seq`

does. In order for `seq`

to evaluate to “bottom” if its first
argument is bottom, it must evaluate its first argument. However, even though
`seq`

is introduced to control laziness, it is itself lazy, in that it does not
evaluate the first argument to “normal form” as we defined above. Instead, it
stops once the first of the normal form rules given above is satisfied,
i.e. when it has determined the first argument’s constructor. If that
constructor takes arguments and those arguments happen to be thunks, `seq`

doesn’t care, and the whole expression evaluates to the second argument.

In the `nats`

example from before, `seq`

stops evaluating as soon as it uncovers
the first list cons cell:

```
>>> nats = [0..] :: [Integer]
>>> :sprint nats
>>> nats = _
>>> seq nats ()
()
>>> :sprint nats
nats = 0 : _
```

While we’re playing around in GHCi, the second argument to `seq`

doesn’t matter,
since GHCi will evaluate whatever we ask so that it can print it. When using
`seq`

in a real program, typically the first argument will be a subexpression in
the second argument, so that the first argument will be evaluated before
evaluation of the containing expression proceeds. A classic example is the
strict left fold, `foldl'`

```
foldl' :: (b -> a -> b) -> b -> [a] -> b
= z
foldl' _ z [] :xs) = let z' = f z x
foldl' f z (xin seq z' (foldl' f z' xs)
```

Plenty of good writing already exists on how to use `seq`

, namely Simon Marlow’s
*Parallel and Concurrent Programming in Haskell* (this
chapter
in particular) and HaskellWiki’s article on
folds. Another note: in
practice it tends to be quite tedious to use `seq`

directly, so instead the
handy bang
patterns
language extension is typically used.

The `seq`

documentation uses the term “weak head normal form” to describe a
value in a state where its constructor is known, but the constructors’ arguments
may not be known. In *The Implementation of Functional Programming Languages*,
Simon Peyton Jones gives this more formal definition of weak head normal form:

A lambda expression is in

weak head normal form(WHNF) if and only if it is of the form:\(F \, E_1 \, E_2 \, \ldots \, E_n\)

where \(n \ge 0\)

and either \(F\) is a variable or data object, or \(F\) is a lambda abstraction or built-in function and \((F \, E_1 \, E_2 \, \ldots \, E_n)\) is not a redex for any \(m \le n\).

An expression has no

top-level redexif and only if it is weak head normal form.

This extends the definition of weak head normal form to any sort of function
application in general, not simply application of data constructors. You can
think of a “top-level redex” as roughly equivalent to the lone `_`

that GHCi
would `:sprint`

when examining totally unevaluated values. The following bit is
quite important:

\((F \, E_1 \, E_2 \, \ldots \, E_n)\) is not a redex for any \(m \le n\)

This means that if \(F \, E_1\), or \(F \, E_1 \, E_2\), or so on, *could* be
reduced, then the whole expression is *not* in weak head normal form. This is a
formal statement of the intuitive notion from before that one must “evaluate
until a constructor is determined” to reach WHNF.

For the remainder of this discussion, we will focus on the application of data
constructors, setting aside the application of arbitrary functions. Although we
can use `seq`

to control when function applications are reduced, we lack any
control over whether or not arbitrary lambda abstractions are in normal
form. The `(->)`

type is built-in magic in GHC, and it doesn’t make sense to
talk about what its “constructors” are.

`deepseq`

and `NFData`

Equipped with workable definitions of normal form and weak head normal form we
can examine (and indeed critique) a popular Haskell package called
`deepseq`

. This package provides a class called `NFData`

and a few associated
utility functions. `NFData`

has a single method, `rnf :: a -> ()`

that evaluates
its argument to normal form, then returns `()`

. The documentation for the
`Control.DeepSeq`

module notes three useful applications of the class:

- Avoiding resource leaks in lazy IO programs.
^{5} - Ensuring that lazy values containing divergent values do not “leak” outside
the scope of their exception handler.
^{6} - Forcing evaluation to occur on one thread that uses a synchronization
primitive to send data to another thread.
^{7}

In practice, solving these sorts of issues is exactly what `deepseq`

is used
for. However, in the package documentation there is no discussion of what laws
`NFData`

instances should obey, nor is there any concrete definition of what
“normal form” means. The closest the documentation gets is mentioning that
“normal form data” is “data structures with no unevaluated components.”

Despite the lack of a solid definition of normal form, we find that almost all
of the `NFData`

instances provided in the package satisfy the three normal form
rules given earlier. A majority of the instances are for data types with no type
arguments, and with constructors that accept monomorphic arguments. In the case
of types like `Bool`

, `Int`

, `Double`

, etc., weak head normal form implies
normal form, since the data constructors take no arguments. WHNF implies that
the constructor is known, and only the first rule for normal forms is relevant
in the case of constructors with no arguments, so for such types a value in weak
head normal form is in normal form. In the case of monomorphic newtypes like
`CInt`

, the procedure for evaluating to normal form follows trivially from the
wrapped type.

A handful of the provided instances are structurally recursive. What should the
`NFData`

instance for lists look like? We can derive the implementation by
examining the normal form rules. By the first rule, we must determine if the
list value’s constructor is `:`

or `[]`

. If it’s `[]`

we’re done, since that
constructor takes no arguments. By the second rule, if the value’s constructor
is determined to be `:`

, we must evaluate its arguments. By the third rule, we
must evaluate those arguments to normal form; this means that the type of the
list elements must have an `NFData`

instance as well. As a corollary to the
third rule, in order to evaluate the list value to normal form, we must walk
down the entire length of the list. We can follow this same derivation procedure
to determine the correct instances for `Maybe`

, `Either`

, tuples, `Ratio`

,
`Complex`

, and so on.

Where normal forms can become quite confusing and where `NFData`

instances can
become quite controversial, is the case of types with phantom type variables. By
“phantom type variables,” I mean type constructors that take arguments that do
not appear in any of the data constructors’ arguments. This can lead to some
confusing or counterintuitive `NFData`

instances, but with the normal form
rules to guide us we can determine what the correct instances should be. Let’s
look at an uncontroversial instance first, the `Proxy`

type.

`Proxy`

values are meant for passing type information around at the value level,
and the type definition is quite simple:

`data Proxy a = Proxy`

Here we have a single constructor with no arguments, and a type constructor with
a single phantom argument. Since the type constructor takes no arguments, by the
first normal form rule, all we need to do is determine the constructor. Here’s
the `NFData`

instance:

```
instance NFData (Proxy a) where
Proxy = () rnf
```

Although I have never required this instance myself, it obeys the normal form
rules, and I’ve never encountered an argument that this instance should be
removed from the `deepseq`

package. The key difference between this instance and
the others we’ve discussed so far is that the type variable `a`

does not appear
in the constructor. A critical corollary: Whether or not a value of type `Proxy a`

is in normal form has *nothing* to do with *any* values of type `a`

. This
statement follows from the normal form rules, and it is absolutely critical to
bear this principle in mind when reasoning about `NFData`

instances for types
with phantom type variables.

Here’s another uncontroversial instance, the `Const`

functor. Here’s its
definition:

`newtype Const a b = Const { getConst :: a }`

In this case, we have one type variable that appears in a data constructor, and
one phantom type variable. From the normal form rules, this means that `a`

must
have an `NFData`

instance if we are to write an `NFData`

instance for `Const`

,
but `b`

does not require one, because whether or not a value of type `Const a b`

is in normal form has nothing to do with any values of type `b`

. Here is the
`NFData`

instance:

```
instance NFData a => NFData (Const a b) where
= rnf . getConst rnf
```

Let’s consider a trickier case, the `Ptr`

type. `base`

provides a class called
`Storable`

for types that can be read from and written to plain memory
addresses. A value of type `Ptr a`

is an address that points to some data that
may be read to produce a value of type `a`

, or that a value of type `a`

may be
written to. However, the data constructor for `Ptr`

only contains an `Addr#`

,
which is GHC’s primitive type for memory addresses, and `a`

is a phantom type
variable. Indeed, a function `castPtr :: Ptr a -> Ptr b`

is provided, which
allows us to change the pointer’s type to whatever we wish, just like a C style
cast. Here’s the type definition:

`data Ptr a = Ptr Addr#`

Here we have one constructor with a single argument. `Addr#`

is a unique in that
it is an “unboxed” type, for our purposes this just means that there are never
any thunks that can be evaluated to a lone `Addr#`

. If we have an `Addr#`

value
at all, then we know it’s evaluated. This means that `Ptr a`

is a type for which
WHNF implies normal form, and `deepseq`

provides a utility function for writing
`NFData`

instances for such types. Its definition is provided here, along with
the `NFData`

instance:

```
rwhnf :: a -> ()
= seq x ()
rwhnf x
instance NFData (Ptr a) where
= rwhnf rnf
```

I’ve noticed an extremely common misunderstanding surrounding `NFData`

instances
like the one for `Ptr`

. Because pointers can reference values, it is claimed
that some programmers might assume that using `rnf`

on a pointer will evaluate
the referred-to data. In the case of `Ptr`

, we cannot provide an `rnf`

that has
this functionality without using `unsafePerformIO`

, since the only way to read
or write the referred-to value is by doing IO. This same argument applies to
`FunPtr`

and `ForeignPtr`

.

A yet more controversial case is `IORef`

. `IORef`

is a bit like `Ptr`

, however,
the value referred to by an `IORef`

is a typical lifted heap object; it works
with any type and there is no need for a `Storable`

-like class for reading and
writing values. Furthermore, `IORef`

supports useful synchronization operations
like `atomicModifyIORef`

. Here’s its definition:

`data IORef a = IORef (STRef RealWorld a)`

The `IO`

type is built upon the `ST`

type, and an `IORef`

is simply a wrapper
around an `STRef`

with the right kind of state token. I won’t discuss the guts
of `IO`

and `ST`

further here, but this Haskell WikiBook chapter on mutable
objects provides a good
primer. Here’s the definition of `STRef`

:

`data STRef a = STRef (MutVar# s a)`

Like the `Addr#`

in `Ptr`

, a `MutVar#`

is always in normal form. `MutVar#`

is
interesting in that its first argument, the state token, behaves like a phantom
type variable (values of type
`RealWorld`

in the implementation of `IO`

behave similarly). With this information we can
determine the correct `NFData`

instances for `STRef`

and `IORef`

, according to
the normal form rules:

```
instance NFData (STRef s a) where
= rwhnf
rnf
instance NFData (IORef a) where
= rwhnf rnf
```

The same argument for these `STRef`

and `IORef`

instances applies to the
instances for `MVar`

(`deepseq`

currently has such an instance) and `TVar`

(`deepseq`

is, as of this writing, missing an instance for `TVar`

).

So far we’ve discussed arguments for the presence of certain (perhaps
unintuitive at first) `NFData`

instances. However, it should be noted that
`deepseq`

contains an instance that, according to the normal form rules,
*cannot* have an `NFData`

instance. This instance is provided for values of type
`a -> b`

:

```
instance NFData (a -> b) where
= rwhnf rnf
```

It is not meaningful to apply the normal form rules as they’re presented here to
values of function type. The first rule falls down: The `->`

type has no
constructors available to the programmer, so there is no way to satisfy it.

## A Proposal for `NFData`

Based on the definitions and arguments presented here, I offer the following
proposal to amend the `deepseq`

package as it currently exists:

- Add the normal form rules to the
`deepseq`

documentation as laws for the`NFData`

class, restating them more formally if necessary. - Add missing law-abiding instances for types in
`base`

, like`TVar`

,`ForeignPtr`

, and others. - Remove law-breaking
`NFData`

instances, like`a -> b`

. - Reword package documentation to avoid any suggestion that
`rnf`

is a shotgun that can remove any and all thunks in its path; it’s inability to perform IO prohibits such functionality, and I believe that the perception that it provides such functionality is the root of widespread misunderstanding about what it means for value references to be in normal form.

If you ever find that you need missing `NFData`

instances for types in `base`

or
other boot packages, please add them to my
`deepseq-instances`

package. If you agree with the definitions I’ve formulated here, please consider
participating in discussions surrounding `deepseq`

on its GitHub
page and the Haskell libraries mailing
list.

Consider the C expression

`a ? b : c`

.`b`

will only be evaluated if`a`

is not zero, and`c`

will only be evaluated if`a`

is zero. It is not possible to define your own control structure in C that works with arbitrary values and has this lazy short-circuiting behavor. Go ahead and try to define your own function in C that has the exact same semantics as the ternary operator; without tricks like promoting the arguments to function types, you won’t be able to do it.↩︎There is also a

`:print`

GHCi command that will assign fresh names to all of the found thunks. We don’t need that feature to demonstrate laziness, though.↩︎Thanks to Lalaithion42 on Reddit for pointing this out!↩︎

In the book

*The Implementation of Functional Programming Languages*, Simon Peyton Jones gives this definition of normal form: “If an expression contains no redexes then evaluation is complete, and the expression is said to be in*normal form*.” Thunks are how the RTS represents not-yet-reduced redexes at program runtume.↩︎I wasn’t able to find a good example of this issue in the wild, but here’s a short example:

`returnException :: IO (Int, Int) = do returnException let e = error "x" <- try (pure (e, e)) :: IO (Either SomeException (Int, Int)) r case r of Left e -> throwIO e Right r -> pure r`

You might expect

`returnException`

to always throw, but instead it never throws!`>>> r <- returnException >>> r (*** Exception: x CallStack (from HasCallStack): error, called at <interactive>:47:13 in interactive:Ghci11`

This is because

`try`

is lazy. See the`evaluate`

function for a similar use case.↩︎See the section

*MVar as a Container for Shared State*in Simon Marlow’s*Parallel and Concurrent Programming in Haskell*for a good example of this problem.↩︎