使用Lua Function表示Lambda calculus

http://blog.csdn.net/yuanlin2008/article/details/8627081

很多程序語言所帶給你的“完美”的感覺都來自於數學抽象之美。

在Lua中，function被描述成“具有真正的詞法範圍的一類值”(first-class values​​ with proper lexical scoping)。

所謂的“一類值”，應該滿足以下條件:

• 可以被保存到變量和數據結構中
• 可以被當作子程序的參數和返回值
• 可以在運行期創建
• 具有內在標識，不依賴於任何給定的名稱

大多數語言的基本數據類型，比如int，就屬於“一類值”。很多語言中的函數實​​現，只能滿足其中一些條件。比如在C中可以將函數指針保存到變量中，可以將函數指針當作參數和返回值。這樣的函數實現一般不會被算作“一類值"。

在Lua中，所有的值都是“一類”值，包括function本身。函數可以被保存到任何的變量或者table中，可以被當作參數和返回值使用，所有的函數（更準確的說應該是closure）都是運行期被創建的，函數本身並沒有名字，名字只是對函數的引用而已。作為“一類值”的function更為抽象，可以用來表示很多的"Functional Programming"的概念。比如“高階函數”(Higher-order functions)，“匿名函數”(Anonymous functions")。這些功能在很多語言中都是通過特殊的語法來支持的，而在lua中則不需要。

而所謂的“真正詞法範圍”，則是說Lua function可以訪問外圍函數中的局部變量。這是通過lua的closure來實現的。

“具有真正的詞法範圍的一類值”使得Lua function可以用來表示" Lambda calculus "。Lambda calculus是Functional Programming的數學基礎。他使用抽象的function和一套簡單的規則來構建一個完整的等價於"Turing Machine"的計算模型。使用Lua function來表示Lambda calculus可以讓你從另一個更真實的角度去理解Lambda calculus的語義，同時也可以更深入的體會Lua function功能的強大。並且對於程序員來說，這本身也是一個非常有趣的嘗試。

Lambda calculus是一個操作lambda expression的系統。Lambda expression由variable，function abstraction和function application組成。我們可以使用一個Lua function的定義來代表一個function abstraction。這個function接受一個參數，也就是variable，並返回一個function。而對這個function的調用，就是function application。這樣，我們就有了lambda calculus基本規則對應的lua實現。Lambda calculus可以通過如此簡單的基本規則構建出各種高層語義，比如數據類型，算數和邏輯運算，循環和遞歸等等。這也就是說，理論上我們可以僅僅使用lua function，而不需要任何其他的語言功能，來進行任何的計算。我想這也就是"functional programming"的極限了吧。

我們首先來看一些最簡單的function。

Identity

λx.x

單位函數直接返回應用的參數。對應的lua function為:

[plain] view plain copy print ?

1. function identity(x)  
2.     return x;  
3. end  

將一個identity應用到identity，結果還應該是identity。

λx.x λx.x=>λx.x

[plain] view plain copy print ?

1. print(identity(identity) == identity)  

Lua中的結果應該是true

Self Application Function

λs.(ss)

自應用函數將參數應用到參數本身。對應的lua function為:

[plain] view plain copy print ?

1. function self_apply(s)  
2.     return s(s);  
3. end  

將自應用函數應用到identity，最終會得到identity：

λs.(ss) λx.x => λx.x λx.x => λx.x

[plain] view plain copy print ?

1. print(self_apply(identity) == identity);  

將自應用函數應用到自身，會造成估值不能結束:

λs.(ss) λs.(ss) => λs.(ss) λs.(ss) =>...

同樣，對於lua調用

[plain] view plain copy print ?

1. self_apply(self_apply)  

也會一直無限循環下去。由於self_apply函數中的s(s)是一個tail call，所以這個無限循環不會造成調用棧溢出。

Function Application Function

λf.λa.(fa)

函數應用函數將參數f應用到參數a上。對應的lua function為:

[plain] view plain copy print ?

1. function apply(f)  
2.     return (function(a)  
3.         return f(a);  
4.     end);  
5. end  

這個lua function與對應的lambda expression的語義完全一致：最外層函數接受一個參數f，函數體為λa.(fa)，也就是一個參數為a的函數。而這個內層函數的函數體為(fa)，也就是將f應用到a。

如果將此函數應用到identity：

λf.λa.(fa) λx.x => λa.(λx.x a)

會得到一個參數為a的函數。而對於lua function也是如此：

[plain] view plain copy print ?

1. apply(identity)  

會返回一個帶有identity upvalue的函數對象。

如果將此函數連續應用到identity：

λf.λa.(fa) λx.x λx.x =>λa.(λx.xa) λx.x => λx.x λx.x => λx.x

效果就和將identity應用到自身是一樣的。

對應的lua調用：

[plain] view plain copy print ?

1. print(apply(identity)(identity) == identity)  

應該返回true。

接下來，我們開始構建一些基礎的function，並在這些基礎上構建更高層的語義。

Boolean Values

在lambda calculas中，我們可以通過函數來表示boolean values​​。

• TRUE可以表示成λf.λs.f，代表選擇兩個參數中的第一個。
• FALSE可以表示成λf.λs.s，代表選擇兩個參數中的第二個。

其對應的lua function為：

[plain] view plain copy print ?

1. function TRUE(f)  
2.     return (function(s)  
3.         return f;  
4.     end);  
5. end  
6.   
7. function FALSE(f)  
8.     return (function(s)  
9.         return s;  
10.     end);  
11. end  

我們可以測試一下這個lambda expression:

TRUE identity apply == λf.λs.f identity apply => λs.identity apply => identity

FALSE identity apply == λf.λs.s identity apply => λs.s apply => apply

同樣，對應的lua調用也成立：

[plain] view plain copy print ?

1. print(TRUE(identity)(apply) == identity) -- true  
2. print(FALSE(identity)(apply) == apply) -- true  

Condition

根據Boolean value的定義，我們可以構造出條件判斷的lambda function:

λt.λf.λb.(btf)

這個表達式的語義是根據boolean值b，來選擇t或者f。如果b為TRUE，就選擇t，否則選擇f。

其對應的lua function為：

[plain] view plain copy print ?

1. function COND(t)  
2.     return (function(f)  
3.         return (function(b)  
4.             return b(t)(f);  
5.         end);  
6.     end);  
7. end  

我們可以通過將條件表達式應用到identity，apply和TRUE，來看一下結果：

λt.λf.λb.(btf) identity apply TRUE =>  
λf.λb(b identity f) apply TRUE =>  
λb(b identity apply) TRUE =>  
TRUE identity apply =>  
identity

同樣，對應的Lua調用也成立：

[plain] view plain copy print ?

1. print(COND(identity)(apply)(TRUE) == identity) -- true  

這等同於如下邏輯：

[plain] view plain copy print ?

1. if(true)  
2.     return identity  
3. else  
4.     return apply  

至此，我們已經看到，僅僅使用lua function，就可以構造出基於if...else...的邏輯判斷語義。

NOT

λb.(COND FALSE TRUE b) == λb.(λt.λf.λb(btf) FALSE TRUE b) => λb(b FALSE TRUE)

這個表達式的語義是：當b為TRUE時，選擇FALSE，否則選擇TRUE。

對應的lua function:

[plain] view plain copy print ?

1. function NOT(b)  
2.     return b(FALSE)(TRUE);  
3. end  

[plain] view plain copy print ?

1. print(NOT(TRUE) == FALSE); -- true  
2. print(NOT(NOT(TRUE)) == TRUE); --true  

AND

λx.λy.(COND y FALSE x) == λx.λy.(λt.λf.λb(btf) y FALSE x) => λx.λy.(xy FALSE)

這個表達式的語義是：當x為TRUE時，選擇y，否則選擇FALSE。

對應的lua function:

[plain] view plain copy print ?

1. function AND(x)  
2.     return (function(y)  
3.         return x(y)(FALSE);  
4.     end);  
5. end  

[plain] view plain copy print ?

1. print(AND(TRUE)(TRUE) == TRUE); -- true  
2. print(AND(TRUE)(FALSE) == FALSE); -- true  
3. print(AND(FALSE)(TRUE) == FALSE); -- true  
4. print(AND(FALSE)(FALSE) == FALSE); -- true  

OR

λx.λy.(COND TRUE yx) == λx.λy.(λt.λf.λb(btf) TRUE yx) => λx.λy.(x TRUE y)

這個表達式的語義是：當x為TRUE時，選擇TRUE，否則選擇y。

對應的lua function:

[plain] view plain copy print ?

1. function OR(x)  
2.     return (function(y)  
3.         return x(TRUE)(y);  
4.     end);  
5. end  

[plain] view plain copy print ?

1. print(OR(TRUE)(TRUE) == TRUE); -- true  
2. print(OR(TRUE)(FALSE) == TRUE); -- true  
3. print(OR(FALSE)(TRUE) == TRUE); -- true  
4. print(OR(FALSE)(FALSE) == FALSE); -- true  

至此，我們已經有了基本的邏輯運算符NOT，AND和OR。可以通過他們來組合出更複雜的boolean邏輯表達式。

Natural Numbers

使用lambda expression表示自然數，我們首先要定義0。我們將0定義為identity。

[plain] view plain copy print ?

1. zero = identity  

然後，定義一個succ函數，代表自然數n的下一個自然數：

λn.λb.(b FALSE n)

[plain] view plain copy print ?

1. function succ(n)  
2.     return (function(b)  
3.         return b(FALSE)(n);  
4.     end);  
5. end  

這樣我們就可以定義出自然數1~9:

[plain] view plain copy print ?

1. one = succ(zero);  
2. two = succ(one);  
3. three = succ(two);  
4. four = succ(three);  
5. five = succ(four);  
6. six = succ(five);  
7. seven = succ(six);  
8. eight = succ(seven);  
9. nine = succ(eight);  

每個自然數都使用一個函數來表示。

接著我們需要定義一個函數iszero來判斷一個自然數是否為0：

λn.(n TRUE)

然後我們定義一個函數iszero，用來判斷是否是0:

λn.(n TRUE)

[plain] view plain copy print ?

1. function iszero(n)  
2.     return n(TRUE);  
3. end  

[plain] view plain copy print ?

1. print(iszero(zero) == TRUE) -- true  
2. print(iszero(one) == FALSE) -- true  

最後，我們還可以定義一個pred函數，用來獲得一個自然數的前一個自然數：

λn.(COND zero (n FALSE) (iszero n)) => λn.((iszero n) zero (n FALSE))

[plain] view plain copy print ?

1. function pred(n)  
2.     return iszero(n)(zero)(n(FALSE));  
3. end  

這裡麵包含了當n為0時的特殊處理。當n為0時，返回0。

[plain] view plain copy print ?

1. print(pred(one) == zero) -- true  

至此，我們有了基本的自然數的表示方法。接下來，我們將利用自然數來計數，進行一個簡單的循環。

Loop

在Functional Programming中，循環使用遞歸調用來進行。Lambda calculus的遞歸調用是通過將一個Y Conbinator函數引用到一個stepper函數來實現的。stepper函數代表了循環的每一次需要做的事情，而YConbinator函數則多次調用這個stepper函數，來表示循環。

Y Conbinator:

λf.(λx.(f (xx)) λx.(f (xx)))

[plain] view plain copy print ?

1. function recursive(f)  
2.     return (function(x)  
3.         return f(x(x))  
4.     )(function(x)  
5.         return f(x(x))  
6.     end)  
7. end  

stepper函數我們將它設計為傳入一個自然數然後遞減：

λs.λn.(COND zero (s (pred n) (iszero n))

[plain] view plain copy print ?

1. function stepper(next_step)  
2.     return (function(n)  
3.         return COND(zero)(next_step(pred(n))(iszero(n))  
4.     end)  
5. end  

當我們調用：

[plain] view plain copy print ?

1. recursive(stepper)(five)  

這個調用並沒有之循環5次，而是會無限遞歸下去，直到棧溢出。原因在於我們對於lambda expression的reduction採用的是normal order，而lua版本實際上等於applicative order reduction。Applicative order reduction在此情況下會無限遞歸。解決這個問題的辦法就是延遲一些字表達式的估值。我們可以將這兩個函數改寫為：

[plain] view plain copy print ?

1. function recursive(f)  
2.     return (function(x)  
3.         return f(function(dummy) return x(x) end)  
4.     end)(function(x)  
5.         return f(function(dummy) return x(x) end)  
6.     end)  
7. end  
8.   
9. function stepper(next_step)  
10.     return (function(n)  
11.         return COND(function(dummy)  
12.             return zero  
13.         end)(function(dummy)  
14.             print("one step");  
15.             return next_step(identity)(pred(n))  
16.         end)(iszero(n))(identity)  
17.     end)  
18. end  

當我們再次調用:

[plain] view plain copy print ?

1. recursive(stepper)(five)  

我們會看到這個循環正確的執行了5次。

綜上所述，我們已經使用lua function作為lambda calculas的表示形式，從新構建了一個包含了高層語義的計算模型，從而也體會到了lua function高度抽象的能力。希望對大家學習lambda calculus和lua function有所幫助。