https://liujiacai.net/blog/2016/02/22/recursion-without-name/

https://mvanier.livejournal.com/2897.html

## 问题的引入

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

## 简单的想法

(define sort-of-factorial
(lambda (n)
(if (= n 0)
1
(* n (<???> (- n 1))))))

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

(almost-factorial f)

(define factorialB (almost-factorial factorialA))

(define factorialA (almost-factorial factorialA))

## 不动点

### 引入不动点

(define identity (lambda (x) x))
(define factorial0 (almost-factorial identity))

(factorial0 0)
==> ((almost-factorial identity) 0)
==> 1

(factorial0 1)
==> ((almost-factorial identity) 1)
==> (* 1 (identity 0))
==> 0

(define factorial1 (almost-factorial factorial0))

(factorial1 0)
==> 1

(factorial1 1)
==> ((almost-factorial factorial0) 0)
==> (* 1 (factorial0 0))
==> 1

(factorial1 2)
==> ((almost-factorial factorial0) 1)
==> (* 2 (factorial0 1))
==> 0

(define factorial{k} (almost-factorial factorial{k-1}))

(define factorial-infinity
(almost-factorial
(almost-factorial
(almost-factorial
...))))

factorial-infinity = (almost-factorial factorial-infinity)

## Y运算符

### 引入Y运算符

(Y f) = fixpoint-of-f

(f fixpoint-of-f) = fixpoint-of-f

factorial-infinity = (Y almost-factorial)

f = (Y almost-f)

### 定义（惰性求值）

(Y f) = fixpoint-of-f = (f fixpoint-of-f) = (f (Y f))

(define (Y f) (f (Y f)))

; lambda表达式
(define Y
(lambda (f)
(f (Y f))))

(Y 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 (Y almost-factorial))

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

==>

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

==>

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

### 定义（非惰性求值）

#### 引入Y运算符

(define (Y f) (f (Y f)))

(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))

(define (part-factorial self n)
(if (= n 0)
1
(* n (self (- n 1)))))

(part-factorial part-factorial n)
; 参数数量不匹配
(* n (part-factorial (- n 1)))

(define (part-factorial self n)
(if (= n 0)
1
(* n (self self (- n 1)))))

(define factorial (part-factorial part-factorial))
(factorial n) = n!

(define (part-factorial self)
(lambda (n)
(if (= n 0)
1
(* n ((self self) (- n 1))))))

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

(let ((x <expr1>)) <expr2>)
==> ((lambda (x) <expr2>) <expr1>)

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

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

(define (part-factorial self)
(almost-factorial
(self self)))

(define factorial (part-factorial part-factorial))

(define part-factorial
(lambda (self)
(almost-factorial
(self self))))

(define factorial
(let ((part-factorial (lambda (self)
(almost-factorial
(self self)))))
(part-factorial part-factorial)))

; 用x替换part-factorial
(define factorial
(let ((x (lambda (self)
(almost-factorial (self self)))))
(x x)))

(define factorial
((lambda (x) (x x))
(lambda (self)
(almost-factorial (self self)))))

; 用x替换self
(define factorial
((lambda (x) (x x))
(lambda (x)
(almost-factorial (x x)))))

(define (make-recursive f)
((lambda (x) (x x))
(lambda (x) (f (x x)))))

(define factorial (make-recursive almost-factorial))

(define (Y f)
((lambda (x) (x x))
(lambda (x) (f (x x)))))

#### 等价定义

(define Y
(lambda (f)
(f (Y f))))

(Y f) = (lambda (x) ((Y f) x))

; (define (Y f) (f (Y f)))
(define Y
(lambda (f)
(f (lambda (x) ((Y f) x)))))

; (define (Y f)
;   ((lambda (x) (x x))
;    (lambda (x) (f (x x)))))
(define Y
(lambda (f)
((lambda (x) (x x))
(lambda (x) (f (x x))))))

((lambda (x) (x x))
(lambda (x) (f (x x))))

==>
(let (y (lambda (x) (f (x x))))
(y y))

==>
((lambda (x) (f (x x))
(lambda (x) (f (x x)))

(define Y
(lambda (f)
((lambda (x) (f (x x)))
(lambda (x) (f (x x))))))

#### 验证不动点性质

(Y f) = (f (Y f))

(Y f)
= ((lambda (x) (f (x x)))
(lambda (x) (f (x x))))
= (let (y (lambda (x) (f (x x))))
(f y y))
= (f ((lambda (x) (f (x x)))
(lambda (x) (f (x x)))))
= (f (Y f))

## 小结

(define f (F1 f))

f = (F2 f)

(define f (Y F2))

(define Y
(lambda (f)
(f (lambda (x) ((Y f) x)))))

(define Y
(lambda (f)
((lambda (x) (x x))
(lambda (x) (f (x x))))))

(define Y
(lambda (f)
((lambda (x) (f (x x)))
(lambda (x) (f (x x))))))