; `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?