16

se si stesse scrivendo un algoritmo di bioinformatica in Haskell, si sarebbe probabilmente utilizzare un tipo di dati algebrico per rappresentare i nucleotidi:In che modo i linguaggi funzionali rappresentano i tipi di dati algebrici in memoria?

data Nucleotide = A | T | C | G 

Faresti simile in standard ML o OCaml, presumo (ho mai usato davvero neanche).

Un valore di tipo Nucleotide può essere contenuto in due bit. Tuttavia, farlo causerebbe tempi di accesso più lenti rispetto a quando si utilizza un byte per il valore Nucleotide, in quanto è necessario selezionare i due bit di interesse utilizzando operatori binari.

Esiste quindi un compromesso intrinseco che il compilatore deve fare tra l'efficienza della memoria e l'efficienza computazionale quando si decide come rappresentare i tipi di dati algebrici. Inoltre, la rappresentazione di tipi di dati algebrici in memoria è resa più complicata dal fatto che il valore può essere di dimensioni variabili:

data Maybe a = Just a | Nothing 

Chiaramente, un valore Maybe a della forma Just a è logicamente maggiore di un valore di modulo Nothing. In un esempio estremo come questo:

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

sicuramente non vorrebbe avere per memorizzare in un Little valore puntatori nulli o valori zero per i cinque valori contenuti in Big valori. Presumo che si utilizzi solo la memoria allocata su heap di dimensioni variabili, con un ID costruttore all'inizio (ad esempio, 0 per Big e 1 per Little). Tuttavia, se si desidera memorizzare i valori Hulk nello stack (una rappresentazione più veloce), è necessario memorizzare la memoria vuota insieme ai valori Little in modo che tutti i valori del tipo Hulk abbiano la stessa dimensione. Un altro compromesso.

Simon Marlow ha risposto alla mia domanda generale relativa a GHC in un previous StackOverflow question. Tuttavia, ho tre domande correlate che rimangono senza risposta:

  • Do ML standard (SML/NJ e MLton) e OCaml utilizzano la stessa tecnica?
  • In tal caso, i compilatori meno comuni di questi linguaggi (o dei loro fratelli) possono sperimentare con altre tecniche?
  • Esiste un modo ragionevolmente semplice (idealmente un flag pragma o opzione) in questi linguaggi per utilizzare una rappresentazione più efficiente della memoria, come la rappresentazione a due bit di Nucleotide? Tale efficienza della memoria è necessaria per molte applicazioni di bioinformatica; se ogni Nucleotide dovesse essere un byte, gli algoritmi di bioinformatica ad alte prestazioni dovrebbero ricorrere a un po 'di manipolazione manuale.
+0

Per haskell, è possibile verificare con le opzioni su GHC come ['-ddump-asm'] (https://gist.github.com/bheklilr/2fdb1b4b640c9fa02e19) o' -ddump-simpl' per vedere come è memorizzato su un livello più basso. Fondamentalmente, per il tuo semplice esempio, ogni tag sembra essere rappresentato come un 'long', ma ci sono alcuni metadati che non sono sicuro di cosa stiano facendo. L'essenza di base è che ogni costruttore viene trasformato in una chiusura, quindi quelli vengono combinati per formare la chiusura del tipo di dati. – bheklilr

+8

Di sicuro non otterrete una risposta (o un rispondente) più definitiva su GHC rispetto a quella di Simon Marlow nella domanda collegata. Poiché questa è l'implementazione standard di Haskell, forse dovresti rivolgere la tua domanda ad un'altra lingua, o forse possiamo chiuderla come duplicato di quella. Cosa ne pensi? –

+0

@DanielWagner: Suppongo che la mia domanda attuale non risponda completamente a questo, come ho chiesto anche a SML e OCaml. Lo ripeterò per chiedere informazioni sulle tecniche generali e sulle implementazioni efficienti in termini di memoria. – Mike

risposta

2

Non c'è una risposta singola: i tipi di dati sono strutture astratte e possono essere implementati in una varietà di modi a discrezione dell'implementatore. In pratica, considerazioni come la compilazione separata tendono a limitare un po 'le cose.

Per il caso specifico dell'imballaggio di un tipo di dati contenente solo costruttori nullari nel minor numero possibile di bit, è possibile procedere definendo le funzioni dal tipo di dati al numero intero piccolo e viceversa. Un tipo integrale nascosto da un tipo astratto (o in Haskell, newtype) sarebbe anche una scelta ragionevole. Imballare e decomprimere i piccoli numeri interi in qualunque forma aggregata con cui stai lavorando sarebbe il tuo lavoro.

A proposito, Real World OCaml ha a very nice chapter sulla rappresentazione dei valori OCaml (sommario: non molto diverso da GHC ai fini di questa domanda).

+0

I valori OCAML non sono molto diversi quando si rimane nel sottoinsieme comune, ma le cosiddette "varianti polimorfiche", che non sono nel sottoinsieme comune, sono degne di nota in sé. –

+0

In effetti, ci sono anche oggetti. Non penso che questi costrutti abbiano molto a che fare con la questione dei PO, quindi mi ripropongo di suggerire che c'è di più nell'argomento. – gsg

Problemi correlati