通用数据结构描述语言

Question

我想知道是否存在任何声明性语言用于任意描述数据结构的格式和语义，可以将其编译为任何一组目标语言中该结构的特定实现。也就是说，类似通用的数据定义语言，但旨在描述任意数据结构，例如向量，列表、树等，以及这些结构上的操作的语义。我问这个问题是因为我有一个可行的实现这个概念的想法，我只是想知道它是否值得，以及因此，以前是否已经做过。

另一个稍微更抽象的问题：数据结构的规范规范（它做什么）和它的实现（它如何做）之间是否有任何真正的区别？更具体地说，相同需求的单独实现是否应该被视为不同的结构？

Answer 1

您可能对消息传递规范/数据序列化语言感兴趣，例如 Google 的 Protocol Buffers 以及 ASN.1。这与您正在寻找的倾斜略有不同，但本质相同。

两者都是声明通信通用消息的方法。协议缓冲区消息规范“编译”为不同的语言，但中心协议是一致的。 ASN.1 具有多个不同的编译实用程序以及不同的协议表示，与不同的文字实现保持逻辑一致。例如，看看 XER、PER 与 BER。

我喜欢一种规范语言，它只专注于针对逻辑内存结构的简单打包二进制布局。简单的 C 结构可能是表达这一点的最简单的常用方式。我曾希望 ASN.1 能够通过某种方式实现这一目标，但经过一番研究后，ASN.1 PER 很接近，但又不完全是这样。

编辑： Apache Thrift 和 Capn' Proto 也可能很有趣。

Answer 2

如果您愿意，XML 与 XSLT 的组合可以描述数据结构，并以您选择的任何语言提供匹配的定义。我从未试图正式证明这一点，但我的第一个猜测是 S 表达式是 XML 的超集（模语法差异）。

至少在理论上，对数据结构的作用及其实现方式的描述之间确实存在（或至少可能存在）差异。举一个明显的例子，您可以描述从键到值的通用映射，它可以使用基于哈希表、跳跃列表、二叉搜索树等的实现。这主要是在足够高的抽象级别上描述它的问题允许实施中的差异。如果您包含太多要求（复杂性、顺序等），您可以很快排除许多实现。

Answer 3

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 ]

    // …

其实现在 快速集合的快速合成中描述 和广义数据结构综合作者：卡尔文·隆卡里克、埃米娜·托拉克和迈克尔·D·恩斯特。

Answer 4

动态逻辑中有一些解决此类问题的方法，它们试图捕获程序的语义。然而，动态逻辑的含义是先决条件和后置条件，并且与列表的实际实现无关。

这些数据结构本质上与实现相关，因为链表和数组之间的唯一区别在于它在内存中的布局方式。

为此，有一种通用数据定义语言——任何高级编程语言——C、C++、java——来指定这一点。它们中的任何一个都与另一个一样通用，因为在这种情况下，它们中的任何一个都可以编译为另一个。