def add x y = if iszero y then x else add (succ x) (pred y)but that doesn't work. That definition itself expands (through space, as it were) forever, keeping on recursively copying the definition for

We're going to fix that using two simple ideas that work
together: abstraction, which we call Abstracto®, and
self-replication, which works with with Abstracto to yield a vital
function named `recursive` or Y.

(f [args])Here

lambda g . (g [args])What happens? Nothing! That's the beauty of it. With Abstracto, we have a function that just ``lies there and looks at us''. BUT if we want

(f [args])we simply apply the Abstracto'd function to

(lambda g . (g [args]) f) => (f [args]).WARNING: Abstracto alone cannot solve our basic motivating problem! For example, that last

def add1 f x y = %function prototype if iszero y then x else f (succ x) (pred y) %function callYou see

... else add (succ x) (pred y) => ... => add (succ x) (pred y) == **boom**And the first argument to

So this is frustrating... What to do?

def addcustom f x y = if iszero y then x else f f (succ x) (pred y)where the 2nd copy of the function

def add = (addcustom addcustom)And in fact this approach works under normal order evaluation. Recall that for reasons given in Chapter 8 and illustrated by our same add function, applicative order evaluation may not terminate in conditional statements (

Let's not give up on `add1`. Our problem is that single `f` in

else f (succ x) (pred y)which means

else f f (succ x) (pred y)So to save

def selfapply = lambda s . (s s)We can build self-replication with

(selfapply selfapply) == (lambda s . (s s) lambda s . (s s)) => ... => (lambda s . (s s) lambda s . (s s)) => ... => ...The problem with replicating a function application is that by definition it will apply itself forever, not expanding forever in space by beta-reduction as our original problem add does, but running forever through time.

We know Abstracto stops infinite expansion in definitions that
recursively refer to themselves, and using the same power it
can also stop
infinite applications. We are going to shield `selfapply`'s
self-application with Abstracto, thus tame it, see it's what we need
to implement recursion. We call the result `Y` (or `recursive`).

def Y f = (lambda s . (f (s s)) lambda s . (f (s s)))Clearly

Before we apply it, we can peer inside and predict what we'll get:

def Y f = (lambda s . (f (s s)) lambda s . (f (s s))) -------- ********************The underlined body is a picture of what we expect. First we see the function

Y(f) = f Y(f).What is

`Y` is a *fixed-point combinator* in untyped lambda calculus. There
an infinite number of them (!). Two more examples are in the
footnote .

else (Y add1) (succ x) (pred y)and after working out that

(Y add1) => ... => add1 (Y add1)so

(Y add1) (succ x) (pred y) => ... => add1 (Y add1) (succ x) (pred y)Sure enough, the first

Thus `Y` achieves the effect of the "`f f`" in
`addcustom` by its patented combination
of Abstracto (here used to create `add1` and `Y`),
and `selfapply` (`Y`'s main
ingredient). It's general, and works for any function.
Mathematicians like `Y` mainly
because it is a deep and elegant notion in recursive function theory.
We care because
it
provides a general way to create working recursive
functions.

rec add x y = if iszero y then x else add (succ x) (pred y)we understand that this is shorthand for two new defs: one for an Abstracto-d helper function and one for

def add1 f x y = if iszero y then x else f (succ x) (pred y) def add = (Y add1)And remember...

def Y = lambda f. (lambda s . (f (s s)) lambda s . (f (s s)))or as we can also write,

def Y f = (lambda s . (f (s s)) lambda s . (f (s s)))Happy recursing!

"A version of the `Y` combinator
that can be used in call-by-value (applicative-order)
evaluation is given by eta-expansion of part of the ordinary `Y`
combinator:"

Z = lambda f. (lambda x. f (lambda y. x x y)) (lambda x. f (lambda y. x x y)) -----------------This notation has function application written not like

>>> Z = lambda f: (lambda x: f(lambda *args: x(x)(*args))) (lambda x: f(lambda *args: x(x)(*args))) >>> fact = lambda f: lambda x: 1 if x == 0 else x * f(x-1) >>> Z(fact)(5) 120The book

(define Y (lambda (g) ((lambda (f) (f f)) (lambda (f) (g (lambda (x) ((f f) x))))))) ---------------------- (f f)

Last Change: 1/8/14