## Prequel: lazy evaluation

The book The Implementation of Functional Programming
Languages
discusses at length the graph reduction implementation of a non-strict
functional language (see esp. chapters 10-12). This technique is what
is usually called *lazy evaluation*.

The point about lazy evaluation is that each function argument is
evaluated at most once (when it is first needed). This also applies to
names bound with `let`

s as `let`

s are (in the book) transformed into
function applications.

The picture is a bit more complicated for GHC, but in essence: *lazy
evaluation guarantees that a monomorphic (non-polymorphic) expression
with a name is evaluated only once.*

## The beef: `fix`

Now I'll continue where I left off in a previous
posting about `fix`

. We are
dissecting the standard definition of fix:

> fix f = let x = f x in x

I previously explored one alternative definition, and now I'll use
another as a springboard. So: why is `fix`

not defined as

> myfix f = f (myfix f)

which is obviously equivalent to the previous one? The oft-heard answer is that the former definition has "better sharing characteristics".

Let's have a look at an infinite list of ones.

> ones = 1:ones :: [Integer] > ones_myfix = myfix (1:) :: [Integer] > ones_fix = fix (1:) :: [Integer]

The typesigs are here to keep us monomorphic.

First up, `ones`

. The name `ones`

gets bound to a cons-cell
(constructed by `(:)`

), that has `1`

as its head and `ones`

as its
tail. Only one cons-cell is ever allocated. Now let's have a look at
what `ones_myfix`

does.

ones_myfix ==> myfix (1:) ==> 1:myfix (1:) ==> 1:1:myfix (1:) ==> ...

This equivalent to `ones_myfix = 1:ones_myfix`

, but only *up to
naming*, and naming is crucial when dealing with lazy evaluation. The
call `myfix (1:)`

is not memoised so it is re-evaluated when we
progress through the list, and each call allocates a new cons cell.
The solution is to add an intermediate name, which is exactly what
(the real) `fix`

does:

ones_fix ==> fix (1:) ==> let x = 1:x in x

Which creates one cons cell exactly like `ones`

, except the cell is
called `x`

. This is why the standard definition of fix has those
"better sharing characteristics".

## Afterword

The Implementation of Functional Programming Languages takes an
approach where `fix`

(AKA the Y
combinator) is taken as a
built-in and recursive `let`

s are implemented with it. In GHC,
recursive `let`

s are elementary and thus `fix`

can be defined without
any special tricks.

The book actually mentions that there are two distinct ways for
implementing the built-in **Y**: either cyclically (by sharing) or
non-cyclically (re-evaluating at each step). This is exactly the same
design decision we encounter with haskell's `fix`

.

**Updated 01:40**