一种语言能算什么,又能保证什么?
阶乘可以不用名字写出来。这个技巧提出了一个更难的问题:如果每个程序都必须停下来,还能允许任意递归吗?沿着这个分歧,再看幻灯片、库与语言扩展。
递归的表达能力与终止保证之间的取舍
Weirich用不动点组合子让匿名函数获得递归能力;Wadler明确简单类型演算的终止保证排除了无限制不动点算子。同一递归机制在前者是表达能力来源,在后者是保证边界。
对照原文与时间戳 · 2
the function y calculates the fixpoint of an improver function.not using What's called the fixo operator that is unlimited General recursion比较的是演算与类型约束,不是宣称所有静态类型语言都不能递归。
极简解释器与幻灯片都能承载通用计算
Byrd说明变量查找、Lambda与应用的极小核心已能表达通用计算;PowerPoint演示以动画磁带和可修改转移表模拟图灵机。两者揭示通用计算不依赖熟悉的表面语法或庞大语言。
对照原文与时间戳 · 2
you only need these three lines that's turn complete actuallyessentially imitate any transition function of any other touring machinePowerPoint仍需人工点击推进;可计算性等价不意味着速度、内存或工程可用性等价。
让用户库承担语言增长
Steele要求用户定义构造像语言原语一样自然,以少数增长机制容纳多种领域需求;Unison的分布式能力与解释器让用户自行实现执行策略,把分布式编程抽象交给库作者。
对照原文与时间戳 · 2
the new words defined by a library should look just like the primitivesthe idea is that distributed programming should just be a libraryUnison未被证明直接源自该演讲;远端批计算示例不等于完整解决状态型分布式服务。
数组表达力强,不等于语言扩展无缝
生命游戏展示 APL 原语组合如何省去显式循环;Steele 则指出历史 APL 的用户定义与内建原语外观不一致,使社区难以无缝扩展语言。前者的表达能力并不自动解决后者的扩展接口问题。
对照原文与时间戳 · 2
you'll notice that it contains no explicit loops and no temporary variablesnew words defined by the user do not look like language primitives at all.Steele 评价的是其演讲时期的 APL;不能据此断言现代 Dyalog 缺少用户函数或算子。
读完再想一步
给语言加一种表达能力前,先写下一个从此可能失去的保证。