An introduction to data representation synthesis
Authors:
- Martin RinardMRMartin Rinard
Open Access
- 1 December 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 55 (12) , 91-99
Abstract
We consider the problem of specifying combinations of data structures with complex sharing in a manner that is 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 permits the user to specify different concrete representations for relations, and show that operations on concrete representations soundly implement their relational specification. We also describe an auto-tuner that automatically identifies the best decomposition for a particular workload. 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.Keywords
Funding Information
- Division of Computer and Network Systems (CCF-0702681CNS-050955)
- Division of Computing and Communication Foundations (CCF-0702681CNS-050955)
This publication has 15 references indexed in Scilit:
- Data representation synthesis2011
- Shape Analysis of Low-Level C with Overlapping Structures2010
- jStar2008
- First-Class Relationships in an Object-Oriented LanguageLecture Notes in Computer Science, 2005
- Generalized Typestate Checking for Data Structure Consistency2005
- Role analysis2002
- Design wizards and visual programming environments for GenVoca generatorsIEEE Transactions on Software Engineering, 2000
- P2: A Lightweight DBMS GeneratorJournal of Intelligent Information Systems, 1997
- Automating relational operations on data structuresIEEE Software, 1993
- Programming by Refinement, as Exemplified by the SETL Representation SublanguageACM Transactions on Programming Languages and Systems, 1979