HackerTube English?
程序的表达能力 →

一种语言能算什么,又能保证什么?

阶乘可以不用名字写出来。这个技巧提出了一个更难的问题:如果每个程序都必须停下来,还能允许任意递归吗?沿着这个分歧,再看幻灯片、库与语言扩展。

本文的问题 · 4
  1. 递归的表达能力与终止保证之间的取舍
  2. 极简解释器与幻灯片都能承载通用计算
  3. 让用户库承担语言增长
  4. 数组表达力强,不等于语言扩展无缝

递归的表达能力与终止保证之间的取舍

Weirich用不动点组合子让匿名函数获得递归能力;Wadler明确简单类型演算的终止保证排除了无限制不动点算子。同一递归机制在前者是表达能力来源,在后者是保证边界。

对照原文与时间戳 · 2
the function y calculates the fixpoint of an improver function.
Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich · ▶ 46:27–47:02
not using What's called the fixo operator that is unlimited General recursion
"Propositions as Types" by Philip Wadler · ▶ 21:59–22:07

比较的是演算与类型约束,不是宣称所有静态类型语言都不能递归。

极简解释器与幻灯片都能承载通用计算

Byrd说明变量查找、Lambda与应用的极小核心已能表达通用计算;PowerPoint演示以动画磁带和可修改转移表模拟图灵机。两者揭示通用计算不依赖熟悉的表面语法或庞大语言。

对照原文与时间戳 · 2
you only need these three lines that's turn complete actually
William Byrd on "The Most Beautiful Program Ever Written" [PWL NYC] · ▶ 44:35–44:43
essentially imitate any transition function of any other touring machine
On The Turing Completeness of PowerPoint (SIGBOVIK) · ▶ 4:07–4:17

PowerPoint仍需人工点击推进;可计算性等价不意味着速度、内存或工程可用性等价。

让用户库承担语言增长

Steele要求用户定义构造像语言原语一样自然,以少数增长机制容纳多种领域需求;Unison的分布式能力与解释器让用户自行实现执行策略,把分布式编程抽象交给库作者。

对照原文与时间戳 · 2
the new words defined by a library should look just like the primitives
Growing a Language, by Guy Steele · ▶ 23:25–23:32
the idea is that distributed programming should just be a library
"Unison: a new distributed programming language" by Paul Chiusano · ▶ 36:04–36:12

Unison未被证明直接源自该演讲;远端批计算示例不等于完整解决状态型分布式服务。

数组表达力强,不等于语言扩展无缝

生命游戏展示 APL 原语组合如何省去显式循环;Steele 则指出历史 APL 的用户定义与内建原语外观不一致,使社区难以无缝扩展语言。前者的表达能力并不自动解决后者的扩展接口问题。

对照原文与时间戳 · 2
you'll notice that it contains no explicit loops and no temporary variables
Conway's Game Of Life in APL · ▶ 3:11–3:29
new words defined by the user do not look like language primitives at all.
Growing a Language, by Guy Steele · ▶ 20:13–20:18

Steele 评价的是其演讲时期的 APL;不能据此断言现代 Dyalog 缺少用户函数或算子。

读完再想一步

给语言加一种表达能力前,先写下一个从此可能失去的保证。