2019 CS61A HW2 Q4: Church Numerals (python)

--- tags: cs61a --- # 2019 CS61A HW2 Q4: Church Numerals (python) 6/20 當初看到這題第一眼時，整個人直接傻掉，連題目的意思都看不太懂... 題目網址: https://inst.eecs.berkeley.edu/~cs61a/fa19/hw/hw02/ Church Numerals 是美國數學家與邏輯學家 Alonzo Church 發明的數字系統，他發明的這套數字系統不需要倚賴我們原來的數字123, 它純粹是以邏輯建構出來的，而它可以進行加法、乘法、Boolean 運算等數學運算。這題是讓我們訓練對 Higher Order Fuction 的感覺，意思就是函數的函數的函數..., 所以在做的時候頭腦很容易就打結。 --- ## 題目題目提供 Church Numerals 的基礎元素，0 以及一個能夠找到任何數字下一個數字的函數。 ``` zero(f): return lambda x: x def successor(n): return lambda f: lambda x: f(n(f)(x)) ``` 在這個系統 zero 就相當於是數字0，它是一個函數會回傳一個函數，也可以把它寫成 ``` zero = lambda f: lambda x: x ``` 而 successor 能夠找到下一個數字 ``` one = successor(zero) two = successor(one) ``` ## 計算元素 one 與 two (不可以用到 successor 函數) ### 計算one 將zero帶入successor的參數裡 successor(zero) 會 return -> lambda f: lambda x: f(zero(f)(x)) - - -(1) 而 zero(f) 會 return -> lambda x: x - - -(2) 將(2)帶回(1): lambda f: lambda x: f((lambda x: x)(x)) 化簡一下 ``` one = lambda f: lambda x: f(x) ``` 也可以寫成 ``` def one(f): return lambda x: f(x) ``` ### 計算two 將one帶入successor的參數裡 successor(one) 會 return -> lambda f: lambda x: f(one(f)(x)) - - -(1) 同上面計算one 將one(f)帶入(1): lambda f: lambda x: f((lambda x: f(x))(x)) 化簡一下 ``` two = lambda f: lambda x: f(f(x)) ``` 也可以寫成 ``` def two(f): return lambda x: f(f(x)) ``` 至此已能稍微看出一些規律，首先這個數字系統的數字都是會回傳函數的函數，其參數f也是一個函數，也就是開頭都是lambda f: lambda x:，而它回傳的函數的回傳值為f(x)的組合，one是f(x)、two是ff(x)，可以想像three是fff(x)。 ## 設計 Church Numerals 與一般數字的轉換函數 Church_to_int 為了方便觀察運算結果，先設計Church_to_int 目標: Church_to_int(zero) -> 0 Church_to_int(one) -> 1 Church_to_int(two) -> 2 可以先想到的是 one、two 回傳的函數 lambda x: 回傳的 f(x) 的個數和它所代表的一般數字是一樣的，one 就回傳一個、two 就兩個，所以必須善用這個 f 函數。將 f 函數設計成一個能夠計數的函數 ``` f = lambda x: x+1 #f(0) = 1 #f(1) = 2 ``` 將 f 放進 Church_to_in 裡 ``` def Church_to_int(n): f = lambda x: x+1 return n(f)(0) #Church_to_int(zero) -> zero(f)(0) = 0 #Church_to_int(one) -> one(f)(0) = 1 (跑一次f(x)) #Church_to_int(two) -> two(f)(0) = 2 (跑兩次f(x)) ``` 也可以寫成 ``` f = lambda x: x+1 Church_to_int = lambda n: n(f)(0) ``` --- 以下運算，加法、乘法和乘冪皆不可以用到 successor 函數 ## 設計加法運算 add_Church(m, n) 首先先想像一下在這裡的加法運算應該長甚麼樣子目標: add_Church(two, three) -> five 也就是ff(x) + fff(x) -> fffff(x) 可以看出要做的事情是把two當中的x帶入three回傳的函數的回傳值fff(x) 把這件事拆成兩個部分: 1. 把two當中的x代入: two(f)(x) 2. three回傳的函數的回傳值fff(x): three(f)(x) 合起來就是 two(f)(three(f)(x))，此時的值為 fffff(x)，還不是我們要的 five，因為 five 是一個回傳函數的函數，開頭應該 lambda f: lambda x: 整合一下 ``` def add_Church(m, n): return lambda f: lambda x: m(f)(n(f)(x)) ``` 也可以寫成 ``` add_Church(m, n) = lambda m, n: lambda f: lambda x: m(f)(n(f)(x)) ``` ## 設計乘法運算 mul_Church(m, n) 乘法運算就比加法運算難一些目標: mul_Church(two, three) -> six 也就是ff(x) * fff(x) -> ffffff(x) 我們知道2 * 3能夠被看成是有2份的3，所以往這個方向去想，如果 two 的 f 函式的功能就是製造出fff(x)，也就是兩份的 three 那乘法就被實現出來了。把這件事拆成兩個部分: 1. 製造 three 回傳的函數的回傳值 fff(x): three(f) = lambda x: fff(x) 2. 代入 two 當中的 f 函式: two(f)(x) 合起來就是 two(three(f))(x) two(three(f))(x) = three(three(f)(x)) = ffffff(x) 此時的值為 ffffff(x)，還不是我們要的 six，因為 six 是一個回傳函數的函數，開頭應該lambda f: lambda x: 整合一下 ``` def mul_Church(m, n): return lambda f: lambda x: m(n(f))(x) ``` 也可以寫成 ``` mul_Church(m, n) = lambda m, n: lambda f: lambda x: m(n(f))(x) ``` 注意一點，這裡的 lambda f: lambda x: m(n(f)(x))(x) 可以直接寫成 lambda f: m(n(f)) 就可以了，因為 m(n(f)) 本身的回傳值就是 lambda x: ffffff(x) ## 設計乘冪運算(次方運算) pow_church(m, n) 目標: pow_church(two, three) -> $2^3 = 8$ 次方運算跟乘法運算的關係，就好比乘法運算跟加法運算的關係乘法是連續的加法 -> $2 * 3 = 2 + 2 + 2$ 次方是連續的乘法 -> $2^3 = 2 * 2 * 2$ 所以我們可以往這個方向找線索為了要讓3個2相乘，我們現在需要使 three 當中的 fff(x) 的 f 函式之間為相乘2的關係以下進行分析: * 使 three 當中的 fff(x) 的 f 函式之間為相乘2的關係: 為了防止搞混，以下先將 three 的 f(x) 簡稱 f3 要使 f3(f3(x)）之間為乘2的關係，我們必須要讓 f3 成為一個會執行 x 兩次的一個函式，此時的 x 為一個函數 f3(x) 會執行 x 兩次 f3(f3(x)) 會執行 f3(x) 兩次，也就是執行 x 四次所以 f3 是一個能夠執行其參數 (可能為某個函數 f ) 兩次的一個函數 f3 = lambda f: lambda x: f(f(x)) 有沒有發現這個東西就是 two 所以 f3(f3(f3((x)) 其實就是 two(two(two(x))) 這時我們就發現 two 設計成參數為函數並且回傳一個函數的目的之一，就是讓 two 能夠在身為數字的同時，也能當作運算來使用整理一下把 two 代入 three(f) three = lambda f: lambda x: fff(x) three(two) = lambda x: two(two(two(x))) 要注意的是此時原先的 x 變成了 f 的功用，因為 x 會代入 two(x)，我們替換一下寫法， three(two) = lambda f: two(two(two(f))) = lambda f: lambda x: ffffffff(x) 也就是 eight eight(f)(x) = two(two(two(f)))(x) = ffffffff(x) ![](https://i.imgur.com/TK1wURY.png) ``` # m的n次方 def pow_church(m, n): return n(m) ``` 也可以寫成 ``` pow_church(m, n) = lambda f: n(m) ```