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

[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

[ghrar.livejournal.com]

где там в вышке перемена мест слагаемых меняет сумму?)))

[dil.livejournal.com]

Я что-то вообще не понимаю, как сериализуются функции.

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

[perepertoz.livejournal.com]

как-то в практике было некоммутативное сравнение.
но, разумеется, само с собой оно всегда давало тру.
хехе, но чтобы два разных сравнения использовать - не было (вернее, второе было немощное и всегда выдавало исключение)

[frizzby.livejournal.com]

Скажите, а что такое полиморфное сравнение? Гугл по этой фразе первым отдаёт этот пост, а дальше вообще ничего по теме.

[sorhed.livejournal.com]

Ну, то есть и в окамле такой же бардак как в джаве с equals/compare.

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