The Z combinator — λ-calculus

There remains a problem that afflicts both Curry’s and Turing’s combinators alike: under eager order (call-by-value) both loop forever. The recursive argument — $\mathrm{Y}\,F$ or $\Theta\,F$ itself — is unwound by the runtime in advance, before the function is even called, never reaching any useful work. This can be fixed by delaying the recursive call — turning it into a value that unfolds only when it is actually needed.

The idea is dead simple: wrap a function around the self-application. Technically this is an η-expansion $x\,x$ $\to \lambda v.\,x\,x\,v$ . A call wrapped in $\lambda$ is already a value and unfolds only on a real call. So from Curry’s combinator (1.24) we get the Z combinator — the same construction, only each $x\,x$ is replaced by $\lambda v.\,x\,x\,v$ :

\displaystyle Z

\displaystyle = \lambda f.\,(\lambda x.\,f\,(\lambda v.\,x\,x\,v))\,(\lambda x.\,f\,(\lambda v.\,x\,x\,v))

(1.27)

Let us trace the first unfolding. Set $W$ $= \lambda x.\,F\,(\lambda v.\,x\,x\,v)$ ; then in two β-steps:

\displaystyle Z\,F \;

\displaystyle \to_\beta\; W\,W \;

\displaystyle \to_\beta\; F\,(\lambda v.\,W\,W\,v) \;

\displaystyle =\; F\,(\lambda v.\,Z\,F\,v).

The last equality folds $W\,W$ back into $Z\,F$ . The key point is that the recursive call has come out wrapped in $\lambda v$ : under $\lambda$ it stays a value and unfolds only when actually applied to an argument (whereas $\mathrm{Y}\,F$ and $\Theta\,F$ unfold immediately under eager order).

The same factorial as in the sections on Curry and Turing (the same template $F$ , the same numeral $\overline{3}$ ) is computed by genuine β-reductions, and the wrapped call opens up exactly when we move on to the next number:

\displaystyle \mathbf{fac}\;\overline{3}

\displaystyle = Z\,F\;\overline{3}

\displaystyle \twoheadrightarrow_\beta F\,(\lambda v.\,Z\,F\,v)\;\overline{3}

\displaystyle \twoheadrightarrow_\beta \mathbf{mul}\;\overline{3}\;((\lambda v.\,Z\,F\,v)\;\overline{2})

\displaystyle \twoheadrightarrow_\beta \mathbf{mul}\;\overline{3}\;(Z\,F\;\overline{2})

\displaystyle \twoheadrightarrow_\beta \mathbf{mul}\;\overline{3}\;(\mathbf{mul}\;\overline{2}\;(\mathbf{mul}\;\overline{1}\;(Z\,F\;\overline{0})))

\displaystyle \twoheadrightarrow_\beta \mathbf{mul}\;\overline{3}\;(\mathbf{mul}\;\overline{2}\;(\mathbf{mul}\;\overline{1}\;\overline{1}))

\displaystyle = \overline{6}

So under eager order (call-by-value) it does not unfold in advance and does not loop — the recursive call fires at exactly the right moment.

None of Y, Θ, Z typechecks in the simply typed λ-calculus: the self-application $x\,x$ would require a recursive type.

In Haskell that recursive type is exactly what one introduces — by wrapping the self-application in a newtype; and on it one clearly sees that Z does not rely on laziness. The ordinary $\mathtt{fix}$ rests on the lazy knot $\mathtt{let\;x = f\;x}$ , whereas Z builds recursion by self-application and hides the recursive call under $\lambda v$ — under a value. Let us force evaluation to be strict (the argument is forced before the function is applied, as under call-by-value): the naive Y loops, whereas Z calmly computes the factorial:

newtype Rec a = Rec { unRec :: Rec a -> a }

-- $! forces the argument before applying f — that is exactly eager order (call-by-value)

-- naive Y: the recursive call (unRec x x) is not a value, forced in advance => loops
yStrict :: (a -> a) -> a
yStrict f = w (Rec w) where w x = f $! unRec x x

-- Z: the call is wrapped in (\v -> ...), already a value — $! does not unfold it
zStrict :: ((b -> c) -> b -> c) -> b -> c
zStrict f = w (Rec w) where w x = f $! \v -> unRec x x v

fac :: (Int -> Int) -> Int -> Int
fac rec n = if n == 0 then 1 else n * rec (n - 1)

-- yStrict fac 5  =>  loops
-- zStrict fac 5  =>  120   -- Z computed it without any laziness