• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

5天前 11次浏览

# Church Numerals

## Nagging

This section is out of scope for our course, so the problems below is optional.
That is, the problems in this section don’t count for your final score and don’t have any deadline.
Do it at any time if you want an extra challenge or some practice with high order function and abstraction!

P.s. 问过助教老师了，是可以发上网的

## Homework

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:

``````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 `successor(successor(zero))` respectively, but do not call `successor` in your
implementation.
Next, implement a function `church_to_int` that converts a church numeral argument to a
regular Python integer.
Finally, implement functions `add_church` , `mul_church` , and `pow_church` that perform addition,
multiplication, and exponentiation on church numerals.

``````##########################
# Just for fun Questions #
##########################
HW_SOURCE_FILE = 'lab02.py'

from operator import add, mul, sub

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1

def zero(f):
return lambda x: x

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

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

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

three = successor(two)

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 ***"

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 ***"

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 ***"

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 ***"
``````

## Solution

``````def one(f):
return lambda x: f(x)

def two(f):
return lambda x: f(f(x))
``````

`successor` 的定义，发现数字 (N) 对应的函数 (F_N(f)) 的定义应当为：

[F_N(f) = f(F_{N-1}(f)) = dots = underbrace{f(f(f(dots(f}_{N个}))))
]

``````def church_to_int(n):
return n(increment)(0)
``````

``````def add_church(m, n):
return lambda f: lambda x: m(f)( n(f)(x) )
``````

``````def mul_church(m, n):
return lambda f: m(n(f))
``````

(F_m(f)) 的功用是将 (m)(f) 嵌套起来，那么 (F_n(F_m(f))) 的功用也就是将 (n)(F_m) 嵌套起来，即

[begin{align*}
F_n(F_m(f)) &= underbrace{F_m(F_m(F_m(dots(F_m}_{n个})))) \
&= overbrace{underbrace{f(f(f(dots(f(underbrace{f(f(f(dots(f(dots underbrace{f(f(f(dots dots dots(f}_{m个})))))}_{m个})))))}_{m个}}^{n个}))))
end{align*}
]

``````def pow_church(m, n):
return n(m)
``````