Data representation synthesis
Data representation synthesis
复制标题
数据表示综合
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Shmuel Sagiv
中科院分区：
文献类型：
--
作者：
Peter Hawkins;A. Aiken;Kathleen Fisher;M. Rinard;Shmuel Sagiv
我们考虑的问题是，如何以声明式的方式指定具有复杂共享的数据结构的组合，并产生可证明是正确的代码。在我们的方法中，抽象数据类型使用关系代数和函数依赖来指定。我们描述了一种分解语言，它允许用户为关系指定不同的具体表示，并展示了对具体表示的操作很好地实现了它们的关系规范。很容易将我们的编译器合成的数据表示合并到现有系统中，导致代码更简单、结构正确，并且在性能上与它所替换的代码相当。
We consider the problem of specifying combinations of data structures with complex sharing in a manner that is both declarative and results in provably correct code. In our approach, abstract data types are specified using relational algebra and functional dependencies. We describe a language of decompositions that permit the user to specify different concrete representations for relations, and show that operations on concrete representations soundly implement their relational specification. It is easy to incorporate data representations synthesized by our compiler into existing systems, leading to code that is simpler, correct by construction, and comparable in performance to the code it replaces.