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

Если вы пишете алгоритм биоинформатики в Haskell, вы, вероятно, будете использовать тип алгебраических данных для представления нуклеотидов:

data Nucleotide = A | T | C | G

Вы бы сделали аналогично в стандартном ML или OCaml, я предполагаю (я никогда не использовал его).

Значение типа Nucleotide может содержаться в двух битах. Тем не менее, это приведет к тому, что время доступа будет медленнее, чем если бы вы использовали один байт за значение Nucleotide, так как вам нужно было бы выбрать два бита интереса, используя двоичные операторы.

Следовательно, существует неотъемлемый компромисс, который компилятор должен делать между эффективностью памяти и вычислительной эффективностью при принятии решения о том, как представлять алгебраические типы данных. Более того, представление алгебраических типов данных в памяти усложняется тем, что значение может иметь переменный размер:

data Maybe a = Just a | Nothing

Очевидно, что значение Maybe a формы Just a логически больше значения формы Nothing. В крайнем примере:

data Hulk a b c d e = Big a b c d e | Little

вам определенно не захочется хранить в нулевых указателях значения Little или нулевые значения для пяти значений, содержащихся в значениях Big. Я предполагаю, что вы просто используете выделенную кучу память с переменным размером с идентификатором конструктора в начале (например, 0 для Big и 1 для Little). Однако, если вы хотите сохранить значения Hulk в стеке (более быстрое представление), вам нужно сохранить пустую память вместе с значениями Little, чтобы все значения типа Hulk были одинакового размера. Другой компромисс.

Саймон Марло ответил на мой общий вопрос в отношении GHC в qaru.site/info/3240/.... Однако у меня есть три связанных вопроса, которые остаются без ответа:

  • Используют ли стандартные ML (SML/NJ и MLton) и OCaml ту же технику?
  • Если да, то какие-либо менее распространенные компиляторы этих языков (или их братьев и сестер) экспериментируют с другими методами?
  • Есть ли достаточно простой способ (в идеале - флаг прагмы или флажка) на этих языках использовать более эффективное представление памяти, например двухбитное представление Nucleotide? Такая эффективность памяти необходима для многих применений биоинформатики; если каждый Nucleotide должен был быть одним байтом, высокопроизводительные алгоритмы биоинформатики должны были бы прибегать к ручному путанию.

Ответы

Ответ 1

Нет единого ответа: типы данных являются абстрактными структурами и могут быть реализованы различными способами по усмотрению исполнителя. На практике такие соображения, как отдельная компиляция, имеют тенденцию несколько ограничивать ситуацию.

Для конкретного случая упаковки типа данных, содержащего только нулевые конструкторы, как можно меньше бит, вы можете продолжить, определяя функции от типа данных до малого целого и обратно. Интеллектуальный тип, скрытый абстрактным типом (или в Haskell, newtype), также был бы разумным выбором. Упаковка и распаковка небольших целых чисел в любую сводную форму, с которой вы работаете, будет вашей работой.

Кстати, в Real World OCaml очень хорошая глава о представлении значений OCaml (краткое резюме: не сильно отличается от GHC для цели этого вопроса).