Many applications require specialized data structures not found in the standard libraries, but implementing new data structures by hand is tedious and error-prone. This paper presents a novel approach for synthesizing efficient implementations of complex collection data structures from high-level specifications that describe the desired retrieval operations. Our approach handles a wider range of data structures than previous work, including structures that maintain an order among their elements or have complex retrieval methods. We have prototyped our approach in a data structure synthesizer called Cozy. Three large, real-world case studies compare structures generated by Cozy against handwritten implementations in terms of correctness and performance.
Thu 16 Jun
|13:30 - 14:00|
|14:00 - 14:30|
Ravi ChughUniversity of Chicago, Brian HempelUniversity of Chicago, Mitchell SpradlinUniversity of Chicago, Jacob AlbersUniversity of ChicagoPre-print Media Attached
|14:30 - 15:00|
Calvin LoncaricUniversity of Washington, Emina TorlakUniversity of Washington, Michael D. ErnstUniversity of WashingtonMedia Attached