RECURSION THROUGH ABSTRACTION AND SELF-REPLICATION

INTRODUCTION

The treatment in the readings is a bottom-up development that tries to motivate how we would come up with the recursion (Y) function, or paradoxical combinator. This version is sort of a top-down development that shows how to achieve what we want with a naive approach supplemented with two simple mechanisms. -- CB

OUR PROBLEM

We want to define a recursive function with syntax like:
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.

Preview

Abstracto performs "functionization". It is a concrete sounding word for what is usually known in λ-calculus as "abstraction", which our focus group said "sounds too abstract". Abstracto just turns an expression into a parameterized function that does not get further evaluation until it is applied to some argument. Abstracto is used to prevent functions like add (above) from infinitely expanding, or exploding in space. However, Abstracto in this case generates a need for a self-replication capability for functions. A natural candidate for a self-replication function suggests itself, but it runs forever, never terminating -- it explodes in time, if you will. Again, Abstracto is used to prevent this type of explosion: the resulting self-replicator is called Y. Y, along with the Abstracto-d version of functions like add, gives an elegant and complete way to produce recursive functions 'automatically'.

Abstracto®

The protective shield of Abstracto® actually prevents unwanted expansion of recursive-looking functions like add! This shield allows you to invoke your function ``at execution time'', under your control, not at ``compile time'' under control of the inexorable beta-reduction process. Just watch this: 
(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 ) is as dangerous as ever and applying even an Abstracto-d version of add (above) to add will blow up.

Abstracto® and add

If Abstracto is so great, let's use it on add: 
def add1 f x y =   %function prototype
if iszero y
then x
else  f (succ x) (pred y) %function call
You 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?

Customization and Self-Replication

Our problem is that add1 wants three arguments. We can simply go in and supply a third argument in add1: what's missing is the first argument, the function to be applied. So we go ahead and write it in: it's obviously just f itself: 
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.

Self-Replication, Abstracto, and Y

We may remember selfapply. 
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 .

Y in Use

How does Y work? If we send (Y add1) into add1 (apply add1 to (Y add1)), then (Y add1) comes in for the argument f. Now f is evaluated (prior to its application to (succ x) and (pred y)). But it has been bound at the call to add1 by β-reduction, and is now (Y add1)), which evaluates to add1 (Y add1). Thus the right thing has happened. That is, we first see this: 
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.

From add to rec add

Y and Abstracto work behind the syntactically-sugary scenes. When we use rec to make a definition: 
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!

Footnote

If Abstracto is so great, why can't it deal with the applicative order problem? Guess what? It can. See, e.g., Wikipedia on Fixed Point Combinator.

"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)
120
The 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)

Last Change: 1/8/14