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

Question

Мне интересно, существует ли любой декларативный язык для произвольно описания формата и семантики структуры данных, которые могут быть скомпилированы на конкретную реализацию этой структуры в любом из наборов целевых языков. То есть что-то вроде общего Язык определения данных Но ориентирован на описание произвольных структур данных, таких как векторы, списки, деревья и т. Д., И семантика операций на этих структурах. Я спрашиваю, потому что у меня была идея для осуществимой реализации этой концепции, и мне просто интересно, стоит ли оно того, и, следовательно, было ли это сделано раньше.

Другой, немного более абстрактный вопрос: есть ли реальная разница между нормативной спецификацией структуры данных (что она делает) и его реализация (как это делает)? Более конкретно, должен отделить реализации того же самого требования считаться разным структуры?

Answer 1

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

Он может автоматически генерировать реализацию (в 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 ]

    // …

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

Answer 2

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

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

Answer 3

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

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

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

Редактировать: Apache Rebse а также Capn 'Proto. Также может быть интересно.

Answer 4

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

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

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