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