计算机界TOP3难题“相等”是软件工程中许多重大问题的根源...(计算机界常提到的2000年问题指的是什么)

原标题：计算机界 top 3 难题：“相等”是软件工程中许多重大问题的根源！


有一个笑话说，计算机科学界有两大难题：一是缓存失效问题，二是命名问题。但我认为还有第三个更难的问题：相等问题。你没看错，等号“=”看似简单，但等号的使用和误用，是软件工程中许多重大问题的根源。

声明：本文已获作者craig stuntz翻译授权。




作者 | craig stuntz

译者 | 弯月，责编 | 郭芮

头图 | csdn 下载自视觉中国

出品 | csdn（id：csdnnews）

以下为译文：

相等的原理

我来展示一下在编程语言中相等有多么容易出错。但首先我要解释一下相等应有的模样，而这其实非常难解释！当我们讨论相等“应该如何”时，我们必须指出是特定语境下的相等，因为相等的成立有许多方式，许多方式在不同的语境下都是成立的。


“数学的精髓在于，同一个东西可以用不同的方式呈现给我们。”

——barry mazur，《when is one thing equal to some other thing》


定律

我说过，在不同的语境下，相等有不同的含义，但尽管如此，有些东西是永远成立的。这就是相等的定律。

相等是一个二元操作，它是：


反射的，即对于任意值 a 都有 a = a
对称的，即a = b可以推出b = a，反之亦然
传递的，即如果a = b且b = c，则a = c

在编程的世界中，我们需要增加一条定律，因为有时候程序员会做一些奇怪的事情：

相等必须是：


一致的，即如果a = b且a或b的任何字段都没有发生变化，那么稍后再次检查时a = b应当依然成立。

上面的定律看似简单，但流行的编程语言甚至连如此简单的定律都无法遵守。但更严重的关于相等的问题甚至都很难精确描述。

结构相等性

在编程语言对于相等的各种实现中，一个重要的区别就是结构相等和引用相等。

结构相等会检查两个引用是否为同一个值。f#默认采用了结构相等：







type mystring = { somefield : string }
let a = { somefield = "some value" }
let b = { somefield = "some value" }
if a = b then // 返回true, 进入 "then" 代码块
但在c#中则不是这样，c#使用的是引用相等。引用相等要求两个被比较的对象是同一个对象。换句话说，它会比较两个变量是否指向同一个内存地址。指向两个不同内存地址的引用会被判为不相等，即使它们的值完全一样：











class mystring {
private readonly string somefield;
public string somefield { get; }
public mystring(string somefield) => this.somefield = somefield;
}
var a = new mystring("some value");
var b = new mystring("some value");

程序中何时应当使用结构相等？如果变量的值不会改变更，那么几乎任何情况下都应该使用结构相等！我所知的绝大多数编程语言在诸如integers之类的类型上都使用结构比较。除了java之外，int类型进行结构比较，integer类型进行引用比较，这迷惑了一代又一代的程序员。python的is也有类似的问题。

对于引用类型（如对象）也应当进行结构比较。考虑一个单元测试，你希望检查返回的对象是否等于你期待的值。在使用结构相等的语言中，这个操作非常简单：








[<testmethod>]
let ``the result of the calculation is the expected value`` =
let expected = { somefield = "some value"; someotherfield = 15; stillanotherfield = true; ... }
let actual = calculate
assert.areequal(expected, actual)
但如果语言不支持结构相等，而开发者需要自行开发，就会遇到难题。

引用相等

但正如我刚才说过的那样，某些特定情况下不应该使用结构相等。一种情况就是语言支持变量内容改变的情况，而绝大多数编程语言都支持。当某个变量的值被改变后，说这个变量等于另一个变量显然是不合理的。当然，你可以说在进行比较的时刻，这两个变量（在结构上）是相等的，比如在单元测试的最后一行时是相等的，但一般情况下你无法假设这两个变量是同一个东西。这点理解起来有些困难，我来举例说明。

