不动点组合子

2016-07-28
6分钟阅读时长
Scheme

相关服务条款和隐私政策(?)

不动点组合子只是函数式编程的理论基础, 并没有什么实用性

该用循环的时候就用循环, 该用递归的时候就用递归(而不需要知道Y组合子在哪里出现)

甚至可以说, 我们说见到的Lisp方言的底层并非由Y组合子实现而是图灵机模型实现:

因为我们的计算机根本就不是根据Lambda演算理论构建的

或者再简单的说, 这并不是一个用于编程的设定, 只是在数学层面让某些东西(Lambda演算)更加的"科学"(符合逻辑)

阅读下文视为你已经阅读过了上文, 对于浪费你n个小时研究一堆东西发现卵用没有而产生的精神损失不负任何责任

序

不动点组合子是一个神奇的设定, 他的作用简单说来只有一个, 那就是

用于计算（高阶）函数的不动点, 使得Lambda演算可以定义匿名递归函数。

那么, 高阶函数是什么? 不动点是什么? Lambda演算是什么? 匿名递归函数又是什么?

Lambda演算

所谓Lambda演算是一种计算模型[1]

在这种计算模型中, 一切都是函数, 甚至连数值都没有(详见church计数)

它具有和图灵机等价的计算能力, 但比起图灵机, Lambda演算 基本上 只依赖两条数学推理规则

匿名函数

比起这两条数学推理规则, 我们先看看Lambda演算中的函数是什么

我们先来看看我们说熟悉的数字

print (3+3)

我们如果是要求这两个数字一定是相同的, 我们可以写成这样

a = 3
print (a+a)

这里我们引入了变量的概念后才能做到, 那么如果假设没有变量呢?

print 3 (*2)

我们为了减少一条规则, 又不得不增加一条规则来弥补他所减少的东西

这也是我们说熟悉的演算, 比起"简洁", 我们更在乎他是否"方便"

而Lambda演算却恰好相反[2]

我们刚开始说定义的数是没有变量的定义的, 所以我们可以试试引入类似这样的函数, 也就是所谓的 「匿名函数」

那么他又应该长什么样呢?

我们又需要引入 「lambda」 这个符号, 比如平方函数sqr=x*x

我们可以写成(S-表达式表示)

(lambda (x) (* x x))

表示参数x, 执行并返回x*x

为了表示方便我们把他写成

(define sqr
  (lambda (x) (* x x)))
注意
这里的sqr并不是说我们要引入变量的设定, 而是为了让我们知道这个函数的作用是sqr 调用的时候, 我们可以简单的使用(sqr 2), 而不是用冗长但符合Lambda演算规则的
((lambda (x) (* x x)) 2)

再比如阶乘操作factorial, 我们的习惯是

(define (factorial x)
  (if (zero? x)
      1
      (* x (factorial (- x 1)))))

而使用lambda演算

(define factorial
  (lambda (x)
    (if (zero? x)
        1
        (* x (factorial (- x 1))))))

到这一步的时候, 我们发现函数定义出现了函数自己, 但没函数名又意味着无法直接引用函数自己

这个问题有点类似于上面的相同数值问题,

但是数值产生的问题仅仅是因为不方便(我们大可以使用 print 3+3 , print 4+4 来实现, 因为数值本身根本不能引发递归)

而这里如果不能实现递归的话我们也不能实现循环(循环我们可以认为是一种尾递归), 更不能说什么图灵机等价了

为了解决这个问题我们首先要引入Lambda的两个推理规则

Lambda的推理规则

Alpha变换

Alpha变换表达的是被绑定变量的名称是不重要的, 用代码来表示就是

;; f为任意函数(Lambda表达式)
(define fun-read-x (lambda (x) (f x)))
(define fun-read-y (lambda (y) (f y)))
;; fun-read-x fun-read-y 是eq(等价)的

尽管如此, 这条规则并非像他看起来这么简单, 注意参数影响的范围有些时候并不是那么容易, 比如对于

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

和下面这个是等价的

(lambda (y) (lambda (x) x) y)

Beta规约

Beta规约表达的是Lambda表达式的作用, 他在参数被给了一个值后能够被算出来

;; f为任意函数(Lambda表达式)
((lambda (x) (f x)) v)
(f v)
;; 以上两句等价

不允许任何beta归约的Lambda表达式被称为Beta范式

不过要注意

并非所有的Lambda表达式都存在与之等价的Beta范式
若存在, 则对于相同的形式参数命名而言是唯一的

对于第一条, 我们可以构造一个可以用Beta规约无限展开的Lambda表达式(使用不动点组合子就会发现其实很容易构造)

第二条由 Church-Rosser定理[3] 证明

Eta变换

Eta变换表达的是 外延性 的概念, 在这里外延性指的是, 两个函数对于所有的参数得到的结果都一致, 当且仅当它们是同一个函数

