Как OCaml может сортировать полиморфные варианты по их текстовому представлению?

avatar
Gregory Nisbet
8 апреля 2018 в 03:53
199
1
9

В OCaml полиморфное сравнение реализуется путем обхода представления значений во время выполнения, которое состоит из непосредственных значений и указателей на блоки.

Согласно Real World Ocaml, полиморфный вариант без параметров просто сохраняется как неупакованное целое число. Отрывок воспроизведен здесь для удобства.

Полиморфный вариант без каких-либо параметров сохраняется как неупакованный целым числом, поэтому занимает в памяти только одно слово, как обычный вариант. Это целочисленное значение определяется путем применения хэш-функции к названию варианта. Хеш-функция не отображается напрямую компилятором, но библиотека type_conv от Core предоставляет альтернативная реализация: ...

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

# List.sort Pervasives.compare
     [ `L ; `K ; `J ; `I ; `H ; `G ; `F ; `E ; `D; `C ; `B; `A ];; 
[`A; `B; `C; `D; `E; `F; `G; `H; `I; `J; `K; `L]

Есть одна небольшая проблема: кажется, что длина представления имеет наибольшее значение при упорядочении.

# List.sort compare  [ `BBBB; `AAAA; `AAA; `ABA; `BB; `ZZ; `AA ];; 
[`AA; `BB; `ZZ; `AAA; `ABA; `AAAA; `BBBB]

Как это удается OCaml? Каким образом информация, необходимая OCaml для лексикографической сортировки вариантов, по-прежнему присутствует во время выполнения? Разве полиморфный вариант без аргументов не должен быть неотличим от обычного целого числа?

Выбрали ли разработчики OCaml хеш-функцию, которая по совпадению/дизайну имеет такое поведение для коротких имен вариантов?

Источник
Richard-Degenne
9 апреля 2018 в 14:09
0

Просто ради того, чтобы констатировать очевидное, я настоятельно рекомендую вам не полагаться на такое свойство в реальном коде.

Gregory Nisbet
10 апреля 2018 в 02:42
0

@RichouHunter Меня просто удивило, что порядок сравнения не является «полностью непредсказуемым».

Richard-Degenne
10 апреля 2018 в 07:55
0

Конечно, я мог сказать. Я просто не хочу, чтобы будущий читатель думал об этом.

Ответы (1)

avatar
Jeffrey Scofield
8 апреля 2018 в 04:32
9

Благодаря своей конструкции хэш-функция сохраняет порядок коротких строк. Но это не общее свойство.

# List.sort compare [`AAAAAAA; `BAAAAAA; `CAAAAAA];;
- : [> `AAAAAAA | `BAAAAAA | `CAAAAAA ] list =
       [`BAAAAAA; `CAAAAAA; `AAAAAAA]
#

Код хэширования для OCaml 4.06.0 выглядит следующим образом:

CAMLexport value caml_hash_variant(char const * tag)
{
  value accu;
  for (accu = Val_int(0); *tag != 0; tag++)
    accu = Val_int(223 * Int_val(accu) + *((unsigned char *) tag));
#ifdef ARCH_SIXTYFOUR
  accu = accu & Val_long(0x7FFFFFFFL);
#endif
  /* Force sign extension of bit 31 for compatibility between 32 and 64-bit
     platforms */
  return (int32_t) accu;
}

Мне кажется, что для коротких строк символов с кодами меньше 223 это будет способствовать сохранению лексического порядка.