CS61A HW 03 Church Numerals

背景

The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. The purpose was to show that functions are sufficient to describe all of number theory: if we have functions, we do not need to assume that numbers exist, but instead we can invent them.

逻辑学家阿隆索·邱奇发明了一个利用函数表示自然数的系统。

Your goal in this problem is to rediscover this representation known as Church numerals. Here are the definitions of zero, as well as a function that returns one more than its argument:

我们的目标就是实现Church numerals，零和一的定义如下

def zero(f):
    return lambda x: x

def successor(n):
    return lambda f: lambda x: f(n(f)(x))

定义一和二

First, define functions one and two such that they have the same behavior as successor(zero) and successsor(successor(zero)) respectively, but do not call successor in your implementation.

首先我们要实现一和二的定义，在此之前我们可以分析一下零和一是怎么用函数表示的。

零的定义是\(F_{zero}(x)=x\)，我们将零带入successor可以得到\(F_{one}(x)=f(x)\)，那么显而易见二就是\(F_{two}(x)=f(f(x))\)，以此类推。那么一和二很容易就可以定义出来。

def one(f):
    """Church numeral 1: same as successor(zero)"""
    "*** YOUR CODE HERE ***"
    return lambda x: f(x)


def two(f):
    """Church numeral 2: same as successor(successor(zero))"""
    "*** YOUR CODE HERE ***"
    return lambda x: f(f(x))

将 church numeral 转化为整数

Next, implement a function church_to_int that converts a church numeral argument to a regular Python integer.

接下来是实现 church numeral 到整数的转化。

从这一题开始就渐渐开始难度了。由定义可知，church numeral 是一个 high-order function，返回的是函数本身，这个返回的函数的参数是一个函数，同时返回函数也是一个函数，参数是x。

\[\text{设}g(x)=-x \]

\[one(g)(1)=g(1)=-1 \]

\[two(g)(1)=g(g(1))=1 \]

由上面那个例子可能能帮助大家更直观的理解church numeral的构成，转化到整数最关键的是传入函数\(f\)如何构造。可以看到数字与函数调用的次数是一样的，如果每次调用的时候加1，就可以实现转化。

def church_to_int(n):
    """Convert the Church numeral n to a Python integer.

    >>> church_to_int(zero)
    0
    >>> church_to_int(one)
    1
    >>> church_to_int(two)
    2
    >>> church_to_int(three)
    3
    """
    "*** YOUR CODE HERE ***"
    return n(lambda x: x + 1)(0)

定义运算

Finally, implement functions add_church, mul_church, and pow_church that perform addition, multiplication, and exponentiation on church numerals.

最后来构造加法、乘法和乘方运算。

加法

我们还是先从公式的角度分析一下

\[n+m=\underbrace{f(f(\cdots(f}_{n+m}(x)))) \]

得到 n+m 只需有 n+m 个\(f\)复合就可以，即

\[\begin{aligned} n+m&=F_n(f)(F_m(f)(x))\\ &=\underbrace{f(f(\cdots(f}_{n}(F_m(f)(x)))))\\ &=\underbrace{f(f(\cdots(f}_{n}(\underbrace{f(f(\cdots(f}_{m}(x))))) \end{aligned}\]

def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.

    >>> church_to_int(add_church(two, three))
    5
    """
    "*** YOUR CODE HERE ***"
    return lambda f: lambda x: n(f)(m(f)(x))

乘法

\[n\times m=\underbrace{f(f(\cdots(f}_{n\times m}(x)))) \]

n是n个\(f(x)\)复合，m是m个\(f(x)\)复合，\(n\times m\)是n个m个\(f(x)\)复合

我们先将n个m写出来，每个\(F_m\)是m个\(f(x)\)，得到

\[\begin{aligned} n\times m&=F_n(F_m(f))(x)\\ &=\underbrace{F_m(f)(F_m(f)(\cdots(F_m}_{n}(f)(x))))\\ &=\underbrace{\underbrace{f(f(\cdots(f}_{m}(\underbrace{f(f(\cdots(f}_{m}(\cdots(\underbrace{f(f(\cdots(f}_{m}}_{n}(x)))) \end{aligned}\]

即\(n\times m\)

def mul_church(m, n):
    """Return the Church numeral for m * n, for Church numerals m and n.

    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    "*** YOUR CODE HERE ***"
    return lambda f: n(m(f))

乘方

\[m^n=\underbrace{f(f(\cdots(f}_{m^n}(x)))) \]

和乘法类似，这次我们需要n个m个m，也就是n个\(m\times m\)，先上推导再解释

\[\begin{aligned} m^n&=F_n(F_m)(f)(x)\\ &=\underbrace{F_m(F_m(\cdots(F_m}_{n})))(f)(x)\\ &=\underbrace{F_m(F_m(\cdots(F_m(}_{n-1}\underbrace{f(f(\cdots(f}_{m})))(x)\\ &=\underbrace{F_m(F_m(\cdots(F_m(}_{n-2}\underbrace{f(f(\cdots(f}_{m\times m})))(x)\\ &\qquad \vdots\\ &=F_m(\underbrace{f(f(\cdots(f}_{m^{n-1}})))(x)\\ &=\underbrace{f(f(\cdots(f}_{m^n}(x)))) \end{aligned}\]

这里 evaluate 的顺序很关键，第一步\(F_n\)将n个\(F_m\)复合，之后\(f\)作为\(F_n\)第二个参数被传入，最里层变为\(F_m(f)\)开始复合，一层层向外，最外层\(x\)作为\(F_m\)的第二个参数被传入。实际程序运行的顺序肯定和这里不完全一样，但是基本思路是这样的。一开始可能想不明白这个和乘法有什么区别，乘法复合的是\(F_m\)第二个参数，乘方复合的是\(F_m\)第一个参数，无论是 debug 还是 environment diagram 都没有办法形象的展现这个程序的运行方式，只能靠意会了。

def pow_church(m, n):
    """Return the Church numeral m ** n, for Church numerals m and n.

    >>> church_to_int(pow_church(two, three))
    8
    >>> church_to_int(pow_church(three, two))
    9
    """
    "*** YOUR CODE HERE ***"
    return n(m)