The Z combinator

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)$\displaystyle \mathrm{Y}$ $\displaystyle {} = \lambda f.\,(\lambda x.\,f\,(x\,x))\,(\lambda x.\,f\,(x\,x))$ we get the Z combinator — the same construction, only each $x\,x$ is replaced by $\lambda v.\,x\,x\,v$:

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

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 chapters 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:

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