evolution of Y combinator

thought-in-y-combinator.rkt

#lang racket

;;; a definition of Y(notice: it's not Y Combinator),
;;; which can run in a strict language
; (Y f) = (f (Y f)) = (f (lambda (x) ((Y f) x)))
(define Y
  (lambda (f)
    (f (lambda (x) ((Y f) x)))))

(define almost-factorial
  (lambda (f)
    (lambda (n)
      (if (= n 0) 1
            (* n (f (- n 1)))))))

(define factorial
  ((lambda (f)
     (f (lambda (x) ((Y f) x))))
   almost-factorial))

(define (part-factorial self n)
  (if (= n 0) 1
      (* n (self self (- n 1)))))
; this will work: (part-factorial part-factorial 5)

; but it is far from the original way of calling factorial function.
; So ...
(define (part-factorial self)
  (lambda (n)
    (if (= n 0) 1
        (* n ((self self) (- n 1))))))
; (part-factorial part-factorial 5) ==> 120
; (define factorial (part-factorial part-factorial))

;; abstract (self self) to f
(define (part-factorial self)
  (let ((f (self self)))
    (lambda (n)
      (if (= n 0) 1
          (* n (f (- n 1)))))))
; the follows works only for a lazy language, not a strict language
; (define factorial (part-factorial part-factorial))

; any let expression can be converted into an equivalent lambda expression using:
; (let (x <expr1>) <expr2>) ==> ((lambda (x) <expr2>) <expr1)
; So ...
(define (part-factorial self)
  ((lambda (f)
    (lambda (n)
      (if (= n 0) 1
          (* n (f (- n 1))))))
   (self self)))
; ===>
(define (part-factorial self)
  (almost-factorial
   (self self)))
; (define factorial (part-factorial part-factorial))

; ===>
(define part-factorial
  (lambda (self)
    (almost-factorial
     (self self))))

; then we can rewrite factorial to:
(define factorial
  (let ((part-factorial (lambda (self)
                          (almost-factorial (self self)))))
    (part-factorial part-factorial)))
; which can be rewritten a little more concisely, by let ==> lambda
(define factorial
  ((labmda (x) (x x))
   (lambda (self)
     (almost-factorial (self self)))))
; finally, we get here.

(define (make-recursive f)
  ((lambda (x) (x x))
   (lambda (x)
     (f (x x)))))
(define factorial (make-recursive almost-factorial))
; the make-recursive is the lazy Y combinator,
; also known as the normal-order Y Combinator.
(define (Y f)
  ((lambda (x) (x x))
   (lambda (x) (f (x x)))))
; ===>
(define Y
  (lambda (f)
    ((lambda (x) (f (x x)))
     (lambda (x) (f (x x))))))
; for a given function f (which is a non-recursive function like almost-factorial),
; the corresponding recursive function can be obtained
; first by computing (lambda (x) (f (x x))),
; and then applying this lambda expression to itself.
; This is the usual definition of the normal-order Y combinator.

;;; How to check it will do the right thing
; checking (Y f) = (f (Y f))

;;; The strict Y Combinator

; start from
(define (part-factorial self)
  (let ((f (self self)))
    (lambda (n)
      (if (= n 0) 1
          (* n (f (- n 1)))))))

; ===>
(define (part-factorial self)
  (let ((f (lambda (y) ((self self) y))))
    (lambda (n)
      (if (= n 0) 1
          (* n (f (- n 1)))))))
; this one can work in a strict language.

; At last, the strict(or applicative-order) Y Combinator is
(define Y
  (lambda (f)
    ((labmda (x) (x x))
     (lambda (x) (f (lambda (y) ((x x) y)))))))
; then (define factorial (Y almost-factorial))