为什么 GHC 元组的大小限制为 62？

Question

There is no upper bound on the size of a tuple, but some Haskell implementations may restrict the size of tuples, and limit the instances associated with larger tuples. However, every Haskell implementation must support tuples up to size 15, together with the instances for Eq, Ord, Bounded, Read, and Show. (...)

但是，众所周知，GHC 不支持大小大于 62 的元组。以下是我尝试在 GHCi 中创建大小为 63 的元组时发生的情况：

<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

我认为重新猜测：评论中此更改的时机是错误的。首先，据我所知，这个限制从 6.12.1 之前的 LONG 开始就存在了。在Trac #98 from November 2002中可以看出，在5.02.2版本中，限制是37（而不是62），并且尝试使用更大的元组产生了一条神秘消息：

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

Simon Peyton-Jones 通过让编译器在编译管道中更早地检查大小并生成更好的错误消息（在 Git commit b44c6881 中可见）修复了该错误。在进行此提交时，限制已经从 37 增加到 62（Git 提交 9af77fa4，它将模板 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 元组限制。但是，实际上使用这些预分配数组的函数很乐意根据需要生成更大的构造函数 ("Build one specially"):

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)

这就是编译器在 Simon 添加 5.04 的错误消息之前所做的事情——它专门构建了一个。

不幸的是，当编译器在 ghc/libraries/ghc-prim/GHC/Tuple.hs。根据 The tuple types 标题下 TysWiredIn.hs 中的（稍微过时的）注释，Tuple.hs 中的声明用于构造元组构造函数的信息表和入口代码，即使这些在理论上可以以编程方式动态生成任意大的元组。

那么，这对 modern-day 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)

我怀疑对于前两个程序，编译器优化了对缺少的构造函数的引用，但最终程序需要它。我在 Tuple.hs 中添加了一个 100 元组的声明并重建编译器后，所有三个程序都已编译并且运行正常。

简而言之，在 Tuple.hs 中编译手动构造的元组列表会生成支持最大 62 的元组所需的数据结构，但没有人有足够的动力去 re-implement 这一数据结构生成独立于 Tuple.hs 拐杖。如果他们这样做了，GHC 可能会支持任意大小的元组。

顺便说一句，Tuple.hs 中关于 Manuel 段错误的说明（在对此问题的评论之一中引用）日期为 2001 年 7 月，当时它被签入 libraries/base/Data/Tuple.hs，所以不管它是什么是关于，它与 GHC 6.12.1 无关。这个问题可能是 Simon 将最大值设置为 62 的原因，但该限制似乎不再适用于现代 GHC。

为什么 GHC 元组的大小限制为 62？

Why are GHC tuples limited to size 62?

size

haskell

tuples

compiler-errors

compiler-specific