I'm trying to learn python and CS on my own using a course online that is based off SICP. I understand the basics of church numerals, but I am having trouble on adding church numerals using lambda functions in python.
This is my code below for context:
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."""
return lambda x: f(x)
def two(f):
"""Church numeral 2."""
return lambda x: f(f(x))
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
"""
return n(lambda x: x + 1)(0)
def mul_church(m, n):
"""Return the Church numeral for m * n, for Church numerals m and n.
>>> three = successor(two)
>>> four = successor(three)
>>> church_to_int(mul_church(two, three))
6
>>> church_to_int(mul_church(three, four))
12
"""
return lambda x: m(n(x))
This is add_church function that I am having trouble with:
def add_church(m, n):
"""Return the Church numeral for m + n, for Church numerals m and n.
>>> three = successor(two)
>>> church_to_int(add_church(two, three))
5
"""
return lambda f: lambda x: m(f(x))(n(x))
I have concluded that a way to add church numerals would be to somehow have one of the functions in add_church(m, n) to be the input or "x" in the other's lambda function. However, I keep getting errors that imply that I am not using the right arguments in my function call.
For example, when I call:
church_to_int(add_church(one, two))
I get an "int object not callable" error amongst others and have also tried other different methods with no success.
I think there is something that I am not seeing about lambda functions which is causing me to have trouble with implementing add_church. I've been spending a while on figuring this out, so any help that will guide me to the answer will be greatly appreciated.
Recall that Church encoding can be understood as repeated application of a function to an argument. So to add m + n
, we need to apply a function f
to an argument x
m + n
times, or equivalently apply it n
times and then apply it m
times:
def add_church(m, n):
def m_plus_n(f):
def f_repeated_m_plus_n_times(x) # f ** (m + n)
intermediate_result = (n(f))(x) # (f ** n) (x)
final_result = (m(f))(intermediate_result) # (f ** m) ((f ** n) (x))
return final_result
return f_repeated_m_plus_n_times
return m_plus_n
In lambda form, removing redundant parentheses:
def add_church(m, n):
"""Return the Church numeral for m + n, for Church numerals m and n.
>>> three = successor(two)
>>> church_to_int(add_church(two, three))
5
"""
return lambda f: lambda x: m(f)(n(f)(x))