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

recursive(stepper)(five)

我们会看到这个循环正确的执行了5次。

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