logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

使用Lua Function表示Lambda calculus

 guitarhua 2013-08-21

目录(?)[+]

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为:

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

将一个identity应用到identity，结果还应该是identity。

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

  1. print(identity(identity) == identity)  
Lua中的结果应该是true

Self Application Function

λs.(s s)

自应用函数将参数应用到参数本身。对应的lua function为:

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

将自应用函数应用到identity，最终会得到identity：

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

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

将自应用函数应用到自身，会造成估值不能结束:

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

同样，对于lua调用

  1. self_apply(self_apply)  
也会一直无限循环下去。由于self_apply函数中的s(s)是一个tail call，所以这个无限循环不会造成调用栈溢出。

Function Application Function

λf.λa.(f a)

函数应用函数将参数f应用到参数a上。对应的lua function为:

  1. function apply(f)  
  2.     return (function(a)  
  3.         return f(a);  
  4.     end);  
  5. end  
这个lua function与对应的lambda expression的语义完全一致：最外层函数接受一个参数f，函数体为λa.(f a)，也就是一个参数为a的函数。而这个内层函数的函数体为(f a)，也就是将f应用到a。

如果将此函数应用到identity：

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

会得到一个参数为a的函数。而对于lua function也是如此：

  1. apply(identity)  
会返回一个带有identity upvalue的函数对象。

如果将此函数连续应用到identity：

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

效果就和将identity应用到自身是一样的。

对应的lua调用：

  1. print(apply(identity)(identity) == identity)  
应该返回true。

接下来，我们开始构建一些基础的function，并在这些基础上构建更高层的语义。

Boolean Values

在lambda calculas中，我们可以通过函数来表示boolean values。

  • TRUE可以表示成λf.λs.f，代表选择两个参数中的第一个。
  • FALSE可以表示成λf.λs.s，代表选择两个参数中的第二个。

其对应的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  

我们可以测试一下这个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调用也成立：

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

Condition

根据Boolean value的定义，我们可以构造出条件判断的lambda function:

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

这个表达式的语义是根据boolean值b，来选择t或者f。如果b为TRUE，就选择t，否则选择f。

其对应的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  

我们可以通过将条件表达式应用到identity，apply和TRUE，来看一下结果：

λ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

同样，对应的Lua调用也成立：

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

这等同于如下逻辑：

  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(b t f) FALSE TRUE b) => λb(b FALSE TRUE)

这个表达式的语义是：当b为TRUE时，选择FALSE，否则选择TRUE。

对应的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)

这个表达式的语义是：当x为TRUE时，选择y，否则选择FALSE。

对应的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)

这个表达式的语义是：当x为TRUE时，选择TRUE，否则选择y。

对应的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  

至此，我们已经有了基本的逻辑运算符NOT，AND和OR。可以通过他们来组合出更复杂的boolean逻辑表达式。

Natural Numbers

使用lambda expression表示自然数，我们首先要定义0。我们将0定义为identity。
  1. zero = identity  

然后，定义一个succ函数，代表自然数n的下一个自然数：

λn.λb.(b FALSE n)

  1. function succ(n)  
  2.     return (function(b)  
  3.         return b(FALSE)(n);  
  4.     end);  
  5. end  
这样我们就可以定义出自然数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);  
每个自然数都使用一个函数来表示。

接着我们需要定义一个函数iszero来判断一个自然数是否为0：

λn.(n TRUE)

然后我们定义一个函数iszero，用来判断是否是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  

最后，我们还可以定义一个pred函数，用来获得一个自然数的前一个自然数：

λ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  

这里面包含了当n为0时的特殊处理。当n为0时，返回0。

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

至此，我们有了基本的自然数的表示方法。接下来，我们将利用自然数来计数，进行一个简单的循环。

Loop

在Functional Programming中，循环使用递归调用来进行。Lambda calculus的递归调用是通过将一个Y Conbinator函数引用到一个stepper函数来实现的。stepper函数代表了循环的每一次需要做的事情，而YConbinator函数则多次调用这个stepper函数，来表示循环。

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函数我们将它设计为传入一个自然数然后递减：

λ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  
当我们调用：
  1. recursive(stepper)(five)  
这个调用并没有之循环5次，而是会无限递归下去，直到栈溢出。原因在于我们对于lambda expression的reduction采用的是normal order，而lua版本实际上等于applicative order reduction。Applicative order reduction在此情况下会无限递归。解决这个问题的办法就是延迟一些字表达式的估值。我们可以将这两个函数改写为：
  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  
当我们再次调用:
  1. recursive(stepper)(five)  
我们会看到这个循环正确的执行了5次。

综上所述，我们已经使用lua function作为lambda calculas的表示形式，从新构建了一个包含了高层语义的计算模型，从而也体会到了lua function高度抽象的能力。希望对大家学习lambda calculus和lua function有所帮助。


分享到：

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： guitarhua > 《理学》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多