第一部分 计算的本质——从哲学到数学本文内容摘自本人的开源书《从沙子到车辙 - 一个工程师的理解》 在线阅读/下载from-sand-to-rutsgitclone https://github.com/Lularible/from-sand-to-ruts⭐ 如果对您有帮助欢迎 Star 支持也欢迎通过 GitHub Issues 交流讨论。1.1 什么是计算一间屋子一叠白纸你被困在一间屋子里。房间里有一张桌子、一把椅子、一叠白纸、一支铅笔。墙上有一扇小窗偶尔会有人从窗口递进来一张纸条上面写着一个数字。你可以看一眼纸条然后在白纸上写字、画图、撕掉、揉成一团。你也可以把一张写好的纸从窗口递出去。问题是你能否判断递进来的那些数字中是否有两个是相同的你可能会说这还不简单把每一个递进来的数字都记下来新的数字来了就翻看之前的记录看看有没有重复。但等等——那叠白纸是有限的。假设只有 100 张每张纸只能写 50 个数。窗口递进来的数字可能有几千个。在有限的白纸——也就是有限的记忆空间——和有限的时间——也就是天黑之前必须给出答案——之下你能否完成这个任务如果有无限的白纸、无限的时间这个问题当然可解。但现实中你总是在有限资源下工作。这就是计算的本质问题。在计算机科学里这个问题叫做集合成员判定问题set membership。在内存和查找次数都小于数据流长度时绝对的精确判定本质上不可能——这不是困难而是原理上的天花板。现实的出路只有两条要么放宽资源上限要么接受近似解。一个没有计算机的人会怎么做也许把数字从小到大排列在白纸上——新数字来了折半查找。如果白纸快用完了就只记录那些出现频率最高的数字。如果实在装不下就放弃精确答案用概率方法给出近似结果。你逃不出资源的牢笼。一切计算策略本质上都是在限制下做最优选择。算法白纸上的兵法让我们把刚才那个判断重复数字的过程用工程师的语言写下来。这不是某种特定编程语言而是任何懂逻辑的人都能读懂的伪代码——它本身就是计算的食谱算法在有界内存中判断重复数字 输入一串数字流 D[1], D[2], D[3]... 从窗口递入 资源N 张白纸每张可写 M 个数字总容量 C N × M 输出发现重复时返回 true纸用完时返回 unknown 步骤 1. 维护一个有序列表 S初始为空 2. 对于每一个递进来的数字 x a. 在 S 中二分查找 x - 如果找到输出 true发现重复终止 - 如果未找到继续 b. 如果 S 的大小 C - 将 x 插入 S 中正确位置保持有序 - 继续处理下一个数字 c. 如果 S 已满 - 输出 unknown白纸耗尽无法判定 - 终止你看这就是一个算法——确定的步骤、有限的资源、明确的终止条件。这里没有灵感、没有顿悟、没有运气。每一步都是机械的。这个算法有什么问题对——它可能输出 unknown。在资源有限的约束下正确性不再是百分百对而是在能力范围内做到最好。这就是现实世界的计算。你在 ECU 上跑的每一段代码本质上都是这个算法的变体你有 64KB 的栈空间你有 10ms 的周期预算你有 8 个优先级的抢占调度——你总是在约束下做最优决策。现在我们退一步。这个白纸铅笔窗口的模型到底抓住了计算的什么本质是三个东西输入、规则、输出。你拿到输入纸条上的数字按照确定的规则二分查找 有序插入产生确定的输出true 或 unknown。这套模式——输入、规则、输出——在人类的文明史上早就有迹可循。而且演化了数千年。算盘、骨头与齿轮计算工具的前世在讨论图灵之前我们需要回到更早的起点——人类是从什么时候开始计算的算盘大约出现在公元前 500 年的中国。它本质上是一个手动操作的寄存器组——上面两珠子代表 5下面五珠子代表 1每列是一个十进制位。你拨珠子就是在改变存储单元的值。算盘的巧妙之处在于它是一种人机协作的计算模型。人负责提供算法口诀算盘负责提供状态存储和机械操作进位。它没有自动化的运算器但它是人类第一次把计算从脑子里外包到一个物理工具上。算盘在中国用了两千多年。但西方走了一条不同的路。1614 年苏格兰数学家约翰·纳皮尔John Napier发明了对数并制造了纳皮尔骨筹Napier’s bones——一组刻有乘法表的木棒。你把木棒排列起来就能把乘法转化成加法。这本质上是一个查表机器——它不计算它只是把预先算好的结果存储起来供你检索。纳皮尔骨筹很聪明但它不能自动化。它还是一把辅助尺不是一台自动机。紧接而来的是计算尺slide rule。1622 年威廉·奥特雷德William Oughtred把两根对数刻度的尺子放在一起滑动它们来做乘除运算。计算尺的原理是纳皮尔对数的直接应用log(a×b) log(a) log(b)。你滑动尺子就是在做加法而刻度告诉你加法结果对应的真数。计算尺不擅长加减法——它只擅长乘除法——但它在工程领域统治了三百多年。阿波罗 11 号的宇航员带着计算尺上了月球以防那台只有 4KB RAM 的导航计算机失灵。把复杂运算映射到简单运算、把精确运算映射到近似运算——计算的思想从一开始就带着降维的基因。但这还不够。这些工具只辅助计算不自动计算。真正的转折发生在 17 世纪。帕斯卡和莱布尼茨齿轮上的梦想1642 年19 岁的布莱兹·帕斯卡Blaise Pascal在法国鲁昂看着他的税务官父亲每天跟成堆的账目搏斗。他决定造一台能自动做加减法的机器——帕斯卡加法机Pascaline。这台机器的核心是一个黄铜齿轮组。每个齿轮有 10 个齿代表 0 到 9。当你拨动齿轮做加法时每转满 10 个齿就通过一个棘爪机构推动高位的齿轮前进一格——这就是进位。帕斯卡加法机是世界上第一台真正的机械计算器——虽然它只能做加减法乘法可以通过反复加法实现除法也可以通过反复减法实现只是非常慢。帕斯卡造了大约 50 台现在仍有 9 台存世。帕斯卡的机器很美但有一个严重局限它只能做加减。乘除需要人工把运算分解成多次加减这实际上混淆了计算和操作者的界限。帕斯卡加法机没有解决自动进行复杂计算的问题。三十年后的 1673 年莱布尼茨在巴黎展出了一台更先进的机器——莱布尼茨阶梯鼓轮计算器Stepped Reckoner。莱布尼茨的天才之处在于他设计了一种阶梯鼓轮——一个圆柱体上面刻有 9 条不同长度的齿条使得不同位数的齿轮可以啮合不同的齿数。这使得他的机器能直接做乘法你输入被乘数转动曲柄机器自动完成累加操作。它甚至能做除法。但更重要的是莱布尼茨不只是个工程师——他是第一个把计算和哲学等同起来的人。他在设计这台机器的同时正在酝酿一个更宏大的想法如果数字可以在齿轮上自动运算——那逻辑行不行推理行不行人类的全部知识能不能也有一套通用表意文字Characteristica Universalis让所有争议都变成算一算就清楚的问题莱布尼茨的机器因为 17 世纪的精密加工水平达不到要求而频频卡齿——但他在哲学层面埋下的种子长出了整个现代计算机科学的大树。冯·诺依曼说计算机是逻辑的机器时他只是在回应莱布尼茨。巴贝奇和艾达超前了一个世纪的幻想帕斯卡和莱布尼茨造的是计算器——它们能根据输入的数值算出结果。但真正接近通用计算机的狂想来自 19 世纪的英国。查尔斯·巴贝奇Charles Babbage是个脾气很坏的人。他讨厌伦敦街头的风琴手说他们污染了城市的声学环境、讨厌出版商、讨厌英国政府。但他有一项无与伦比的才华他可以用机械零件——齿轮、杠杆、曲柄、滑块——构建极其复杂的逻辑系统。1822 年巴贝奇开始设计差分机Difference Engine。这台机器的目的是用差分法自动计算并打印数学表格对数表、三角函数表等。当时的数学表格完全靠人工手工计算错误率极高——航海家靠着一张算错了的对数表漂到了不该去的地方船毁人亡。巴贝奇受够了这种不可靠“如果有办法把错误的数学表格付之一炬或沉入海底世界的良心会安宁得多。”差分机的原理很漂亮。许多复杂的数学函数如多项式、三角函数可以用有限差分来表示。比如 f(x) x² 的值是 1, 4, 9, 16, 25… 一阶差是 3, 5, 7, 9… 二阶差是 2, 2, 2… 看——二阶差是常数所以如果你知道初始值和各阶差分你只需要反复做加法就能生成整个表格。差分机就是一台加法 进位 打印的专用机。英国政府给巴贝奇投了相当于今天的几百万英镑。但巴贝奇中途放弃了差分机因为他脑子里已经有了一个更宏大的蓝图——分析机Analytical Engine。分析机的设计已经惊人地接近现代计算机。它有存储器Store用于存放数字、运算室Mill相当于 CPU 的 ALU、穿孔卡片输入系统从雅卡尔提花织机借来的灵感以及条件跳转能力可以根据计算结果选择不同的执行路径。它是一台通用计算机——至少在设计图纸上是。巴贝奇的设计如此复杂19 世纪的精工水平根本造不出来。模具加工需要的公差微米级远超出了当时最好的机械水平。他花了几十年烧掉了政府和个人自己的大笔财富分析机始终是一堆图纸。这里我想插入一段作为工程师的共鸣。我曾经在面板厂做过良率工程师。CVD化学气相沉积机台往玻璃基板上沉积氮化硅薄膜的时候厚度的均匀性要控制在百分之几以内——也就是十几到几十个原子的堆叠精度。曝光机的对准精度要跑到亚微米级。在这样的精度下一颗肉眼根本看不见的微尘落上去——只要落在关键图形上——就足以让那个面板单元的TFT电路短路严重时这块片子直接报废。巴贝奇造不出他的分析机本质上是因为他生活在一个物理精度还追不上逻辑想象的时代。计算不只是一个数学概念——它需要一个物理载体。载体如果不够完美理论就是“空中楼阁”。这不仅仅是19世纪的问题——在21世纪的半导体工厂里工程师们每天都在对抗同一个问题物理世界永远在往逻辑世界里面掺沙子。但话说回来。巴贝奇的分析机虽然没造成它却间接促成了人类历史上最重要的编程事件。艾达·洛夫莱斯Ada Lovelace是诗人拜伦的女儿但她的母亲立志把她培养成数学家以免她像父亲一样感性泛滥。艾达在 17 岁时认识了巴贝奇成了他的崇拜者和合作者。1842-1843 年间她翻译了一篇关于分析机的法语论文——但她写的附录Note A 到 Note G远比原文长也比原文重要。在 Note G 中她详细描述了如何用分析机计算伯努利数——这是人类历史上第一个公开发表的计算机程序。艾达比巴贝奇看得更远。巴贝奇主要把分析机看成一台超级计算器——处理数字。但艾达在注释里写道“分析机可以处理任何能够用符号表示的对象……它可以谱写精密复杂的音乐作品”。她看到了计算机的本质不是算数而是符号操作。任何可以被符号化、被规则化处理的东西——数字、文字、音符、甚至逻辑命题——都在计算机的射程之内。这个洞见早了整整 100 年。Note G 里的那个伯努利数算法如果你用今天的伪代码写出来包含循环、条件分支、变量赋值、嵌套迭代——和你在 ECU 上写的嵌入式 C 代码没有本质区别。1843 年法拉第已发现电磁感应原理十余年第一条电报线路即将在英国建成——但电在多数人眼中仍是一种神秘的自然力。第一个白炽灯泡还要等三十多年计算机更是一个无人知晓的词汇。而艾达已经用鹅毛笔在纸上写出了一份可执行算法。巴贝奇和艾达都没有活着看到分析机实现。巴贝奇死在贫困中伦敦的科学界给了他一个寒酸的葬礼。但他们的图纸和笔记留下来了。1991 年伦敦科学博物馆按照巴贝奇的原设计用当时的公差水平完整复刻了一台差分机 2 号——它工作了精确到 31 位有效数字。不是设计错了——是时代还没到。穿孔卡片计算离开书桌巴贝奇从雅卡尔提花织机借来了穿孔卡片的灵感但真正把穿孔卡片变成大规模数据处理工具的人是赫尔曼·何勒内斯Herman Hollerith。1880 年代美国人口普查局面临一个危机。上一次手工普查花了 7 年才统计完——等报告出版的时候数据已经老了 7 年。何勒内斯发明了一套机电制表系统用穿孔卡片记录每个人的属性性别、年龄、种族、职业等然后把卡片塞进一台读卡机——读卡机里有一排弹簧针针穿过卡片上的孔就会触碰到下方的汞杯接通电路推动计数器走一格。这就是电第一次正式介入计算——虽然还只是做统计不是做逻辑。1890 年普查用了何勒内斯的系统只花了 6 周就算完了初步结果完整统计用了 2.5 年——为政府省了 500 万美元。何勒内斯从此发家他的公司后来经过几轮合并在 1924 年改名为——IBM。穿孔卡片的哲学含义很深远信息可以脱离人脑而存在在物理介质上可以被机器阅读和处理。莱布尼茨的通用表意文字在穿孔卡片上找到了第一次工业化实践。而 IBM 的那些制表机、排序机、卡片打孔机——它们虽然还不算通用计算机但它们已经发展了输入/输出子系统、脉冲检测电路、继电器逻辑——这些后来都成了真正计算机的器官。计算究竟是什么意思有了这些历史铺垫我们可以回到最初的哲学问题。从数学上我们可以这样定义计算是一组确定性的规则作用于一组给定的输入经过有限步骤产生确定的输出。这个定义里有三个关键词。确定性同样的输入同样的规则必须产生同样的输出。你今天算 112明天算也得是 2。帕斯卡的齿轮每次转同样的角度你做除法时的口诀每次念同样的字。确定性是计算的第一前提。有限性必须在有限步骤内完成。永远算不完等于没算。巴贝奇的分析机设计了条件跳转就是为了在满足某个条件时终止循环——否则齿轮会永远转下去。你的 ECU 的每个 task 必须在规定时间内完成——否则操作系统会触发 watchdog 超时、复位、进 safe state。机械性每一步操作都是简单机械的不需要灵感或顿悟。理论上一个傻子也能执行。算盘口诀、纳皮尔骨筹的查表、穿孔卡片的弹簧针——全部满足这个条件。这个定义有一个极其重要的推论如果一个问题存在机械性的求解步骤那它就是可计算的。如果没有这样的步骤它就是不可计算的。从白纸到 ECU资源约束下的计算让我们把白纸实验和真实汽车电子场景做一个穿透式的映射。ECU 资源64KB SRAM, 512KB Flash, 112MHz Cortex-M4F。CAN 负载率 85%每 10ms 一次 MAIN task每 1ms 一次 fast ISR。你不是在一间屋子里翻白纸。你是在一个比指甲还小的硅片上以 112MHz 的频率做着同样的事。你写的每一行 C 代码——while 循环、if 判断、数组访问——都在指挥这间硅屋这块 Flash 页存这个数组、那个外设寄存器值和这个阈值对比、如果 CAN ID 匹配就拷贝到转发缓冲区。你写代码时可曾意识到你的每一个 if 语句都在消耗有限的计算资源——时钟周期、栈深度、分支预测表的条目汽车电子不同于服务器。服务器加内存就好了。ECU 的 MCU 是焊死在 PCB 上的——128KB SRAM 不够用你只能优化代码不能换芯片。服务器没有实时性。ECU 的 Main Task 超时 1 毫秒也不行——因为碰撞传感器的信号如果在 5ms 内没有到达 ESP 控制器系统会进入降级模式刹车助力减弱。有限资源 确定性规则 有限步骤 硬实时约束 → 这就是汽车嵌入式的计算。物理基底的诅咒为什么半导体工程师比理论家更焦虑作为在半导体工厂工作过的人我对有限资源有一种别人没有的切肤之痛。理论家说“内存不够就加内存”——但在芯片行业加内存意味着加 SRAM 面积。6T SRAM cell 在 40nm 工艺下大约占 0.3 μm²——要加 1KB 的 SRAM就需要额外约 8192 个这样的 cell相当于在 die 上多占 0.0025 mm²。对于一些 die 面积本身很小的芯片比如几十 mm² 的这已经是不可忽略的开销。而硅面积就是钱——每多占一点晶圆厂的成本模型就要重算。更微妙的是加面积会降良率。缺陷密度D0是晶圆厂的命门——以 40nm 为例典型 D0 在 0.5-1.0 defects/cm²。一颗 10 mm² 的 die良率大约 90% 出头如果设计改动让它增加到 12 mm²良率就会掉到 88-89%。看似几个百分点的下降乘以每月数万片的产能损失就是数百万美元级别的。所以当我看到巴贝奇的分析机因为 19 世纪机械加工精度不够而造不出来时我完全理解那种感觉不是想法错了——是物理基底不够好。在无尘车间我们 24 小时盯着 CVD 机台的气体流量、PVD 机台的溅射功率、光刻机的 focus/exposure 参数——表面上在做生产实际上是在和物理世界的噪声、随机涨落、缺陷密度搏斗。而你作为一个嵌入式工程师可能没有进过无尘室。但你在 ECU 上用 MISRA C 约束语言、关掉数据缓存、锁定内存区——和我在面板厂里追踪一颗颗粒物的逻辑是完全一样的。所有工程师无论上游还是下游本质上都在和基底的不完美交手。以有涯求无涯当我们把什么是计算追问到底会撞上一件奇妙的事计算其实是人类试图用有限的手段去把握无限的世界的努力。算盘用的是两颗上珠 五颗下珠。纳皮尔骨筹用的是牛骨上刻的数字。帕斯卡的齿轮用的是 17 世纪黄铜冶金和手工锉削。巴贝奇的设计——如果真能造出来——会是一个两吨重的黄铜巨兽由蒸汽驱动。何勒内斯的制表机用的是弹簧针和汞杯。你的 S32K144用的是 55nm 硅工艺、FinFET 晶体管、铜互连。介质一直在变——但输入、规则、输出这个三元结构从来没变过。复杂的汽车电子系统不过是这个结构的层层叠加CAN 收发器的模拟比较器在做输入的差分阈值判定。FlexCAN 协议引擎在做 CRC 的规则运算。你的 ISR 在做输出——往发送缓冲写数据。外部 LED 亮起——最终输出。庄子说吾生也有涯而知也无涯。以有涯随无涯殆已。他说的殆是累死了的意思。但工程人的回答是正因为有涯才更要追求无涯。每进一寸世界就变大一分。这条路算盘工匠走过纳皮尔走过帕斯卡走过莱布尼茨走过巴贝奇走过艾达·洛夫莱斯走过何勒内斯走过。现在轮到你了。莱布尼茨站在 17 世纪的书房里望着窗外说“我们要造一台机器把人类的知识都算出来。”问题是这可能吗本篇小结今天我们做了一件事重新思考计算到底是什么。关键结论计算是输入、规则、输出的三元结构从算盘到ECU介质一直在变但这三个要素从未改变。一切计算都在有限资源下运行巴贝奇的分析机败给了19世纪的机械精度你的ECU在64KB SRAM和10ms周期下做最优决策——同一个故事。计算的物理基底决定了它的上限逻辑从来不缺想象力缺的是能把想象力刻进硅片的工艺。下一节我们看莱布尼茨那个把所有人类知识都算出来的梦想——是怎么被击碎的。【下集预告】莱布尼茨的梦想太狂野了。他觉得人类的所有争论都可以算出来——不需要吵架不需要打仗坐下来算一算就知道谁对谁错。200 年后的 1900 年巴黎。一位德国数学家在第二届国际数学家大会上把莱布尼茨的梦想升级成了 23 个具体问题。他说我们必须知道——我们必将知道。他相信答案一定是 YES。他错了。而且错得如此壮烈——因为击碎这场梦的是一个 24 岁瘦弱的奥地利年轻人用一张纸、一支笔和一句这句话不可证。