Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3472749.3474740acmconferencesArticle/Chapter ViewAbstractPublication PagesuistConference Proceedingsconference-collections
research-article

Assuage: Assembly Synthesis Using A Guided Exploration

Published: 12 October 2021 Publication History

Abstract

Assembly programming is challenging, even for experts. Program synthesis, as an alternative to manual implementation, has the potential to enable both expert and non-expert users to generate programs in an automated fashion. However, current tools and techniques are unable to synthesize assembly programs larger than a few instructions. We present Assuage : ASsembly Synthesis Using A Guided Exploration, which is a parallel interactive assembly synthesizer that engages the user as an active collaborator, enabling synthesis to scale beyond current limits. Using Assuage, users can provide two types of semantically meaningful hints that expedite synthesis and allow for exploration of multiple possibilities simultaneously. Assuage exposes information about the underlying synthesis process using multiple representations to help users guide synthesis. We conducted a within-subjects study with twenty-one participants working on assembly programming tasks. With Assuage, participants with a wide range of expertise were able to achieve significantly higher success rates, perceived less subjective workload, and preferred the usefulness and usability of Assuage over a state of the art synthesis tool.

Supplementary Material

VTT File (p134-talk.vtt)
VTT File (p134-video_figure.vtt)
VTT File (p134-video_preview.vtt)
MP4 File (p134-talk.mp4)
Talk video and captions
MP4 File (p134-video_figure.mp4)
Video figure and captions
MP4 File (p134-video_preview.mp4)
Video preview and captions

References

