简单易懂的程序语言入门小册子（4）：基于文本替换的解释器，递归，如何构造递归函数，Y组合子

时间：2014-04-21 12:48:35 阅读：660 评论：0 收藏：0 [点我收藏+]

递归。哦，递归。递归在计算机科学中的重要性不言而喻。递归就像女人，即令人烦恼，又无法抛弃。

先上个例子，这个例子里的函数double输入一个非负整数 $n$ ，输出 $2n$ 。

d o u b l e = λ n . (i f (i s z e r o n) 0 (+ 2 (d o u b l e (? n 1))))

${double} = \lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; ({double} \; (- \; n \; 1))))$

现在的问题是，这个递归函数在我们的语言里没法直接定义。我说的直接定义是指像这个用let表达式：

(l e t d o u b l e λ n . (i f (i s z e r o n) 0 (+ 2 (d o u b l e (? n 1)))) M)

$({let} \; {double} \; \lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; ({double} \; (- \; n \; 1)))) \; M)$ 把这个let表达式宏展开会看得更清楚些：

(λ d o u b l e . M λ n . (i f (i s z e r o n) 0 (+ 2 (d o u b l e (? n 1)))))

$(\lambda {double}.M \; \lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; ({double} \; (- \; n \; 1)))))$

λn.(if(iszeron)0(+2(double(?n1))))

$\lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; ({double} \; (- \; n \; 1))))$ 里的double是个自由变量。解释器求值到这里的时候，根本不知道double指的是什么函数。

如何构造递归函数

获得递归的一个关键是如何在函数体中找到自己（结合一开始的比喻，这句话好像蕴含了其他意义深远的意思）。一个简单的方法是在double上增加一个参数（一般就是第一个参数），把自己传入参数。把这个修改后的函数叫做mkdouble1吧。先不考虑mkdouble1的定义，先观察mkdouble1的行为。因为调用mkdouble1要把自己作为第一个参数传入，所以调用递归函数应该这样写：

((m k d o u b l e 1 m k d o u b l e 1) n)

$(({mkdouble1} \; {mkdouble1}) \; n)$ 也就是说，double就是

(mkdouble1mkdouble1)

$({mkdouble1} \; {mkdouble1})$ 。

d o u b l e = = (m k d o u b l e 1 m k d o u b l e 1) (λ v . (v v) m k d o u b l e 1)

$\begin{eqnarray*} {double} &=& ({mkdouble1} \; {mkdouble1}) \\ &=& (\lambda v.(v \; v) \; {mkdouble1}) \end{eqnarray*}$ 最后一步变换是为了让mkdouble1只出现一次。

现在来考虑mkdouble1的定义。在double上增加一个参数 $f$ ：

m k d o u b l e 1 = λ f . λ n . (i f (i s z e r o n) 0 (+ 2 (d o u b l e (? n 1))))

${mkdouble1} = \lambda f.\lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; ({double} \; (- \; n \; 1))))$ 函数调用的时候传入参数

$f$ 的是mkdouble1。也就是说

$f$ 代表的是mkdouble1。因此，函数体里递归调用的double用

(ff)

$(f \; f)$ 替换：

m k d o u b l e 1 = λ f . λ n . (i f (i s z e r o n) 0 (+ 2 ((f f) (? n 1))))

${mkdouble1} = \lambda f.\lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; ((f \; f) \; (- \; n \; 1))))$ 所以double的定义是：

d o u b l e = (λ v . (v v) λ f . λ n . (i f (i s z e r o n) 0 (+ 2 ((f f) (? n 1)))))

${double} = (\lambda v.(v \; v) \; \lambda f.\lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; ((f \; f) \; (- \; n \; 1)))))$ 这个定义可以用之前实现的解释器运行。测试一下：

‘(let double ((lambda 
v (v v))
              (lambda 
f
                (lambda 
n
                  (if 
(iszero n) 0 (+ 2 ((f f) (- n 1)))))))
   (double 4))
 
>> 8

Y组合子

