为什么GHC元组限制为62？

Question

来自Haskell 98的报告:

元组的大小没有上限,但是一些Haskell实现可能会限制元组的大小,并限制与较大元组相关联的实例.但是,每个Haskell实现必须支持最大为15的元组,以及Eq,Ord,Bounded,Read和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

我承认,这是按照哈斯克尔98规范,同时又有大小比62更大的元组很可能是高度不必要的,但我不明白到底为什么,这是因为它是在GHC.

---

总结一下:

• 为什么会出现元组大小限制？
• 为什么尺寸限制在62？

此外:

• 为什么仅从GHC 6.12.2开始就是这种情况？
• 其他突出的Haskell实现是否这样做？他们的理由是什么？

Answer 1

我认为推测重新:评论中这种变化的时机是错误的.首先,据我所知,该限制自6.12.1之前的LONG开始存在.从2002年11月的Trac#98可以看出,在版本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 commit 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元组限制在哪里.但是,实际使用这些预分配数组的函数很乐意按需生成更大的构造函数("专门构建一个"):

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.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顺便说一下,关于Manuel的段错误(在对这个问题的评论之一中引用)的说明可以追溯到2001年7月,当它被检查时libraries/base/Data/Tuple.hs,无论它是什么,它都与GHC 6.12.1无关.这个问题可能是Simon将max设置为62的原因,但这个限制似乎不再适用于现代GHC.