Bidirectional evaluation with direct manipulation

Abstract

We present an evaluation update (or simply, update) algorithm for a full-featured functional programming language, which synthesizes program changes based on output changes. Intuitively, the update algorithm retraces the steps of the original evaluation, rewriting the program as needed to reconcile differences between the original and updated output values. Our approach, furthermore, allows expert users to define custom lenses that augment the update algorithm with more advanced or domain-specific program updates.

To demonstrate the utility of evaluation update, we implement the algorithm in Sketch-n-Sketch, a novel direct manipulation programming system for generating HTML documents. In Sketch-n-Sketch, the user writes an ML-style functional program to generate HTML output. When the user directly manipulates the output using a graphical user interface, the update algorithm reconciles the changes. We evaluate bidirectional evaluation in Sketch-n-Sketch by authoring ten examples comprising approximately 1400 lines of code in total. These examples demonstrate how a variety of HTML documents and applications can be developed and edited interactively in Sketch-n-Sketch, mitigating the tedious edit-run-view cycle in traditional programming environments.

References

1. Davi M. J. Barbosa, Julien Cretin, Nate Foster, Michael Greenberg, and Benjamin C. Pierce. 2010. Matching Lenses: Alignment and View Update. In International Conference on Functional Programming (ICFP).
2. Aaron Bohannon, J. Nathan Foster, Benjamin C. Pierce, Alexandre Pilkiewicz, and Alan Schmitt. 2008. Boomerang: Resourceful Lenses for String Data. In Symposium on Principles of Programming Languages (POPL).
3. Aaron Bohannon, Jeffrey A. Vaughan, and Benjamin C. Pierce. 2006. Relational Lenses: A Language for Updateable Views. In Principles of Database Systems (PODS).
4. Michael Bostock, Vadim Ogievetsky, and Jeffrey Heer. 2011. D3: Data-Driven Documents. IEEE Transactions on Visualization and Computer Graphics (VIS) (2011).
5. Adam Chlipala, Leaf Petersen, and Robert Harper. 2005. Strict Bidirectional Type Checking. In Workshop on Types in Languages Design and Implementation (TLDI) .
6. Ravi Chugh, Brian Hempel, Mitchell Spradlin, and Jacob Albers. 2016. Programmatic and Direct Manipulation, Together at Last. In Conference on Programming Language Design and Implementation (PLDI).
7. Robert Bruce Findler and Matthew Flatt. 2006. Slideshow: Functional Presentations. Journal of Functional Programming (2006).
8. J. Nathan Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan Schmitt. 2007. Combinators for Bidirectional Tree Transformations: A Linguistic Approach to the View-Update Problem. ACM Transactions on Programming Languages and Systems (TOPLAS) 29, 3 (2007).
9. Brian Hempel and Ravi Chugh. 2016. Semi-Automated SVG Programming via Direct Manipulation. In Symposium on User Interface Software and Technology (UIST) .
10. Soichiro Hidaka, Zhenjiang Hu, Kazuhiro Inaba, Hiroyuki Kato, Kazutaka Matsuda, and Keisuke Nakano. 2010. Bidirectionalizing Graph Transformations. In International Conference on Functional Programming (ICFP).
11. Zhenjiang Hu, Shin-Cheng Mu, and Masato Takeichi. 2008. A Programmable Editor for Developing Structured Documents Based on Bidirectional Transformations. Higher-Order and Symbolic Computation (2008).
12. Edwin L. Hutchins, James D. Hollan, and Donald A. Norman. 1985. Direct Manipulation Interfaces. Human-Computer Interaction (1985).
13. Shinya Kawanaka and Haruo Hosoya. 2006. biXid: A Bidirectional Transformation Language for XML. In International Conference on Functional Programming (ICFP) .
14. Andrew J. Ko and Brad A. Myers. 2008. Debugging Reinvented: Asking and Answering Why and Why Not Questions About Program Behavior. In International Conference on Software Engineering (ICSE).
15. Dongxi Liu, Zhenjiang Hu, and Masato Takeichi. 2007. Bidirectional Interpretation of XQuery. In Symposium on Partial Evaluation and Semantics-based Program Manipulation (PEPM) .
16. Solomon Maina, Anders Miltner, Kathleen Fisher, Benjamin C. Pierce, David Walker, and Steve Zdancewic. 2018. Synthesizing Quotient Lenses. Proceedings of the ACM on Programming Languages (PACMPL), Issue ICFP (2018).
17. Kazutaka Matsuda, Zhenjiang Hu, Keisuke Nakano, Makoto Hamana, and Masato Takeichi. 2007. Bidirectionalization Transformation Based on Automatic Derivation of View Complement Functions. In International Conference on Functional Programming (ICFP) .
18. Kazutaka Matsuda and Meng Wang. 2015. Applicative Bidirectional Programming with Lenses. In International Conference on Functional Programming (ICFP) .
19. Kazutaka Matsuda and Meng Wang. 2018. HOBiT: Programming Lenses Without Using Lens Combinators. In European Symposium on Programming (ESOP) .
20. Mikaël Mayer, Viktor Kunčak, and Ravi Chugh. 2018. Bidirectional Evaluation with Direct Manipulation. (2018). Extended version of OOPSLA 2018 paper available as forthcoming CoRR report.
21. Anders Miltner, Kathleen Fisher, Benjamin C. Pierce, David Walker, and Steve Zdancewic. 2018. Synthesizing Bijective Lenses. Proceedings of the ACM on Programming Languages (PACMPL), Issue POPL (2018).
22. Martin Monperrus. 2018. Automatic Software Repair: A Bibliography. Comput. Surveys (2018).
23. Shin-Cheng Mu, Zhenjiang Hu, and Masato Takeichi. 2004a. An Algebraic Approach to Bi-directional Updating. In Asian Symposium on Programming Languages and Systems (APLAS) .
24. Shin-Cheng Mu, Zhenjiang Hu, and Masato Takeichi. 2004b. An Injective Language for Reversible Computation. In Conference on Mathematics of Program Construction (MPC) .
25. Keisuke Nakano, Zhenjiang Hu, and Masato Takeichi. 2009. Consistent Web Site Updating Based on Bidirectional Transformation. International Journal on Software Tools for Technology Transfer (Web Site Evolution 2008) (2009).
26. Benjamin C. Pierce and David N. Turner. 2000. Local Type Inference. ACM Transactions on Programming Languages and Systems (TOPLAS) (2000).
27. Guillaume Pothier, Éric Tanter, and José Piquer. 2007. Scalable Omniscient Debugging. In Object-Oriented Programming Systems and Applications (OOPSLA) .
28. Raghu Rajkumar, Nate Foster, Sam Lindley, and James Cheney. 2014. Lenses for Web Data. Electronic Communications of the EASST (Bidirectional Transformations 2013) (2014).
29. Hesam Samimi, Max Schäfer, Shay Artzi, Todd Millstein, Frank Tip, and Laurie Hendren. 2012. Automated Repair of HTML Generation Errors in PHP Applications using String Constraint Solving. In International Conference on Software Engineering (ICSE) .
30. Ben Shneiderman. 1983. Direct Manipulation: A Step Beyond Programming Languages. Computer (August 1983).
31. Janis Voigtländer. 2009. Bidirectionalization for Free! (Pearl). In Symposium on Principles of Programming Languages (POPL).
32. Xiaoyin Wang, Lu Zhang, Tao Xie, Yingfei Xiong, and Hong Mei. 2012. Automating Presentation Changes in Dynamic Web Applications via Collaborative Hybrid Analysis. In Symposium on the Foundations of Software Engineering (FSE).

Index Terms

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction paradigms

      • Graphical user interfaces

• Software and its engineering

  • Software notations and tools

    • Context specific languages

      • Specialized application languages

    • General programming languages