我们假设有一个对象，表示一个人。在采用了结构相等的f#中，我可以这样写：




type person = { name : string; age : integer; offspring : person list }
现在我有两个朋友jane和sue，她们都有一个叫john的儿子，年龄都是15岁。他们是不同的人，但姓名和年龄都一样。没问题！





let jane = { name = "jane"; age = 47; offspring = [ { name = "john"; age = 15; offspring = [] } ] }
let sue = { name = "sue"; age = 35; offspring = [ { name = "john"; age = 15; offspring = [] } ] }
也可以这样写：






let john = { name = "john"; age = 15; offspring = [] };
let jane = { name = "jane"; age = 47; offspring = [ john ] }
let sue = { name = "sue"; age = 35; offspring = [ john ] }
这两段代码的功能完全一样。我没办法区别两个儿子，即使我知道他们是不同的人。但这没有问题！如果我需要区别他们，我可以把他们dna的hash之类的属性加到person类型中。但如果我只需要知道他们的名字和年龄，那么是否能区分两个对象并不重要，因为不管怎么区分，它们的值都是一样的。

假设jane的儿子改名成pat。f#不支持改变变量的值，所以我需要为john（还有jane！）创建新的person实例：




let newjane = { name = "jane"; age = 47; offspring = [ { name = "pat"; age = 15; offspring = [] } ] }
这个新的变量newjane似乎有点奇怪，但实际上并不会构成问题。上面的代码没有问题。现在用c#试一下，在c#中，变量默认情况下是可以修改的：






var john = new person("john", 15, null);
var jane = new person("jane", 15, new list<person> { john });
var sue = new person("sue", 15, new list<person> { john });
这段代码显然是不正确的：如果jane的儿子改名为pat，我可以直接改变引用的值：




jane.offspring.first.name = "pat";
但我就会发现sue的儿子也改名了！因此，即使两个儿子最初的名字是一样的，但他们并不相等！所以我应该写成：





var jane = new person("jane", 15, new list<person> { new person("john", 15, null) });
var sue = new person("sue", 15, new list<person> { new person("john", 15, null) });
这样jane和sue的孩子就是引用不相等。所以，在可以改变变量内容的语言中，默认采用引用相等是合理的。

另一种应该采用引用相等的情况是，事先知道引用相等的结果与结构相等相同。测试结构相等显然需要额外开销，如果真的需要测试结构相等，那么这个额外开销是正常的。但是，假设你创建了大量的对象，而且事先知道每个对象都是结构不相等的，那么花费额外开销来测试结构相等是没有必要的，因为仅仅测试引用相等就可以得出同样的结果。

相等性的表示

在实数中，0.999……（无限循环小数）等于1。注意这里说的“实数”与编程语言中的real类型不一样。在数学中，实数是无限的，而编程语言中的实数是有限的。因此，编程语言中没有0.999……这样的写法，但没关系，你可以使用1，反正两者的值是一样的。

这本质上是数学家在表示实数系统时采用的一种选择。如果在系统中加入另外一种对象，比如无限小的数，那么0.999……和1就不相等了。


“但是这并不等于说规范可以任意确定，因为不接受一种规范，必然会导致不得不发明奇怪的新对象，或者不得不放弃某些熟知的数学规则。”

——timothy gowers，《mathmetics: a very short introduction》


类似地，在实数系统中，1/2和2/4表示同样的值。


在ieee-754浮点数系统中，-0 = 0。

内涵和外延

一个函数何时等于另一个函数？绝大多数编程语言会进行引用相等的比较，我觉得这没有问题。因为，对函数进行结构比较有什么意义呢？也许我们可以使用反射来检查函数的实现，看看它们实现是否一样？但怎样才叫“一样”？变量名是否必须完全一样？快速排序和归并排序是不是“一样”的函数？

