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

Question

Из отчета на 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? Каковы их причины?

Answer 1

Я думаю, что спекуляция: время этого изменения в комментариях неверно. Во-первых, насколько я могу судить, предел существует с LONG до 6.12.1. Как видно из TraC#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 кортежа и улучшенным сообщением об ошибке.

Я считаю, что оригинальная ошибка TraC#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 кортежа. Однако функции, которые на самом деле используют эти предварительно выделенные массивы, с удовольствием генерируют большие конструкторы по требованию ("Создайте один специально"):

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

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

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 Сегфоут Мануэля (упоминается в одном из комментариев к этому вопросу) датируется июлем 2001 года, когда он был зарегистрирован libraries/base/Data/Tuple.hsТак что, как бы то ни было, это не имело ничего общего с GHC 6.12.1. Эта проблема, вероятно, является причиной того, что Симон установил максимальное значение 62, но, похоже, ограничение больше не применимо к современному GHC.