;; f为任意函数(Lambda表达式)
(lambda (x) (f x))
f
;; 以上两句等价

这个看起来跟Beta是一样的, 可以在没有给出具体参数的时候化简, 所以一般也可以省去这条规则

不动点组合子

Y Combinator

Y组合子又叫"不动点组合子"

它接受一个函数, 返回的是这个函数的不动点

里面的"不动点"指的是高阶函数的 不动点

关于为什么递归就需要Y组合子, 来看一下递归的定义

函数的递归就是函数直接或间接地调用自身

那么Y组合子给出的方案就是 先把自己"算出来"以方便自己调用自己

(define (Y F)
  (let ([W
         (lambda (x)
           (F (lambda arg (apply (x x) arg))))])
;; (F (lambda arg (apply (x x) arg)))其实就是(F x x),
;; 不过写成前面那种形式可以避免计算的时候陷入无穷的递归
    (W W)))

验证 

(define (Y F)
  (let ([W
         (lambda (x)
           (F (lambda arg (apply (x x) arg))))])
    (W W)))
;; =>
(define Y
  (lambda (F)
    ((lambda (x) (F (lambda arg (apply (x x) arg))))
     (lambda (x) (F (lambda arg (apply (x x) arg)))))))
(Y g)
;; beta规约 =>
((lambda (x) (g (lambda arg (apply (x x) arg))))
   (lambda (x) (g (lambda arg (apply (x x) arg)))))
;; alpha变换 =>
(((lambda (y) (g (lambda arg (apply (y y) arg))))
   (lambda (x) (g (lambda arg (apply (x x) arg))))) 5)
;; beta规约 =>
(g (lambda arg
       (apply ((lambda (x) (g (lambda arg (apply (x x) arg))))
               (lambda (x) (g (lambda arg (apply (x x) arg)))))
              arg)))
;; scheme语法化解 =>
(g ((lambda (x) (F* (lambda arg (apply (x x) arg))))
      (lambda (x) (F* (lambda arg (apply (x x) arg))))))
;; =>
(g (Y g))

高阶函数

上面一直没有提到, 但是我们已经使用了高阶函数, 并且似乎也没有违反我们的直觉

现在我们给出高阶函数的定义

所谓高阶函数是指这样的一种函数, 它接受一个函数作为参数, 返回值也是一个函数

这跟匿名函数的递归有什么关系呢

我们不妨重新来想想匿名函数递归的策略:

我们在函数里面, 对函数外的信息能知道的只有两个, 一是函数的名字, 还有一个是函数的参数

既然函数没有名字, 那么我们只有尝试从函数的参数里获得需要的信息了, 所以我们需要构造高阶函数G, 使它满足 (G f) = f

对于这个函数, 需要干两件事: 找到G, 找到解(G f)=f的办法

找到G

寻找G很简单, 既然我们想让 (G f) = f , 那么把上面f定义中关于f的引用参数化就可以了

(G (f x))
;; =>
(lambda (f) ;; 阶乘
  (lambda (x)
    (zero? x)
    1
    (* x (f (- x 1)))))

函数G接受参数 (f x), 输出是一个参数为x的函数, 而它的定义中没有关于自身的引用

实际上, 这种构造方法可以用于构造任意递归函数的G

找到解(G f)=f的办法

求解方程 (G f) = f 的办法我们已经完成了, 也就是使用Y Combinator

匿名函数递归

不动点组合子的使用方式

先来看使用不动点组合子后函数的形式

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

根据之前不动点组合子的推理可以得到以下过程

((Y F*) 5)
;; =>
((F* (Y F*)) 5)
;; =>
((lambda (n)
    (if (zero? n)
        1
        (* n ((Y F*) (- n 1))))) 5)
;; =>
(if (zero? 5)
    1
    (* 5 ((Y F*) (- 5 1))))
;; =>
(* 5 ((Y F*) 4))
;; => .... =>
(* 5 (* 4 (* 3 (* 2 (* 1)))))
;; =>
120

递归

至此我们已经可以容易的写出匿名函数的递归形式了(其实也就是把匿名函数作为参数调用)

(define F
  (lambda (f)
    (lambda (x)
      (if (zero? x)
          1
          (* x (f (- x 1)))))))
(define fact (Y F))
;; test
(fact 5) ;; => 120

Footnotes

[1] 这是一个优美的计算模型, 整个Lambda演算只用简单的两种操作(alpha变换和beta规约)做到 图灵完备 (图灵机具有相同计算能力), 或者更通俗的讲就是与现在的计算机的 计算能力 等价 [2] 这大概也是为什么他不能流行的原因之一吧.. [3] 当且仅当两个表达式等价时, 它们会在形式参数换名后得到同一个范式

#Scheme
上一页 Macro
下一页 技巧向

相关

CPS变换
Lambda表达式
Macro
技巧向