0%

邱奇(Church)计数

发表于 更新于 分类于

引言

在计算机中，程序和数据并没有一个明显的分界线。数据可以被当作程序执行，程序也可以作为数据使用。

前者，很多语言提供了eval功能，将一段数据作为代码执行，比如JavaScript

1
eval("alert(1)")

这里我们主要说一下后者。

假设有一门语言，它可以定义函数，调用函数，但没有提供基础的数字类型，我们要如何使用函数来实现数字这一特性。

为了实现这个特性，我们要对这个特性有个初步的了解。

也就是，什么是数字？

在日常生活中，我们可以说，我有3个苹果、他打了我2下、口袋里空空如也1块钱也没有等等。

我们把数字作为计数的一个东西（循环定义？），换句话说是某一个东西（上述苹果）或某个动作（打人）的重复。

3个苹果就是有一个苹果，又有一个苹果，还有一个苹果；

打人2下，就是打一下，再打一下；

0就是空空如也，口袋没钱或者没执行打人这个动作。

如果一种语言可以定义函数、调用函数，那我们就可以通过定义一个函数，然后再调用这个函数表示数字，调用这个函数n次就代表数字n。

这种程序表示数字的方式叫邱奇编码，数字叫邱奇数。以lambda演算的发明者阿隆佐·邱奇命名。

定义数字

邱奇数就是函数被调用的次数。

为了使函数可以被调用多次，我们让这个函数调用的返回值能够被重新应用于这个函数。

换句话说，这个函数的参数和返回值的类型是相同的。

比如定义函数f，函数参数为a

那1就是f(a)，2就是f(f(a))，以此类推。

对于0，就是函数f，一次也没被调用。

没被调用怎么表示？

我们需要注意的是，数字是函数被调用的次数，在数字被使用前，函数是不能被调用的，否则调用完了数据也就看不到了。

有点像上发条的玩具，定义一个数字就是给玩具上好适当的发条，使用这个数字时，就是打开开关，玩这个玩具看被上了多少发条。

也就是说1，实际上是——接受一个函数和此函数的参数，并将这个参数应用到这个函数上。是一个动作，也是一个函数。

1
2
3
4
5
one = \f a -> f a

--two = \f a -> f (f a)
--two = \f a -> f . f a
two = \f -> f . f

另外一种语言，比如js写就是

1
2
3
4
5
6
7
var one = function(f, a) {
    return f(a)
}

var two = function(f, a) {
    return f(f(a))
}

既然如此，0就是

1
zero = \f a -> a

传进的函数f，被忽略

简单计算

数字是可以被计算的，如两个数字相加

先从简单的开始，加一个固定的数，如加1

按照之前的定义，加1，就是在原来的基础上，多执行一次相同的动作

比如：

1
addOne n f a = f (n f a)

为什么这样写？为什么会有三个参数，这分别代表什么意思？

在分析之前，我们先考虑下类型，邱奇数的类型、作为依据的被调用函数的类型以及计算函数参数的类型等

首先看被调用函数的类型

之前提到

为了使函数可以被调用多次，我们让这个函数调用的返回值能够被重新应用于这个函数。

换句话说，这个函数的参数和返回值的类型是相同的。

这里包含以下信息：

  1. 这个被调用函数是一个函数（显而易见）
  2. 这个函数可以接受一个参数
  3. 这个函数的参数类型与返回值类型相同，返回值可以被重新应用于此函数

也就是我们可以给此函数的类型起个别名，用以下表示

1
2
-- 接受一个类型a，返回一个类型a，别名Func
type Func a = a -> a

再看数字的类型

之前也有提到

1，实际上是——接受一个函数和此函数的参数，并将这个参数应用到这个函数上。是一个动作，也是一个函数。

同样，这包含以下信息：

  1. 这个邱奇数是一个函数
  2. 这个函数接受两个参数，一个是之前提到的被调用Func a，一个是可被应用到函数的参数，也就是a
  3. 考虑这个函数的返回值类型，由于函数体只是简单的将参数应用到被调用函数上，然后返回，所以其类型也就是Func a的返回值类型，同样是a

于是，我们就有了邱奇数的类型别名

1
2
-- 接受一个类型Func a和类型a，返回一个类型a，别名ChurchNum
type ChurchNum a = Func a -> a -> a

对于加一函数addOne

很明显，它接受一个类型ChurchNum a，返回另一个比它大1的另一个ChurchNum a

也就是

1
addOne :: ChurchNum a -> ChurchNum a

如果返回值类型不用邱奇数的类型别名，则为

1
addOne :: ChurchNum a -> (a -> a) -> a -> a

那addOne的实现

1
2
addOne :: ChurchNum a -> (a -> a) -> a -> a
addOne n f a = f (n f a)

可以理解为，addOne接受一个ChurchNum a类型的邱奇数，实参为n，返回另一个邱奇数，这个返回的邱奇数（类型为函数），接受两个参数，实参分别为f和a

到这里，两个邱奇数相加的函数add，也就很容易出来了

1
2
3
4
-- 类型，接受两个邱奇数，返回另一个邱奇数
add :: ChurchNum a -> ChurchNum a -> ChurchNum a
-- 实现，先将参数a应用于f n1次，再将结果应用f n2次
add n1 n2 f a = n2 f (n1 f a)

检验

我们一直在说邱奇数是一组动作，这组动作代表一个参数被应用于一个函数多少次

还举例说定义数字像是给玩具上发条，使用数字是让玩具动起来

那怎样才能让玩具动起来

我们可以用实际的例子来说明

比如我们可以说动作是——给一个字符串头上加一个字符'a'，动作的参数就是被加的字符串，初始参数这里我们用空字符串

1
2
let f = ('a':)
let a = ""

做几个简单的计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
-- 0，执行这个函数，看看结果，也就是让玩具动起来
Prelude> zero f a
-- 返回空字符串，也就是加字符a这个动作没有被执行
""
-- 通过0加一定义1
Prelude> one = addOne zero
-- 通过1加一定义2
Prelude> two = addOne one
-- 通过1 + 2定义3
Prelude> three = add one two
-- 查看3的结果
Prelude> three f a
-- 字符a被加到字符串头上3次
"aaa"

虽然我们之前假设系统中没有数字类型，但为了方便我们的验证，用其做一下检查是没问题的

我们可以说动作是——给一个系统数字加一，动作的初始参数是0

运行

1
2
3
4
5
6
7
let f = (+1)
let a = 0

one = addOne zero
two = addOne one
three = add one two
three f a

得到

1
2
3
4
5
6
7
8
Prelude> let f = (+1)
Prelude> let a = 0
Prelude>
Prelude> one = addOne zero
Prelude> two = addOne one
Prelude> three = add one two
Prelude> three f a
3