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

Question

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

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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