A simple Y-combinator deduction.

ycomb.rkt

#lang racket

; a simple example to deduce Y-combinator for factorial function
; author: Wei Chen([email protected])

; 1. 
; we can use lambda extraction to get reference to self
(define f1 
  (lambda (fac)
    (lambda (x)
      (if (= 0 x)
          1
          (* x
             (fac (sub1 x)))))))

; 2. 
; step 1 is not truly factorial, it only receives an argument, then returns the 'fac' function. 
; so what do we pass to it?
(define f2 
  ((lambda (fac)
     (lambda (x)
       (if (= 0 x)
           1
           (* x
              (fac (sub1 x))))))
   (lambda (fac)
     (lambda (x)
       (if (= 0 x)
           1
           (* x
              (fac (sub1 x))))))))

; 3. 
; step 2 is not enough, when we call with parameter larger than 0, it will crash. Since 
; when we execute the 'else' branch of if expression, the 'fac' is not a true 'fac', it's
; actually a 'fac-maker'. when we need a true 'fac' function, we call 'fac-maker' with something.
; so with what? 'fac-maker' self!!!
(define f3
  ((lambda (fac-mk)
     (lambda (x)
       (if (= 0 x)
           1
           (* x ((fac-mk fac-mk) (sub1 x))))))
   (lambda (fac-mk)
     (lambda (x)
       (if (= 0 x)
           1
           (* x ((fac-mk fac-mk) (sub1 x))))))))

; 4.
; notice we call a function with itself, this can be abstracted as follows. 
(define f4
  ((lambda (fac-mk)
     (fac-mk fac-mk))
   (lambda (fac-mk)
     (lambda (x)
       (if (= 0 x)
           1
           (* x ((fac-mk fac-mk) (sub1 x))))))))

; 5. 
; we also want to abstrct out the (fac-mk fac-mk) in fac-mk's definition.
; while this will not work, why? using substitution model!
;; not runnable
;((lambda (fac-mk)
;   (fac-mk fac-mk))
; (lambda (fac-mk)
;   ((lambda (fac)
;      (lambda (x)
;        (if (= 0 x)
;            1
;            (* x (fac (sub1 x)))))) 
;    (fac-mk fac-mk))
;   ))

; 6.
; before we make it work, let's abstract the recursive function out!
; also not runnable
;((lambda (f)
;   ((lambda (fac-mk)
;      (fac-mk fac-mk))
;    (lambda (fac-mk)
;      (f (fac-mk fac-mk)))))
; (lambda (fac)
;   (lambda (x)
;     (if (= 0 x)
;            1
;            (* x (fac (sub1 x)))))))

; 7.
; use eta reduction to stop infinite lambda application. tada!!
(define f7
  ((lambda (f)
     ((lambda (fac-mk)
        (fac-mk fac-mk))
      (lambda (fac-mk)
        (lambda (x) 
          ((f (fac-mk fac-mk)) x)))))
   (lambda (fac)
     (lambda (x)
       (if (= 0 x)
           1
           (* x 
              (fac (sub1 x))))))))