;;-----------------------------------------------------------------
;; 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))