Общая структура данных Язык описания

Если хотите, комбинация XML и XSLT может описывать структуру данных и предоставлять соответствующее определение практически на любом языке по вашему выбору. Я никогда не пытался доказать это формально, но мое первое предположение будет заключаться в том, что S-выражения являются надмножеством XML (по модулю синтаксических различий).

По крайней мере теоретически да, есть (или, по крайней мере, могут быть) различия между описанием того, что делает структура данных, и тем, как она это делает. В качестве очевидного примера вы могли бы описать общее отображение ключей в значения, которое могло бы использовать реализацию, основанную на хеш-таблицах, списках пропуска, двоичных деревьях поиска и т. д. В основном это вопрос описания на достаточно высоком уровне абстракции, чтобы допускать различия в реализации. Если вы включите слишком много требований (сложность, порядок и т. д.), вы можете довольно быстро исключить множество реализаций.

Вас могут заинтересовать языки спецификации обмена сообщениями/сериализации данных, такие как протокольные буферы Google, а также ASN.1. Это немного другой наклон, чем вы ищете, но в том же духе.

Оба являются способами объявления общих сообщений для связи. Протокол буферизует спецификации сообщений, которые "компилируются" для разных языков, но центральный протокол непротиворечив. ASN.1 имеет несколько различных утилит компиляции, а также различные представления протокола, которые остаются логически согласованными с различными буквальными реализациями. Посмотрите, например, на XER, PER и BER.

Мне бы хотелось, чтобы язык спецификаций сосредоточился на простом упакованном двоичном макете в сравнении с логической структурой памяти. Возможно, простые структуры C — самый простой способ выразить это. Я надеялся, что у ASN.1 есть какой-то способ добраться до этого, но, немного посмотрев на него, ASN.1 PER близок, но не совсем.

Изменить: Apache Thrift и Capn' Proto также может быть интересным.

В динамической логике есть подходы к такого рода вещам, которые пытаются уловить семантику программ. Однако значение с точки зрения динамической логики связано с предусловиями и постусловиями и не зависит от фактической реализации списка.

Эти структуры данных по своей сути связаны с реализацией, поскольку единственная разница между связанным списком и массивом заключается в том, как он размещается в памяти.

Для этого существует общий язык определения данных — любой язык программирования высокого уровня — C, C++, java — который определяет это. Любой из них является таким же общим, как и другой, поскольку в этом контексте любой из них может быть скомпилирован в другой.

Cozy — это «инструмент, который синтезирует реализации структур данных из спецификаций очень высокого уровня» и, по сути, является язык, который я на самом деле искал (или собирался написать), когда задавал этот вопрос.

Он может автоматически генерировать реализацию (на момент написания этой статьи на Java или C++) из спецификации структуры данных, написанной на собственном языке. Спецификация описывает абстрактное состояние, операции обновления и операции запроса структуры данных, а также инварианты, которые необходимо поддерживать, и предположения, которые может использоваться решателем для оптимизации реализации. Например, вот частичная спецификация для структуры данных графа:

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 ]

    // …

Его реализация описана в Быстрый синтез быстрых коллекций и Синтез обобщенной структуры данных Кальвина Лонкарика, Эмины Торлак и Майкла Д. Эрнста.