计科理论方向参考鄙视链

看上去有现实需求非得定义一个序以正视听。“链”嘛，离散数学里都摸过的吧？不过其实也不需要是全序。

首先，通用计算模型定义了所谓计算机科学(CS)的天花板。不考虑计算模型，CS作为学科的边界就是模糊的。

其次，根据应用需求，计算模型退行到更具体的领域特定模型，历史地看，主要分为体系结构和其它所有模型两大方向。

体系结构研究的计算模型即计算机模型。具体计算机的物理实现直接或间接依赖这些模型。

其它模型是不一定依赖体系结构的各种领域特定模型，例如AI有AI的模型，别的业务有别的模型。但这些模型的实用实现依附于计算机模型，所以这里整个作为“其它”。

值得一提的是，编程语言理论(PLT)是理论CS中最特殊的，因为它首要研究对象是编程语言(PL)的模型。即便历史地看，体系结构模型独立于PL模型发展，但补充理论进展之后，具体的计算机模型是可以通过PL模型derive的，所以比所有体系结构层次还要高。

而PL为所有不依赖体系结构的其它模型在计算机的提供可行性保证。考虑只有计算机模型是无法实现应用意义上的计算的，PL模型同样比其它非体系结构意义上的传统模型更加普遍。

没有任何其它领域特定模型有这样的特殊性。某种意义上，PL模型是计算模型的最嫡系后裔，即便体系结构的计算机模型也不能与其相提并论。

当然历史是一回事，现实又是另一回事。但理解一个领域的整体问题，两种视角都是必要的。尴尬的是，两者都不太被许多从业者足够重视。

这间接地导致了科班背景是一个笑话——计算机科学出身的，连什么算计算机科学的问题都不知道。跨考和转码倒是因此不受那么大的影响，不知是不是好事了。

虽然更大的背景下，究竟什么叫“科学”也是个争议不休的问题（科学哲学的科学划界问题），放在这里还是有些过了。

所以这里从重新梳理一下脉络，标注一些本应是常识的基础问题。

通用目的计算模型的例子有不少，不过值得提的，也就是著名的LC(λ-calculi)、CL(combinatory logic)、TM(Turing machine)、μ-递归函数等。

值得一提的是，这些模型的提出早于理论CS的正式建立。这段前CS历史有不少超越CS本身需要被关注的地方，值得作为所有当代理工科学生的常识，因为它涉及到数学的根本。

本质上，计算模型是关于计算的形式系统。形式系统是数理逻辑这种数学基础(fundamentals of mathematics)方向研究的对象。

有的形式系统，作为具体的数学基础(foundation of mathematics)被这些领域建立。最通用的是集合论(set theory)和某种外挂的描述逻辑的元语言复合的系统。

其中作为当代数学家最通用的基础技术栈是ZFC(Zermelo-Fraenkel set theory + Axiom of Choice)+FOL(first-order logic)。

这里，E. Zermelo和A. Fraenkel提出和发展的公理化集合论分阶段地解决了一些G. Cantor（以及R. Dedekind）的朴素集合论的具体技术问题，但全局影响最大的是可能解决了第三次数学危机。

