6.16. Неподнятые типы и примитивные операции

6.16.1. Неподнятые типы

Большинство типов в GHC являются упакованными, то есть значения такого типа представлены указателем на объект в куче. Например, представление Haskell Int — это двухсловный объект в куче. Неподнятый тип, однако, представлен самим значением; указатели и выделение памяти в куче не используются.

Неподнятые типы соответствуют типам «необработанной машины», которые вы использовали бы в C: Int# (long int), Double# (double), Addr# (void *) и т. д. Примитивные операции (PrimOps) над этими типами соответствуют ожидаемым: например, (+#) — это сложение значений типа Int#s, то есть знакомая всем машинная операция сложения, обычно реализуемая одной инструкцией.

Примитивные (неподнятые) типы нельзя определить на Haskell, поэтому они встроены в язык и компилятор. Примитивные типы всегда являются неприподнятыми, то есть значение примитивного типа не может быть ⊥. (Примечание: «упакованный» тип означает, что значение представлено указателем на объект в куче; «поднятый» тип означает, что термы этого типа могут быть равны ⊥. Пример см. в следующем абзаце.) Мы придерживаемся соглашения (но это только соглашение), согласно которому примитивные типы, значения и операции имеют суффикс # (см. Магический знак решётки). Для некоторых примитивных типов предусмотрен специальный синтаксис литералов, также описанный в том же разделе.

Примитивные значения часто представлены простым битовым шаблоном, например Int#, Float#, Double#. Но это не обязательно так: примитивное значение может быть представлено указателем на объект, выделенный в куче. Например, Array# — тип примитивных массивов. Таким образом, Array# — это неприподнятый упакованный тип. Примитивный массив размещается в куче, потому что его значение слишком велико, чтобы поместиться в регистре, а его копирование было бы слишком затратным; в некотором смысле представление указателем здесь случайно. Если указатель представляет примитивное значение, он действительно указывает на это значение: никаких невычисленных отсроченных вычислений и никаких косвенных ссылок. На другом конце указателя не может находиться ничего, кроме примитивного значения. Программа с интенсивными численными вычислениями, использующая неподнятые типы, может работать намного быстрее своего «обычного» аналога — в одном примере мы наблюдали трёхкратное ускорение.

6.16.2. Кинды неподнятых типов

Поскольку неподнятые типы представлены без использования указателей, мы не можем хранить их в полиморфном типе данных. Например, узел Just типа Just 42# должен был бы отличаться от узла Just типа Just 42; первый хранит непосредственно целое число, а второй — указатель. В настоящее время GHC не поддерживает такие разновидности узлов Just (как и для любых других типов данных). Поэтому кинда неподнятого типа отличается от кинды упакованного типа.

В отчёте Haskell указано, что * (записывается как Type и импортируется из Data.Kind в диалекте Haskell, используемом GHC) — кинда обычных типов данных, например Int. Кроме того, у конструкторов типов могут быть кинды со стрелками; например, кинда Maybe — Type -> Type. Кинда неподнятых типов задаёт их представление во время выполнения. Например, тип Int# имеет кинду TYPE IntRep, а Double# — кинду TYPE DoubleRep. Эти кинды указывают, что представление Int# во время выполнения — машинное целое число, а представление Double# — машинное число с плавающей точкой двойной точности. Напротив, кинда Type на самом деле является синонимом TYPE LiftedRep. Подробнее о механизмах TYPE см. в разделе о полиморфизме представления во время выполнения.

Поскольку кинда Int# — не Type, следует, что Maybe Int# запрещено. Аналогично, поскольку переменные типов обычно имеют кинду Type (например, в (.) :: (b -> c) -> (a -> b) -> a -> c все переменные типов имеют кинду Type), полиморфизм обычно не работает с примитивными типами. Если взглянуть на это шире, в этом есть смысл, поскольку полиморфной функции необходимо работать с указателями на свои данные, а большинство примитивных типов являются неподнятыми.

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