因此我们说，只要函数对于同样的输入返回同样的输出（不管其内部实现如何），函数就是外延相等的，而如果内部定义也一样，则是内涵相等的。当然，这也取决于语境。可能在某个语境中，我需要常数时间的函数，在另一个语境中，速度无关紧要。重要的是，必须有语境才能定义相等，才能用它来比较两个函数。

我不知道是否有哪种语言在比较函数时尝试过采用引用相等之外的方法。但很容易想出，这会很有用！（例如，优化器尝试移除重复的代码等。）你只能自己实现，但我不得不说，没有相等比较，总要比错误的相等比较强。

相等和赋值

当程序员的第一天就学过，“等于”这个名字有两种不同的概念。一种是赋值，另一种是测试相等性。在java中需要这样写：





const avalue = somefunction; // 赋值
这两者本质上是不同的。比较返回布尔值，而在面向表达式的语言（如ruby）中，赋值返回被赋的值。

所以ruby代码可以这样写：




a = b = c =

3
实际上会把3赋给变量a，b和c。不要在引用类型上尝试，很可能得不到你想要的结果！

在非面向表达式的语言（如c#）中，赋值没有返回值。

在数学中，赋值和测试相等性都使用相等运算符：





if avalue = 3 ...
where avalue = somefunction
（而且在数学中，有时候=还用于其他关系，如合同（congruence）。与数学中的其他东西一样，这里也要区分语境；在阅读论文或书籍时必须注意语境。）

为什么数学不要求两种不同的操作，而编程语言要求？因为在数学中可以轻易判断出语境，而且也并非所有语言都要求不同的运算符。例如，f#中赋值和测试相等都采用=。尽管两者采用相同的符号，但赋值和测试相等是完全不同的操作。





let avalue = somefunction; // 赋值
if avalue = 3 then // 测试相等
语法的选择部分出于历史原因：f#基于ml，而ml基于数学；而java的语法基于java→c→algo→fortran。

用于编译fortran代码的机器很难根据语法来区分两种情况，因此采用不同的运算符是合理的。于是c语言把这个“特性”带到了新的高度，所以你甚至可以写：





