General data description structure

Question

I am wondering if there is any declarative language for an arbitrary description of the format and semantics of a data structure that can be compiled for a specific implementation of this structure in any of the many target languages. That is, something like a generic data definition language , but is intended to describe arbitrary data structures, such as vectors, lists, trees, etc., and the semantics of operations on these structures. I ask because I had an idea for the possible implementation of this concept, and I just wonder if it is worth it and therefore whether it has been done before.

Another, slightly more abstract question: is there any real difference between the normative specification of the data structure (what it does) and its implementation (how it does it)? In particular, should the implementation of the same requirements be divided into different structures?

Answer 1

If you like it, a combination of XML with XSLT can describe the data structure and provide an appropriate definition essentially in any language, if you want. I never tried to prove this formally, but first of all, I assumed that S-expressions are a superset of XML (modulo syntactic differences).

At least theoretically, yes, there are (or at least there may be) differences between describing the data structure and how it does it. For an obvious example, you can describe a general mapping from keys to values ​​that an implementation based on hash tables, skip lists, binary search trees, etc. can use. Basically it is a matter of describing it at a fairly high level of abstraction to allow for differences in implementation. If you include too many requirements (complexity, order, etc.), you can quickly eliminate many implementations.

Answer 2

You may be interested in data / data transfer specification languages ​​such as Google protocol buffers, as well as ASN.1. This is a slightly different bias that you are looking for, but in the same vein.

Both are ways to declare common messages for communication. Message specification buffer protocols are “compiled” into different languages, but the central protocol is consistent. ASN.1 has many different compilation utilities, as well as various protocol representations that are logically compatible with various literal implementations. Look, for example, on XER, PER vs. BER.

I would like a specification language that just focuses on a simple, packaged binary layout versus the logical memory structure. Maybe simple C structures are the simplest common way to express this. I was hoping that ASN.1 would somehow handle this, but with a little look at it, ASN.1 PER is close, but not quite that way.

Edit: Apache Thrift and Capn 'Proto can also be interesting.

Answer 3

There are approaches to such things in dynamic logics that try to capture the semantics of programs. However, the meaning in terms of dynamic logic lies in the premises and postconditions and is agnostic in relation to the actual implementation of the list.

These data structures are intrinsically related to implementation, since the only difference between a linked list and an array is exactly how it is laid out in memory.

To do this, there is a common data definition language — any high-level programming language — C, C ++, java — that indicates this. Any of them is as common as the other, because in this context, any of them can be compiled with the other.