y combinator推导

ycombinator.rkt

#lang racket
;;定义阶乘函数
(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

;;由于我们不能使用define，那么把fact作为参数名
(lambda (f)
  (lambda (n)
    (if (= n 1) 1
        (* n (f (- n 1))))))

;;如果可以命名，可以把这个东西叫meta-fact
;;meta-fact接受一个函数作为参数，返回一个计算阶乘的函数
(define meta-fact
  (lambda (f)
    (lambda (n)
      (if (= n 1) 1
          (* n ((f f) (- n 1)))))))

;;其实meta-face接受的参数是它自己
((meta-fact meta-fact) 5) ;;120

;;好吧，故事继续回到我们不能使用define
;;(meta-fact meta-fact)需要这样写
((lambda (f)
    (lambda (n)
      (if (< n 2) 1
          (* n ((f f) (- n 1))))))
 (lambda (f)
    (lambda (n)
      (if (< n 2) 1
          (* n ((f f) (- n 1)))))))

;;提取重复的操作
((lambda (x) (x x))
 (lambda (f)
    (lambda (n)
      (if (< n 2) 1
          (* n ((f f) (- n 1)))))))

;;把(f f)用一个参数g代替
((lambda (x) (x x))
 (lambda (f)
   ((lambda (g)
      (lambda (n)
        (if (= n 1) 1
            (* n (g (- n 1))))))
        (f f))))

;;call-by-value在这一步会死循环的
;;做一个变换(f f) -> (lambda (v) ((f f) v))
((lambda (x) (x x))
 (lambda (f)
   ((lambda (g)
      (lambda (n)
        (if (= n 1) 1
            (* n (g (- n 1))))))
        (lambda (v) ((f f) v)))))
   
;;把中间那一部分提取出来，用参数F替换
((lambda (F)
  ((lambda (x) (x x))
   (lambda (f)
     (F (lambda (v) ((f f) v))))))
 (lambda (g)
      (lambda (n)
        (if (< n 2) 1
            (* n (g (- n 1)))))))

;;上面的那一部分就是Y
(lambda (F)
  ((lambda (x) (x x))
   (lambda (f)
     (F (lambda (v) ((f f) v))))))