• Нельзя определить newtype, тип представления которого (тип аргумента конструктора данных) является неподнятым типом. Поэтому следующий код недопустим:

  newtype A = MkA Int#
  

  Однако это ограничение можно ослабить, включив расширение UnliftedNewtypes. Поведение таких типов описано в разделе о неприподнятых newtype.

• Нельзя связать переменную неподнятого типа в привязке верхнего уровня.
• Нельзя связать переменную неподнятого типа в рекурсивной привязке.

• Неподнятые переменные можно связывать в (нерекурсивной привязке не верхнего уровня), но такое сопоставление с образцом необходимо сделать строгим. (Если этого не сделать, будет выдано предупреждение -Wunbanged-strict-patterns.) Например, вместо:

  data Foo = Foo Int Int#
  
  f x = let (Foo a b, w) = ..rhs.. in ..body..
  

  необходимо написать:

  data Foo = Foo Int Int#
  
  f x = let !(Foo a b, w) = ..rhs.. in ..body..
  

  поскольку тип b — Int#. См. раздел Динамическая семантика шаблонов с восклицательным знаком.

6.16.3. Неподнятые кортежи

UnboxedTuples

Включает:

UnboxedSums

Начиная с версии:

6.8.1

Неподнятые кортежи на самом деле не экспортируются модулем GHC.Exts; это синтаксическое расширение (UnboxedTuples). Неподнятый кортеж выглядит так:

