日韩黑丝制服一区视频播放|日韩欧美人妻丝袜视频在线观看|九九影院一级蜜桃|亚洲中文在线导航|青草草视频在线观看|婷婷五月色伊人网站|日本一区二区在线|国产AV一二三四区毛片|正在播放久草视频|亚洲色图精品一区

搜索
分享

使用Lua Function表示Lambda calculus

 guitarhua 2013-08-21

目錄(?)[+]

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

很多程序語(yǔ)言所帶給你的“完美”的感覺(jué)都來(lái)自于數(shù)學(xué)抽象之美。

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

所謂的“一類(lèi)值”，應(yīng)該滿足以下條件:

  • 可以被保存到變量和數(shù)據(jù)結(jié)構(gòu)中
  • 可以被當(dāng)作子程序的參數(shù)和返回值
  • 可以在運(yùn)行期創(chuàng)建
  • 具有內(nèi)在標(biāo)識(shí)，不依賴于任何給定的名稱

大多數(shù)語(yǔ)言的基本數(shù)據(jù)類(lèi)型，比如int，就屬于“一類(lèi)值”。很多語(yǔ)言中的函數(shù)實(shí)現(xiàn)，只能滿足其中一些條件。比如在C中可以將函數(shù)指針保存到變量中，可以將函數(shù)指針當(dāng)作參數(shù)和返回值。這樣的函數(shù)實(shí)現(xiàn)一般不會(huì)被算作“一類(lèi)值"。

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

而所謂的“真正詞法范圍”，則是說(shuō)Lua function可以訪問(wèn)外圍函數(shù)中的局部變量。這是通過(guò)lua的closure來(lái)實(shí)現(xiàn)的。

“具有真正的詞法范圍的一類(lèi)值”使得Lua function可以用來(lái)表示"Lambda calculus"。Lambda calculus是Functional Programming的數(shù)學(xué)基礎(chǔ)。他使用抽象的function和一套簡(jiǎn)單的規(guī)則來(lái)構(gòu)建一個(gè)完整的等價(jià)于"Turing Machine"的計(jì)算模型。使用Lua function來(lái)表示Lambda calculus可以讓你從另一個(gè)更真實(shí)的角度去理解Lambda calculus的語(yǔ)義，同時(shí)也可以更深入的體會(huì)Lua function功能的強(qiáng)大。并且對(duì)于程序員來(lái)說(shuō)，這本身也是一個(gè)非常有趣的嘗試。

Lambda calculus是一個(gè)操作lambda expression的系統(tǒng)。Lambda expression由variable，function abstraction和function application組成。我們可以使用一個(gè)Lua function的定義來(lái)代表一個(gè)function abstraction。這個(gè)function接受一個(gè)參數(shù)，也就是variable，并返回一個(gè)function。而對(duì)這個(gè)function的調(diào)用，就是function application。這樣，我們就有了lambda calculus基本規(guī)則對(duì)應(yīng)的lua實(shí)現(xiàn)。Lambda calculus可以通過(guò)如此簡(jiǎn)單的基本規(guī)則構(gòu)建出各種高層語(yǔ)義，比如數(shù)據(jù)類(lèi)型，算數(shù)和邏輯運(yùn)算，循環(huán)和遞歸等等。這也就是說(shuō)，理論上我們可以僅僅使用lua function，而不需要任何其他的語(yǔ)言功能，來(lái)進(jìn)行任何的計(jì)算。我想這也就是"functional programming"的極限了吧。

我們首先來(lái)看一些最簡(jiǎn)單的function。

Identity

λx.x

單位函數(shù)直接返回應(yīng)用的參數(shù)。對(duì)應(yīng)的lua function為:

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

將一個(gè)identity應(yīng)用到identity，結(jié)果還應(yīng)該是identity。

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

  1. print(identity(identity) == identity)  
Lua中的結(jié)果應(yīng)該是true

Self Application Function

λs.(s s)

自應(yīng)用函數(shù)將參數(shù)應(yīng)用到參數(shù)本身。對(duì)應(yīng)的lua function為:

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

