haskell - puros - programacion funcional vs orientada a objetos

¿Cómo los lenguajes funcionales representan tipos de datos algebraicos en la memoria?

Question

Si estuvieras escribiendo un algoritmo bioinformático en Haskell, probablemente usarías un tipo de datos algebraicos para representar los nucleótidos:

data Nucleotide = A | T | C | G

Haría lo mismo en Standard ML u OCaml, supongo (nunca he usado realmente ninguno).

Un valor de tipo Nucleotide puede estar claramente contenido en dos bits. Sin embargo, al hacerlo, los tiempos de acceso serían más lentos que si usara un byte por valor de Nucleotide , ya que necesitaría seleccionar los dos bits de interés mediante operadores binarios.

Por lo tanto, existe una compensación inherente que el compilador debe establecer entre la eficiencia de la memoria y la eficiencia computacional cuando se decide cómo representar los tipos de datos algebraicos. Además, la representación de tipos de datos algebraicos en la memoria se complica debido al hecho de que el valor puede ser de tamaño variable:

data Maybe a = Just a | Nothing

Claramente, a Maybe a valor de la forma Just a es lógicamente más grande que un valor de la forma Nothing . En un ejemplo extremo como este:

data Hulk a b c d e = Big a b c d e | Little

definitivamente no querrá tener que almacenar en un valor nulo los punteros nulos o valores cero para los cinco valores contenidos en los valores Big . Supongo que usará la memoria asignada en el montón de tamaño variable, con un ID de constructor al principio (por ejemplo, 0 para Big y 1 para Little ). Sin embargo, si quisiera almacenar los valores de Hulk en la pila (una representación más rápida), tendría que almacenar la memoria en blanco junto con los valores Little para que todos los valores del tipo Hulk sean del mismo tamaño. Otra compensación.

Simon Marlow respondió mi pregunta general con respecto a GHC en una pregunta anterior de StackOverflow . Sin embargo, tengo tres preguntas relacionadas que siguen sin respuesta:

• ¿La ML estándar (SML / NJ y MLton) y OCaml usan la misma técnica?
• Si es así, ¿algún compilador menos común de estos idiomas (o sus hermanos) experimenta con otras técnicas?
• ¿Hay una manera razonablemente fácil (idealmente, un indicador de pragma u opción) en estos lenguajes para usar una representación más eficiente de la memoria, como la representación de dos bits de Nucleotide ? Tal eficiencia de memoria es necesaria para muchas aplicaciones bioinformáticas; si cada Nucleotide tuviera que ser de un byte, los algoritmos bioinformáticos de alto rendimiento tendrían que recurrir a manipulaciones manuales de bits.

Answer 1

No hay una respuesta única: los tipos de datos son estructuras abstractas y pueden implementarse de diversas maneras a discreción del implementador. En la práctica, consideraciones como la compilación separada tienden a restringir las cosas un tanto.

Para el caso específico de empaquetar un tipo de datos que contenga solo constructores nulary en el menor número de bits posible, puede continuar definiendo funciones de tipo de datos a entero pequeño y viceversa. Un tipo integral oculto por un tipo abstracto (o en Haskell, newtype ) también sería una elección razonable. Empacar y desempaquetar los enteros pequeños en cualquier forma global con la que esté trabajando sería su trabajo.

Por cierto, Real World OCaml tiene un capítulo muy bueno sobre la representación de los valores OCaml (resumen aproximado: no muy diferente de GHC para los propósitos de esta pregunta).