haskell - promedio - ¿Por qué las tuplas de GHC están limitadas al tamaño 62?

funciones tuplas haskell

Question

Del informe Haskell 98 :

No hay un límite superior en el tamaño de una tupla, pero algunas implementaciones de Haskell pueden restringir el tamaño de las tuplas y limitar las instancias asociadas con tuplas más grandes. Sin embargo, cada implementación de Haskell debe admitir tuplas hasta el tamaño 15, junto con las instancias de Eq, Ord, Bounded, Read y Show. (...)

Sin embargo, es bien sabido que GHC no admite tuplas de tamaño superior a 62. Esto es lo que sucede cuando intento crear una tupla de tamaño 63 en 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

Reconozco que esto está de acuerdo con la especificación Haskell 98, y también que es probable que una tupla de tamaño mayor a 62 sea altamente innecesaria, pero no entiendo por qué exactamente esto es como lo es en GHC.

Resumir:

• ¿Por qué hay un límite de tamaño de la tupla en absoluto?
• ¿Por qué el límite de tamaño es específicamente de 62?

Adicionalmente:

• ¿Por qué este es el caso solo de GHC 6.12.2 y en adelante?
• ¿Otras implementaciones de Haskell prominentes hacen esto? ¿Cuáles son sus razones?

Answer 1

Creo que la especulación es: el momento de este cambio en los comentarios es incorrecto. Primero, por lo que puedo decir, el límite ha existido desde LARGO ANTES de la 6.12.1. Como se puede ver en Trac # 98 a partir de noviembre de 2002 , en la versión 5.02.2, el límite era 37 (en lugar de 62), y tratar de usar una tupla más grande generó un mensaje misterioso:

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

Simon Peyton-Jones corrigió el error al hacer que el compilador verificara el tamaño anteriormente en el proceso de compilación y generara un mensaje de error más agradable (visible en Git commit b44c6881 ). En el momento en que se realizó esta confirmación, el límite ya había aumentado de 37 a 62 (Git commit 9af77fa4, que integraba el trabajo de Haskell de la plantilla en el HEAD), por lo que se lanzó GHC 5.04 con un límite de 62 tuplas y un mejor mensaje de error.

Creo que el error Trac # 98 original apunta a la razón de un límite. En ghc/compiler/prelude/TysWiredIn.hs , se ghc/compiler/prelude/TysWiredIn.hs un conjunto de tipos de tuplas y constructores de datos:

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

donde mAX_TUPLE_SIZE es el límite de 62 tuplas en cuestión. Sin embargo, las funciones que realmente utilizan estos arreglos preasignados están felices de generar constructores más grandes a pedido ("Construya uno especialmente"):

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)

y esto es lo que solía hacer el compilador antes de que Simon agregara el mensaje de error para 5.04: construyó uno especialmente.

Desafortunadamente, esto causó un error (no un error de seguridad, solo un error) más adelante en el proceso de compilación cuando el compilador no pudo encontrar una definición de interfaz para la tupla demasiado grande en la lista dada en ghc/libraries/ghc-prim/GHC/Tuple.hs . Según los comentarios (ligeramente desactualizados) en TysWiredIn.hs bajo el encabezado The tuple types , las declaraciones en Tuple.hs se usan para construir las tablas de información y el código de entrada para los constructores de tuplas, aunque teóricamente podrían generarse de manera programática sobre la marcha Para tuplas arbitrariamente grandes.

Entonces, ¿qué significa esto para la GHC de hoy en día? Bueno, por las mismas razones técnicas descritas anteriormente, aunque el compilador está preparado para generar tuplas arbitrariamente grandes, hay un límite impuesto por el hecho de que requieren declaraciones coincidentes en .../GHC/Tuple.hs .

Realicé algunos experimentos, compilando GHC desde el origen con la verificación de la longitud de la tupla desactivada. El compilador resultante compiló exitosamente y ejecutó el siguiente programa con una tupla de 100:

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

y se imprime "Falso". Funcionó bien cuando lo modifiqué para agarrar el último elemento de la misma tupla:

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

Sin embargo, el programa:

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

falló con un error de vinculación:

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

Sospecho que para los dos primeros programas, el compilador optimizó la referencia al constructor faltante, pero el programa final lo necesitaba. Después de agregar una declaración para un 100-tuple en Tuple.hs y reconstruir el compilador, los tres programas se compilaron y funcionaron bien.

En resumen, la compilación de la lista de tuplas construida manualmente en Tuple.hs genera las estructuras de datos requeridas para admitir tuplas hasta el tamaño 62, y nadie ha estado lo suficientemente motivado para volver a implementar esta generación de estructura de datos para ser independiente de la muleta Tuple.hs . Si lo hicieran, GHC probablemente apoyaría tuplas de tamaño arbitrario.

Como nota aparte, la nota en Tuple.hs sobre la falta de seguridad de Manuel (mencionada en uno de los comentarios a esta pregunta) data de julio de 2001, cuando se registró en las libraries/base/Data/Tuple.hs , así que sea lo que sea, No tuvo nada que ver con GHC 6.12.1. Este problema es probablemente la razón por la que Simon estableció el máximo, pero el límite ya no parece aplicarse con el moderno GHC.