Y Combinator 的 Scheme 实现

By guenchi at 2018-02-06 • 0人收藏 • 317人看过

Y Combinator 的 Scheme 实现

什么是 Y Combinator?

用 Scheme 的观点来看,Y 就是这样一个操作符,它作用于任何一个 (接受一个函数作为参数的) 函数 F,就会返回一个函数 X。再把 F 作用于这个函数 X,还是得到 X。所以 X 被叫做 F 的不动点(fixed point)。

所以我们常常见到 "(Y F) = (F (Y F))" 这种说法。比如在这里:

../images/scheme_shield.png

…… 为了防止误人子弟,你最好先找本 Lambda Calculus 的书来看 看。Lambda calculas 里的 Y Conbinator 要广泛的多。F 不一定只 接受一个函数作为参数。Fixed point 不但可以是函数,还可以是任 何 lambda term。

因为Scheme 是一种实际的语言,跟纯粹的理论还是有一定差距。如 果要完全实验 lambda calculas, 最好使用一些专用的 lambda 计算 器。比如:http://okmij.org/ftp/Computation/lambda-calc.html 就有多种语言实现的 lambda 计算器。

在 Scheme 里,通常 Y Combinator 是用来实现一些很 hack 的编程 技巧,用来定义“没有名字的递归”。

用 Scheme 来定义 Y Combinator

(define Y
  (lambda (F)
    (let ((W (lambda (x) 
               (F (lambda arg (apply (x x) arg))))))
      (W W))))

看起来很像讲 lambda calculas 的书里的定义。

测试

我们先定义一个函数 F*,它的不动点是一个 factorial 函数。

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

然后运行:

((Y F*) 5)

得到 120. 再运行:

((F* (Y F*)) 5)

结果还是 120。这说明我们的定义正确。

参考资料

Franco 教授的网页

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

叙述了这个 Y Combinator 的定义是怎样一步一步写出来的,非常启 发人的思维。看了这些推导,你可能就体会到当初 Fixed Point Theorem 是怎么想出来的。

不过他的定义有一个问题,那就是按照他原来的定义,不动点函数只 能接受一个参数。


登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...