计算模型大致可以分为两类，λ演算和其他…好吧，也许Post的产生式系统和Herbrand-Goedel等式属于前者，但是毋庸置疑所有总所周知并且被广泛接受的模型比如图灵机，RAM和λ演算可不是一类的。Guy Blelloch将这类差异划分为语言和机器。基于机器的模型全部是在无界内存下的有限控制理论基础上讨论的。它依靠程序员去管理内存，实现一切结构，并且没有记号，没有解释器这样的机制在运行时改变程序；机器模型全部是非冯诺依曼机，因为它们没有存储程序的思想。基于语言的模型，相较之下，没有把程序和数据分开，并提供建立真实语言的基础，直接且没有编码。这似乎是一个λ演算的决定性优势：尽管机器模型出现在我们教材的前几章，但是他们本质上没有实际重要性，而λ演算对编程和逻辑系统的机械化来说是直接有用的。但现在机器模型仍然处于主宰地位，特别是算法和复杂度的领域，λ演算却作为冷门怪异的知识仅仅被计算机科学家的一小部分人研究。这是怎么回事？
遇到这个问题时，我的同事（至少在理论这边）认为这个问题一点意思都没有，回避了这个问题，因为“所有计算模型都需要多项式时间”，so who care? 好吧，如果你的工作在多项式因子的复杂度完成，并且你只关心对自然数（或者其他有限对象）的计算，那我猜这问题确实无所谓。你把某个问题算了一遍，对于那些利益相关的对象是如何在某个模型上表现的毫不关心，那细节的确无所谓。
但是明显地这些模型有所谓，事实上，说这话的同事在任何情况下都不会考虑经典的机器模型作为他工作的基础！毫无疑问，如果这些模型都是等价的话，选什么没关系，所以我们都可以选择λ演算，对吧？好吧，确实是这样。显而易见，有些模型是比其他模型更合适的！怎么会这样？
一个原因是许多工作并不是取决于多项式因子的（有人可能更认为，大部分都不是的）。所以对于这些目的，模型是有所谓的。另一方面，没有人在实际工作中用“正式的”模型。没人用图灵机码去描述算法，甚至RAM代码也没有用（Knuth是个例外）。反而，他们用的是类Algol语言，或者类C语言，或者类似的命令式编程符号。也就是说，他们用的是编程语言，而不是机器！他们当然这么做。但那又为什么强调机器模型呢？他们写的那些语言意味着什么？
答案是这些语言是由描述这样那样的类Algol语言如何对应于这样那样的RAM代码或者图灵机码的解释器定义的。这种表述虽不正式，但已足够准确使人明白。关键是，你推理的不是你写的代码，而是编译器写的代码，因为正式来讲目标代码才是“真正的”代码，伪代码只是提供一个方便。所以在工作中，你脑子里必须有一个编译器：它对一切你写的代码都清楚明白，知道如何翻译成，比如RAM代码。这并不是太难，因为伪代码简单，简单到你可以直接在脑子里编译它。这种方式不错，但是会逐渐出现问题，因为它约束了我们表达算法的语言从而限制了我们能够方便表达和分析的算法的范围。
那为什么坚持使用这样麻烦的方式呢？一个原因是，传统。我的导师用它，所以我也用它。或者，如果你想要发论文，你最好用一种评审熟悉的风格写。
一个更实际的原因是，机器模型是描述计算开销的基础。计算的一“步”就是机器的一步，我们通过估算解决同一问题算法的步数来比较算法（取决于乘法因子，大部分情况下）。只要我们能够“手工编译”类Algol语言到机器码，我们就可以给一个比汇编语言高级的语言赋一个开销，还可以对各类算法做合理的比较。这种方法良好的满足了我们的需求，但是现在它开始没那么管用了（并行是一个原因，但还有许多其他理由）。
有一个替代选项，为我们书写的语言提供了开销语义，并且直接地在这个基础上开展我们的分析，不用迎合编译器或者依赖机器。简而言之我们采用了计算的语言模型，而非机器模型，生活更美好！表达算法有更多的方式，还简化了分析算法的方法。
要用这种方式我们需要我们使用的语言一个开销语义。这也就是λ演算的优势，因为它是描述计算的语言模型的典型例子。简单来说，λ演算的右箭头标记表示一步推导，写作M→M’，表示M程序经过一步计算之后的结果为M’程序。执行过程直接由我们写出，并且模型还为计算步骤提供了良定义的标记，我们可以数出来获取程序的时间复杂度。数十年的经验表明这种方法扩展到了真实语言。
有什么缺点呢？我个人找不出什么缺点。我一直很困惑，觉得λ演算应该在算法圈子里被接受。正如任何机器模型都被当做完美的计算基础，而业界的行为都显明机器模型对实际完成的工作有很大的限制！
唯一的原因我觉得，除去强大的社会影响，就是停滞不前，还未发现λ演算里关于开销的概念对算法分析的适合。（一个研究员最近告诉我“你可以塞一头大象在β推导里！”，然而他还是没法解释我哪错了。）一种验证这个观点的方法就是，定义出一个λ演算到RAM代码的编译器，确保λ演算里的抽象步骤能被RAM在常量时间里实现（不考虑输入大小，只考虑静态程序的大小）。Blelloch和Greiner在90年代初已经精确的完成了这项分析。详见Guy’s web page。
之后的博文里我会深入的考察这些思想，并且表明（通过检查Blelloch的工作）λ演算不仅可以作为一个串行算法的良好模型，对并行算法也是一样！而且我们可以轻松地把模型扩展为具有重要抽象能力的语言比如高阶函数或者不用优化就能表达和分析算法。
翻译 by locatino
原文