Thumbnail
Access Restriction
Subscribed

Author Rinard, Martin ♦ Sagiv, Mooly ♦ Fisher, Kathleen ♦ Hawkins, Peter ♦ Aiken, Alex
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
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.
Description Affiliation: Tel-Aviv University (Sagiv, Mooly) || Stanford University (Hawkins, Peter; Aiken, Alex) || MIT (Rinard, Martin) || Tufts University (Fisher, Kathleen)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 55
Issue Number 12
Page Count 9
Starting Page 91
Ending Page 99


Open content in new tab

   Open content in new tab
Source: ACM Digital Library