[1]
Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo Martin, Mukund Raghothaman, Sanjit Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2013. Syntax-guided synthesis, In 2013 Formal Methods in Computer-Aided Design. 2013 Formal Methods in Computer-Aided Design, FMCAD 2013, 1–17. https://doi.org/10.1109/FMCAD.2013.6679385
[2]
Shaon Barman, Rastislav Bodik, Satish Chandra, Emina Torlak, Arka Bhattacharya, and David Culler. 2015. Toward Tool Support for Interactive Synthesis. In 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!)(Pittsburgh, PA, USA) (Onward! 2015). Association for Computing Machinery, New York, NY, USA, 121–136. https://doi.org/10.1145/2814228.2814235
[3]
David Basin, Yves Deville, Pierre Flener, Andreas Hamfelt, and Jørgen Fischer Nilsson. 2004. Synthesis of Programs in Computational Logic. Springer Berlin Heidelberg, Berlin, Heidelberg, 30–65. https://doi.org/10.1007/978-3-540-25951-0_2
[4]
Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania. 2009. The Multikernel: A New OS Architecture for Scalable Multicore Systems. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (Big Sky, Montana, USA) (SOSP ’09). Association for Computing Machinery, New York, NY, USA, 29–44. https://doi.org/10.1145/1629575.1629579
[5]
James Bornholt and Emina Torlak. 2018. Finding Code That Explodes under Symbolic Evaluation. Proc. ACM Program. Lang. 2, OOPSLA, Article 149 (Oct. 2018), 26 pages. https://doi.org/10.1145/3276519
[6]
J. Richard Buchi and Lawrence H. Landweber. 1969. Solving Sequential Conditions by Finite-State Strategies. Trans. Amer. Math. Soc. 138 (1969), 295–311. http://www.jstor.org/stable/1994916
[7]
Sarah E. Chasins, Maria Mueller, and Rastislav Bodik. 2018. Rousillon: Scraping Distributed Hierarchical Web Data. In Proceedings of the 31st Annual ACM Symposium on User Interface Software and Technology (Berlin, Germany) (UIST ’18). Association for Computing Machinery, New York, NY, USA, 963–975. https://doi.org/10.1145/3242587.3242661
[8]
Allen Cypher. 1995. EAGER: PROGRAMMING REPETITIVE TASKS BY EXAMPLE. In Readings in Human–Computer Interaction, RONALD M. BAECKER, JONATHAN GRUDIN, WILLIAM A.S. BUXTON, and SAUL GREENBERG (Eds.). Morgan Kaufmann, 804–810. https://doi.org/10.1016/B978-0-08-051574-8.50083-2
[9]
Cristina David and Daniel Kroening. 2017. Program synthesis: challenges and opportunities. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 375, 2104 (2017), 20150403.
[10]
Ian Drosos, Titus Barik, Philip J. Guo, Robert DeLine, and Sumit Gulwani. 2020. Wrex: A Unified Programming-by-Example Interaction for Synthesizing Readable Code for Data Scientists. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems (Honolulu, HI, USA) (CHI ’20). Association for Computing Machinery, New York, NY, USA, 1–12. https://doi.org/10.1145/3313831.3376442
[11]
R. A. Fisher. 1922. On the Interpretation of χ2 from Contingency Tables, and the Calculation of P. Journal of the Royal Statistical Society 85, 1 (1922), 87–94. http://www.jstor.org/stable/2340521
[12]
Pierre Flener and Derek Partridge. 2001. Inductive Programming. Automated Software Engg. 8, 2 (April 2001), 131–137. https://doi.org/10.1023/A:1008797606116
[13]
Joel Galenson, Philip Reames, Rastislav Bodik, Björn Hartmann, and Koushik Sen. 2014. CodeHint: Dynamic and Interactive Synthesis of Code Snippets. In Proceedings of the 36th International Conference on Software Engineering (Hyderabad, India) (ICSE 2014). Association for Computing Machinery, New York, NY, USA, 653–663. https://doi.org/10.1145/2568225.2568250
[14]
G Mark Grimes, Ryan M Schuetzler, and Justin Scott Giboney. 2021. Mental models and expectation violations in conversational AI interactions. Decision Support Systems(2021), 113515.
[15]
Sumit Gulwani. 2011. Automating String Processing in Spreadsheets Using Input-Output Examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages(Austin, Texas, USA) (POPL ’11). Association for Computing Machinery, New York, NY, USA, 317–330. https://doi.org/10.1145/1926385.1926423
[16]
S. Gulwani. 2012. Synthesis from Examples: Interaction Models and Algorithms. In 2012 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. 8–14. https://doi.org/10.1109/SYNASC.2012.69
[17]
Sumit Gulwani, William R. Harris, and Rishabh Singh. 2012. Spreadsheet Data Manipulation Using Examples. Commun. ACM 55, 8 (Aug. 2012), 97–105. https://doi.org/10.1145/2240236.2240260
[18]
Sumit Gulwani, José Hernández-Orallo, Emanuel Kitzelmann, Stephen H. Muggleton, Ute Schmid, and Benjamin Zorn. 2015. Inductive Programming Meets the Real World. Commun. ACM 58, 11 (Oct. 2015), 90–99. https://doi.org/10.1145/2736282
[19]
Sumit Gulwani, Susmit Jha, Ashish Tiwari, and Ramarathnam Venkatesan. 2011. Synthesis of Loop-Free Programs. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (San Jose). Association for Computing Machinery, New York, NY, USA, 62–73. https://doi.org/10.1145/1993498.1993506
[20]
Sumit Gulwani, Alex Polozov, and Rishabh Singh. 2017. Program Synthesis. Vol. 4. NOW. 1–119 pages.
[21]
Tihomir Gvero and Viktor Kuncak. 2015. Interactive Synthesis Using Free-Form Queries. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, Vol. 2. 689–692.
[22]
Sandra G. Hart and Lowell E. Staveland. 1988. Development of NASA-TLX (Task Load Index): Results of Empirical and Theoretical Research. In Human Mental Workload, Peter A. Hancock and Najmedin Meshkati (Eds.). Advances in Psychology, Vol. 52. North-Holland, 139–183. https://doi.org/10.1016/S0166-4115(08)62386-9
[23]
John L. Hennessy and David A. Patterson. 2019. A New Golden Age for Computer Architecture. Commun. ACM 62, 2 (Jan. 2019), 48–60. https://doi.org/10.1145/3282307
[24]
David A. Holland. 2020. Toward Automatic Operating System Ports via Code Generation and Synthesis. Ph.D. Dissertation. Cambridge, MA, USA. Advisor(s) Margo I. Seltzer and Stephen Chong.
[25]
David A. Holland, Jingmei Hu, Ming Kawaguchi, Eric Lu, Stephen Chong, and Margo I. Seltzer. 2020. Aquarium: Cassiopea and Alewife Languages. arxiv:1908.00093 [cs.PL]
[26]
David A. Holland, Ada T. Lim, and Margo I. Seltzer. 2002. A New Instructional Operating System. In Proceedings of the 33rd SIGCSE Technical Symposium on Computer Science Education (Cincinnati, Kentucky) (SIGCSE ’02). Association for Computing Machinery, New York, NY, USA, 111–115. https://doi.org/10.1145/563340.563383
[27]
Eric Horvitz. 1999. Principles of Mixed-Initiative User Interfaces. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (Pittsburgh, Pennsylvania, USA) (CHI ’99). Association for Computing Machinery, New York, NY, USA, 159–166. https://doi.org/10.1145/302979.303030
[28]
Jingmei Hu, Eric Lu, David A. Holland, Ming Kawaguchi, Stephen Chong, and Margo I. Seltzer. 2019. Trials and Tribulations in Synthesizing Operating Systems. In Proceedings of the 10th Workshop on Programming Languages and Operating Systems (Huntsville, ON, Canada) (PLOS’19). Association for Computing Machinery, New York, NY, USA, 67–73. https://doi.org/10.1145/3365137.3365401
[29]
Jinseong Jeon, Xiaokang Qiu, Armando Solar-Lezama, and Jeffrey S. Foster. 2015. Adaptive Concretization for Parallel Program Synthesis. In Computer Aided Verification, Daniel Kroening and Corina S. Păsăreanu (Eds.). Springer International Publishing, Cham, 377–394.
[30]
Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. 2010. Oracle-Guided Component-Based Program Synthesis. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1 (Cape Town, South Africa) (ICSE ’10). Association for Computing Machinery, New York, NY, USA, 215–224. https://doi.org/10.1145/1806799.1806833
[31]
Vu Le and Sumit Gulwani. 2014. FlashExtract: A Framework for Data Extraction by Examples. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (Edinburgh, United Kingdom) (PLDI ’14). Association for Computing Machinery, New York, NY, USA, 542–553. https://doi.org/10.1145/2594291.2594333
[32]
Vu Le, Daniel Perelman, Oleksandr Polozov, Mohammad Raza, Abhishek Udupa, and Sumit Gulwani. 2017. Interactive Program Synthesis. arxiv:1703.03539 [cs.PL]
[33]
Tak Yeon Lee, Casey Dugan, and Benjamin B. Bederson. 2017. Towards Understanding Human Mistakes of Programming by Example: An Online User Study. In Proceedings of the 22nd International Conference on Intelligent User Interfaces(Limassol, Cyprus) (IUI ’17). Association for Computing Machinery, New York, NY, USA, 257–261. https://doi.org/10.1145/3025171.3025203
[34]
Zohar Manna and Richard Waldinger. 1980. A Deductive Approach to Program Synthesis. ACM Trans. Program. Lang. Syst. 2, 1 (Jan. 1980), 90–121. https://doi.org/10.1145/357084.357090
[35]
Mikaël Mayer, Gustavo Soares, Maxim Grechkin, Vu Le, Mark Marron, Alex Polozov, Rishabh Singh, Ben Zorn, and Sumit Gulwani. 2015. User Interaction Models for Disambiguation in Programming by Example. In 28th ACM User Interface Software and Technology Symposium (UIST 2015) (28th acm user interface software and technology symposium (uist 2015) ed.). ACM – Association for Computing Machinery.
[36]
Brad Myers and Richard McDaniel. 2001. Demonstrational interfaces: sometimes you need a little intelligence, sometimes you need a lot. (01 2001), 45–60.
[37]
Brad A. Myers. 1990. Creating User Interfaces Using Programming by Example, Visual Programming, and Constraints. ACM Trans. Program. Lang. Syst. 12, 2 (April 1990), 143–177. https://doi.org/10.1145/78942.78943
[38]
Brad A. Myers. 1998. Scripting Graphical Applications by Demonstration. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (Los Angeles, California, USA) (CHI ’98). ACM Press/Addison-Wesley Publishing Co., USA, 534–541. https://doi.org/10.1145/274644.274716
[39]
Brad A. Myers and Richard McDaniel. 2001. Demonstrational Interfaces: Sometimes You Need a Little Intelligence, Sometimes You Need a Lot. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 45–60.
[40]
D. Partridge. 1997. The case for inductive programming. Computer 30, 1 (1997), 36–41. https://doi.org/10.1109/2.562924
[41]
Hila Peleg, Sharon Shoham, and Eran Yahav. 2018. Programming Not Only by Example. In Proceedings of the 40th International Conference on Software Engineering (Gothenburg, Sweden) (ICSE ’18). Association for Computing Machinery, New York, NY, USA, 1114–1124. https://doi.org/10.1145/3180155.3180189
[42]
Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama. 2016. Program Synthesis from Polymorphic Refinement Types. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (Santa Barbara, CA, USA) (PLDI ’16). Association for Computing Machinery, New York, NY, USA, 522–538. https://doi.org/10.1145/2908080.2908093
[43]
C. Rich and R. C. Waters. 1988. The Programmer’s Apprentice: a research overview. Computer 21, 11 (1988), 10–25. https://doi.org/10.1109/2.86782
[44]
Leonid Ryzhyk, Adam Walker, John Keys, Alexander Legg, Arun Raghunath, Michael Stumm, and Mona Vij. 2014. User-Guided Device Driver Synthesis. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (Broomfield, CO) (OSDI’14). USENIX Association, USA, 661–676.
[45]
Mark Santolucito, Drew Goldman, Allyson Weseley, and Ruzica Piskac. 2019. Programming by Example: Efficient, but Not ”Helpful”. In 9th Workshop on Evaluation and Usability of Programming Languages and Tools (PLATEAU 2018)(OpenAccess Series in Informatics (OASIcs), Vol. 67), Titus Barik, Joshua Sunshine, and Sarah Chasins(Eds.). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 3:1–3:10. https://doi.org/10.4230/OASIcs.PLATEAU.2018.3
[46]
Armando Solar-Lezama, Christopher Grant Jones, and Rastislav Bodik. 2008. Sketching Concurrent Data Structures. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (Tucson, AZ, USA) (PLDI ’08). Association for Computing Machinery, New York, NY, USA, 136–148. https://doi.org/10.1145/1375581.1375599
[47]
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. 2006. Combinatorial Sketching for Finite Programs. SIGARCH Comput. Archit. News 34, 5 (Oct. 2006), 404–415. https://doi.org/10.1145/1168919.1168907
[48]
Venkatesh Srinivasan and Thomas Reps. 2015. Synthesis of Machine Code from Semantics. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (Portland, OR, USA) (PLDI ’15). Association for Computing Machinery, New York, NY, USA, 596–607. https://doi.org/10.1145/2737924.2737960
[49]
Venkatesh Srinivasan, Tushar Sharma, and Thomas Reps. 2016. Speeding up Machine-Code Synthesis. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (Amsterdam, Netherlands) (OOPSLA 2016). Association for Computing Machinery, New York, NY, USA, 165–180. https://doi.org/10.1145/2983990.2984006
[50]
Venkatesh Srinivasan, Ara Vartanian, and Thomas Reps. 2017. Model-Assisted Machine-Code Synthesis. Proc. ACM Program. Lang. 1, OOPSLA, Article 61 (Oct. 2017). https://doi.org/10.1145/3133885
[51]
Chenglong Wang, Alvin Cheung, and Rastislav Bodik. 2017. Interactive Query Synthesis from Input-Output Examples. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 1631–1634. https://doi.org/10.1145/3035918.3058738
[52]
Henry S. Warren. 2012. Hacker’s Delight (2nded.). Addison-Wesley Professional.
[53]
B. L. Welch. 1938. The Significance of the Difference Between Two Means when the Population Variances are Unequal. Biometrika 29, 3/4 (1938), 350–362. http://www.jstor.org/stable/2332010
[54]
Tianyi Zhang, Zhiyang Chen, Yuanli Zhu, Priyan Vaithilingam, Xinyu Wang, and Elena L Glassman. 2021. Interpretable Program Synthesis. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI ’21). Association for Computing Machinery.
[55]
Tianyi Zhang, London Lowmanstone, Xinyu Wang, and Elena L. Glassman. 2020. Interactive Program Synthesis by Augmented Examples. In Proceedings of the 33rd Annual ACM Symposium on User Interface Software and Technology (Virtual Event, USA) (UIST ’20). Association for Computing Machinery, New York, NY, USA, 627–648. https://doi.org/10.1145/3379337.3415900

