Универсальный язык описания структуры данных
Я задаюсь вопросом, существует ли там какой-либо декларативный язык для того, чтобы произвольно описать формат и семантику структуры данных, которая может быть скомпилирована в определенную реализацию той структуры в любом ряде выходных языков. Таким образом, что-то как универсальный язык определения данных, но приспособленный к описанию произвольных структур данных, таких как векторы, списки, деревья, и т.д., и семантика операций на тех структурах. Я спрашиваю, потому что у меня была идея для выполнимой реализации этого понятия, и я просто задаюсь вопросом, стоит ли это того, и, следовательно, было ли это сделано прежде.
Другой, немного более абстрактный вопрос: есть ли какая-либо реальная разница между нормативной спецификацией структуры данных (что она делает), и ее реализация (как она делает это)? Строго говоря, должен разделить реализации тех же требований считаться различными структурами?
3 ответа
В динамической логике есть подходы к такого рода вещам, которые пытаются уловить семантику программ. Однако значение с точки зрения динамической логики заключается в терминах предусловий и постусловий и не зависит от фактической реализации списка.
Эти структуры данных по своей сути связаны с реализацией, поскольку единственное различие между связанным списком и массивом заключается в том, как они размещаются в памяти.
Для этого существует общий язык определения данных - любой язык программирования высокого уровня - C, C ++, java - который определяет это. Любой из них является таким же универсальным, как и другой, поскольку в этом контексте любой из них может быть скомпилирован для другого.
Если вы захотите, комбинация XML с XSLT может описать структуру данных и предоставить соответствующее определение практически на любом языке, если вы выберете. Я никогда не пытался доказать это формально, но сначала предполагаю, что S-выражения являются надмножеством XML (по модулю синтаксических различий).
По крайней мере теоретически, да, есть (или, по крайней мере, могут быть) различия между описанием того, что делает структура данных, и тем, как она это делает. В качестве очевидного примера вы можете описать общее сопоставление ключей со значениями, которое может использовать реализацию, основанную на хэш-таблицах, списках пропуска, деревьях двоичного поиска и т. Д. Это в основном вопрос описания его на достаточно высоком уровне абстракции, чтобы допускают различия в реализации. Если вы включите слишком много требований (сложность, порядок и т. Д.), Вы можете довольно быстро исключить многие реализации.
Возможно, вас заинтересуют языки спецификации обмена сообщениями / сериализации данных, такие как протоколы протокольных буферов Google, а также ASN.1. Это немного другой уклон, чем вы ищете, но в том же духе.
Оба являются способами объявления общих сообщений для связи. Спецификации сообщений буферов протокола "компилируются" для разных языков, но центральный протокол согласован. ASN.1 имеет несколько различных утилит компиляции, а также различные представления протоколов, логически согласованные с различными буквальными реализациями. Посмотрите, например, на XER, PER и BER.
Мне бы понравился язык спецификаций, который просто сосредоточился бы на простом упакованном двоичном макете по сравнению с логической структурой памяти. Возможно, простые структуры C - самый простой способ выразить это. Я надеялся, что у ASN.1 есть какой-то способ добраться до этого, но, посмотрев немного, я понял, что ASN.1 PER близок, но не совсем так.
Правка: Apache Thrift и Capn 'Proto также могут быть интересными.