通用数据结构描述语言

如果您喜欢的话,XML和XSLT的组合可以描述一个数据结构,如果您选择的话,还可以提供基本上任何语言的匹配定义。我从未尝试过正式地证明它,但我的第一个猜测是,S表达式是XML的超集(模块语法差异)。

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

您可能对消息规范/数据序列化语言(如Google的协议缓冲区和ASN.1)感兴趣。它的倾斜角度与你想要的稍有不同,但在同一个纹理中。

这两种方法都是为通信声明通用消息的方法。协议将消息规范“编译”到不同的语言,但是中心协议是一致的。ASN.1有多个不同的编译实用程序以及不同的协议表示,它们在逻辑上与不同的文本实现保持一致。例如,看看XER、PER和BER。

我喜欢一种规范语言,它只关注简单的压缩二进制布局和逻辑内存结构。可能普通的C结构是表达这一点的最简单的常用方法。我曾希望ASN.1能有办法做到这一点,但在看了一会儿之后,ASN.1每一个都很接近,但不是很接近。

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

在动态逻辑中,有一些处理这类问题的方法,它们试图捕捉程序的语义。然而,动态逻辑的含义是先决条件和后置条件,对于列表的实际实现不可知。

这些数据结构本质上与实现联系在一起,因为链表和数组之间的唯一区别就是它在内存中的布局。

为此,有一个通用的数据定义语言---任何高级编程语言——C、C++、Java——指定这一点。它们中的任何一个都和另一个一样通用,因为在这个上下文中,它们中的任何一个都可以编译为另一个。

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 ]

    // …

其实现在 Fast Synthesis of Fast Collections 和 Generalized Data Structure Synthesis 作者:卡尔文·隆卡里克、埃米娜·托勒克和迈克尔·D·恩斯特。