research-article

On the simplicity of synthesizing linked data structure operations

Authors:

Darya Kurilova,

Derek RaysideAuthors Info & Claims

GPCE '13: Proceedings of the 12th international conference on Generative programming: concepts & experiences

Pages 155 - 158

https://doi.org/10.1145/2517208.2517225

Published: 27 October 2013 Publication History

Get Access

Abstract

We argue that synthesizing operations on recursive linked data structures is not as hard as it appears and is, in fact, within reach of current SAT-based synthesis techniques - with the addition of a simple approach that we describe to decompose the problem into smaller parts. To generate smaller pieces of code, i.e., shorter routines, is obviously easier than large and complex routines, and, also, there is more potential for automating the code synthesis.

In this paper, we present a code generation algorithm for synthesizing operations of linked data structures and, as an example, describe how the proposed algorithm works to synthesize operations of an AVL tree.

References

[1]

G. Adelson-Velskii and E. M. Landis. An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences, 146:263--266, 1962. (Russian) English translation by Myron J. Ricci in Soviet Math. Doklady, 3(2):1259--1263, 1962.

Google Scholar

[2]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press and McGraw-Hill, 2nd edition, 2001.

Digital Library

Google Scholar

[3]

G. Dennis. A Relational Framework for Bounded Program Verification. PhD thesis, MIT, 2009.

Google Scholar

[4]

S. Gulwani. Dimensions in program synthesis. In PPDP. 2010. Invited talk paper.

Digital Library

Google Scholar

[5]

S. Gulwani, S. Jha, A. Tiwari, and R. Venkatesan. Synthesis of loop-free programs. In PLDI, 2011.

Digital Library

Google Scholar

[6]

D. Jackson. Software Abstractions: Logic, Language, and Analysis. The MIT Press, revised edition, 2012.

Digital Library

Google Scholar

[7]

V. Kuncak, M. Mayer, R. Piskac, and P. Suter. Complete functional synthesis. In PLDI, 2010.

Digital Library

Google Scholar

[8]

K. R. M. Leino and A. Milicevic. Program extrapolation with Jennisys. In OOPSLA, 2012.

Digital Library

Google Scholar

[9]

D. Rayside, S. Montaghami, S. Leung, S. Yuen, S. Xu, and D. Jackson. Synthesizing iterators from abstraction functions. In GPCE, 2012.

Digital Library

Google Scholar

[10]

A. Solar-Lezama, L. Tancau, R. Bodik, V. Saraswat, and S. A. Seshia. Combinatorial sketching for finite programs. In ASPLOS. 2006.

Digital Library

Google Scholar

[11]

A. Solar-Lezama, C. G. Jones, and R. Bodik. Sketching concurrent data structures. In PLDI, 2008.

Digital Library

Google Scholar

[12]

S. Srivastava, S. Gulwani, and J. S. Foster. From program verification to program synthesis. In POPL, 2010.

Digital Library

Google Scholar

[13]

K. Yessenov. A light-weight specification language for bounded program verification. Master's thesis, MIT, 2009.

Google Scholar

Cited By

View all

Milicevic ANear JKang EJackson D(2017)Alloy*: a general-purpose higher-order relational constraint solverFormal Methods in System Design10.1007/s10703-016-0267-2Online publication date: 27-Jan-2017
https://doi.org/10.1007/s10703-016-0267-2
Milicevic ANear JKang EJackson DBertolino ACanfora GElbaum S(2015)Alloy*Proceedings of the 37th International Conference on Software Engineering - Volume 110.5555/2818754.2818829(609-619)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2818754.2818829
Milicevic ANear JKang EJackson D(2015)Alloy*: A General-Purpose Higher-Order Relational Constraint Solver2015 IEEE/ACM 37th IEEE International Conference on Software Engineering10.1109/ICSE.2015.77(609-619)Online publication date: May-2015
https://doi.org/10.1109/ICSE.2015.77
Show More Cited By

Index Terms

On the simplicity of synthesizing linked data structure operations
1. Theory of computation
  1. Logic
  2. Semantics and reasoning
    1. Program reasoning

Recommendations

On the simplicity of synthesizing linked data structure operations
GPCE '13

We argue that synthesizing operations on recursive linked data structures is not as hard as it appears and is, in fact, within reach of current SAT-based synthesis techniques - with the addition of a simple approach that we describe to decompose the ...
Synthesizing transformations on hierarchically structured data
PLDI '16

This paper presents a new approach for synthesizing transformations on tree-structured data, such as Unix directories and XML documents. We consider a general abstraction for such data, called hierarchical data trees (HDTs) and present a novel example-...
Synthesizing transformations on hierarchically structured data
PLDI '16: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation

This paper presents a new approach for synthesizing transformations on tree-structured data, such as Unix directories and XML documents. We consider a general abstraction for such data, called hierarchical data trees (HDTs) and present a novel example-...

Comments

Information & Contributors

Information

Published In

GPCE '13: Proceedings of the 12th international conference on Generative programming: concepts & experiences

October 2013

198 pages

ISBN:9781450323734

DOI:10.1145/2517208

General Chair:
Jaakko Järvi
Texas A&M University, USA
,
Program Chair:
Christian Kästner
Carnegie Mellon University, USA

ACM SIGPLAN Notices Volume 49, Issue 3
GPCE '13
March 2014
181 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2637365
Editors:
Mark W. Bailey
Hamilton College, Clinton, NY
,
Jaakko Järvi
Texas A&M University, USA
,
Christian Kästner
Carnegie Mellon University, USA
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GPCE'13

Sponsor:

SIGPLAN

GPCE'13: Generative Programming: Concepts and Experiences

October 27 - 28, 2013

Indiana, Indianapolis, USA

Acceptance Rates

GPCE '13 Paper Acceptance Rate 20 of 59 submissions, 34%;

Overall Acceptance Rate 56 of 180 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
108
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Milicevic ANear JKang EJackson D(2017)Alloy*: a general-purpose higher-order relational constraint solverFormal Methods in System Design10.1007/s10703-016-0267-2Online publication date: 27-Jan-2017
https://doi.org/10.1007/s10703-016-0267-2
Milicevic ANear JKang EJackson DBertolino ACanfora GElbaum S(2015)Alloy*Proceedings of the 37th International Conference on Software Engineering - Volume 110.5555/2818754.2818829(609-619)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2818754.2818829
Milicevic ANear JKang EJackson D(2015)Alloy*: A General-Purpose Higher-Order Relational Constraint Solver2015 IEEE/ACM 37th IEEE International Conference on Software Engineering10.1109/ICSE.2015.77(609-619)Online publication date: May-2015
https://doi.org/10.1109/ICSE.2015.77
Chou SAmarasinghe S(2022)Compilation of dynamic sparse tensor algebraProceedings of the ACM on Programming Languages10.1145/35633386:OOPSLA2(1408-1437)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563338

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On the simplicity of synthesizing linked data structure operations

Synthesizing transformations on hierarchically structured data

Synthesizing transformations on hierarchically structured data