用途:invariant-guard 是一个面向算法编写与审查的正确性优先技能,用于处理那些“显而易见的实现其实有微妙错误”的场景,例如后置条件强于循环自然不变式、读写指针原地修改、多参数或带累积状态的递归、含重复或边界值的差一错误,以及必须终止的迭代改进(不动点、牛顿法、EM)。它应在算法已选定、循环体尚未编写之前加载。\n\n主要能力:规定一套不可协商的规则——每个循环必须有一行不变式(若无法用一句话写出,说明循环尚未设计好)和一行终止论证(指出每轮严格递减或趋近边界的量);每个递归必须有显式基线条件和一个严格递减的非负度量;写代码前先列出适用边界情况及其预期行为;尽量用类型让非法状态不可表示。会给出“写前协议”:函数契约、循环不变式、终止论证、基线条件与度量、边界情况表、非法状态不可表示手段、代码、自检,缺任何一项就不输出代码。\n\n使用方式:按上述顺序在消息中先陈述再编码;代码中每个循环用 // inv: 或 # inv: 注释不变式,每个递归注明基线条件与度量;函数入口断言前置条件,能用类型(和类型、新类型、非空类型)就不用运行时检查。附带 Boyer–Moore 多数投票与最左二分查找的示例,说明为何需要第二遍验证。\n\n适用场景:线性扫描累积、双指针、二分查找、滑动窗口、BFS/DFS、分治、贪心加优先队列、并查集、原地分区等算法形状。与 lemmaly(选算法)和 mathguard(选数学方法)配套。\n\n限制:它不是自动证明器,需作者自己写不变式,它不会机械检查,建议配合基于属性的测试;默认不覆盖并发,除非显式扩展;浮点与溢出边界因语言而异,边界表只是检查清单;对显然不会失败的琐碎代码会增加负担;若作者跳过书写不变式,该技能无法检测。
invariant-guard
通用与其它
更新于 10-16 06:13