將自應(yīng)用函數(shù)應(yīng)用到identity，最終會(huì)得到identity：

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

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

將自應(yīng)用函數(shù)應(yīng)用到自身，會(huì)造成估值不能結(jié)束:

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

同樣，對(duì)于lua調(diào)用

  1. self_apply(self_apply)  
也會(huì)一直無(wú)限循環(huán)下去。由于self_apply函數(shù)中的s(s)是一個(gè)tail call，所以這個(gè)無(wú)限循環(huán)不會(huì)造成調(diào)用棧溢出。

Function Application Function

λf.λa.(f a)

函數(shù)應(yīng)用函數(shù)將參數(shù)f應(yīng)用到參數(shù)a上。對(duì)應(yīng)的lua function為:

  1. function apply(f)  
  2.     return (function(a)  
  3.         return f(a);  
  4.     end);  
  5. end  
這個(gè)lua function與對(duì)應(yīng)的lambda expression的語(yǔ)義完全一致：最外層函數(shù)接受一個(gè)參數(shù)f，函數(shù)體為λa.(f a)，也就是一個(gè)參數(shù)為a的函數(shù)。而這個(gè)內(nèi)層函數(shù)的函數(shù)體為(f a)，也就是將f應(yīng)用到a。

如果將此函數(shù)應(yīng)用到identity：

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

會(huì)得到一個(gè)參數(shù)為a的函數(shù)。而對(duì)于lua function也是如此：

  1. apply(identity)  
會(huì)返回一個(gè)帶有identity upvalue的函數(shù)對(duì)象。

如果將此函數(shù)連續(xù)應(yīng)用到identity：

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

效果就和將identity應(yīng)用到自身是一樣的。

對(duì)應(yīng)的lua調(diào)用：

  1. print(apply(identity)(identity) == identity)  
應(yīng)該返回true。

接下來(lái)，我們開(kāi)始構(gòu)建一些基礎(chǔ)的function，并在這些基礎(chǔ)上構(gòu)建更高層的語(yǔ)義。

Boolean Values

在lambda calculas中，我們可以通過(guò)函數(shù)來(lái)表示boolean values。

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

其對(duì)應(yīng)的lua function為：

  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  

我們可以測(cè)試一下這個(gè)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

同樣，對(duì)應(yīng)的lua調(diào)用也成立：

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

Condition

根據(jù)Boolean value的定義，我們可以構(gòu)造出條件判斷的lambda function:

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

這個(gè)表達(dá)式的語(yǔ)義是根據(jù)boolean值b，來(lái)選擇t或者f。如果b為T(mén)RUE，就選擇t，否則選擇f。

其對(duì)應(yīng)的lua function為：

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

我們可以通過(guò)將條件表達(dá)式應(yīng)用到identity，apply和TRUE，來(lái)看一下結(jié)果：

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

同樣，對(duì)應(yīng)的Lua調(diào)用也成立：

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

這等同于如下邏輯：

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

至此，我們已經(jīng)看到，僅僅使用lua function，就可以構(gòu)造出基于if...else...的邏輯判斷語(yǔ)義。

NOT

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

這個(gè)表達(dá)式的語(yǔ)義是：當(dāng)b為T(mén)RUE時(shí)，選擇FALSE，否則選擇TRUE。

對(duì)應(yīng)的lua function:

  1. function NOT(b)  
  2.     return b(FALSE)(TRUE);  
  3. end  
  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(b t f) y FALSE x) => λx.λy.(x y FALSE)

這個(gè)表達(dá)式的語(yǔ)義是：當(dāng)x為T(mén)RUE時(shí)，選擇y，否則選擇FALSE。

對(duì)應(yīng)的lua function:

  1. function AND(x)  
  2.     return (function(y)  
  3.         return x(y)(FALSE);  
  4.     end);  
  5. end  
  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 y x) == λx.λy.(λt.λf.λb(b t f) TRUE y x) => λx.λy.(x TRUE y)

這個(gè)表達(dá)式的語(yǔ)義是：當(dāng)x為T(mén)RUE時(shí)，選擇TRUE，否則選擇y。

