[翻译]Y组合子

发表于: 2017-10-11 17:59 3097

[翻译]Y组合子

阳春

2017-10-11 17:59

3097

原文:http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

译者注：严格意义上本文不能算翻译。本人国庆期间读了《The Little Schemer》，第九章的Y组合子很有意思，为了加深理解又找到上面的文章。参照这篇文章的代码和思想，写出本文。说明一下，《The Little Schemer》的代码皆可以在Racket(http://www.racket-lang.org/)上面跑，语言选R5RS即可。本文大部分代码与原文代码稍微有点不同，使用了《The Little Schemer》中的cond-else格式，不是原文的if格式。

Y组合子

从+1开始

(define add1
  (lambda (n)
    (+ n 1)))

正常调用

(add1 1)

匿名调用，就是用函数实体替代函数名。

((lambda (n)
    (+ n 1)) 1)

或者，把函数当成参数

((lambda (f)
   (f 1))
 (lambda (n)
    (+ n 1)))

以上说明，在不使用递归的情况下，有没有函数名对lambda表达式的使用是没有什么影响的，那么现在思考，在没有define的情况下，函数可以进行递归调用吗。

经典的递归函数：

(define fact
  (lambda (n)
  (cond
    ((= n 0) 1)
    (else (* n (fact (- n 1)))))))

这是用于计算阶乘的经典递归函数。考虑去掉define，那么应该构建一个能生成该函数的函数。并且该函数不再有递归。先考虑生成：

(define fact-maker
  (lambda (procedure)
    (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n ((procedure procedure) (- n 1))))))))

其实就是令g(g)等于f，构建一个函数，并使用自身作为参数，生成f。

（那么假设不使用自己作为参数呢，会生成什么玩意。。）

调用：

((fact-maker fact-maker) 5)

那么函数体其实变成了(fact-maker fact-maker)，代入函数体，也就是：

(define new-fact
((lambda (procedure)
    (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n ((procedure procedure) (- n 1)))))))
  (lambda (procedure)
    (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n ((procedure procedure) (- n 1)))))))))

那么

(new-fact 5)

或者

(((lambda (procedure)
    (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n ((procedure procedure) (- n 1)))))))
  (lambda (procedure)
    (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n ((procedure procedure) (- n 1)))))))) 5)

无define函数

都可以调用该函数，注意，上面的函数已经没有define了。

怎么理解上面这个东西，其实就是原来的f(x)=x*f(x-1)，变成了

f(x)=x*g(g)(x-1)，(高阶函数：接受一个或多个函数作为输入，输出一个函数)接下来的问题是怎么推而广之，抽象化之，通用化之。

抽象

考虑主体部分：

(define F
  (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n ((procedure procedure) (- n 1)))))))

其中(procedure procedure)部分,应用参数变换(f arg)到((lambda (x)(f x)) arg)

(define F
  (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n (
                (lambda (arg) ((procedure procedure) arg) (- n 1))
                                        ))))))

再把函数当成参数，应用变换(f x)到((lambda (g)(g x)) f)

(define F
  ((lambda (func-arg)
  (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n (func-arg (- n 1)))))))
                (lambda (arg) ((procedure procedure) arg ))))

代回new-fact

(define new-fact
((lambda (procedure)
    ((lambda (func-arg)
  (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n (func-arg (- n 1)))))))
                (lambda (arg) ((procedure procedure) arg ))))
  (lambda (procedure)
    ((lambda (func-arg)
  (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n (func-arg (- n 1)))))))
                (lambda (arg) ((procedure procedure) arg ))))))

整理出

(define F*
  (lambda (func-arg)
  (lambda (n)
      (cond
    ((= n 0) 1)
    (else (* n (func-arg (- n 1))))))))

变成

(define new-fact
((lambda (procedure)
    (F*
                (lambda (arg) ((procedure procedure) arg ))))
  (lambda (procedure)
    (F*
                (lambda (arg) ((procedure procedure) arg ))))))

这便是Y组合子的通用形式：

(define Y
  (lambda (X)
    ((lambda (procedure)
    (X (lambda (arg) ((procedure procedure) arg ))))
  (lambda (procedure)
    (X (lambda (arg) ((procedure procedure) arg )))))
    ))

调用

((Y F*) 7)

它的发现者是Haskell B. Curry

这是所有递归都可以用lambda表达式运算的证明，所以define在lambda运算中并非必要，只是语法糖。

不动点组合子参考WIKI

本该结束，再举个应用的例子，代码为原文提供

(define findmax
    (lambda (l)
      (if (null? l)
          'no-list
          (if (null? (cdr l))
              (car l)
              (max (car l) (findmax (cdr l)))))))

先像fact到F*一样创建M

(define M
    (lambda (func-arg)
      (lambda (l)
        (if (null? l)
            'no-list
            (if (null? (cdr l))
                (car l)
                (max (car l) (func-arg (cdr l))))))))

调用