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

Question

来自Haskell 98 report :

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 之前。可以在 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 提交 b44c6881 中可见)来修复错误。在进行此提交时，限制已经从 37 增加到 62(Git 提交 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)

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

不幸的是，当编译器在 ghc/libraries/ghc-prim/GHC/Tuple.hs 中给出的列表中找不到太大元组的接口(interface)定义时，这会在编译过程的后期导致错误(不是段错误，只是错误)。 .根据 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)

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

简而言之，编译 Tuple.hs 中手动构建的元组列表生成所需的数据结构以支持最大为 62 的元组，并且没有人有足够的动力重新实现此数据结构生成以独立于 Tuple.hs拐杖。如果他们这样做了，GHC 可能会支持任意大小的元组。

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