文：郑元春
人生苦短，我用Python！
命令式和函数式模型是从数学家图灵、丘奇、克林、波斯特等人在20世纪30年代所做工作的基础上成长起来的。这些先驱者分别基于自动机、符号操作、递归函数、和组合学开发出了几种差异巨大的形式化模型。现在人们已经证明这些不同的理论具有相同能力：任何一种模型里可以计算的东西，在另一种模型里也能计算。这些形式化模型都可以看作计算机的数学模型。曾经看过一篇报道，里面写道。其实现在使用的遵从冯诺依曼结构体系的计算机来源于阿兰图灵的图灵机模型，从数学角度和计算模型来看，图灵机并不是最优或是最好的语言模型，图灵只是用另一种方式阐述了计算过程。这也从侧面说明了前辈们提出的各种计算模型都是能够相互转换的，古语云：条条大路通罗马！
一/图灵机--计算机雏形(Turning Machine)
图灵机:图灵的计算模型
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
- 在纸上写上或擦除某个符号
- 把注意力从纸的一个位置移动到另一个位置
而在每个阶段，人要决定下一步的动作，依赖于:
- 此人当前所关注的纸上某个位置的符号
- 此人当前思维的状态
为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成:
1.一条无限长的纸带TAPE
纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号[ ]表示空白。纸带上的格子从左到右依次被编号为0, 1, 2, ...，纸带的右端可以无限伸展。
2.一个读写头HEAD
该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
3.一套控制规则TABLE
它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
4.一个状态寄存器
它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。
注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。
[以上采集自维基中文图灵机]
在图灵机组成部分中我们可以看到如今的计算机的雏形。比如纸带可以当成内存，读写头可以看做地址寻址，控制规则可以看成CPU执行指令，状态寄存器就是CPU内的寄存器。
二/lambda 演算(Lambda Calculus)
λ演算（英语：lambda calculus，λ-calculus）是一应用于研究函数定义、函数应用和递归的形式系统。它由阿隆佐·邱奇和他的学生斯蒂芬·科尔·克莱尼在20世纪30年代引入。邱奇运用λ演算在1936年给出判定性问题（Entscheidungsproblem）的一个否定的答案。这种演算可以用来清晰地定义什么是一个可计算函数。关于两个lambda演算表达式是否等价的命题无法通过一个“通用的算法”来解决，这是不可判定性能够证明的头一个问题，甚至还在停机问题之先。Lambda演算对函数式编程语言有巨大的影响，比如Lisp语言、ML语言和Haskell语言。
Lambda演算可以被称为最小的通用程序设计语言。它包括一条变换规则（变量替换）和一条函数定义方式，Lambda演算之通用在于，任何一个可计算函数都能用这种形式来表达和求值。因而，它是等价于图灵机的。尽管如此，Lambda演算强调的是变换规则的运用，而非实现它们的具体机器。可以认为这是一种更接近软件而非硬件的方式。
Lambda演算伟大的原因有很多种：
- 非常简单
- 图灵完备
- 容易读写
- 语义足够强大，可以从它开始做（任意）推理
- 他有一个很好的实体模型
- 容易创建变种，以便我们探索各种构建计算或是语义方式的属性
在图灵机模型中，所有的计算都会表达成一种状态的转换，从程序的开始到结果的输出，里面的计算都是建立在读写头和状态寄存器基础上。在Lambda演算中，它是建立在函数的概念基础上，纯粹的Lambda演算中，everything is function，连值的概念也没有。对于一个演算，需要定义的基本元素就只有两个：
- 语法（描述如何在Lambda演算中写出合法的表达式）
- 一组规则（符号化的操作表达式）
Lambda演算有3类表达式：
1.函数定义
函数是一个表达式
lambda x. body
一个参数是x的函数，他的返回值是body的计算结果。这里，lambda表达式绑定了参数x
2.标识符引用
标识符引用就是一个名字，这个名字用于匹配函数表达式的某个参数名
3.函数应用
将函数定义用于实际的演算中，把函数值放到它的参数前面的形式
(lambda x . plus x x) y
柯里化
Lambda定义里面函数只接受一个参数，这对于有多个参数的函数实现起来有很大的局限。但是这里一定要有个思想的转变（函数就是值，演算中的函数可以返回值或是返回一个函数）。
举例，实现加法x+y：
lambda x.(lambda y. plus x y)
由于只能是单参数的函数，所以第一层里面的函数返回的是一个函数（返回的并不是值），这样就能够实现多参数函数的功能实现。
本质上，添加多个参数的函数并没有添加任何的东西，实际上是简化了语法。
Lambda演算运算法则：只有两条真正的法则：称为Alpha和Beta，Alpha称为【转换】，Beta称为【规约】。
1.Alpha转换
Alpha是一个重命名操作，就是说变量的命名是不重要的，我们可以修改表达式中的参数的名称，只要同时修改函数体内对他的自由引用。
lambda x . x^2 -> alpha[x / y] <- lambda y . y^2
这样丝毫不会改变表达式的含义，但是这一点很重要，它可以使得我们实现比如递归之类的事情。
2.Beta规约
这条规则使得lambda演算能够执行任何可以由机器来完成的计算。如果你有一个函数应用，你可以对这个函数体中和对应函数标识符相关的部分做替换，替换方法是把标识符用参数值替换。
(lambda y . (lambda x. x+y)) q这是一个创建函数的函数，他的返回body是一个函数，用标识符（值）q来替换所有的引用参数y,所以，其结果是lambda x .x+q
(lambda z . (lambda x . x+z))，假设我们应用它：
(lambda z . (lambda x . x+z))(x+2)
这里面应用标识符 x+2中x是自由的，但是函数里面的x是绑定的。如果直接使用Beta规约得到的结果是：lambda x .x+x+2
如果先使用Alpha转换alpha[x/y]得到的结果是：lambda y . y+x+2
当使用3来做计算的时候，两个的结果是3+x+2和3+3+2（大相径庭）
三/对比
图灵机是通过不断的挪动读写头在纸带上的位置，通过每一条命令来进行计算。基于这种语言模型的高级语言，就像C++/Java/Python等，都是通过程序语句改变内部变量的值来控制流程和输出。这种命令式的语言内部是存在一种状态的转换过程的，跟图灵机状态转移是一致的。而Lambda演算可以说是更贴近理论上的推理和数学上的演算，跟现在的硬件结构关系不大，Lambda演算中的一切都是从输入到输出的函数。
网友评论