Dati generici Struttura Description Language

Question

mi chiedo se esista un linguaggio dichiarativo per arbitrariamente descrive il formato e la semantica di una struttura di dati, che può essere compilato a una specifica implementazione di quella struttura in qualsiasi di una serie di lingue di destinazione. Cioè, qualcosa come un Data Definition Language ma orientata verso che descrive le strutture di dati arbitrari, quali vettori, liste, alberi, ecc, e la semantica delle operazioni su tali strutture. Lo chiedo perché ho avuto un'idea per un'implementazione fattibile di questo concetto, e mi chiedo solo se ne vale la pena, e, di conseguenza, se è stato fatto prima.

Un altro, domanda un po 'più astratto: esiste una reale differenza tra la specifica normativa di una struttura dati (cosa fa) e la sua attuazione (come lo fa)? Più in particolare, dovrebbe separare implementazioni dello stesso requisiti essere considerato diverso Strutture

Answer 1

accogliente è “uno strumento che sintetizza le implementazioni struttura dei dati dalle specifiche altissimo livello” e sembra essere essenzialmente la lingua mi è stato effettivamente cercando (o considerare la scrittura), quando ho fatto questa domanda.

E 'possibile generare automaticamente un'implementazione (in Java o C ++, nel momento in cui scriviamo) da una specifica struttura di dati scritti nel suo linguaggio proprietario. Una specifica descrive l' stato astratto , operazioni di aggiornamento e operazioni di query di una struttura di dati, così come invarianti che deve essere mantenuta e assunzioni che può essere utilizzato dal risolutore per ottimizzare l'implementazione. Ad esempio, ecco una specifica parziale di una struttura dati grafico:

Graph:
    handletype Node = { id : Int }
    handletype Edge = { src : Int, dst : Int }

    state nodes : Bag<Node>
    state edges : Bag<Edge>

    // Invariant: disallow self-edges.
    invariant (sum [ 1 | e <- edges, e.val.src == e.val.dst ]) == 0;

    op addNode(n : Node)
        nodes.add(n);

    op addEdge(e : Edge)
        assume e.val.src != e.val.dst;
        edges.add(e);

    query out_degree(nodeId : Int)
        sum [ 1 | e <- edges, e.val.src == nodeId ]

    // …

La sua attuazione è descritta in rapida sintesi di Fast collezioni e Generalized dati Struttura Sintesi di Calvin Loncaric, Emina Torlak, e Michael D. Ernst.

Answer 2

Se ti sei sentito come se, una combinazione di XML con XSLT poteva descrivere una struttura di dati, e di fornire una definizione corrispondente in sostanza, qualsiasi lingua se la vostra scelta. Non ho mai provato a dimostrarlo formalmente, ma la mia prima ipotesi è che S-espressioni sono un superset di XML (modulo differenze sintattiche).

Almeno in teoria, sì, ci sono (o almeno può essere) le differenze tra una descrizione di ciò che una struttura di dati fa, e come lo fa. Per un esempio evidente, si potrebbe descrivere una mappatura generica da chiavi ai valori, che potrebbe utilizzare un'implementazione basata su tabelle hash, saltare liste, alberi binari di ricerca, ecc E 'soprattutto una questione di descriverla ad un livello abbastanza alto di astrazione per consentire differenze nell'attuazione. Se si include troppi requisiti (complessità, ordini, ecc) si può abbastanza rapidamente escludere molte implementazioni.

Answer 3

Si può essere interessati a messaggistica lingue di serializzazione specifica / dati come buffer di protocollo di Google così come ASN.1. Si tratta di un taglio leggermente diverso rispetto che stai cercando, ma nella stessa vena.

Entrambi sono modi per dichiarare messaggi generici per le comunicazioni. buffer protocollo messaggio spec "compilazione" per lingue diverse, ma il protocollo centrale è coerente. ASN.1 ha più utilità di compilazione differenti così come diverse rappresentazioni di protocollo che soggiornano logicamente coerente con diverse implementazioni letterali. Guardate XER, PER vs. BER per esempio.

mi piacerebbe un linguaggio di specifica che concentrarsi solo su semplice imballato il layout binario contro una struttura di memoria logica. Può essere che le strutture C semplici sono i più semplici modo comune di esprimere questo. Avevo sperato ASN.1 aveva un modo di arrivare a questo, ma dopo aver guardato per un po ', ASN.1 PER è vicino, ma non del tutto esso.

Modifica: Apache Thrift e Capn' Proto possono anche essere interessante.

Answer 4

Ci sono approcci per questo genere di cose in logiche dinamiche, che tentano di catturare la semantica di programmi. Tuttavia, il significato in termini di logica dinamica è in termini di precondizioni e postcondizioni ed è agnostico per quanto riguarda l'effettiva attuazione della lista.

Queste strutture di dati sono intrinsecamente legata alla attuazione, come unica differenza tra una lista collegata e la matrice è specifico come è strutturato in memoria.

Per questo, v'è un linguaggio generica definizione dei dati --- qualsiasi linguaggio di programmazione di alto livello - C, C ++, Java - che specifica questo. Qualcuno di loro è come generico come l'altro, dal momento che in questo contesto qualsiasi di loro potrebbe essere compilato per l'altro.