# Y-Combinator

https://eecs.ceas.uc.edu/~franco/C511/html/Scheme/ycomb.html

一些情况下不需要给过程命名. 

```scheme
((lambda (x) (+ x 1)) 6)
```

递归函数能不命名么? 以阶乘函数`fact`为例, 下面逐步移掉对`fact`对名字的使用.

```scheme
(define fact
  (lambda (x)
    (if (zero? x)
        1
        (* x (fact (- x 1))))))
```


第一步把名字当做参数传入.

```scheme
(define op-maker
  (lambda (op)
    (lambda (x y)
      (op x y))))
```

用在阶乘这里, 即:

```scheme
(define fact-maker
  (lambda (op)
    (lambda (x)
      (if (zero? x)
          1
          (* x (op (- x 1)))))))
> ((fact-maker fact-maker) 3)
*: contract violation
  expected: number?
  given: #<procedure:.../ycombinator.rkt:15:4>
  argument position: 2nd
  other arguments...:
```

不符合调用规则, 实际是不能工作的.

修改程序:

```scheme
(define fact-maker
  (lambda (op)
    (lambda (x)
      (if (zero? x)
          1
          (* x ((op op) (- x 1)))))))
> ((fact-maker fact-maker) 3)
6
```

现在`fact`等价为`(fact-maker fact-maker)`, 原地替换`fact-maker`则阶乘函数可以等价写为:

```scheme
(define fact
  ((lambda (op)
     (lambda (x)
       (if (zero? x)
           1
           (* x ((op op) (- x 1))))))
   (lambda (op)
     (lambda (x)
       (if (zero? x)
           1
           (* x ((op op) (- x 1))))))))
```

这里实现了一个不需要名字的fact函数.

下面演示使用`Y-combinator`来泛化到所有递归函数上 .

先把计算阶乘的逻辑剥离出来.

```scheme
(define F
  (lambda (n)
    (if (zero? n)
        1
        (* n ((op op) (- n 1))))))
```

我们知道:

```scheme
(f arg) <=> ((lambda (x) (f x)) arg)
```

所以`((op op) (- n 1))`可以改写成:

```scheme
((lambda arg) ((op op) arg) (- n 1))
```

替换`F`中的`((op op) ...)`, 得到.

```scheme
(define F
  (lambda (func-arg)
    (lambda (n)
      (if (zero? n)
          1
          (* n (func-arg (- n 1)))))
    (lambda (arg) ((op op) arg))))
```

现在用改写过的`F`替换掉上面`fact`中的对应逻辑,

```scheme
(define fact
  ((lambda (op)
     ((lambda (func-arg)
       (lambda (n)
         (if (zero? n)
             1
             (* n (func-arg (- n 1))))))
      (lambda (arg) ((op op) arg))))
   (lambda (op)
     ((lambda (func-arg)
       (lambda (n)
         (if (zero? n)
             1
             (* n (func-arg (- n 1))))))
      (lambda (arg) ((op op) arg))))))
```

留意`((lambda (func-arg) ...))`这部分代码是阶乘函数的核心逻辑.将它提出来.

```scheme
(define F*
  (lambda (func-arg)
       (lambda (n)
         (if (zero? n)
             1
             (* n (func-arg (- n 1)))))))
```

那么`fact`可以定义为:

```scheme
(define fact
  ((lambda (op)
     (F* (lambda (arg) ((op op) arg))))
   (lambda (op)
     (F* (lambda (arg) ((op op) arg))))))
```

现在业务逻辑和无命名递归的结构剥离了出来. 

将`fact`的代码泛化. 得到Y组合子.

```scheme
(define Y
  (lambda (X)
    ((lambda (op)
       (X (lambda (arg) ((op op) arg))))
     (lambda (op)
       (X (lambda (arg) ((op op) arg)))))))
```

`fact`函数用`Y`来表达出来, 即:

```scheme
(define fact (Y F*))
```

我们使用Y组合子定义`findmax`函数. 

```scheme
(define M
  (lambda (func-arg)
    (lambda (xs)
      (if (null? xs)
          'none
          (if (null? (cdr xs))
              (car xs)
              (max (car xs) (func-arg (cdr xs))))))))
(define findmax (Y M))
```