这里最著名的表现是B. Russell提出的罗素悖论(Russell's paradox)。

为什么需要特意提到这点？因为和Zermelo集合论同在1908年提出的Russell本人的解决方案是添加类型(type)进行限制。没错，这是作为PLT的研究方向之一的类型论(type theory)的鼻祖。

也就是说，事实上，现代普遍被视为CS一部分PLT其实也是早于整个CS的，某种意义上甚至更加先于上述计算模型——而严格意义上的“计算”此时还不存在。

这又被公理集合论（所有的，不只是ZF/ZFC）的两方面局限性：

1. 因为公理集合论是关于逻辑推理的模型，它不是关于计算(computation)的。关于逻辑和计算的关系会在之后描述。

2. 集合论需要外挂语言操作关于集合论自身的形式化。后期数学一个主流做法是发展出范畴论(category theory)作为替代基础，把集合论的部分（Set范畴）作为特例。然而，这并没有被大多数职业数学家接受；反倒和PLT又有更加说不清道不明的关系，被不少折腾CS的玩家继续捯饬。

所以从出身上，PLT这部分的源流就早于整个CS，更不用说关于体系结构的计算机模型和依赖计算机的模型了。

历史地，CTT(Church-Turing thesis)定义了什么叫计算。LC和TM就是为了解决其中具体问题提出的，作为CTT的一部分，是D. Hilbert（以及W. Ackermann）于1928年提出的可判定性问题(Entscheidungsproblem)的解——即可判定性问题现实上不可实现。

具体地，1930年代，A. Church为研究数学基础（包括可判定性问题）提出UTLC(untyped typed lambda calculus)描述可有效计算(effectively calculable)这一关于作为逻辑操作可形式描述的计算过程的性质。这种基于可有效计算的描述的计算过程即为算法(algorithm)。

同期的A. Turing是Church的博士生，但他不按老师的方式出牌，1936年独立地提出的a-machine(automatic)，后来在Church的review下命名为Turing machine。

TM通过不同方式重新定义了算法。TM上的算法操作被CTT视为等价UTLC上可表达计算的项(term)的规约(reduction)。

基于CTT，其它的一些依赖近似有效计算概念的计算模型（如μ-递归函数）上有相似过程的一些形式被统一表述为可计算函数(computable function)。

这些等价方式事实上定义什么叫计算并给出了关于计算自动化的理论方向，标志理论CS作为独立学科的诞生。注意，CS是关于一般的可自动化的现象，所谓的computer是计算的理论实现，比之后物理实现的计算机要抽象得多（这个意义上“计算机科学”这个翻译并不够信达雅）。

当然，理论CS还有一个更加侧重传统数学的其它来源，特别地，信息论(inforamtion theory)。但这更多地是描述计算系统的统计理论，而非任意细粒度的计算自身的分析性的理论，在此略。

在理论CS之后，如何物理实现自动的计算是一个实际的问题，这个需求直接开启了体系结构研究这个方向的建立。不过这个方面的实践领先于理论研究。和许多误解不同，TM并没有给物理实现提供多少实际的指导（尽管战后Turing本人负责过英国的计算机项目）。

EDVAC之类的方案揭示出很多实用的经典顶层设计（例如区分内存和外存）并非来自理论的指导，而是工程师根据实际限制和需求提出的。这个意义上，体系结构模型很多是后设的简化——而并非计算模型的派生。

另一方面，在物理计算机提供可编程特性后，如何减少人工干预，设计可被自动处理的程序推动了应用PL的建立。类似地，PL在应用上也是先于理论研究的。一个例子是，Lisp的作者J. MaCarthy承认他并不很理解LC，照搬和LC同构的语法只是为了简化抽象的编程应用。但这已经反映出了通用计算模型的威力。

在某种意义上，基于LC派生的具体模型定义了什么叫高级语言。另一方面，1924年M. Schönfinkel提出（以及1927年起H. Curry重新发现和提出）的CL可以视为UTLC中去除λ抽象(lambda abstraction)的语法而以具名组合子(combinator)替代的系统，在这个意义上，可以认为是去除了抽象的低级语言。

所谓的λ抽象是LC中以符号λ引导的项，对应于现代PL中的匿名函数。而Lisp等方式可使用匿名函数导出的具名函数的特性。这也是为什么可以说LC定义了高级语言而CL是低级语言，因为有和没有函数就是两者的首要差别。

需要指出的是，十余年之后流行的E. Dijkstra的结构化编程的程序构造的定义甚至并不太涵盖同期已有的PL（考虑Lisp的年代，再考虑P. Landin的J operator等等），连应用限制都被D. Knuth拿来diss，算不上是多严肃的分类，因此现代一般也仅作为历史注记。

以一般的函数，而非其它“控制结构”来界定高级语言的分野，在现代这已经不是一个开放问题，尽管非PL背景的工程界知者甚少。

另一点鲜为人知的是，Church本人也试图给LC做减法，移除K组合子而把原始的LC称为λK演算，以满足更好的逻辑（可证明）性质。但是，它并不能表达一般的偏可计算函数(partial computable function)，因此后世仍把LC叫做LC而非LKC，Church本人的这个弱化的变体称为λI演算。

不同于传统的纯数学，基于LC的计算模型允许非传统数学意义上的扩展，例如副作用(side effect)。这使UTLC的可扩展性比其它计算模型显著地多。

尽管关于LC的派生的理论和描述现有PL的工作在1970年代之后才开展，这不能弱化理论上远超于工程领域的进展的后果。

另一方面，CTT的UTLC“不停机”结论促使现代类型论研究的开展。STLC(simply typed lambda calculus)在这类理论中占据基础核心地位，关于类型系统的演算几乎全是扩展自STLC，包括著名的λ立方体(cube)。

对工业界（的底层），LC的一个间接的主要影响是，直至2010年代的新的实用PL仍有以所谓lambda表达式等特性作为卖点。这在许多已经支持了“函数”的工业界PL中也屡见不鲜，例如Java和C++。落后80年的显然只能成为被鄙视的背景，而非鄙视其它领域的资本。

也就是因为这个认知上的显著断层，才有“语言只是工具”的调调。

实际上，语言作为描述计算的方式，不间断地影响着用户。往往是用户对此没有自觉——特别是对改变语言满足需求的实现这个方法完全无能为力——才有这种错觉。

为什么不会想到去改进现有的语言，和适应语言的限制，是理论CS背景和基础不可靠的用户迟早会面对的鸡和蛋的问题。（如果不是，请不要说自己具有CS背景。）

在学术上，LC这样的模型有另外的重要影响。

它们本质上和范畴论类似而不同于集合论，提供的模型和形式语言是一体的，不需要外挂的逻辑作为元语言，因此足够作为数学基础的需要。不同的是，范畴论更直接地符合数学直觉主义的需要，适合拿来当做胶水语言来用，它的扩展的繁琐仍然是成问题的——也就是纯数学意义上形式化的进度未必有1930年代就有的基础来的快。

重点是，这种一体化是个“计算”性质。过于强调逻辑上的完美，就会像Church做减法一样损失计算上的可用性，导致反而不够格作为数学基础；要么就是只能退一步外挂个逻辑语言了。

说这个是为了强调，纯数学就未必（在实现理论CS和数学的共同目标上）更先进了。

再比如说，什么叫函数(function)？这是隐藏的含糊问题普遍得离谱。尽管大多数现代的职业数学家在被Burbaki的严格形式化启蒙运动系统地洗脑过一遍，他们尚且未必能分清function relation和proposition function（理解还不如臭写代码的），摊子还稀烂着要数理逻辑学家（如A. Tarski）擦屁股；范畴论把function弱化为Set范畴中的数学对象而另外启用morphism的语义（但本质上是语法）糖，凭空新增一大堆架构可维护性和人机工效上的问题——这其实也是一部分数学家不太吊范畴论这套的原因——遗憾的是不少PLT fanboy反而也给绕进去了，真是岂有此理。（而且，不管哪个方向，数学教学上都会是灾难；c.f. 新数学运动。）

另外的例子是，在元数学范畴和数学哲学领域中，Benacerraf's identification problem这个幽灵一直没有被排除——到底是集合论那坨{{}}还是其它方式（比如LC下的Church numeral；其实光是集合论就不止一种）才是自然数的“本质”？然而换个懂点OOP混子，就可以说，什么乱七八糟的realization，只是满足Peano axiom这么一个定义什么叫自然数的interface的implementation罢了（虽然还有不少剩下的其它技术问题）。

这些例子倒不是为了鄙视数学界，毕竟大多数情况下，做模型的仍然是在擦形而下的应用需求的屁股，都不配觉察到这些问题。但可以反思一下，说CS本质是数学的fanboy，究竟和实际的当代数学的状况有多少差距？这些人理解的数学到底是哪门子的数学？

再顺一嘴，很多现代数理逻辑的工作仍然是传统意义上的逻辑学家而非数学家在做。这有个直接的尴尬：很多数学基础的问题，其实是所谓西哲（具体来说是分析哲学）的课题，也得指望他们而不是职业数学家来解决。

关于如何建构整个数学并以计算的方式简化普遍工作，这部分仍然有不少开放问题。特别是关于Church style v. Curry style（设计语言时先有类型系统还是先有语义——注意Church支持前者，这里顺序没反）在现实的应用，就不展开了。

还有一些关于NBG set theory、Curry-Howard[-Lambek]同构、PTS(pure type system)，之类的话题上，全局上相对比较次要，这里也略。

不过……这也不妨碍我认为von Neumann作为NBG的作者而不是ENIAC这种集体智慧上凑人头而更显得牛逼——后者的工作再多几倍，也是没法让他有接近Hilber以及H. Poincare相提并论的历史地位的；顺便Turing比起来真只能算是二流了。

反正到此为止，考虑历史成就和数学的缓慢进展，理论CS现在就是已经够格搭上哲学回过头来鄙视某些数学的。

回过头来再看需要鄙视链的主要用户——电池们——的角度。

“语言只是工具”以及CS和数学之间关系的问题已经批判过。那就再补充点具体的领域特定的对象。

比如说——“算法”。

算法是可计算理论（或者说更数学地，递归论；只是更强调蕴含计算复杂度理论和分析方法）的研究核心对象之一，也是证明论需要处理的输入没错；但搞数学的做算法，首先就是要求严格形式的描述，跟电池们要做的“算法”工作，很难说是同一个玩意儿。

后者基本上其实只是特定的实现，其实跟做工程落地的并没高下，反倒更加像是给一个降低编码经验要求的机会掩盖实际编码经验的不足。

当然，是会有一些企业赞助更像样的算法研究，但那跟正经研究其实也就是老板是谁的区别，已经不算是电池们的工作了。即便如此，应用上的压力和已经填满得差不多了的坑（比如《算法导论》和TAOCP会出现的基础问题），导致很少有开辟新赛道的机会。

……啥，量子计算？那不是和体系结构研究结合的复合方向么？不过这么一想，其实传统“搞算法”的撑死其实也就是和经典计算机模型结合的下游应用罢了。因为，一旦完全脱离具体机器，有价值的算法研究很难不上升到常规计算模型甚至更高（比如Kleene's arithmetic hierarchy，比如hypercomputation）的层次，而适合仅仅用“算法”相对low穿了的方向来概括。

退一步讲，仅仅是应用“算法的”思路和折腾算法也并没那么直接的关系（更不说刷题经验了）。多背背赛马题之类的面经，就能指望思路活跃到发明sorting network出来？做梦。

题外话，像“算法”重要性的怪谈的流行，多少是因为需求方对人力的筛选手段比较后进。毕竟手撕所谓算法题还能看出写出来代码长啥样，比起纯粹八股已经算像样了。

但是就算所谓的ACM（实际上是ICPC）获奖经验，又能说明个啥呢？适合工程需要的检验方式本来就极度依赖业务的实际特性，基本是不可能通过几个小时就能出来的输出质量的比较就能确定适配程度的。用手撕看上去更标准化和公平的方式评价，其实跟退回去用教育背景筛选简历相比没差多少——后者还有因为HR工作量而有辩护的余地。

而脱离“语言只是工具”的低级趣味，能问的瞬间就多出很多了。比如“为什么要这么设计”的问题。不过，这回压力就给到旧八股既得利益者身上了。考虑到lambda后进了80+年在工业界重新上位之类的笑话，这部分，现在应该远远是不够卷的。

再比如说——“数据结构”。

这词只不过和“算法”并列得比较多，就顺带针对了，压根就没在上文出现，因为这本来就不是什么系统的研究领域。能成论题的，都是攀附——例如什么FP语言，就有FP数据结构。

光看这层依赖，还能小瞧语言么？

再者，这其实都没法跟算法这个话题比。

什么程序=数据结构+算法的N. Wirth笑话也有人信。懒得分析，直说Wirth咖位能提供多少可信性好了。嗯，理论上好像没啥系统的啊——那就说做了啥语言好了（McCarthy除了AI和发明GC也不是搞了Lisp么），emmm，糊了Pascal……然后看看Pascal和后裔都在吃啥饭？OJ题？好意思说？

J. Backus也是个不咋地的反面教材。搞出语言翻译的idea是不错（BNF这个只能是小菜），但原版FORTRAN这至少跟BASIC一样brain-damaged（因为没有过程(procedure)；brain-damaged是引用Dijkstra说法）的设计，能说明啥？要说原版那么挫比，是因为历史局限性，那跟一年后的LISP比一下，是不是伤害就出来了？而且还后进得不是一点半点，到Fortran77，spec里有要求支持递归调用了？后面的新版哪个不是抄的当时的其它语言，有啥业务先进性？

这里能看出，设计语言的方面直接是有鄙视链的。McCarthy建议保留递归顺带解决ALGOL的spec bug，战斗力一下就不是一个档次。反观Backus到1970年代也只能吹出个FLP(function-level programming)，不知道是不是APL的point-free入脑了。（其实对应到计算模型就是把λ抽象给去掉，改换类似μ-递归函数的方式添加组合子，模型实用上就高下立判。）而且后面流行FP是不是打脸了？

说到FP，还有更多的FP自己的黑屁就不放了，有碍观感。

嗯，跑题了。这是因为数据结构这个话题实在撑不起什么话题，或者说用什么库什么接口，归根过于形而下，流于使用经验而非思路的考察。否则就跟某些抽象代数boy以理解多掌握几种结构就好意思嘚瑟一样了（纯FP语言中这些数学结构还真一般直接对应抽象数据类型）。

非得回来多黑屁一下，那有另一类工程话题。

可能有人听说数据结构的选取比算法的选取更重要云云。

请把这个也当屁放了，因为这里的前提是抽象能力足够的语言导致代码可修改性很烂，所以一开始作为被依赖项的数据结构选取的决策影响远远比改算法更大。换个抽象像样的方式把依赖解耦掉就无关大局了。

（看，又和语言过不去。或者至少跟语言的选型有关，至少对没本事手糊语言的开发者如此。）

当然有抽象能力也得会用。比如用C++的往往知道sequence container requirements，可以using一个容器类型当placeholder别写死。要是这种雕虫小技都不会，就别说什么GP(generic programming)了。（——这个例子就可以看出具体的数据结构选取实际上可以不那么重要，甚至可以推迟返工。）而C也有typedef，为什么C用户圈子这种方式不那么常见呢？主要因为C门槛低导致用户不够卷，没形成idiom。

不够卷也不是好处，会限制能用的技术手段。都说TMP(template metagramming)奇技淫巧，但该用还是用。反观有几个C用户熟练到日用MMP(macro metaprogramming)么？思想包袱成本高下立判。

这里再次体现了对语言的适应会影响用户的思维，语言实际上不可能只是工具。

这种思维对理论的摧毁甚至可以是系统性的。例如Linux Kernel Coding Style还有公然限制typedef _t name是mistake这种鬼话，全然不管名义类型(nominal type)是什么用的（流石C boy，跟Rob Pike混淆nominal type system瞎指点type system一样水）——列了一堆bullets却完全没注意_t是为了设计而不是代码实现引入的这个共同点（提一下又不会死……）。

不过这个也看人或者说自信程度。同样是设计出恶心玩意儿的C用户，POSIX的Austin group就实诚多了（虽然有的设计烂的是真烂）。C++用户经常唯恐对低质量的语言特性掌握不够而时常不敢说自己精通，反倒真能节约滥用特性导致的一些工程成本。

对不起，又不自觉跑题了。因为“数据结构和算法”真的不是noob以上应该多关注的很有兴趣的话题——不是说配不配居于鄙视链的某一个层次，而是说作为工程实现手段上的细节，有没有不配被提起的问题。

要是做有价值的相关基础研究的，自然不会泛泛而谈。

还有更具体领域的理论，其实各有应用价值，就不需要被针对鄙视。

（虽然某种意义上，可能是被鄙视的资格都没有。在强调普遍性来讲，这样倒也没错。）

可能值得一提的就是所谓AGI的G有多假。但滥用炼丹和缺少分析性结论这主要是方法论上的，跟CS本身没太大关系，所以不需要多展开了。

毕竟不那么G的AI，在可用性上已经取得了一些突破。就是没法帮助推进上面的问题的解决罢了。