; `The Why Not of Y, or, LAMBDA: The Ultimate Cop-Out' ; Version 1.7 dated 13 September 2007 ; Peter Doyle ; Copyright (C) 2007 Peter G. Doyle. Permission is granted to copy, distribute ; and/or modify this document under the terms of the GNU Free Documentation License, ; as published by the Free Software Foundation; with no Invariant Sections, no Front-Cover ; Texts, and no Back-Cover Texts. ; Here's my naive take on the U and Y combinators. Paste this into DrScheme and run. ; We start with `fact', the standard recursive definition of factorial. This function calls itself, ; after looking its own definition up in some table of defined functions. We're going to try ; to get around the need to look up the definition. (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) (fact 4) ; A working factorial function needn't call itself: It could call any function that computes factorials. ; Here's a variant called `factoid', that subcontracts most of the work to the standard version `fact'. (define factoid (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) (factoid 5) ; Let's pass the subcontractor function in as a parameter, so we don't have to look up the definition. ; (Here and below, we'll be recycling the name `factoid', rather than generating new names.) (define (factoid fact) (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) ((factoid fact) 6) ; Instead of leaving the work to the standard version, we might as well be our own subcontractor. (define (factoid fact) (lambda (n) (if (= n 0) 1 (* n ((factoid fact) (- n 1)))))) ((factoid fact) 7) ; Along with the definition of `fact', we can pass in our own definition. ; NOTE how we have to add this new extra parameter inside where we call ourselves. ; If you're watching for the trick (and you should be!), this is where it happens. (define (factoid factoid fact) (lambda (n) (if (= n 0) 1 (* n ((factoid factoid fact) (- n 1)))))) ((factoid factoid fact) 8) ; Now we never actually get around to using the original `fact': That parameter could be anything! ((factoid factoid atan) 9) ; So we can get rid of that extra parameter. It was the stone in the soup. ; Could have made this soup without it? (define (factoid factoid) (lambda (n) (if (= n 0) 1 (* n ((factoid factoid) (- n 1)))))) ((factoid factoid) 10) ; This version of `factoid' is what we've been looking for. Let's dignify it with the name `fact0', and rewrite ; the definition using lambda more explicitly. (define fact0 (lambda (fact0) (lambda (n) (if (= n 0) 1 (* n ((fact0 fact0) (- n 1))))))) ((fact0 fact0) 11) ; Pasting in the definition for fact0 allows us to compute factorials without ever using `define'. (((lambda (fact0) (lambda (n) (if (= n 0) 1 (* n ((fact0 fact0) (- n 1)))))) (lambda (fact0) (lambda (n) (if (= n 0) 1 (* n ((fact0 fact0) (- n 1))))))) 12) ; Of course we can do the same thing with any other recursive function. (map ((lambda (fib0) (lambda (n) (if (or (= n 0) (= n 1)) 1 (+ ((fib0 fib0) (- n 1)) ((fib0 fib0) (- n 2)))))) (lambda (fib0) (lambda (n) (if (or (= n 0) (= n 1)) 1 (+ ((fib0 fib0) (- n 1)) ((fib0 fib0) (- n 2))))))) '(0 1 2 3 4 5 6 7 8 9 10)) ; Now let's clean things up and cut down on redundancy by defining a function `U' to convert `fact0' ; and similar functions into standard one-argument functions. This is just a matter of applying ; the function to itself. What could be simpler? (define (U f0) (f0 f0)) ((U fact0) 13) ; Or equivalently (define U (lambda (f0) (f0 f0))) ((U fact0) 14) ; Of course we can paste in the definition of U, rather than defining it as a function. ( ((lambda (f0) (f0 f0)) (lambda (fact0) (lambda (n) (if (= n 0) 1 (* n ((fact0 fact0) (- n 1))))))) 15) (map ((lambda (f0) (f0 f0)) (lambda (fib0) (lambda (n) (if (or (= n 0) (= n 1)) 1 (+ ((fib0 fib0) (- n 1)) ((fib0 fib0) (- n 2))))))) '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)) ; That might just as well be the end of the story. ; But, what if we want to build recursive functions out of prototypes whose bodies look more what we'd see ; in the body of a `define', where we write `fact' instead of `(fact0 fact0)'? (define fact1 (lambda (fact) (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))) ; This was one of our earlier versions of `factoid'. To convert it into a factorial function, we can pass it ; `fact' as a subcontractor. ((fact1 fact) 4) ; That's no good! Instead, the plan is to convert it to work like `fact0', which we already know how to ; promote to the factorial function. Look at `fact0'. (define fact0 (lambda (fact0) (lambda (n) (if (= n 0) 1 (* n ((fact0 fact0) (- n 1))))))) ((fact0 fact0) 5) ; The difference between `fact1' and `fact0' is slight. `fact1' expects to be to be passed `fact', or a suitable ; facsimile, because it plans to call its argument as a subcontractor. `fact0' expects to be passed `fact0', ; or a suitable facsimile, because it plans to apply its argument to itself to produce its subcontractor. ; So we have to jigger `fact1' to get it to apply its argument to itself before calling it. ; The problem here is very like the problem of converting a radian-eating function into a degree eating function. ; To do this, we must arrange to multiply by pi/180 before eating the argument. No problem: (define degrad (lambda (f) (lambda (x) (f (* x (/ 3.1415926535897932384626433832795028841971693993751 180)))))) ((degrad sin) 45) ((degrad tan) 45) ; The same approach should work here to convert fact1 into a facsimile of f0. (define X (lambda (f1) (lambda (f0) (f1 (f0 f0))))) ;(((X fact1) (X fact1)) 6) ; The line above is commented out because this, my friends, is where THE SHIT HITS THE FAN! ; Scheme gets into an infinite loop when it tries to evaluate (f0 f0). Trace it through and you'll ; see why. In the process you'll discover the BIG LIE: Functions in Scheme are NOT treated as ; objects on a par with atoms and lists. Nor could they be, because functions are (potentially) infinite ; sets of ordered pairs, and scheme insists on evaluating the arguments to a function before applying it. ; But it could never determine a whole infinite set of ordered pairs. So it can't use a function as an ; argument to another function without treating it differently than it would a number or a list. It's a sad, ; sad story, which I myself only begin to understand... ; The good news is that we can avoid the infinite loop with the aid of ; LAMBDA - The Ultimate Cop-Out! (define X (lambda (f1) (lambda (f0) (f1 (lambda (n) ((f0 f0) n)))))) (((X fact1) (X fact1)) 6) ; We can use U to avoid the redundancy. ((U (X fact1)) 7) ; Let's plug in the definitions for U and X. ( ((lambda (f0) (f0 f0)) ((lambda (f1) (lambda (f0) (f1 (lambda (n) ((f0 f0) n))))) fact1)) 8) ; Now isolate the argument `fact1'. ( ((lambda (f1) ((lambda (f0) (f0 f0)) (lambda (f0) (f1 (lambda (n) ((f0 f0) n)))))) fact1) 9) ; This hair-raising compound lambda-expression represents the composition `U after X'. ; It is called `Y', or `the Y combinator'. ; It turns prototypes in the style of `fact1' into recursive functions. (define Y (lambda (f1) ((lambda (f0) (f0 f0)) (lambda (f0) (f1 (lambda (n) ((f0 f0) n))))))) ((Y fact1) 10) ; Let's write it all out. ( ((lambda (f1) ((lambda (f0) (f0 f0)) (lambda (f0) (f1 (lambda (n) ((f0 f0) n)))))) (lambda (fact) (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))) 11) ; Taking into account how we've arrived at this, we can see how the various parts of Y work. ; The part (lambda (f1) ...) means we take in a `fact1' style argument. ; (lambda (f0) (f1 (lambda (n) ((f0 f0) n)))) converts that `fact1' style argument to `fact0' style. ; It's really just (lambda (f0) (f1 (f0 f0))), with (lambda (n) (... n)) thrown in to stop the bleeding. ; Then (lambda (f0) (f0 f0)) feeds `fact0' to itself. And away we go. ; Here comes the acid test. (map ((lambda (f1) ((lambda (f0) (f0 f0)) (lambda (f0) (f1 (lambda (n) ((f0 f0) n)))))) (lambda (fib) (lambda (n) (if (or (= n 0) (= n 1)) 1 (+ (fib (- n 1)) (fib (- n 2))))))) '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)) ; We close with a question. Given how much more complex Y is than U, why don't we just stick with U ; and reconcile ourselves to writing `(fib0 fib0)' in place of `fib' in our prototype functions?