[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: scheme@mc.lcs.mit.edu*Subject*: Y combinator derivation (long)*From*: Jim Marshall <marshall@iuvax.cs.indiana.edu>*Date*: Mon ,25 Sep 89 00:20:33 EDT*Organization*: Indiana University, Bloomington*Sender*: scheme-request@mc.lcs.mit.edu

Hello world. Someone recently requested information about deriving the applicative-order Y-combinator from scratch, so I thought I would post a derivation of it in Scheme. The following derivation is similar in flavor to the derivation found in "The Little LISPer" by Friedman/Felleisen, but uses a slightly different starting approach (for one thing, I begin with the "length" function). Maybe this version will be a little easier to follow (maybe not, who knows?). Enjoy... Step 0... We wish to write the recursive function "length" without having to give it a name. Then we could invoke it on a list as follows: ((lambda (l) (if (null? l) 0 (add1 (??? (cdr l))))) '(any old list you like)) The problem, of course, is that we can't plug in the function expression itself directly in place of the ??? because that immediately leads to an infinite regress. It's like trying to quote an entire sentence inside the sentence itself. ---------------------------------------------------------------------- Step 1... This is the _only_ step in the entire derivation that requires any real thought. We can get around the above problem by passing in a _copy_ of the length function as an extra argument and then using _that_ in place of the ???. But we must ensure that the copy of our function looks _exactly_ like the function itself at all times. WE WILL ADHERE TO THIS REQUIREMENT IN EVERY STEP THAT FOLLOWS. Notice that since f is a copy of the function, and the function takes a copy of itself as a second argument, we must also pass f to f (as a second argument). Passing a copy of the function to itself is the whole secret of the Y-combinator. The following expression will evaluate to 5 (the length of the example list): ((lambda (l f) (if (null? l) 0 (add1 (f (cdr l) f)))) '(any old list you like) (lambda (l f) (if (null? l) 0 (add1 (f (cdr l) f))))) ------------------------------------------------------------------------ Step 2... We just switch the order of the function arguments, l and f. "(f (cdr l) f)" changes to "(f f (cdr l))", and the arguments to the top-level invocation also switch places: ((lambda (f l) (if (null? l) 0 (add1 (f f (cdr l))))) (lambda (f l) (if (null? l) 0 (add1 (f f (cdr l))))) '(any old list you like)) ------------------------------------------------------------------------ Step 3... We simply curry the function so that it takes its two arguments one at a time. Note the extra set of ()'s around the top-level invocation as well. This expression still evaluates to 5: (((lambda (f) (lambda (l) (if (null? l) 0 (add1 ((f f) (cdr l)))))) (lambda (f) (lambda (l) (if (null? l) 0 (add1 ((f f) (cdr l))))))) '(any old list you like)) ------------------------------------------------------------------------- Step 4... The above expression is now of the form "(<function> '(any old list you like))", where <function> is now a self-contained recursive version of "length", although still in a clumsy form. We can forget about '(any old list you like) for the remainder of the derivation and concentrate on just the <function> part, since that's what we're interested in. So here it is by itself: ((lambda (f) (lambda (l) (if (null? l) 0 (add1 ((f f) (cdr l)))))) (lambda (f) (lambda (l) (if (null? l) 0 (add1 ((f f) (cdr l))))))) ------------------------------------------------------------------------- Step 5... Notice that in the above expression (f f) returns a function which gets applied to (cdr l). In the same way that the add1 function is equivalent to the function (lambda (a) (add1 a)), the "(f f) function" is equivalent to the function (lambda (a) ((f f) a)). [This is just an inverse eta step to you lambda-calculus pros out there]. This step is necessary to avoid infinite loops, since we're assuming applicative order (i.e, Scheme). ((lambda (f) (lambda (l) (if (null? l) 0 (add1 ((lambda (a) ((f f) a)) (cdr l)))))) (lambda (f) (lambda (l) (if (null? l) 0 (add1 ((lambda (a) ((f f) a)) (cdr l))))))) ------------------------------------------------------------------------- Step 6... Here we just give the (lambda (a) ((f f) a)) function the name "r" using a let-expression. Simple. (Notice how every change to our function requires an identical change to the _copy_ of the function, as mentioned earlier). ((lambda (f) (let ([r (lambda (a) ((f f) a))]) (lambda (l) (if (null? l) 0 (add1 (r (cdr l))))))) (lambda (f) (let ([r (lambda (a) ((f f) a))]) (lambda (l) (if (null? l) 0 (add1 (r (cdr l)))))))) ------------------------------------------------------------------------- Step 7... Now we just expand the let-expressions into their equivalent lambda-forms. In general, "(let ([x val]) body)" is equivalent to "((lambda (x) body) val)". This may look complicated but it's not. Just match up the ()'s carefully. ((lambda (f) ((lambda (r) (lambda (l) (if (null? l) 0 (add1 (r (cdr l)))))) (lambda (a) ((f f) a)))) (lambda (f) ((lambda (r) (lambda (l) (if (null? l) 0 (add1 (r (cdr l)))))) (lambda (a) ((f f) a))))) ------------------------------------------------------------------------- Step 8... Now we can give the (lambda (r) (lambda (l) ...)) expression a name also ("m") using a let-expression, since it has no free variables (except for primitives, but they're bound globally anyway). This step is just like Step 6. (let ([m (lambda (r) (lambda (l) (if (null? l) 0 (add1 (r (cdr l))))))]) ((lambda (f) (m (lambda (a) ((f f) a)))) (lambda (f) (m (lambda (a) ((f f) a)))))) ------------------------------------------------------------------------- Step 9... Now we replace the let-expression for "m" by its equivalent lambda-form, just like in Step 7, and out pops the applicative-order Y-combinator! The expression below still represents the self-contained recursive length function, but now it's in a nicer form. In particular, the (lambda (m) ...) sub-expression is Y: ((lambda (m) ((lambda (f) (m (lambda (a) ((f f) a)))) (lambda (f) (m (lambda (a) ((f f) a)))))) (lambda (r) (lambda (l) (if (null? l) 0 (add1 (r (cdr l))))))) ------------------------------------------------------------------------ Step 10... We just pull out the (lambda (m) ...) sub-expression and call it Y, since all of its variables are bound (after all, it's a combinator). Then the expression above for the recursive length function can be rewritten as shown below. The expression passed to Y is a "template" for the recursive length function. Instead of "???", we call the recursive invocation "r", wrap the whole thing with (lambda (r) ...), and hand it over to Y, which returns a self-contained recursive function. You can give it a name with define if you want, but you don't have to. (define Y (lambda (m) ((lambda (f) (m (lambda (a) ((f f) a)))) (lambda (f) (m (lambda (a) ((f f) a))))))) (Y (lambda (r) (lambda (l) (if (null? l) 0 (add1 (r (cdr l))))))) ------------------------------------------------------------------------- Jim Marshall, Gradual Student | "That it will never come again Computer Science Department | Is what makes life so sweet." Indiana University, Bloomington | -Emily Dickinson marshall@iuvax.cs.indiana.edu | -------------------------------------------------------------------------

- Prev by Date:
**Re: Y combinator derivation** - Next by Date:
**Journal of Functional Programming** - Previous by thread:
**Re: Y combinator derivation** - Next by thread:
**Journal of Functional Programming** - Index(es):