Church 数

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

Church 数 

我们从一道习题开始,解决 Church 数的各种定义和操作。

一道习题

SICP 习题 2.5:

Church 数(church number)用 Scheme 语言是这样定义的:

(define zero (lambda (f) (lambda (x) x)))
(define (1+ n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

这样,我们有了 “零”(zero) 和一个可以把一个 church 数加 1 的操作符 1+. 那么问题是:

  1. 我们怎样定义“一”(one)和“二”(two)?(不用 zero 和 1+)

  2. 我们怎样定义加法操作符 + ?

实验

上面的东西很抽象。只有做实验才能体会到它的中心思想。

我们先定义一个函数 f,用来作为 church 数的参数:

(define (f x) (cons 'x x))

然后用 1+ 和 zero 定义出 one 和 two。这违反了题目规则,但是 这可以让我们对问题的实质有更清晰的认识。

(define one (1+ zero))
(define two (1+ one))

那么

  • ((zero f) '()) 的结果是 '()

  • ((one f) '()) 的结果是 (x)

  • ((two f) '()) 的结果是 (x x)

分析

从上面的实验可以看出:

其实数“零”(zero) 是这样一个函数,它接受一个函数 f 作为参数, 然后返回一个函数,这个函数原封不动的把它的参数 x 返回。

1+ 的意思就是:不管参数 n 是怎样一个 church 数,返回这样一个 church 数:这个 church 数接受一个函数 f 作为参数,然后返回一 个函数,这个函数比 (n f) 对它的参数 x 多进行一次 f 操作。

一个 church 数就是这样一个函数,它接受一个函数 f 作为参数, 然后返回一个函数,这个函数对它的参数 x 进行某种数量的 f 操作, 然后返回结果。这个 f 操作的嵌套层数就是这个 church 数区别于 其它 church 数的特征。

答案

一和二

那么 one 和 two 就很好定义了。


(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

加法

加法就很简单了当 (b f) 对 x 嵌套执行 church 数 b 表示的次数 后,再用 (a f) 对这个结果嵌套 a 次 f.

(define (add a b)
  (lambda (f) (lambda (x) ((a f) ((b f) x)))))

为了让我的解释器的加法 "+" 能继续工作,我用了 add 这个名字。

来试一下:

(define three (add one two))
((three f) '())

结果是 '(x x x)。正确。

一个简化的定义

其实加法有一个更加简单的定义,但是这需要使用以前定义过的 1+ 操作:

(define (add2 a b) ((a 1+) b))

很简单吧。就是对 b 进行 a 次嵌套的 1+.

超纲内容

SICP 的习题只要求我们定义出加法,但是做完了之后似乎意犹未尽。 所以我们接着来把剩下的东西都定义出来吧。

乘法

更进一步,乘法如何定义呢?

(define (mul a b)
  (lambda (f) (lambda (x) ((a (b f)) x))))

它的意思是,通过两个 church 数,返回一个 church 数。这个 church 数接受一个函数 f 作为参数,返回一个函数。这个函数把 (a (b f)) 作用于它的参数 x。

这个 (a (b f)) 怎样理解呢?(b f) 实际上就是这样一个函数,它 对它的参数嵌套执行函数 f,嵌套的层数是 church 数 b 表示的数。 那么 (a (b f)) 就是这样一个函数,它对它的参数嵌套执行函数 (b f), 嵌套的层数是 church 数 a 表示的数。这样 (a (b f)) 实际上 就是这样一个函数,这个函数对它的参数嵌套执行 church 数 a 和 b 的积那么多次 f。

我们可以用这个乘法对 two 和 three 进行操作得到一个 six:

(define six (mul two three))
((six f) '())

((six f) '()) 的结果是 '(x x x x x x)。

乘方

乘方就更简单了:

(define (pow a b) (b a))

试一下:

(define eight (pow two three))
((eight f) '())

((eight f) '()) 结果是 '(x x x x x x x x).

布尔变量,判断语句和判零函数

布尔变量可以这样定义:

(define true
  (lambda (x y) x))

(define false
  (lambda (x y) y))

那么我们可以定义一个判断语句 if*:

(define if*
  (lambda (test a b) (test a b)))

那么 (if* true one two) 会得到 one. (if* false one two) 会得 到 two. 注意这个简单的 if* 必须明确写出两个判断的后果。

接着我们可以定义一些布尔操作符:与,或,非,蕴涵。

(define and*
  (lambda (a b) (if* a b false)))

(define or*
  (lambda (a b) (if* a true b)))

(define not*
  (lambda (x) (if* x false true)))

(define implies*
  (lambda (a b) (or* (not* a) b)))

我们可以接着定义一个永远为假的函数 always-false:

(define always-false
  (lambda (x) false))

接着我们就能定义一个能够判断一个 Church 数是不是“零”的函数:

(define is-zero?
  (lambda (n)
    ((n always-false) true)))

因为 always-false 只有对 true 嵌套执行 0 次的时候才能返回 true,否则返回 false.

pair

我们能定义出 cons, car 和 cdr 等 pair 操作,以及 null 和用来 判断null 的 null?*。这样我们就可以使用 pair 和 list 了。list 只不过就是最后一个 cdr* 是 null 的 pair.

为了不跟原来的操作符名字冲突, 我为它们每个都加一个 *.

(define cons*
  (lambda (a b)
    (lambda (c)
      (c a b))))

(define car*
  (lambda (pair)
    (pair true)))

(define cdr*
  (lambda (pair)
    (pair false)))

(define null
  (lambda (x) true))

(define null?*
  (lambda (d)
    (d (lambda (x y) false))))

下面是测试例子:

(define c1 (cons* one two))

(car* c1)
(cdr* c1)

(null?* null)
(null?* c1)

前驱 

我们定义一个函数 f*,它能够由 list (x) 得到 (x+1 x)。

(define f*
  (lambda (x)
    (cons* (1+ (car* x)) x)))

那么我们就可以定义前驱函数 pred 为:

(define pred
  (lambda (n)
    (if* (is-zero? n)
         zero
         (car* (cdr* ((n f*) (cons* zero null)))))))

(((pred three) f) '())

它从一个 (n n-1 n-2 ... zero) 的 list 里取出第二个元素。 如果我们把一个 church 数作用于这个 pred 函数,就可以得到某一 个数前面的离它有一段距离的那个数了。

测试例子:

(((pred three) f) '())
((((three pred) eight) f) '())

比较两个 church 数的大小

比较两个 church 数的大小可以有很多种办法,其中一种就是让一个 数在一个初值为 (false false) 的 list 前面嵌套 cons* 上 true。 然后然另一个数把这个生成的 list 不断的削减。如果削减到最底下, 它就能看到 false;说明第二个数比第一个大,反之,第二个数比第 一个小。

(define greater?*
  (lambda (a b)
    (car* ((b (lambda (z) (if* (car* z) (cdr* z) z)))
           ((a (lambda (z) (cons* true z))) (cons* false false))))))

(greater?* three two)

(greater?* two three)

减法和除法

这个似乎很难。lambda calculas 的发明者 Church 当年虽然设计出 了 Church number,却没能定义出减法和除法。

如果要用减法,我们首先要定义出带符号整数和负数……


登录后方可回帖

登 录
信息栏

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...