(# e_1, ..., e_n #)

где e_1..e_n — выражения любого типа (примитивного или непримитивного). Тип неподнятого кортежа выглядит так же.

Обратите внимание: если неподнятые кортежи включены, (# — это одна лексема, поэтому при использовании операторов вроде # и #- нужно писать ( # ) и ( #- ), а не (#) и (#-).

Неподнятые кортежи используются функциями, которым нужно возвращать несколько значений, но позволяют избежать выделения памяти в куче, обычно связанного с использованием полноценных кортежей. При возврате неподнятого кортежа его компоненты помещаются непосредственно в регистры или в стек; сам неподнятый кортеж не имеет составного представления. Многие примитивные операции, перечисленные в primops.txt.pp, возвращают неподнятые кортежи. В частности, монады IO и ST используют неподнятые кортежи, чтобы избежать ненужного выделения памяти при последовательном выполнении операций.

Обычно неподнятые кортежи просто используют для возврата нескольких значений, связывая эти результаты с помощью выражения case, например:

f x y = (# x+1, y-1 #)
g x = case f x x of { (# a, b #) -> a + b }

Неподнятый кортеж можно использовать в привязке с образцом, например:

f x = let (# p,q #) = h x in ..body..

Если типы p и q не являются неподнятыми, полученная привязка будет ленивой, как и любая другая привязка с образцом в Haskell. Приведённый выше пример преобразуется в следующий код:

f x = let t = case h x of { (# p,q #) -> (p,q) }
          p = fst t
          q = snd t
      in ..body..

Более того, привязки могут быть даже рекурсивными. Более подробное описание см. в разделе Динамическая семантика шаблонов с восклицательным знаком.

Чтобы ссылаться на сами конструкторы типов неподнятых кортежей, например если вы хотите определить для них экземпляры, используйте (# #), (#,#), (#,,#) и т. д. Это соответствует синтаксису упакованных кортежей (), (,), (,,) и т. д.

6.16.4. Неподнятые суммы

UnboxedSums

Подразумевается расширением:

UnboxedTuples

Начиная с версии:

8.2.1

Включает синтаксис неподнятых сумм. Подразумевается расширением UnboxedTuples.

-XUnboxedSums включает новый синтаксис для анонимных неподнятых типов-сумм. Синтаксис неподнятого типа-суммы с N альтернативами выглядит так:

(# t_1 | t_2 | ... | t_N #)

где t_1 … t_N — типы (которые могут быть неприподнятыми, включая неподнятые кортежи и суммы).

Для альтернатив с несколькими аргументами можно использовать неподнятые кортежи. Например:

(# (# Int, String #) | Bool #)

Синтаксис на уровне термов похож. Начальные и последующие вертикальные черты (|) указывают, какая это альтернатива. Вот два терма приведённого выше типа:

(# (# 1, "foo" #) | #) -- first alternative

(# | True #) -- second alternative

Синтаксис образцов соответствует синтаксису термов:

case x of
  (# (# i, str #) | #) -> ...
  (# | bool #) -> ...

Обратите внимание, что вокруг вертикальных черт всегда должны быть пробелы. Например, (# | 1# | | #) допустимо, а (# | 1# || #) и (#| 1# | | #) недопустимы.

Сами конструкторы типов можно записывать в префиксной форме: (# | #), (# | | #), (# | | | #) и т. д. Частичное применение также должно записываться в префиксной форме, то есть (# | #) Int#. Применения с полным числом аргументов можно записывать в любой форме, поэтому (# | #) Int# Float# эквивалентно (# Int# | Float# #).

Неподнятые суммы являются «неподнятыми» в том смысле, что вместо размещения сумм в куче и представления значений указателями они представлены своими компонентами, как и неподнятые кортежи. Эти «компоненты» зависят от альтернатив типа-суммы. Как и неподнятые кортежи, неподнятые суммы ленивы в своих поднятых компонентах.

Генератор кода старается создать для каждой неподнятой суммы максимально компактную раскладку. В лучшем случае размер неподнятой суммы равен размеру самой большой альтернативы плюс одно машинное слово (для тега). Алгоритм создания раскладки в памяти для типа-суммы работает следующим образом:

• Все типы распределяются по одному из следующих классов: 32-битное слово, 64-битное слово, 32-битное число с плавающей точкой, 64-битное число с плавающей точкой, указатель.
• Для каждой альтернативы типа-суммы создаётся раскладка, состоящая из этих полей. Например, если альтернатива содержит поля Int, Float# и String, раскладка будет содержать поля 32-битного слова, 32-битного числа с плавающей точкой и указателя.

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

  (# (# Word32#, String, Float# #)
  |  (# Float#, Float#, Maybe Int #) #)
  

  Итоговая раскладка будет примерно такой:

  Int32, Float32, Float32, Word32, Pointer
  

  Первое Int32 используется для тега. Полей Float32 два, поскольку типы с плавающей точкой нельзя наложить на другие типы из-за ограничений генератора кода, которые мы надеемся устранить в будущем. Для второй альтернативы требуются два поля Float32: поле Word32 предназначено для Word32# в первой альтернативе. Поле Pointer используется совместно значениями String и Maybe Int альтернатив.

  Другой пример — раскладка неподнятой версии типа Maybe a, (# (# #) | a #):

  Int32, Pointer
  

  Поле Pointer не используется, если тег указывает на Nothing. В противном случае Pointer указывает на значение в Just. Как упоминалось выше, этот тип ленив в своём поднятом поле. Поэтому тип

  data Maybe' a = Maybe' (# (# #) | a #)
  

  в точности изоморфен типу Maybe a, хотя их представления в памяти различаются.

  В вырожденном случае, когда все альтернативы имеют нулевую ширину, например для типа Bool наподобие (# (# #) | (# #) #), раскладка неподнятой суммы содержит только поле тега Int32 (то есть вся конструкция представлена целым числом).

6.16.5. Неприподнятые newtype

UnliftedNewtypes

Начиная с версии:

8.10.1

Включает использование newtype над типами с неприподнятыми представлениями во время выполнения.

В GHC реализовано расширение UnliftedNewtypes, описанное в предложении GHC № 98. UnliftedNewtypes смягчает ограничения на типы, которые могут находиться внутри newtype. Например, следующий тип

newtype A = MkA Int#

принимается, если это расширение включено. При этом создаются тип A :: TYPE IntRep и конструктор данных MkA :: Int# -> A. Хотя GHC выводит кинду A, у этого типа нет никаких визуальных отличительных признаков, указывающих на то, что его кинда не Type, как обычно бывает у newtype. Для большей ясности можно использовать GADTSyntax, чтобы указать сигнатуру кинды.

newtype A :: TYPE IntRep where
  MkA :: Int# -> A

Механизм Coercible работает с неприподнятыми newtype так же, как и с поднятыми типами. В любой из эквивалентных форм записей A, приведённых выше, пользователи также получат доступ к преобразованию между A и Int#.

Вследствие ограничения на полиморфные по представлению связывания поля, полиморфные по представлению, запрещены в конструкторах данных типов данных, объявленных с помощью data. Однако применение конструктора данных newtype реализовано как преобразование, а не как применение функции, поэтому это ограничение не распространяется на поле внутри конструктора данных newtype. Таким образом, проверка типов принимает следующий код:

newtype Identity# :: forall (r :: RuntimeRep). TYPE r -> TYPE r where
  MkIdentity# :: forall (r :: RuntimeRep) (a :: TYPE r). a -> Identity# a

А при включённом расширении UnboxedSums — следующий:

newtype Maybe# :: forall (r :: RuntimeRep). TYPE r -> TYPE (SumRep '[r, TupleRep '[]]) where
  MkMaybe# :: forall (r :: RuntimeRep) (a :: TYPE r). (# a | (# #) #) -> Maybe# a

Это расширение также ослабляет некоторые ограничения на экземпляры семейств данных. В частности, UnliftedNewtypes позволяет задать для newtype instance возвращаемую кинду TYPE r, а не только Type. Например, следующие объявления newtype instance будут допустимы:

class Foo a where
  data FooKey a :: TYPE IntRep
class Bar (r :: RuntimeRep) where
  data BarType r :: TYPE r

instance Foo Bool where
  newtype FooKey Bool = FooKeyBoolC Int#
instance Bar WordRep where
  newtype BarType WordRep = BarTypeWordRepC Word#

Стоит отметить, что расширение UnliftedNewtypes не требуется, чтобы задавать самим семействам данных возвращаемые кинды, включающие TYPE, например как в приведённых выше примерах FooKey и BarType. Это расширение необходимо только для объявлений newtype instance, например FooKeyBoolC и BarTypeWorkRepC выше.

Это расширение влияет на определение того, имеет ли newtype полную заданную пользователем кинду (CUSK). Точное влияние описано в разделе о CUSK.

6.16.6. Неприподнятые типы данных

UnliftedDatatypes

Включает:

DataKinds, StandaloneKindSignatures

Начиная с версии:

9.2.1

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

В GHC реализовано расширение UnliftedDatatypes, описанное в предложении GHC № 265. UnliftedDatatypes смягчает ограничения на допустимые результирующие кинды в объявлениях типов данных. Например, следующий тип

data UList a :: UnliftedType where
  UCons :: a -> UList a -> UList a
  UNil :: UList a

определяет тип списка, имеющий кинду UnliftedType (например, TYPE (BoxedRep Unlifted)). Следовательно, предполагается, что каждое вхождение терма этого типа уже вычислено (и компилятор гарантирует, что это действительно так). Иными словами, неприподнятые типы данных ведут себя как типы данных в строгих языках, таких как OCaml или Idris. Однако, в отличие от StrictData, это расширение не меняет строгость или ленивость полей (возможно, неприподнятого) типа данных. Например, UCons ленив по первому аргументу, поскольку его поле имеет кинду Type.

Поскольку неподнятые типы всегда вычислены, GHC может исключать проверки вычисленности во время выполнения. О том, как это может улучшить производительность некоторых программ, рассказывается в разделе «Мотивация» предложения.

Приведённое выше объявление типа данных в синтаксисе GADT показывает, что неподнятые типы данных совместимы со всеми возможностями GADT. В некотором смысле, верно и обратное: неподнятые типы данных можно объявлять и в синтаксисе Haskell98, если указать результирующую кинду с помощью StandaloneKindSignatures:

type UList :: Type -> UnliftedType
data UList a = UCons a (UList a) | UNil

Можно даже объявлять типы данных, полиморфные по уровню представления:

type PEither :: Type -> Type -> TYPE (BoxedRep l)
data PEither l r = PLeft l | PRight r

f :: PEither @Unlifted Int Bool -> Bool
f (PRight b) = b
f _          = False

Хотя приведённый выше f вполне мог бы быть полиморфным по уровню представления (поскольку в любом случае вычисляет свой аргумент), в настоящее время GHC запрещает более общий тип PEither @l Int Bool -> Bool. Это следствие ограничения на полиморфные по представлению связывания.

Сопоставление с образцом для неподнятого типа данных работает так же, как и для поднятых типов; однако семантику привязок с образцом, содержащих неподнятые типы данных, см. в разделе Динамическая семантика шаблонов с восклицательным знаком.

Из-за ошибки #19487 в настоящее время нельзя объявлять полиморфные по уровню представления типы данных с конструкторами данных без аргументов. Однако есть обходной путь:

type T :: TYPE (BoxedRep l)
data T where
  MkT :: forall l. (() :: Constraint) => T @l

Использование => делает тип MkT поднятым. Если вам нужен вариант без затрат во время выполнения, используйте вместо него MkT :: Proxy# () -> T @l и учитывайте дополнительный аргумент proxy# в местах создания значений.

Это расширение также ослабляет некоторые ограничения на экземпляры семейств данных. В частности, UnliftedDatatypes позволяет задать для data instance возвращаемую кинду, унифицируемую с TYPE (BoxedRep l), а не только Type. Например, следующие объявления data instance будут допустимы:

data family F a :: UnliftedType
data instance F Int = FInt

data family G a :: TYPE (BoxedRep l)
data instance G Int = GInt Int -- defaults to Type
data instance G Bool :: UnliftedType where
  GBool :: Bool -> G Bool
data instance G Char :: Type where
  GChar :: Char -> G Char
data instance G Double :: forall l. TYPE (BoxedRep l) where
  GDouble :: Int -> G @l Double

Стоит отметить, что расширение UnliftedDatatypes не требуется, чтобы задавать самим семействам данных возвращаемые кинды, включающие TYPE, например как в приведённом выше примере G. Это расширение необходимо только для объявлений data instance, например FInt и GBool выше.

6.16.7. Примитивные строковые литералы

Примитивные строковые литералы, также называемые неподнятыми строковыми литералами или литералами Addr#, — это строковые литералы с завершающим знаком решётки #. Они включаются расширением MagicHash и имеют тип Addr#.

Примитивный строковый литерал представляет последовательность байтов. В него можно включить нулевой байт, например "foo\0bar"#, который соответствует байтам [102,111,111,0,98,97,114] :: [Word8] (с неявным нулевым байтом в конце). Кроме того, можно включать только символы с кодом меньше 256: "\xFF"# допустимо и представляет [255] :: [Word8], а "\x3B1"# недопустимо. Иными словами, используется кодировка Latin-1.

Как и строки C, примитивные строковые литералы неявно завершаются нулевым байтом.

Примитивные строковые литералы неизменяемы; попытка записи по их адресу приводит к неопределённому поведению.

6.16.8. Десахаризация строковых литералов

Строковый литерал ASCII без нулевого байта десахаризуется в вызов GHC.CString.unpackCString#, которому передаётся содержимое в виде примитивного строкового литерала. Например, "some string" преобразуется в GHC.CString.unpackCString# "some string"#.

Если строка содержит нулевые байты или символы не из ASCII (символы с кодовыми точками >= 128), она кодируется в модифицированном UTF-8, а затем передаётся в GHC.CString.unpackCStringUtf8#. Модифицированный UTF-8 отличается от стандартного UTF-8 двумя особенностями:

• Нулевой байт кодируется как "\xC0\x80"# (то есть избыточным кодированием U+0000).
• Суррогатные кодовые точки допускаются и кодируются так же, как остальные кодовые точки.

Примеры:

• "Hello\0world!" десахаризуется в GHC.CString.unpackCStringUtf8# "Hello\xC0\x80world!"#.
• "café" десахаризуется в GHC.CString.unpackCStringUtf8# "caf\xC3\xA9"#.
• "\x732B\x1F431" десахаризуется в GHC.CString.unpackCStringUtf8# "\xE7\x8C\xAB\xF0\x9F\x90\xB1"#.
• "\xDFFF\xD800" десахаризуется в GHC.CString.unpackCStringUtf8# "\xED\xBF\xBF\xED\xA0\x80"#.