;;-----------------------------------------------------------------
;; Self application and the Y combinator!
;;-----------------------------------------------------------------

;; Self application: 
;; ((lambda (f) (f f)) (lambda (f) (f f))) ;; loops forever!

;;----
;; We wish to compute the fixed point of the following function;
;; we called this F in class.  Note that F is a function such 
;; that if you apply it to the length function -- the one we're trying
;; to define -- then it gives us back the length function we want!
;; F = 
(lambda (len)
  (lambda (xs) 
    (cond [(empty? xs) 0]
          [else (+ 1 (len (rest xs)))])))

(define explod (lambda (ys) (/ 1 0)))
;; (F explod) ; length fun for empty lists; explodes on bigger lists
;; (F (F explod)) ;; length fun for lists of length 0,1; explodes on bigger lists
;; (F (F (F explod))) ;; length fun for lists of length 0,1,2; explodes on bigger lists
;; ... continue applying F to infinity!

;;-----
;; The fixed point of a function f is some x such that (f x) = x

;; The fixed point of the above F is some length such that 
;; (F length) = length
;; So the fixed point of F is exactly the length function we want.

;;----
;; Now, suppose that Y is the fixed point finder.  That is (Y F) 
;; gives us the fixed point of F. 
;; How can we define F?

;;----
;; Let's posit that there is a Generator G such that G applied to
;; itself (i.e., (G G)) is the fixed point of F (which we called 
;; length above).  That means:
;;    (G G) = length = F(length) = (F (G G))

;; Now what is the data definition for a Generator?  Well, it's 
;; a function that takes a Generator as an argument and produces
;; the answer (fixed point) we are looking for. 
;;
;;    Generator = [Generator -> Ans]
;; 
;; Note that the above is a recursive data definition.

;; Let's define G: 
;; G = (lambda (g) (F (g g)) 
;; Then (G G) = ((lambda (g) (F (g g))) (lambda (g) (F (g g))))

;; But where does F come from? Let's make it an argument: 
;; The following is a function that takes an arbitrary f and 
;; returns the fixed point of f.  So this should be the fixed 
;; point finder Y that we wanted to define: 
(lambda (f) 
  ((lambda (g) (f (g g)))
   (lambda (g) (f (g g)))))

;; But there's a problem. Try running: 
#;
((lambda (f) 
   ((lambda (g) (f (g g)))
    (lambda (g) (f (g g)))))
 F) 
;; where F is the (lambda (len) ...) function we define at the beginning
;; It loops forever!  

;; The above isn't quite the Y (fixed point finder) we wanted to define!
;; We need one final trick, eta expansion: 
;; Note that sin = (lambda (x) (sin x))
;; And in general and function expression Exp = (lambda (x) (Exp x))
;; as long as x does not occur free in Exp.

;; Let's replace (f (g g)) in code above with (lambda (x) (f (g g)) x).
;; This gives us the real fixed point finder Y we wanted: 
(lambda (f) 
  ((lambda (g) (lambda (x) ((f (g g)) x)))
   (lambda (g) (lambda (x) ((f (g g)) x)))))

;; Y combinator, used to implement length
(((lambda (f) 
    ((lambda (g) (lambda (x) ((f (g g)) x)))
     (lambda (g) (lambda (x) ((f (g g)) x)))))
  (lambda (len)
    (lambda (xs) 
      (cond [(empty? xs) 0]
            [else (+ 1 (len (rest xs)))]))))
 '(a b c d))