Cited By

View all
  • (2024)AsFuzzer: Differential Testing of Assemblers with Error-Driven Grammar InferenceProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680345(1099-1111)Online publication date: 11-Sep-2024
  • (2024)PyDex: Repairing Bugs in Introductory Python Assignments using LLMsProceedings of the ACM on Programming Languages10.1145/36498508:OOPSLA1(1100-1124)Online publication date: 29-Apr-2024
  • (2024)Parallel Assembly SynthesisLogic-Based Program Synthesis and Transformation10.1007/978-3-031-71294-4_1(3-26)Online publication date: 7-Sep-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
UIST '21: The 34th Annual ACM Symposium on User Interface Software and Technology
October 2021
1357 pages
ISBN:9781450386357
DOI:10.1145/3472749
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2021

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Program synthesis
  2. assembly programming
  3. interactive synthesis

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Conference

UIST '21

Acceptance Rates

Overall Acceptance Rate 842 of 3,967 submissions, 21%

Upcoming Conference

UIST '24

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)45
  • Downloads (Last 6 weeks)4
Reflects downloads up to 01 Oct 2024

Other Metrics

Citations

Cited By

View all
  • (2024)AsFuzzer: Differential Testing of Assemblers with Error-Driven Grammar InferenceProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680345(1099-1111)Online publication date: 11-Sep-2024
  • (2024)PyDex: Repairing Bugs in Introductory Python Assignments using LLMsProceedings of the ACM on Programming Languages10.1145/36498508:OOPSLA1(1100-1124)Online publication date: 29-Apr-2024
  • (2024)Parallel Assembly SynthesisLogic-Based Program Synthesis and Transformation10.1007/978-3-031-71294-4_1(3-26)Online publication date: 7-Sep-2024
  • (2023)Towards Porting Operating Systems with Program SynthesisACM Transactions on Programming Languages and Systems10.1145/356394345:1(1-70)Online publication date: 3-Mar-2023
  • (2023)Everybody’s Got ML, Tell Me What Else You Have: Practitioners’ Perception of ML-Based Security Tools and Explanations2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179321(2068-2085)Online publication date: May-2023
  • (2022)Exploring the Learnability of Program Synthesizers by Novice ProgrammersProceedings of the 35th Annual ACM Symposium on User Interface Software and Technology10.1145/3526113.3545659(1-15)Online publication date: 29-Oct-2022
  • (2022)How Do We Measure Trust in Visual Data Communication?2022 IEEE Evaluation and Beyond - Methodological Approaches for Visualization (BELIV)10.1109/BELIV57783.2022.00014(85-92)Online publication date: Oct-2022

View Options

Get Access

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format.

HTML Format

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media