Почему кортежи GHC ограничены размером 62?

Из отчета Haskell 98:

Верхняя граница размера кортежа отсутствует, но некоторые реализации Haskell могут ограничивать размер кортежей и ограничивать экземпляры, связанные с большими кортежами. Тем не менее, каждая реализация Haskell должна поддерживать кортежи размером до 15, а также экземпляры для Eq, Ord, Bounded, Read и Show. (...)

Однако хорошо известно, что GHC не поддерживает кортежи размером более 62. Вот что происходит, когда я пытаюсь создать кортеж размера 63 в GHCi:

<interactive>:1:1: error:
    A 63-tuple is too large for GHC
      (max size is 62)
      Workaround: use nested tuples or define a data type

Я понимаю, что это соответствует спецификации Haskell 98, а также, что кортеж размером более 62, вероятно, будет крайне ненужным, но я не понимаю, почему именно это так, как в GHC.

Подводя итог:

  • Почему существует ограничение размера кортежа?
  • Почему ограничение размера составляет 62?

Кроме того:

  • Почему это относится только к GHC 6.12.2 и далее?
  • Делают ли другие выдающиеся реализации Haskell? Каковы их причины?

Ответы

Ответ 1

Я думаю, что спекуляция повторится: время этого изменения комментариев неверно. Во-первых, насколько я могу судить, предел существовал с момента LONG до 6.12.1. Как видно из TraС# 98 с ноября 2002 г., в версии 5.02.2 предел составлял 37 (вместо 62) и пытался используйте более крупный кортеж, созданный таинственным сообщением:

Switches_tupel.lhs:1:
Failed to find interface decl for
`PrelTup.(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,)'
    from module `PrelTup'

Саймон Пейтон-Джонс исправил ошибку, предоставив компилятору проверить размер ранее в конвейере компиляции и создать более приятное сообщение об ошибке (видимое в Git commit b44c6881). К моменту совершения этой фиксации лимит уже был увеличен с 37 до 62 (Git commit 9af77fa4, который интегрировал Template Haskell в HEAD), поэтому GHC 5.04 был выпущен с ограничением в 62 кортежа и лучшей ошибкой сообщение.

Я считаю, что исходная ошибка TraС# 98 указывает на причину ограничения. В ghc/compiler/prelude/TysWiredIn.hs предварительно задан набор типов и типов данных:

boxedTupleArr, unboxedTupleArr :: Array Int (TyCon,DataCon)
boxedTupleArr   = listArray (0,mAX_TUPLE_SIZE) [mk_tuple Boxed   i 
                    | i <- [0..mAX_TUPLE_SIZE]]
unboxedTupleArr = listArray (0,mAX_TUPLE_SIZE) [mk_tuple Unboxed i 
                    | i <- [0..mAX_TUPLE_SIZE]]

где mAX_TUPLE_SIZE - предел 62 кортежей. Однако функции, которые фактически используют эти предварительно распределенные массивы, с удовольствием генерируют большие конструкторы по требованию ( "Build one специально" ):

tupleTyCon :: Boxity -> Arity -> TyCon
tupleTyCon sort i | i > mAX_TUPLE_SIZE 
                = fst (mk_tuple sort i)  -- Build one specially
tupleTyCon Boxed   i = fst (boxedTupleArr   ! i)
tupleTyCon Unboxed i = fst (unboxedTupleArr ! i)

и это то, что раньше делал компилятор, прежде чем Саймон добавил сообщение об ошибке для 5.04 - он специально построил.

К сожалению, это вызвало ошибку (не segfault, просто ошибку) позже в процессе компиляции, когда компилятор не смог найти определение интерфейса для слишком большого кортежа в списке, указанном в ghc/libraries/ghc-prim/GHC/Tuple.hs. Согласно (слегка устаревшим) комментариям в TysWiredIn.hs под заголовком The tuple types объявления в Tuple.hs используются для построения информационных таблиц и кода ввода для конструкторов кортежей, даже если они теоретически могут быть программно созданы на лету для сколь угодно больших кортежей.

Итак, что это значит для современного GHC? Ну, по тем же техническим причинам, о которых говорилось выше, хотя компилятор готов генерировать произвольно большие кортежи, существует ограничение, связанное с тем, что они требуют сопоставления объявлений в .../GHC/Tuple.hs.

Я провел несколько экспериментов, скомпилировав GHC из источника с отключенной проверкой длины кортежа. Получившийся компилятор успешно скомпилировал и выполнил следующую программу со 100-кортежем:

a = (False,...,False)  -- imagine 100 Falses
main = let (x,_,...,_) = a
       in print x

и он напечатал "False". Он отлично работал, когда я модифицировал его, чтобы захватить последний элемент одного и того же кортежа:

a = (False,...,False)  -- imagine 100 Falses
main = let (_,...,_,x) = a
       in print x

Однако программа:

a = (False,...,False)  -- imagine 100 Falses
main = let (x,_,...,_,y) = a
       in print (x,y)

не удалось выполнить ошибку привязки:

[1 of 1] Compiling Main             ( Tuple.hs, Tuple.o )
Linking Tuple ...
Tuple.o(.data+0x0): error: undefined reference to 'ghczmprim_GHCziTuple_Z100T_con_info'
collect2: error: ld returned 1 exit status
`gcc' failed in phase `Linker'. (Exit code: 1)

Я подозреваю, что для первых двух программ компилятор оптимизировал ссылку на отсутствующий конструктор, но для последней программы это понадобилось. После того, как я добавил объявление для 100-кортежей в Tuple.hs и перестроил компилятор, все три программы скомпилированы и работают нормально.

Короче говоря, компиляция вручную построенного списка кортежей в Tuple.hs генерирует требуемые структуры данных для поддержки кортежей до размера 62, и никто не был достаточно мотивирован для повторной реализации этой генерации структуры данных, чтобы быть независимым от Tuple.hs костыль. Если бы они это сделали, GHC, вероятно, поддерживал бы кортежи произвольного размера.

Как примечание, примечание в Tuple.hs о Мануэле segfault (упоминается в одном из комментариев к этому вопросу) датируется июлем 2001 года, когда оно было проверено на libraries/base/Data/Tuple.hs, так что бы это ни было, у него ничего не было с GHC 6.12.1. Вероятно, эта проблема является причиной того, что Max был установлен на 62 Саймоном, но предел больше не применяется к современным GHC.