Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Direct Manipulation for Imperative Programs

  • Conference paper
  • First Online:
Static Analysis (SAS 2019)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 11822))

Included in the following conference series:

  • 752 Accesses

Abstract

Direct manipulation is a programming paradigm in which the programmer conveys the intended program behavior by modifying program values at runtime. The programming environment then finds a modification of the original program that yields the manipulated values. In this paper, we propose the first framework for direct manipulation of imperative programs. First, we introduce direct state manipulation, which allows programmers to visualize the trace of a buggy program on an input, and modify variable values at a location. Second, we propose a synthesis technique based on program sketching and quantitative objectives to efficiently find the “closest” program to the original one that is consistent with the manipulated values. We formalize the problem and build a tool JDial based on the Sketch synthesizer. We investigate the effectiveness of direct manipulation by using JDial to fix benchmarks from introductory programming assignments. In our evaluation, we observe that direct state manipulations are an effective specification mechanism: even when provided with a single state manipulation, JDial can produce desired program modifications for 66% of our benchmarks while techniques based only on test cases always fail.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We assume that the length of the trace in the synthesized program is at most twice the length of the original trace and we use this assumption to initialize the length of the arrays. This constant is parametric and can be modified.

References

  1. Victor, B.: Drawing dynamic visualizations (2013). http://worrydream.com/

  2. Schachman, T.: Apparatus (2015). http://aprt.us/

  3. Hottelier, T., Bodik, R., Ryokai, K.: Programming by manipulation for layout. In: UIST, pp. 231–241 (2014)

    Google Scholar 

  4. Shneiderman, B.: Direct manipulation: a step beyond programming languages. ACM SIGSOC Bullstin, vol. 13, no. 2–3, p. 143 (1982)

    Article  Google Scholar 

  5. Chugh, R., Hempel, B., Spradlin, M., Albers, J.: Programmatic and direct manipulation, together at last. In: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 341–354. ACM (2016)

    Article  Google Scholar 

  6. Hempel, B., Chugh, R.: Semi-automated SVG programming via direct manipulation. In: Proceedings of the 29th Annual Symposium on User Interface Software and Technology, pp. 379–390. ACM (2016)

    Google Scholar 

  7. D’Antoni, L., Samanta, R., Singh, R.: Qlose: program repair with quantitative objectives. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9780, pp. 383–401. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41540-6_21

    Chapter  Google Scholar 

  8. Solar-Lezama, A.: Program sketching. Int. J. Softw. Tools Technol. Transfer 15(5–6), 475–495 (2013)

    Article  Google Scholar 

  9. Singh, R., Gulwani, S., Solar-Lezama, A.: Automated feedback generation for introductory programming assignments. In: ACM SIGPLAN Notices, vol. 48, no. 6, pp. 15–26 (2013)

    Article  Google Scholar 

  10. Yi, J., Ahmed, U.Z., Karkare, A., Tan, S.H., Roychoudhury, A.: A feasibility study of using automated program repair for introductory programming assignments. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ser. ESEC/FSE 2017, pp. 740–751. ACM (2017)

    Google Scholar 

  11. Suzuki, R., et al.: Tracediff: debugging unexpected codebehavior using synthesized code corrections. In: VL/HCC 2017 (2017)

    Google Scholar 

  12. Guo, P.J.: Online python tutor: embeddable web-based program visualization for CS education. In: Proceeding of the 44th ACM Technical Symposium on Computer Science Education, pp. 579–584. ACM (2013)

    Google Scholar 

  13. Rolim, R., et al.: Learning syntactic program transformations from examples. In: Proceedings of the 39th International Conference on Software Engineering, ser. ICSE 2017, pp. 404–415. IEEE Press, Piscataway (2017)

    Google Scholar 

  14. Weiser, M.: Program slicing. In: Proceedings of the 5th International Conference on Software Engineering, pp. 439–449. IEEE Press 1981

    Google Scholar 

  15. Tillmann, N., De Halleux, J., Xie, T., Bishop, J.: Code hunt: gamifying teaching and learning of computer science at scale. In: Proceedings of the First ACM Conference on Learning@ Scale Conference, pp. 221–222. ACM (2014)

    Google Scholar 

  16. Nguyen, H.D.T., Qi, D., Roychoudhury, A., Chandra, S.: Semfix: program repair via semantic analysis. In: Proceedings of the 2013 International Conference on Software Engineering, pp. 772–781. IEEE Press (2013)

    Google Scholar 

  17. edX: Introduction to computer science and programming using python (2017). https://www.edx.org/course/introduction-computer-science-mitx-6-00-1x-10

  18. Verma, S., Roy, S.: Synergistic debug-repair of heap manipulations. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ser. ESEC/FSE 2017, pp. 163–173. ACM (2017)

    Google Scholar 

  19. Galenson, J., Reames, P., Bodik, R., Hartmann, B., Sen, K.: Codehint: dynamic and interactive synthesis of code snippets. In: Proceedings of the 36th International Conference on Software Engineering, pp. 653–663. ACM (2014)

    Google Scholar 

  20. Striewe, M., Goedicke, M.: A review of static analysis approaches for programming exercises. In: Kalz, M., Ras, E. (eds.) CAA 2014. CCIS, vol. 439, pp. 100–113. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08657-6_10

    Chapter  Google Scholar 

  21. Gulwani, S., Radiček, I., Zuleger, F.: Automated clustering and program repair for introductory programming assignments. arXiv preprint arXiv:1603.03165 (2016)

  22. Kim, D., et al.: Apex: automatic programming assignment error explanation. In: ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, ser. OOPSLA 2016, pp. 311–327. ACM (2016)

    Google Scholar 

  23. Mechtaev, S., Yi, J., Roychoudhury, A.: Directfix: Looking for simple program repairs. In: Proceedings of the 37th International Conference on Software Engineering-Volume 1, pp. 448–458. IEEE Press (2015)

    Google Scholar 

  24. Logozzo, F., Ball, T.: Modular and verified automatic program repair. In: ACM SIGPLAN Notices, vol. 47, no. 10, pp. 133–146. ACM (2012)

    Article  Google Scholar 

  25. Le Goues, C., Dewey-Vogt, M., Forrest, S., Weimer, W.: A systematic study of automated program repair: fixing 55 out of 105 bugs for \$8 each. In: International Conference on Software Engineering (ICSE), pp. 3–13. IEEE Press (2012)

    Google Scholar 

  26. Samanta, R., Olivo, O., Emerson, E.A.: Cost-aware automatic program repair. In: Müller-Olm, M., Seidl, H. (eds.) SAS 2014. LNCS, vol. 8723, pp. 268–284. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10936-7_17

    Chapter  Google Scholar 

  27. Von Essen, C., Jobstmann, B.: Program repair without regret. Formal Meth. Syst. Des. 47(1), 26–50 (2015)

    Article  Google Scholar 

  28. Le, X.-B.D., Chu, D.-H., Lo, D., Le Goues, C., Visser, W.: S3: syntax- and semantic-guided repair synthesis via programming by examples. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ser. ESEC/FSE 2017, pp. 593–604. ACM (2017)

    Google Scholar 

  29. Koukoutos, M., Kneuss, E., Kuncak, V.: An update on deductive synthesis and repair in the leon tool. arXiv preprint arXiv:1611.07625 (2016)

  30. Ball, T., Naik, M., Rajamani, S.K.: From symptom to cause: localizing errors in counterexample traces. In: ACM SIGPLAN Notices, vol. 38, no. 1, pp. 97–105. ACM (2003)

    Article  Google Scholar 

  31. Jose, M., Majumdar, R.: Cause clue clauses: error localization using maximum satisfiability. In: ACM SIGPLAN Notices vol. 46. no. (6), pp. 437–446 (2011)

    Article  Google Scholar 

  32. Könighofer, R., Bloem, R.: Automated error localization and correction for imperative programs. In: Formal Methods in Computer-Aided Design (FMCAD), pp. 91–100. IEEE (2011)

    Google Scholar 

  33. Chandra, S., Torlak, E., Barman, S., Bodik, R.: Angelic debugging. In: 2011 33rd International Conference on Software Engineering (ICSE), pp. 121–130. IEEE (2011)

    Google Scholar 

  34. Singh, R., Singh, R., Xu, Z., Krosnick, R., Solar-Lezama, A.: Modular synthesis of sketches using models. In: McMillan, K.L., Rival, X. (eds.) VMCAI 2014. LNCS, vol. 8318, pp. 395–414. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54013-4_22

    Chapter  Google Scholar 

Download references

Acknowledgment

This work was supported by NSF under grants CNS-1763871, CCF-1704117 and CCF-1846327; and by the UW-Madison OVRGE with funding from WARF.

Author information

Authors and Affiliations

  1. University of Wisconsin-Madison, Madison, USA

    Qinheping Hu & Loris D’Antoni

  2. Purdue University, West Lafayette, USA

    Roopsha Samanta

  3. Google, Hanover, USA

    Rishabh Singh

Authors
  1. Qinheping Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roopsha Samanta
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rishabh Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Loris D’Antoni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Loris D’Antoni .

Editor information

Editors and Affiliations

  1. University of Colorado, Boulder, CO, USA

    Bor-Yuh Evan Chang

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hu, Q., Samanta, R., Singh, R., D’Antoni, L. (2019). Direct Manipulation for Imperative Programs. In: Chang, BY. (eds) Static Analysis. SAS 2019. Lecture Notes in Computer Science(), vol 11822. Springer, Cham. https://doi.org/10.1007/978-3-030-32304-2_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-32304-2_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-32303-5

  • Online ISBN: 978-3-030-32304-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation