.
自然语言与元语言
. 自然语言与元语言
自然语言写程序语言规格时的常见歧义,以及对象语言与元语言的分层.
2 自然语言写规格的局限
日常交流里,无论是汉语还是英语,自然语言都足够好用. 说话的人和听话的人共享大量背景,含糊的地方可以靠语境补上,补错了再问一句. 写程序语言的规格时,我们仍会用到这些背景,却不能把关键设计留给读者自行补全: 读者可能是其他国家的程序语言研究者,也可能是十年后的自己; 把规格变成实现时,还要交代机器应当执行哪些步骤. 下面几个例子展示这项任务中需要澄清的问题(自然语言在日常交流里即使含糊也依然有意义).
2.1 弊端一:一句话有多种结构
人读到这些句子时,常会根据语境和常识选择一种结构,但未必选得一样. 实现解析器时,不能指望程序替我们猜出想要的分组, 必须另行规定文法、优先级或其他消歧办法.
2.2 弊端二:没说到的情形
规格的作者心里多半有答案,只是觉得“显然”而没写下来; 然而不同的人眼里“显然”的东西往往不同. C 语言标准用英文写成,几十年来关于某些条款到底允许什么的争论一直没停, 后来还出现了专门把它的含义精确化的研究项目(例如 Cerberus).
2.3 弊端三:全称与否定的范围
讲程序语言的性质时,这类句子到处都是. “每个程序都有某个类型”和“存在一个类型,使得每个程序都有这个类型”, 量词顺序一换,意思就完全不同.
2.5 弊端五:“显然”没法检查
前面四个例子讲的是说清楚有多难. 还有一个问题更根本:我们想要的结论是关于所有程序的. “这门语言里,通过类型检查的程序都不会在运行时出错”, 这句话谈论的是无穷多个程序.
无穷多个程序没法逐一试验;要得到普遍保证,就需要覆盖它们的论证. 无论用什么语言写,若没有说明分类是否穷尽、每一步依据什么, 读者都很难判断是否漏了情形. “其余情形类似”“显然成立”这些话,写的人常常真心相信, 但这恰恰是错误最容易藏身的地方.
2.6 形式化带来了什么
本文采用明确的抽象语法、归纳定义和推导规则, 使结构、适用条件与论证义务能够分别接受检查.
在结构上,本文直接研究已经分好组的语法树,把从字符串到树的解析留在模型之外(对应 结构歧义 ;这并不保证任意文法都能唯一解析).
在适用条件上,用对规则封闭的最小关系定义运行与类型,推不出的判断在这个关系中就不成立,不额外靠常识补规则(对应 不完整的规格 ;这种定义仍可能留下受阻状态,是否符合设计目标还要另行检查).
在量词范围上,约定符号的读法,写明量词管到哪里,不靠语气猜范围(对应 量词的范围 ).
在层次上,区分对象语言中的项和元语言中关于项的判断,不把外部描述自动算作内部表达式(对应 Berry 悖论 ;这并不要求所有形式系统都禁止谈论自身).
在论证义务上,证明要说明怎样覆盖全部情形、怎样使用定义和已有结论;本文先给纸面证明,若要让机器核对,还须把定义与证明编码到明确的逻辑系统中.
性质来自具体的设计选择,换上形式记号本身不会自动带来它们,例如:
- 在文法
E ::= E + E | 0E ::= E + E | 0下,字符串0 + 0 + 00 + 0 + 0仍可有两棵解析树; - 一门语言可以明确规定 和 ,得到精确定义却不确定的关系.
本文这门语言是否有唯一后继,要由 确定性 另外证明.
形式化让歧义、选择和假设更容易定位, 本身不保证唯一解析、唯一后继,也不保证所有读者自动理解一致.
形式化同样离不开自然语言的配合. 下文仍用自然语言说明定义与证明; 出现分歧时,先核对约定、规则及其应用,必要时修改模型或说明. 我们的目标是证明这套规则下的性质,无意为一切语言建立唯一标准.
接下来要用“树”描述程序的结构,先把相关术语说清楚.
2.7 练习:自然语言弊端
Exercises (5)
Exercise 1.1. 分组与执行顺序的区分
一份规格只写了“先乘除,后加减”. 判断它是否同时规定了2 + 3 * 4
2 + 3 * 4
的分组以及
f() + g()
f() + g()
的调用顺序; 设两个函数都会打印一个字符,给出两份分组相同、打印顺序不同的完整顺序规定.Solution
“先乘除,后加减”把
2 + 3 * 4
2 + 3 * 4
规定为
2 + (3 * 4)
2 + (3 * 4)
,结果是 , 但没有规定
f() + g()
f() + g()
先调用谁. 设
f
f
打印
F
F
后返回 ,
g
g
打印
G
G
后返回 : 先左后右打印
FG
FG
,先右后左打印
GF
GF
,两者的数值结果都为 .
可以分别补上“先完整求出左操作数,再求右操作数,最后相加”与相反顺序的规定. 分组解决哪个运算包着哪个运算,执行顺序解决哪件事先发生; 一条优先级约定不能替代后一条规定.
Exercise 1.2. 把量词的范围写出来
检查器接受了甲、乙两个程序,拒绝了丙. 说明“所有提交的程序都没有接受”的两种读法, 分别写成不含糊的句子,判断真假,并写出每种读法的否定.Hint
区分“每一个都遭拒绝”和“至少一个未获接受”, 不要只在原句里换一个近义词.Solution
若把“所有提交的程序都没有接受”理解为“每个提交的程序都遭拒绝”, 那么它为假:甲、乙已经接受. 若理解为“至少有一个提交的程序未获接受”,那么它为真:丙遭拒绝.
第一种说法的否定是“至少有一个提交的程序得到接受”; 第二种说法的否定是“每个提交的程序都得到接受”. 它们的否定也不同,因此原句不能靠读者自行猜范围. 这里约定每次提交最终只有“接受”或“拒绝”两种结果.
Exercise 1.3. 补全一份除法规格
指出“a / b
a / b
返回它们的商”漏掉的情况; 自行设计一个整数除法操作,完整规定输入范围和错误处理, 并写出三个输入及其预期结果. 答案可以有不同设计,但不能把异常情形留空.Hint
至少说明可接受的输入、非整除时的结果、除数为零的处理; 再给能区分不同规定的例子.Solution
一种规定是:两边都必须是非负整数,且除数 必须大于 ; 返回唯一的非负整数 ,满足 . 不满足输入条件时明确报错,不自动把字符串转成整数.
于是
7 / 2
7 / 2
返回 ,
7 / 0
7 / 0
报错,
7 / "2"
7 / "2"
也报错. 第一例排除了“保留小数商”的规定, 后两例分别排除了“零除返回某个普通数”和“字符串自动转换”的规定. 这只是一个可选设计,关键是不能只写“返回商”却把这些决定留给实现者.
Exercise 1.4. 谈论一个名字,不等于增加一个名字
一门小语言只允许三个整数名字:“一”“二”“三”,分别表示 、、. 指出“这门语言里无法命名的最小正整数”所描述的数, 判断这句话是否自动成为该语言的第四个名字,并说明理由.Hint
先检查规定的命名表里有没有那个短语,再看是否偷偷扩充了语言. 参照 Berry 悖论 .Solution
按命名表, 确实是无法命名的最小正整数, 但这个长短语不在命名表里,不属于这门语言的名字. 我们能在解释规格的自然语言里描述 ,不意味着那门小语言也能命名它.
如果正式把这个短语加进命名表,必须规定它在新语言中表示哪个数, 原先关于“最小无法命名的数”的结论也须重新检查. 这个练习展示的是:外部描述不会自动成为内部名字. 至于 Berry 悖论本身,还涉及能否在同一语言中无限制地使用涵盖自身的可定义性概念, 不能简单归结为忘了重新统计.
Exercise 1.5. 找出“其余显然”的缺口
设 表示关于正整数 的一个判断. 某人说:“我验证了 到 ,所以每个正整数都满足 ,其余显然同理.” 请给出一个使前一百次验证全部通过、普遍结论却为假的具体 , 并指出这个论证究竟缺了什么.Hint
构造一个只对前一百个正整数成立的性质, 就能检查有限验证到底证明了什么.Solution
取 为“”. 前一百个正整数都满足它, 却不满足. 因此“检查了一百次”只能支持这一百个具体实例,不能独自推出普遍结论.
要证明所有正整数都满足某个性质,还要给出覆盖所有情况的推理方法; “剩下的显然同理”若没有说明相同的前提和推理步骤, 就只是把待证结论复述了一遍,算不上补完证明.
3 两个层次的语言
先解决 Berry 悖论 .
例如“ 是值”是元语言里的一句话,它在谈论对象语言里的 . 对象语言自己说不出这句话,它里面根本没有“值”这个词. 反过来,元语言里的“所有”“如果……那么”,也不属于对象语言. 在这门小语言里,外部关于项的描述不会自动成为内部表达式, 因此可以避开前面例子中的层次混用. 这不等于只要分层,就排除了所有逻辑问题.