![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
О прелестях полиморфного сравнения
Давеча пришлось мне заниматься софтверной паталогоанатомией. То есть, делать вскрытие чужой программе (с исходниками на OCaml), чтобы понять, почему она сдохла. Программа представляла собой узкоспециализированный diff, читающий и сравнивающий массивы сложных структур данных. Читать данные программа могла кучей способов - по сети, из файла, из базы, ...
И вот ВНЕЗАПНО нашелся такой набор данных (из примерно несколько сотен тысяч элементов), который при сравнении с самим собой из двух разных источников давал неожиданый результат: "вот эти два элемента отличаются. Вот вам первый: ..., а вот второй: ....". При этом распечатанные структуры данных выглядели совершенно идентично.
Надо было разобраться, почему запись номер 543123 не сравнивается сама с собой, будучи прочитанной, скажем, из файла и из базы.
У программы имелся обширный debug output, который показывал, что парсинг, построение внутреннего представления и т.п. дают в обоих случаях абсолютно одинаковые результаты. Очень скоро выяснилось (благо, повторюсь, были исходники), что для сравнения записей используется стандартное полиморфное сравнение. Записи содержали в себе многие сотни полей, поэтому, взяв на перевес fieldslib и Fields.fold, я стал сравнивать записи поэлементно, чтобы вывести имя того поля, которое дает ошибку сравнения.
И тут же получил
Тут "вожатый удивился, трамвай остановился". Ведь прямо перед моей функцией сравнения все записи засовываются в HashSet, который их сравнивает, и никакого exception-а там не бросалось. Пришлось лезть в потроха ocaml runtime, и смотреть, как работает полиморфное сравнение. Выяснилось, что документация не врет: "Equality between functional values raises Invalid_argument", но "compare applied to functional values may raise Invalid_argument" (выделение мое).
И действительно:
Две злосчастные записи содержали значение контейнерного типа, в котором было больше чем обычно элементов. Данные из файла и из базы десериализовались слегка в разном порядке, в результате дерево, которое использовалось для реализации контейнера, строилось немного по-разному (хоть и содержало одни и те же значения), и
Тут собиралась быть мораль, но она, как ни крути, получалась нецензурной.
И вот ВНЕЗАПНО нашелся такой набор данных (из примерно несколько сотен тысяч элементов), который при сравнении с самим собой из двух разных источников давал неожиданый результат: "вот эти два элемента отличаются. Вот вам первый: ..., а вот второй: ....". При этом распечатанные структуры данных выглядели совершенно идентично.
Надо было разобраться, почему запись номер 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 - предсказуемо валился.Тут собиралась быть мораль, но она, как ни крути, получалась нецензурной.
no subject
no subject
no subject
no subject
no subject
no subject
no subject
no subject
no subject
no subject
А что касается этой конкретной задачи - так перед сравнением надо было определить, что подразумевается под равенством. Например, явным образом исключить из сравнения функции. Или придумать, как их сравнивать.
no subject
Проблема, действительно, лечится неиспользованием полиморфного сравнения. Другое дело, что если бы compare всегда бросало бы исключение, то это стало бы ясно сильно раньше. Как я понимаю, изначально записи были маленькие и глупые (типа, один инт, одна строка), и полиморфное сравнение было ОК. А потом добавляли одно поле там, одно тут, и так потихоньку добрались до того, что в один прекрасный день добавили что-то несравнимое. Уже не сильно помня детали и подробности того, как именно сравниваем. Если бы тут же вылетело исключение - я уверен, сразу бы пофиксили. А вот фиг ...
no subject
no subject
но, разумеется, само с собой оно всегда давало тру.
хехе, но чтобы два разных сравнения использовать - не было (вернее, второе было немощное и всегда выдавало исключение)
no subject
no subject
no subject
( 'a -> 'a -> bool ), а не какого-то конкретного( int -> int -> bool )no subject
no subject
no subject
scala> import java.math.BigDecimal
scala> val zero1 = new BigDecimal("0.0")
zero1: java.math.BigDecimal = 0.0
scala> val zero2 = new BigDecimal("0.000000")
zero2: java.math.BigDecimal = 0.000000
scala> zero1 equals zero2
res0: Boolean = false
scala> zero1 compareTo zero2
res1: Int = 0
scala> zero2.stripTrailingZeros
res2: java.math.BigDecimal = 0.000000
scala> val one = new BigDecimal("1.000000")
one: java.math.BigDecimal = 1.000000
scala> one.stripTrailingZeros
res3: java.math.BigDecimal = 1
no subject
Надо, что ли, пост еще один написать.
no subject
То есть, я возмущаюсь тем, что (=) кидает исключение, а compare - нет. С моей точки зрения это баг, и compare должен тоже кидать исключение.
А баг этот замели под ковер и написали, что compare _может_ кинуть исключение. А может и не кинуть. И теперь этот как бы не баг, а фича.
Так понятнее?
PS
Противопоставления OCaml <-> Haskell в моем посте не было, и не надо его сюда приплетать.
no subject
Язык должен следовать rule of the least surpise, иначе это баг. Если исключение то бросается, то не бросается в зависимости от того, как ляжет карта - это баг.
Чтобы быть уже совсем конкретным:
Для конкретной реализации hashtable в ocaml и для двух таблиц "x" и "y", содержащих одни и те же данные (compare x y) может вернуть 0, 1 или исключение в зависимости от того, в каком порядке в них засовывались данные. А все от того, что compare старается "срезать углы" в ряде случаев. Это - big surprise, и так быть не должно, независимо от того, насколько глупой является сама идея применения compare к Hashtable.
Теперь моя мысль полностью понятна, и все еще кажется, что надо продолжать читать между строк ?
no subject
> Правильный подход в вашем случае был бы - дописать для себя свой метод сравнения
своих сложных структур данных (хештаблиц), используя в нем = или == для сравнения
базовых элементов данных. написать метод 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 месяцев тому назад, при первом же прогоне тестов. И это было бы правильно, и это было бы хорошо. И это как раз тот самый случай, когда инструмент может позаботится о программисте, даже если программист плохо читал руководство или не умеет использовать все средства языка.
no subject
Я удивлен тому, что можно кидать или не кидать исключение о нарушании инварианта не всегда, а в зависимости от того, как карта ляжет, и еще я удивлен тому, что оказывается такое можно задокументировать и внезапно это становится ОК.