OP 0016: 统一相等性协议¶
摘要¶
当前 Oort 的相等性由三套互不一致的规则决定:
==对 List/Tuple/Dict/Set 使用 HOST 投影(Python 容器的相等), 嵌套的true/1被当作相等;in在顶层用_strict_equal区分 Bool/Int,嵌套层又退回 HOST 相等;- Dict/Set 的键查找使用 Oort 对象的
__eq__/__hash__,与==无关。
结果是 [true] == [1] 为真而 true in [1] 为假;{: true: 1 :} 与
{: 1: 1 :} 相等,但用 1 取键失败;集合代数把 true 与 1 合并。
本提案定义值相等与键相等两层协议,让 ==、in、Dict/Set 相等、
集合代数与键查找在所有嵌套层级上使用同一套规则。
跨语言调研¶
| 语言 | 值相等 | 键相等/哈希 | 可变容器作键 | 数字跨类型 |
|---|---|---|---|---|
| Python | ==,容器递归 |
__eq__ + __hash__ |
不可哈希 | 1 == 1.0,同一字典键 |
| Ruby | == |
eql? + hash(Hash/Set) |
不可作为键 | 1 == 1.0,但 eql? 为假 |
| Java/Kotlin | equals(数组除外) |
equals + hashCode |
可变对象可作键但不安全 | 包装类型不跨类型相等 |
| Go | ==,仅可比较类型 |
同一 == |
slice/map 不可比较 | 无隐式跨类型 |
| Rust | PartialEq |
Eq + Hash |
需实现 Hash |
无隐式跨类型 |
| JavaScript | ===;对象按身份 |
Map 用 SameValueZero | 对象按身份 | true !== 1 |
来源:
- Python https://docs.python.org/3/reference/datamodel.html#object.__eq__
- Ruby https://docs.ruby-lang.org/en/master/Object.html#method-i-eql-3F、 https://docs.ruby-lang.org/en/master/Hash.html
- Kotlin https://kotlinlang.org/docs/equality.html
- Go https://go.dev/ref/spec#Comparison_operators
- Rust https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
- JavaScript https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness
结论:
- Python/Java/Kotlin/Rust 要求“相等 ⇒ 哈希相同”,但 Oort 还没有用户级哈希
协议;若直接采用单层模型,定义
operator "=="的类会破坏 Dict/Set。 - Ruby 把
==与eql?/hash分开:值相等不自动等于键相等。这与 Oort 当前“用户类默认身份键”的现状最接近,也给未来hash协议留出空间。 - Bool/Int 严格区分是 Oort 已有决策;协议必须在所有嵌套层级保持它。
扩展(2026-11-22,OP 0024):ADT 采用结构值相等与 key-safe 结构键;静态类实例(槽对象)采用身份值相等与身份键。见 OP 0024。
决策¶
D1:值相等 ==¶
- List/Tuple:长度相等,逐元素用 Oort
==比较(可调用用户运算符)。 - Dict:键用 D2 的键相等匹配;对应值用 Oort
==比较。 - Set:用 D2 的键相等比较元素(无序)。
- String:逐码点相等;Null 只等于 Null。
- Bool 与 Int 永不相等,嵌套在容器中同样如此。
- Int 与 Float 保留数值相等:
1 == 1.0为真,[1] == [1.0]也为真。 - 用户类:使用其
operator "==";未定义时用身份。 !=默认是==的取反;显式operator "!="仍然优先。- 身份短路:
a is b直接视为相等;循环容器用“已比较对象对” memo, 对已访问的(a, b)返回真(共归纳/双模拟语义)。
D2:键相等与哈希¶
Dict 键、Set 元素以及 Tuple 的键哈希使用键协议,与值 == 分离:
| 类型 | 键相等 | 哈希 | 备注 |
|---|---|---|---|
| Null | 仅 Null | 固定 | |
| Bool | 同值 | hash(bool) |
Bool/Int 严格 |
| Int | 同值 | hash(int) |
Int 与 Float 不键相等 |
| Float | 同值 | hash(float) |
与 Int 不键相等 |
| String | 同内容 | 字符串哈希 | |
| Tuple | 逐元素键相等 | 逐元素键哈希 | 元素必须可哈希 |
| Type/Function/Module/用户实例 | 身份 | 身份哈希 | 用户 == 不影响键身份 |
| List/Dict/Set | — | 不可哈希 | 不能作键/集合元素 |
- 值相等与键相等可以不同:
1 == 1.0为真,但{1: "a"} != {1.0: "a"},1 in {. 1.0 .}为假。这是 Rubyeql?模型的刻意选择,用于保证键查找 与哈希稳定;未来引入用户hash协议后再讨论是否放宽。 - Dict 相等:键集合按键相等一致,值用
==。 - Set 相等与
& | ^ -:全部按键协议;结果保留原始键对象。 - 用户类自定义
==后仍以身份作为键;文档明确“值相等不隐含键相等”。 未来operator "hash"()提案负责自定义键相等/哈希。
D3:成员测试 in¶
- List/Tuple/String:逐元素用
==(元素在左,查询值在右;与 PythonPyObject_RichCompareBool的元素顺序一致)。 - Dict:按键协议查键。
- Set:按键协议查元素。
!in是in的取反;用户容器显式定义operator "in"时优先。- 因此:
[true] == [1]与true in [1]都为假;1 in [1.0]为真(值相等),但1 in {. 1.0 .}为假(键相等)。
D4:实现方式¶
- 不再用
host_value投影实现相等、成员测试或集合代数。 - List/Tuple 的
==与in改为 CONTEXT 原生运算符,通过NativeContext.binary("==", ...)递归调用 Oort 运算符;这使容器中的 用户类==、扩展运算符与错误传播都走正常分派。 - Dict 相等:按键协议匹配键,值用
ctx.binary("==");Dict/Set 的in直接使用底层 Oort 键容器(Python dict/set 已按键协议哈希)。 - Set 相等与
& | ^ -直接操作底层 Oort 集合,不做 HOST 投影。 OortTuple.__eq__/__hash__保留为键协议实现;嵌套 Tuple 递归。- 循环相等在递归辅助函数中维护
(id(left), id(right))集合;只影响 值相等,键协议不接受可变容器。 host_value继续用于宿主边界与打印,但不再定义语言相等。
D5:兼容性与版本¶
- 这是语义修正,会改变可观察行为(嵌套 Bool/Int、Dict/Set 相等)。
- 实际随 0.3.1 发布:该版本尚未有外部依赖者,按玩具语言 0.x 规则将 修正直接并入下一个发布,并在 CHANGELOG 的 0.3.1 条目标注。原计划的 “下一个 minor 0.4.0” 不再适用。
- 现有程序若依赖 HOST 投影相等,需要按新协议调整。
is/!is仍是身份比较,不参与本协议。
实现与测试¶
ASTInterpreter.values_equal/_values_equal:List/Tuple/Dict 递归、 循环对象对 memo;Set 使用键协议。NativeContext.equal/contains:CONTEXT 原生运算符调用解释器级相等。type_system:List/Tuple/Dict 的==改为 CONTEXT,List/Tuple 的in改为 CONTEXT;Dictin、Set==/in/集合代数改为 VALUE,避免宿主投影。- Dict 键查找继续使用底层 Oort 键容器(Bool/Int 严格、Int/Float 区分、 用户实例身份)。
- 测试:
tests/unit/runtime/test_equality.py,覆盖嵌套 Bool/Int、Int/Float、 Dict/Set 键语义、集合代数、用户==、类型不敏感、循环容器。 - 后续补齐序比较(同一协议):List/Tuple
< <= > >=改为 CONTEXT 递归 Oort 比较,Set 按键协议做子集/超集比较,Dict 移除排序;+/*改为 VALUE 浅拼接/重复。测试见tests/unit/runtime/test_ordering.py,规范见 spec/02“容器排序”。 - 示例/集合助手回归全部通过。
替代方案¶
- Python 单层模型(
==+ 用户__hash__):语义最统一,但必须先有 用户哈希协议;否则自定义==的类作键会破坏 Dict/Set。留作后续。 - 保持 HOST 投影相等,只把
in改成投影:实现最小,但 Bool/Int 严格性会在嵌套层丢失,违背既有语言决策。放弃。 - 让 Int 与 Float 键相等:更接近 Python,但当前 Oort 对象哈希/相等 需要额外规范化;先采用 Ruby 式键区分,等哈希协议统一后再评估。
- 禁止可变容器参与相等:会破坏 List/Dict 的实用比较;放弃。
测试计划¶
- 值相等矩阵:Bool/Int 在 List/Tuple/Dict/Set 的所有嵌套组合; Int/Float 数值相等;String/Null。
in:List/Tuple/String 的值相等;Dict/Set 的键相等;!in; 嵌套容器与用户类==。- Dict:键/值相等、键查找与相等一致、Tuple 键、Int/Float 键区分。
- Set:相等、
& | ^ -、Bool/Int 与 Int/Float 键区分、用户实例身份键。 - 循环 List/Dict 的相等与身份短路。
- 用户类
operator "=="在容器元素中生效;显式!=优先。 - REPL/脚本、扩展运算符与既有集合助手回归。
- 基准:嵌套 1000 元素的
==/in,确认不再深拷贝投影。
非目标¶
- 用户自定义哈希(
operator "hash")与可变键协议;另立提案。 - 重载
is/!is。 - 跨类型数值键统一、NaN 的特殊键语义(先沿用宿主哈希/相等)。
- 序列化、规范化哈希或持久化字典键。