int avalue = somefunction; // 赋值
if (avalue = 3) { // 也是赋值！
给没有c语言经验的人解释一下：这段代码先用3覆盖avalue，然后由于表达式avalue = 3的值为3，因此if的条件为真，因此会继续执行if块内的代码。通常这种写法都是错误的，因此许多c程序员会将if块的条件反过来写，来避免造成该错误：









int avalue = somefunction; // 赋值
// [...]
if (3 = avalue) { // 语法错误：无法将 avalue 赋值给 3.
相等性的使用错误
通过上面的说明，希望大家都已经明白相等性并不简单，“正确”的实现取决于语境。尽管如此，编程语言经常会把最容易的地方搞错！很多时候，这是相等性与其他语言特性的组合造成的，如隐式类型转换。
常见错误：相等性不是反射的
回忆一下相等性的反射率，即任何值都等于它自身，a = a。
在.net中，如果在值类型上调用object.referenceequals，其参数会在执行方法之前分别进行打包，因此即使传递同一个实例，也会返回假：
（来自文档的例子）




int int1 = 3;console.writeline(object.referenceequals(int1, int1)); // 输出 false这意味着在任何.net语言中 a = a 都不一定为真，因此不满足反射率。
在sql中，null不等于自身，因此表达式null = null（或者更可能的情况是，some_expression = some_other_expression时两者都可能为null）会返回false。这会导致下面乱糟糟的语句：




where (some_expression = some_other_expression)or (some_expression is null and some_other_expression is null)而更可能发生的情况是，开发者会忘记null的特殊规则从而导致bug。一些数据库服务器的sql语言支持is not distinct from，它的功能才是=应该有的功能。（或者我应该说，它没有不做=应该做的事情？）否则，就必须使用上面例子中的sql语句。最好的解决办法就是尽可能使用不允许null的列。
ieee-754浮点数也有同样的问题，即nan != nan。一种解释是，nan表示某个不确定的“非数字”结果，而不同计算得出的nan并不一定是同一个不确定的非数字，所以这个比较本身就是不正确的。例如，square_root(-2)和infinity/infinity两者的结果都是nan，但显然它们不一样！有时候sql的null问题也可以类似地解释。这样造成的问题之一就是术语的含义过多：nan和null表示的是“未知”，还是“不精确的值”，或者是“缺少值”？
对于此类正常的浮点运算中不会出现的问题，解决方法之一就是采用联合（union）类型。在f#中可以这样写：







type maybefloat = | float of float| imaginary of real: float * imaginary: float| indeterminate| /// ...然后就可以在计算中正确处理这些情况了。如果在计算中遇到预料之外的nan，可以使用signaling nan来抛出异常。
但是=和浮点数还有更严重的问题。
常见错误：相等过于精确
（更糟糕的是，浮点数是许多其他类型的基础，如某些语言中的tdatetime类型，所以即使一些相等比较本该合理的地方，也不能正常工作。）
sml的实现说明（http://sml-family.org/basis/real.html）上这样说：
判断real是否为相等的类型，如果是，那么相等本身的意义也是有问题的。ieee指出，零的符号在比较中应当被忽略，而任意一个参数为nan时，相等比较应当返回false。这些约束对于sml程序员来说非常麻烦。前者意味着 0 = ~0 为true，而r/0 = r/~0为false。后者意味着r = r可能出现返回false的异常情况，或者对于ref cell rr，可能存在 rr = rr 成立但是 !rr = !rr 不成立的情况。我们可以接受零的无符号比较，但是认为相等的反射率、结构相等，以及<>和not o =的等价性应当被保留。这些额外的复杂性让我们作出决定，real不是具有相等性的类型。
通过禁止real拥有=运算，sml强迫开发者思考他们真正需要什么样的比较。我认为这个特性非常好！
f#提供了[<noequality>]属性，来标记那些=不应该被使用的自定义类型。遗憾的是，他们并没有将float做上标记！
常见错误：不相等的“相等”





常见错误：相等不是对称的
如果你要在java中重载.equals，那么你必须负责确保相等的定律成立！
如果不加注意，那么很容易就会导致不对称的相等，即a.equals(b) != b.equals(a)。
即使不考虑null的情况（因为null会导致nullpointerexception，而.equals是允许这种情况发生的：https://docs.oracle.com/javase/8/docs/api/java/lang/object.html#equals-java.lang.object-），如果你继承一个类并重载.equals，也最好多加小心！


















if (getclass != o.getclass)return false;这不仅仅是我的个人看法，也是object.equals的契约的要求（https://docs.oracle.com/javase/8/docs/api/java/lang/object.html#equals-java.lang.object-）。
常见错误：相等没有传递性
回忆一下相等比较的定律之一就是应当具有传递性，即如果a = b 且 b = c，那么 a = c。不幸的是，与类型转换（type coersion）放在一起后，许多语言都会在这里出问题。
在java中，





常见错误：相等性不一致

















fun main(args: array<string>) {val a = float.nan;val b = float.nan;equalsfloat(a, b);equalsany(a, b);}// prints false, true
这是一个非常不幸的语言特性组合，可能会导致违反直觉的行为。
常见错误：在应当使用结构相等的地方使用引用相等
考虑如下用c#编写的mstest单元测试：










[testmethod] public void calculation_is_correct {var expected = new result(some_expected_value);var actual = _service.docalculation(some_input);
assert.areequal(expected, actual);}
这段代码能正常工作吗？我们不知道！assert.areequal最终会调用object.equals，默认会进行引用比较。除非你重载了result.equals进行结构比较，否则这个单元测试无法正常工作。object.equals认为，如果类型是可改变的，那么不应该重载。通常来说这是合理的，但在单元测试中却未必。（这是因为.equals本应比较.gethashcode，而一个对象的hash code在对象的生命周期中应该不发生改变。）.net framework中对于引用类型的最接近“有保证的结构比较”的是iequatable<t>，但assert.areequal并没有使用，即使实现了也不会使用。
而nunit的情况更糟（https://github.com/nunit/nunit/issues/1249）。
（相反，java的object.hashcode在对象的字段发生变化时是允许变化的。https://docs.oracle.com/javase/7/docs/api/java/lang/object.html#hashcode）
应该怎样看待相等
没想到关于=运算符我写了这么多还没写完！好吧，这已经远远超过了运算符本身。为什么如此复杂？基本上有两个原因：


非本质的复杂性：我们的编程语言在相等比较方面做得并不好。经常完全不能正常工作，甚至在不能正常工作时也不会明确表示这一点，例如会在本应进行引用比较的地方使用结构比较。
本质的复杂性：相等性本身就是复杂的，如比较浮点数。而在诸如比较函数等边缘情况下就更为复杂。
另一种划分方法就是“应该由编程语言的实现者负责解决的问题”（上面的“非本质的复杂性”）和“应该由编程语言的使用者负责解决的问题”。
编程语言应该怎么做？
关于非本质的复杂性，现状是几乎每一种主流编程语言对于相等性的实现都有问题。这个“必须遵循几个定律的简单运算”正是编程语言为了保证正确性而依赖的东西！但在我看来，只有sml真正思考了怎样在语义和运行时/标准库方面同时保证符合定律的相等性，而sml完全不是主流语言。
首先，在禁止相等比较的地方，编程语言应该很容易创建不允许相等比较的类型，因为这易操作完全没有必要复杂（如f#中的[<noequality>]），然后应该在标准库中尽可能多地使用该特性，如浮点类型。
我不知道还有哪些允许改变变量值的语言能够用不困惑的方式处理结构相等的。但很容易想象理想状态应该怎样！准备两个运算符，一个表示结构相等，一个表示引用相当，只在编程语言可以合理地支持的语境下才允许相应的运算符。例如，如果.net的object.referenceequals和值类型不进行包裹，并且使用类似于iequatable<t>的东西允许成功够许愿使用结构相等运算符，那么开发者就很容易弄清楚哪个是哪个。
程序员应该怎么做？
也许你读了这篇文章后会觉得，“哇，相等好复杂！我还是不要编程了，回家种地算了。”但这篇文章如此之长的原因主要是太多的语言都做错了。都作对的确需要些心思，但并不是太难。肯定比种地要简单。
在已有的类型上进行相等比较时，先问问自己：


在这里进行相等比较本身合理吗？
如果合理，那么是应该进行结构比较，还是引用比较？
对于相应的比较方法，我采用的编程语言提供了哪些支持？
我采用的编程语言对于该比较方法的实现是正确的吗？
在设计自定义类型时也可以询问类似的问题：


我的类型应该支持相等比较吗？还是需要一个更复杂的比较，就像float那样？
我的类型应该是可改变的吗？它会对相等性产生怎样的影响？
应该支持引用比较？还是结构比较？还是应该同时支持两者？
如果你的类型是可改变的，则应该考虑将其改成不可改变的。即使语言默认是可改变的，这一点也可以实现！这样做除了能在相等性比较方面获得许多好处之外，不可改变的架构还有许多其他的好处。采用了不可改变数据结构的c# roslyn编译器就是非常好的例子：
语法树的第三个属性是，它们是不可改变的，而且是线程安全的。这意味着，在获得一棵树之后，它就是当前代码状态的快照，而且永远不会改变。这样多个用户可以在不同的线程中与同一个语法树同时进行操作，而无需担心死锁或重复的问题。由于树是不可改变的，也不能针对树进行直接的改变，因此负责创建和修改语法树的工厂方法实际上会创建树的新快照。树本身的效率很高，因为它会重用底层结点，所以创建新版本的速度很快，只需要使用少量内存。
——.net compiler platform sdk文档
原文：https://www.craigstuntz.com/posts/2020-03-09-equality-is-hard.html返回搜狐，查看更多


责任编辑：