Thu 16 Jun 2016 14:30 - 15:00 at Grand Ballroom Santa Ynez - Synthesis I Chair(s): Eran Yahav

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.