这一小节比较理论，知道个思路就行了。所以我就随便写写。好学的人可以自己查资料（Programming Languages and Lambda Calculi, The Little Schemer）。

mkdouble1并不能让人很满意，因为它不优雅（都是时臣的错）。 mkdouble1递归调用的地方用的是 $(f \; f)$ ，而比较好看比较符合直觉的应该只有一个 $f$ 。定义这个所谓的比较好看的函数mkdouble如下：

m k d o u b l e = λ f . λ n . (i f (i s z e r o n) 0 (+ 2 (f (? n 1))))

${mkdouble} = \lambda f.\lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; (f \; (- \; n \; 1))))$ 我们希望能从mkdouble得到递归函数double。这是能做到的。只要在利用mkdouble1的double定义上做几个简单的推导就行了：

d o u b l e = = = = (λ v . (v v) λ f . λ n . (i f (i s z e r o n) 0 (+ 2 ((f f) (? n 1))))) (λ v . (v v) λ f . (λ f . λ n . (i f (i s z e r o n) 0 (+ 2 (f (? n 1)))) (f f))) (λ x . (λ v . (v v) λ f . (x (f f))) λ f . λ n . (i f (i s z e r o n) 0 (+ 2 (f (? n 1))))) (λ x . (λ v . (v v) λ f . (x (f f))) m k d o u b l e)

$\begin{eqnarray*} {double} &=& (\lambda v.(v \; v) \; \lambda f.\lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; ((f \; f) \; (- \; n \; 1))))) \\ &=& (\lambda v.(v \; v) \; \lambda f.(\lambda f.\lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; (f \; (- \; n \; 1)))) \; (f \; f))) \\ &=& (\lambda x.(\lambda v.(v \; v) \; \lambda f.(x \; (f \; f))) \; \lambda f.\lambda n.({if} \; ({iszero} \; n) \; 0 \; (+ \; 2 \; (f \; (- \; n \; 1))))) \\ &=& (\lambda x.(\lambda v.(v \; v) \; \lambda f.(x \; (f \; f))) \; {mkdouble}) \end{eqnarray*}$

$\lambda x.(\lambda v.(v \; v) \; \lambda f.(x \; (f \; f)))$ 被称作Y组合子，记为Y。然后有：

d o u b l e = (Y m k d o u b l e)

${double} = ({Y} \; {mkdouble})$

Y组合子可以用来构造递归函数。不过上面的定义在call-by-value的调用方式下会进入无限循环。具体原因就不讲了，只讲结论：问题出在 $(f \; f)$ 这里，对 $(f \; f)$ 做一个 $\eta$ 逆归约就行了。修改后的Y组合子记为 ${Y}_{v}$ ：

Y v = λ x . (λ v . (v v) λ f . (x (λ u . ((f f) u))

${Y}_{v} = \lambda x.(\lambda v.(v \; v) \; \lambda f.(x \; (\lambda u.((f \; f) \; u))$

测试一下。 Call-by-value的测试：

‘(let Y (lambda 
x
          ((lambda 
v (v v))
           (lambda 
f (x (lambda 
u ((f f) u))))))
   (let mkdouble (lambda 
f
                   (lambda 
n
                     (if 
(iszero n)
                         0
                         (+ 
2 (f (- n 1))))))
     ((Y mkdouble) 4)))
 
>> 8

Call-by-name的测试：

‘(let Y (lambda 
x
          ((lambda 
v (v v))
           (lambda 
f (x (f f)))))
   (let mkdouble (lambda 
f
                   (lambda 
n
                     (if 
(iszero n)
                         0
                         (+ 
2 (f (- n 1))))))
     ((Y mkdouble) 4)))
 
>> 8

简单易懂的程序语言入门小册子（4）：基于文本替换的解释器，递归，如何构造递归函数，Y组合子,布布扣,bubuko.com

简单易懂的程序语言入门小册子（4）：基于文本替换的解释器，递归，如何构造递归函数，Y组合子

原文：http://www.cnblogs.com/skabyy/p/3677836.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)