Warum sind GHC-Tupel auf die Größe 62 beschränkt?

Question

Von den 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. (...)

Allerdings ist es allgemein bekannt, dass GHC Tupel einer Größe von mehr als 62 nicht hier unterstützen, was passiert, wenn ich ein Tupel von Größe 63 in GHCi zu erstellen versuchen:

<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 

Ich weiß, dass dies in Übereinstimmung mit der Haskell 98-Spezifikation ist, und auch, dass ein Tupel der Größe größer als 62 ist wahrscheinlich sehr unnötig, aber ich verstehe nicht, warum genau das ist, wie es in GHC ist.

---

Fassen wir zusammen:

• Warum gibt es ein Tupel Größenbeschränkung alle an?
• Warum ist die Größenbeschränkung speziell bei 62?

Zusätzlich:

• Warum ist dies der Fall nur von GHC 6.12.2 und weiter?
• Machen andere bekannte Haskell-Implementierungen das? Was sind ihre Gründe?

Answer 1

Ich denke, die Spekulation re: das Timing dieser Änderung in den Kommentaren ist falsch. Erstens, so weit ich das beurteilen kann, gibt es das Limit seit LONG vor 6.12.1. Wie in TraC#98 from November 2002, in der Version 5.02.2 zu sehen ist, war die Grenze 37 (statt 62) und erzeugt einen größeren Tupel zu verwenden versuchen, eine geheimnisvolle Nachricht: den Fehler behoben

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

Simon Peyton-Jones durch der Compiler überprüft die Größe früher in der Kompilierpipeline und erzeugt eine schönere Fehlermeldung (sichtbar in Git commit b44c6881). Zu der Zeit, als dieser Commit durchgeführt wurde, wurde das Limit bereits von 37 auf 62 erhöht (Git commit 9af77fa4, das Template Haskell in den HEAD integrierte), so dass GHC 5.04 mit einem 62-Tupel-Limit und einer besseren Fehlermeldung veröffentlicht wurde.

Ich glaube, dass der ursprüngliche TraC# 98 Bug auf den Grund für ein Limit hinweist. In ghc/compiler/prelude/TysWiredIn.hs, wird ein Satz von Tupels Typ und Daten Konstruktoren vorbelegt:

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]] 

wo mAX_TUPLE_SIZE ist die 62-Tupel Grenze in Frage. die Funktionen jedoch, die tatsächlich Verwendung diese vorbelegt Arrays sind glücklich größere Konstrukteure bei Bedarf zu erzeugen („Build eine speziell“):

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) 

und das ist, was der Compiler vor Simon zu tun pflegte, um die Fehlermeldung hinzugefügt für 5.04 - es wurde speziell gebaut.

Leider verursachte dies später (wenn es sich um einen segfault, nur einen Fehler handelt) einen Fehler, als der Compiler keine Schnittstellendefinition für das zu große Tupel in der in ghc/libraries/ghc-prim/GHC/Tuple.hs angegebenen Liste finden konnte.Gemäß den (etwas veralteten) Kommentaren in TysWiredIn.hs unter der Überschrift The tuple types werden die Deklarationen in Tuple.hs verwendet, um die Infotabellen und den Eintragscode für Tupelkonstruktoren zu konstruieren, obwohl diese theoretisch programmtechnisch im Hintergrund für beliebig große Tupel erzeugt werden könnten.

Was bedeutet das für den heutigen GHC? Nun, aus den gleichen technischen Gründen, die oben beschrieben wurden, gibt es, obwohl der Compiler bereit ist, beliebig große Tupel zu erzeugen, eine Grenze, die dadurch bedingt ist, dass sie übereinstimmende Deklarationen in .../GHC/Tuple.hs benötigen.

Ich habe ein paar Experimente durchgeführt, kompilieren GHC aus Quelle mit der Tupel-Länge-Prüfung deaktiviert. Der resultierende Compiler kompilierte erfolgreich und führte das folgende Programm mit einem 100-Tupel aus:

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

und es gedruckt "False". Es funktionierte gut, wenn ich es verändert das letzte Element des gleichen Tupels zu greifen:

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

jedoch das Programm:

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

mit einem Gestänge Fehler fehlgeschlagen:

[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) 

I vermute, dass der Compiler für die ersten beiden Programme den Verweis auf den fehlenden Konstruktor wegoptimierte, aber das endgültige Programm benötigte ihn. Nachdem ich eine Deklaration für ein 100-Tupel in Tuple.hs hinzugefügt und den Compiler neu aufgebaut habe, kompilierten alle drei Programme und liefen gut.

Kurz erzeugt die manuell konstruiert Liste von Tupeln in Tuple.hs Kompilieren erforderliche Datenstrukturen Tupeln bis zur Größe 62, und keiner war ausreichend motiviert neu zu implementieren diese Datenstruktur Generation zu sein, unabhängig von der Tuple.hs Krücke zu unterstützen . Wenn dies der Fall wäre, würde GHC wahrscheinlich Tupel beliebiger Größe unterstützen.

Als beiseite, die Notiz in Tuple.hs über Manuels segfault (in einer der Kommentare auf diese Frage verwiesen) stammt aus dem Juli 2001, als es in libraries/base/Data/Tuple.hs geprüft wurde, so was auch immer es ging, es hatte nichts mit dem zu tun GHC 6.12.1. Dieses Problem ist wahrscheinlich der Grund dafür, dass der Max von Simon auf 62 gesetzt wurde, aber das Limit scheint bei modernen GHC nicht mehr zu gelten.