很多程序语言所带给你的“完美”的感觉都来自于数学抽象之美。
在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。
λx.x
单位函数直接返回应用的参数。对应的lua function为:
将一个identity应用到identity,结果还应该是identity。
λx.x λx.x=>λx.x
λs.(s s)
自应用函数将参数应用到参数本身。对应的lua function为:
将自应用函数应用到identity,最终会得到identity:
λs.(s s) λx.x => λx.x λx.x => λx.x
将自应用函数应用到自身,会造成估值不能结束:
λs.(s s) λs.(s s) => λs.(s s) λs.(s s) =>...
同样,对于lua调用
λf.λa.(f a)
函数应用函数将参数f应用到参数a上。对应的lua function为:
如果将此函数应用到identity:
λf.λa.(f a) λx.x => λa.(λx.x a)
会得到一个参数为a的函数。而对于lua function也是如此:
如果将此函数连续应用到identity:
λf.λa.(f a) λx.x λx.x =>λa.(λx.x a) λx.x => λx.x λx.x => λx.x
效果就和将identity应用到自身是一样的。
对应的lua调用:
接下来,我们开始构建一些基础的function,并在这些基础上构建更高层的语义。
在lambda calculas中,我们可以通过函数来表示boolean values。
其对应的lua function为:
我们可以测试一下这个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调用也成立:
λt.λf.λb.(b t f)
这个表达式的语义是根据boolean值b,来选择t或者f。如果b为TRUE,就选择t,否则选择f。
其对应的lua function为:
我们可以通过将条件表达式应用到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调用也成立:
这等同于如下逻辑:
至此,我们已经看到,仅仅使用lua function,就可以构造出基于if...else...的逻辑判断语义。
这个表达式的语义是:当b为TRUE时,选择FALSE,否则选择TRUE。
对应的lua function:
这个表达式的语义是:当x为TRUE时,选择y,否则选择FALSE。
对应的lua function:
这个表达式的语义是:当x为TRUE时,选择TRUE,否则选择y。
对应的lua function:
至此,我们已经有了基本的逻辑运算符NOT,AND和OR。可以通过他们来组合出更复杂的boolean逻辑表达式。
然后,定义一个succ函数,代表自然数n的下一个自然数:
λn.λb.(b FALSE n)
接着我们需要定义一个函数iszero来判断一个自然数是否为0:
λn.(n TRUE)
然后我们定义一个函数iszero,用来判断是否是0:
λn.(n TRUE)
最后,我们还可以定义一个pred函数,用来获得一个自然数的前一个自然数:
λn.(COND zero (n FALSE) (iszero n)) => λn.((iszero n) zero (n FALSE))
这里面包含了当n为0时的特殊处理。当n为0时,返回0。
至此,我们有了基本的自然数的表示方法。接下来,我们将利用自然数来计数,进行一个简单的循环。
在Functional Programming中,循环使用递归调用来进行。Lambda calculus的递归调用是通过将一个Y Conbinator函数引用到一个stepper函数来实现的。stepper函数代表了循环的每一次需要做的事情,而YConbinator函数则多次调用这个stepper函数,来表示循环。
Y Conbinator:
λf.(λx.(f (x x)) λx.(f (x x)))
λs.λn.(COND zero (s (pred n) (iszero n))
综上所述,我们已经使用lua function作为lambda calculas的表示形式,从新构建了一个包含了高层语义的计算模型,从而也体会到了lua function高度抽象的能力。希望对大家学习lambda calculus和lua function有所帮助。
联系客服