對(duì)應(yīng)的lua function:

  1. function OR(x)  
  2.     return (function(y)  
  3.         return x(TRUE)(y);  
  4.     end);  
  5. end  
  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  

至此，我們已經(jīng)有了基本的邏輯運(yùn)算符NOT，AND和OR?？梢酝ㄟ^(guò)他們來(lái)組合出更復(fù)雜的boolean邏輯表達(dá)式。

Natural Numbers

使用lambda expression表示自然數(shù)，我們首先要定義0。我們將0定義為identity。
  1. zero = identity  

然后，定義一個(gè)succ函數(shù)，代表自然數(shù)n的下一個(gè)自然數(shù)：

λn.λb.(b FALSE n)

  1. function succ(n)  
  2.     return (function(b)  
  3.         return b(FALSE)(n);  
  4.     end);  
  5. end  
這樣我們就可以定義出自然數(shù)1~9:
  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);  
每個(gè)自然數(shù)都使用一個(gè)函數(shù)來(lái)表示。

接著我們需要定義一個(gè)函數(shù)iszero來(lái)判斷一個(gè)自然數(shù)是否為0：

λn.(n TRUE)

然后我們定義一個(gè)函數(shù)iszero，用來(lái)判斷是否是0:

λn.(n TRUE)

  1. function iszero(n)  
  2.     return n(TRUE);  
  3. end  
  1. print(iszero(zero) == TRUE) -- true  
  2. print(iszero(one) == FALSE) -- true  

最后，我們還可以定義一個(gè)pred函數(shù)，用來(lái)獲得一個(gè)自然數(shù)的前一個(gè)自然數(shù)：

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

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

這里面包含了當(dāng)n為0時(shí)的特殊處理。當(dāng)n為0時(shí)，返回0。

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

至此，我們有了基本的自然數(shù)的表示方法。接下來(lái)，我們將利用自然數(shù)來(lái)計(jì)數(shù)，進(jìn)行一個(gè)簡(jiǎn)單的循環(huán)。

Loop

在Functional Programming中，循環(huán)使用遞歸調(diào)用來(lái)進(jìn)行。Lambda calculus的遞歸調(diào)用是通過(guò)將一個(gè)Y Conbinator函數(shù)引用到一個(gè)stepper函數(shù)來(lái)實(shí)現(xiàn)的。stepper函數(shù)代表了循環(huán)的每一次需要做的事情，而YConbinator函數(shù)則多次調(diào)用這個(gè)stepper函數(shù)，來(lái)表示循環(huán)。

Y Conbinator:

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

  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函數(shù)我們將它設(shè)計(jì)為傳入一個(gè)自然數(shù)然后遞減：

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

  1. function stepper(next_step)  
  2.     return (function(n)  
  3.         return COND(zero)(next_step(pred(n))(iszero(n))  
  4.     end)  
  5. end  
當(dāng)我們調(diào)用：
  1. recursive(stepper)(five)  
這個(gè)調(diào)用并沒(méi)有之循環(huán)5次，而是會(huì)無(wú)限遞歸下去，直到棧溢出。原因在于我們對(duì)于lambda expression的reduction采用的是normal order，而lua版本實(shí)際上等于applicative order reduction。Applicative order reduction在此情況下會(huì)無(wú)限遞歸。解決這個(gè)問(wèn)題的辦法就是延遲一些字表達(dá)式的估值。我們可以將這兩個(gè)函數(shù)改寫(xiě)為：
  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  
當(dāng)我們?cè)俅握{(diào)用:
  1. recursive(stepper)(five)  
我們會(huì)看到這個(gè)循環(huán)正確的執(zhí)行了5次。

綜上所述，我們已經(jīng)使用lua function作為lambda calculas的表示形式，從新構(gòu)建了一個(gè)包含了高層語(yǔ)義的計(jì)算模型，從而也體會(huì)到了lua function高度抽象的能力。希望對(duì)大家學(xué)習(xí)lambda calculus和lua function有所幫助。


分享到：

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類(lèi)似文章 更多