О прелестях полиморфного сравнения

[dastapov]

Давеча пришлось мне заниматься софтверной паталогоанатомией. То есть, делать вскрытие чужой программе (с исходниками на OCaml), чтобы понять, почему она сдохла. Программа представляла собой узкоспециализированный diff, читающий и сравнивающий массивы сложных структур данных. Читать данные программа могла кучей способов - по сети, из файла, из базы, ...

И вот ВНЕЗАПНО нашелся такой набор данных (из примерно несколько сотен тысяч элементов), который при сравнении с самим собой из двух разных источников давал неожиданый результат: "вот эти два элемента отличаются. Вот вам первый: ..., а вот второй: ....". При этом распечатанные структуры данных выглядели совершенно идентично.


Надо было разобраться, почему запись номер 543123 не сравнивается сама с собой, будучи прочитанной, скажем, из файла и из базы.

У программы имелся обширный debug output, который показывал, что парсинг, построение внутреннего представления и т.п. дают в обоих случаях абсолютно одинаковые результаты. Очень скоро выяснилось (благо, повторюсь, были исходники), что для сравнения записей используется стандартное полиморфное сравнение. Записи содержали в себе многие сотни полей, поэтому, взяв на перевес fieldslib и Fields.fold, я стал сравнивать записи поэлементно, чтобы вывести имя того поля, которое дает ошибку сравнения.

И тут же получил Exception: Invalid_argument "equal: functional value". И действительно, в записи содержалось поле с этим самым функциональным типом. Там был сложный чисто функциональный контейнер, но для простоты предоложим, что это была обычная функция (a->a).

Тут "вожатый удивился, трамвай остановился". Ведь прямо перед моей функцией сравнения все записи засовываются в HashSet, который их сравнивает, и никакого exception-а там не бросалось. Пришлось лезть в потроха ocaml runtime, и смотреть, как работает полиморфное сравнение. Выяснилось, что документация не врет: "Equality between functional values raises Invalid_argument", но "compare applied to functional values may raise Invalid_argument" (выделение мое).

И действительно:

# let x = (fun a b -> a);;
val x : 'a -> 'b -> 'a = <fun>

# let y = (fun a b -> b);;
val y : 'a -> 'b -> 'b = <fun>

# compare x x;;
- : int = 0

# compare x y;;
Exception: Invalid_argument "equal: functional value".

# x = x;;
Exception: Invalid_argument "equal: functional value".

# x = y;;
Exception: Invalid_argument "equal: functional value".


Две злосчастные записи содержали значение контейнерного типа, в котором было больше чем обычно элементов. Данные из файла и из базы десериализовались слегка в разном порядке, в результате дерево, которое использовалось для реализации контейнера, строилось немного по-разному (хоть и содержало одни и те же значения), и compare для этих деревьев выдавал 1, а eq - предсказуемо валился.

Тут собиралась быть мораль, но она, как ни крути, получалась нецензурной.

Comments

[http://users.livejournal.com/_adept_/]

Возможно из текста это почему-то не очевидно, но сравнивались не сериализованные представления фунций, а сами функции. Т.е. compare и (=) применялись к одним и тем же значениям с разным результатом без очевидного объяснения.

То есть, я возмущаюсь тем, что (=) кидает исключение, а compare - нет. С моей точки зрения это баг, и compare должен тоже кидать исключение.

А баг этот замели под ковер и написали, что compare _может_ кинуть исключение. А может и не кинуть. И теперь этот как бы не баг, а фича.

Так понятнее?

PS
Противопоставления OCaml <-> Haskell в моем посте не было, и не надо его сюда приплетать.

[http://users.livejournal.com/_adept_/]

Извините, но мне кажется, что вы спорите сами с собой а не со мной сейчас.

Язык должен следовать rule of the least surpise, иначе это баг. Если исключение то бросается, то не бросается в зависимости от того, как ляжет карта - это баг.

Чтобы быть уже совсем конкретным:
Для конкретной реализации hashtable в ocaml и для двух таблиц "x" и "y", содержащих одни и те же данные (compare x y) может вернуть 0, 1 или исключение в зависимости от того, в каком порядке в них засовывались данные. А все от того, что compare старается "срезать углы" в ряде случаев. Это - big surprise, и так быть не должно, независимо от того, насколько глупой является сама идея применения compare к Hashtable.

Теперь моя мысль полностью понятна, и все еще кажется, что надо продолжать читать между строк ?

[http://users.livejournal.com/_adept_/]

> Правильный подход в вашем случае был бы - дописать для себя свой метод сравнения
своих сложных структур данных (хештаблиц), используя в нем = или == для сравнения
базовых элементов данных. написать метод Hashtbl.compare.
..
> по-моему это программист должен читать руководство и правильно использовать средства языка.

Никто с этим не спорит, и в идеальном мире так и должно быть. Теперь смотрим, что происходит в реальном мире. Кто-то 100500 лет тому назад пишет код, который оперирует записями вида { name:string; age:int; money:float }. Списки таких записей сортируются и/или сравниваются с помощью полиморфных (=) и (compare), засовываются в HashSet или другие подобные контейнеры, и все работает хорошо и замечательно.

Идут года, в этот код (и в эту запись) добавляются новые данные, в программу добавляется новая функциональность. Вот уже в ней 10000 строк, а в записи 400 полей. Каждый раз, когда кто-то добавляет поле в запись, компилятор услужливо показывает, что и где надо поменять. Дополнительно используются regression test-ы, и все довольны и счастливы. И вот кто-то добавляет в эту запись вычислимое поле типа HashMap. Прогоняет regression test-ы. Все хорошо и отлично, все работает.

И вдруг, 1000 коммитов и 5 месяцев спустя, все ломается. Потому, что сравнение записей внезапно ведет себя не так, как раньше. А происходит это потому, что сравнение вычислимых полей типа HashMap внезапно пошло по другому code path внутри compare, и мы на выходе получаем другой результат. Некорректный, но без исключения. А если бы карта лягла чуть по-другому, и мы построили бы тот же самый HashMap чуть в другом порядке, то получили бы exception.

А самое главное - если бы compare был внутри реализован без оптимизаций, то мы бы получили исключение сразу же, 5 месяцев тому назад, при первом же прогоне тестов. И это было бы правильно, и это было бы хорошо. И это как раз тот самый случай, когда инструмент может позаботится о программисте, даже если программист плохо читал руководство или не умеет использовать все средства языка.

[http://users.livejournal.com/_adept_/]

Да елки же! Я удивлен совсем другому.

Я удивлен тому, что можно кидать или не кидать исключение о нарушании инварианта не всегда, а в зависимости от того, как карта ляжет, и еще я удивлен тому, что оказывается такое можно задокументировать и внезапно это становится ОК.