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 add in for add.
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 f is going to be applied, so it must be evaluated first, and if it's defined in terms of itself (like add above), its evaluation (or expansion) never ends, as we've seen. Now let's try Abstracto! We abstract the function call in the sense of turning the above application of f into a function that applies f; when we want to apply it (run it) we must send in the f as an argument --- f is no longer a command to be run, but an argument to be passed. With a new name for the formal parameter, we would have:
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 f (send f in as argument) and we get
(lambda g . (g [args]) f) => (f [args]).WARNING: Abstracto alone cannot solve our basic motivating problem! For example, that last (f
def add1 f x y = %function prototype if iszero y then x else f (succ x) (pred y) %function callYou see add1, thanks to Abstracto, is not going to expand forever: the name add1 does not appear in its definition. It's going to sit there quietly, like a nice little function and wait for three arguments. The first argument must be something like add, but it can't be add (which gives us infinite recursion when we try to evaluate):
... else add (succ x) (pred y) => ... => add (succ x) (pred y) == **boom**And the first argument to add1 can't be add1 -- add1 expects three arguments (line %function prototype) but only sees two (on line %function call).
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 f serves as the first f's first argument. Then we simply define
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 (But see footnote at end). So in a way we're done. On the other hand we'd like a way to create something like addcustom from add "automatically", one that would also work on fib(n), say, which has two recursive calls.
Let's not give up on add1. Our problem is that single f in
else f (succ x) (pred y)which means won't work if it expects three arguments. We know that the following replicated version, from addcustom, does work.
else f f (succ x) (pred y)So to save add1 we need some way to achieve the effect of replicating f without getting into trouble. It would be ideal if f would replicate itself just once and then only when it is invoked, thus creating its own first argument.
def selfapply = lambda s . (s s)We can build self-replication with selfapply, but...
(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 Y is an inactive item, just like any Abstracto-d function, just another function ready to be applied somewhere.
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 f, and then we see a self-application of the under-starred argument. But that's just f followed by Y (!!). Eureka! We have a replication function that replicates just once, just when it is applied to f. In fact, In traditional notation, we have
Y(f) = f Y(f).What is Y? Y is like a little function-generator, or function-iterator. When called with (applied to) any function (say g for a change), it generates a copy of that function g and spits it out to the left, ready for evaluation, and it makes a copy of itself next, for use later (in the recursion as the first argument for the very g it just coughed up).
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 x is > 0 and we are going to take this branch of the if, we know that by definition and construction
(Y add1) => ... => add1 (Y add1)so
(Y add1) (succ x) (pred y) => ... => add1 (Y add1) (succ x) (pred y)Sure enough, the first add1 now has three arguments and the first argument is the same as the one that came in for f, that is (Y add1). This is just what we need for well-behaved recursion.
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 add, which is Y's application to that helper function.
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 (f x) but like f x (as we introduced in class). You can see what they mean by eta-expansion if you note that by eta-reduction (which we did learn about, in lectures or text at the end of Chapter 2). With η-reduction the underlined expression goes to (x x): η-expansion just wraps Abstracto around our previous (s s) The article goes on to show the above combinator working in Python:
>>> 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 The Little Schemer has another, different applicative-order combinator in a new but obvious notation that also uses eta-expansion (eta-reduction shown underlined):
(define Y (lambda (g) ((lambda (f) (f f)) (lambda (f) (g (lambda (x) ((f f) x))))))) ---------------------- (f f)