A scalable method for deductive generalization in the spreadsheet paradigm

ABSTRACT

In this paper, we present an efficient method for automatically generalizing programs written in spreadsheet languages. The strategy is to do generalization through incremental analysis of logical relationships among concrete program entities from the perspective of a particular computational goal. The method uses deductive dataflow analysis with algebraic back-substitution rather than inference with heuristics, and there is no need for generalization-related dialog with the user. We present the algorithms and their time complexities and show that, because the algorithms perform their analyses incrementally, on only the on-screen program elements rather than on the entire program, the method is scalable. Performance data is presented to help demonstrate the scalability.

REFERENCES

• 1: Ambler, A. 1999. The Formulate visual programming language. Dr. Dobb's Journal 24, 8, 21--28.
• 2: Ambler, A. and Hsia, Y. 1993. Generalizing selection in by-demonstration programming. J. Vis. Lang. Comput. 4, 3, 283--300.
• 3: Burnett, M. and Ambler, A. 1994. Interactive visual data abstraction in a declarative visual programming language. J. Vis. Lang. Comput. 5, 1, 29--60.
• 4: M. M. Burnett , J. W. Atwood Jr , Z. T. Welch, Implementing Level 4 Liveness in Declarative Visual Programming Languages, Proceedings of the IEEE Symposium on Visual Languages, p.126, September 01-04, 1998
• 5: Margaret Burnett , John Atwood , Rebecca Walpole Djang , James Reichwein , Herkimer Gottfried , Sherry Yang, Forms/3: A first-order visual language to explore the boundaries of the spreadsheet paradigm, Journal of Functional Programming, v.11 n.2, p.155-206, March 2001
• 6: Margaret Burnett , Nanyu Cao , John Atwood, Time in Grid-Oriented VPLs: Just Another Dimension?, Proceedings of the 2000 IEEE International Symposium on Visual Languages (VL'00), p.137, September 10-13, 2000
• 7: Margaret M. Burnett , Herkimer J. Gottfried, Graphical definitions: expanding spreadsheet languages through direct manipulation and gestures, ACM Transactions on Computer-Human Interaction (TOCHI), v.5 n.1, p.1-33, March 1998 [doi>10.1145/274444.274445]
• 8: Burnett, M., Yang, S., and Summet, J. 2001b. A Scalable Method for Deductive Generalization in the Spreadsheet Paradigm. Technical Rep. TR 01-60-02, Oregon State University, Corvallis, Ore; http://www.cs.orst.edu/∼burnett/reprints.html.
• 9: Ed Huai-hsin Chi , John Riedl , Phillip Barry , Joseph Konstan, Principles for Information Visualization Spreadsheets, IEEE Computer Graphics and Applications, v.18 n.4, p.30-38, July 1998 [doi>10.1109/38.689659]
• 10: Allen Cypher , David Canfield Smith, KidSim: end user programming of simulations, Proceedings of the SIGCHI conference on Human factors in computing systems, p.27-34, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223908]
• 11: Martin R. Frank , James D. Foley, A pure reasoning engine for programming by demonstration, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.95-101, November 02-04, 1994, Marina del Rey, California, United States [doi>10.1145/192426.192466]
• 12: Heger, N., Cypher, A., and Smith, D. 1998. Cocoa at the Visual Programming Challenge 1997. J. Vis. Lang. Comput. 9, 2, 151--169.
• 13: John Hughes, Lazy memo-functions, Proc. of a conference on Functional programming languages and computer architecture, p.129-146, January 1985, Nancy, France
• 14: Kahn, K. 1996. ToonTalk---An animated programming environment for children. J. Vis. Lang. Comput. 7, 2, 197--217.
• 15: David Kurlander , Steven Feiner, A history-based macro by example system, Proceedings of the 5th annual ACM symposium on User interface software and technology, p.99-106, November 15-18, 1992, Monteray, California, United States [doi>10.1145/142621.142633]
• 16: Jennifer L. Leopold , Allen L. Ambler, Keyboardless Visual Programming Using Voice, Handwriting, and Gesture, Proceedings of the 1997 IEEE Symposium on Visual Languages (VL '97), p.28, April 23-26, 1997
• 17: Henry Lieberman, Tinker: a programming by demonstration system for beginning programmers, Watch what I do: programming by demonstration, MIT Press, Cambridge, MA, 1993
• 18: Richard G. McDaniel , Brad A. Myers, Getting more out of programming-by-demonstration, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.442-449, May 15-20, 1999, Pittsburgh, Pennsylvania, United States [doi>10.1145/302979.303127]
• 19: Brad A. Myers, Graphical techniques in a spreadsheet for specifying user interfaces, Proceedings of the SIGCHI conference on Human factors in computing systems: Reaching through technology, p.243-249, April 27-May 02, 1991, New Orleans, Louisiana, United States [doi>10.1145/108844.108903]
• 20: Brad A. Myers, Peridot: creating user interfaces by demonstration, Watch what I do: programming by demonstration, MIT Press, Cambridge, MA, 1993
• 21: Brad A. Myers, Scripting graphical applications by demonstration, Proceedings of the SIGCHI conference on Human factors in computing systems, p.534-541, April 18-23, 1998, Los Angeles, California, United States [doi>10.1145/274644.274716]
• 22: Brad Myers , Scott E. Hudson , Randy Pausch, Past, present, and future of user interface software tools, ACM Transactions on Computer-Human Interaction (TOCHI), v.7 n.1, p.3-28, March 2000 [doi>10.1145/344949.344959]
• 23: Myers, B. and Maulsby, D. 1993. Glossary. In Watch What I Do: Programming by Demonstration, A. Cypher, Ed. MIT Press, Cambridge, Mass., 593--603.
• 24: Brad A. Myers , David Canfield Smith , Bruce Horn, Report of the “End-User Programming” working group, Languages for developing user interfaces, A. K. Peters, Ltd., Natick, MA, 1992
• 25: Dan R. Olsen, Jr. , Xinyu Deng, Inductive groups, Proceedings of the 9th annual ACM symposium on User interface software and technology, p.193-199, November 06-08, 1996, Seattle, Washington, United States [doi>10.1145/237091.237120]
• 26: Corrina Perrone , Alexander Repenning, Graphical Rewrite Rule Analogies: Avoiding the Inherit or Copy & Paste Reuse Dilemma, Proceedings of the IEEE Symposium on Visual Languages, p.40, September 01-04, 1998
• 27: A. Repenning, Bending the rules: steps toward semantically enriched graphical rewrite rules, Proceedings of the 11th International IEEE Symposium on Visual Languages, p.226, September 05-09, 1995
• 28: Sassin, M. 1994. Creating user-intended programs with programming by demonstration. In Proceedings of the IEEE Symposium on Visual Languages (St. Louis, Mo, Oct. 4--7, 1994). IEEE Computer Society Press, Los Alamitos, Calif., 153--160.
• 29: Smith, D. 1975. Pygmalion: a computer program to model and stimulate creative thought, Ph.D. dissertation, Stanford University, Stanford Calif. 1975. (A more accessible summary of this work can be found in Cypher, A. 1993. Watch What I Do: Programming by Demonstration. MIT Press, Cambridge, Mass.)
• 30: Atsushi Sugiura , Yoshiyuki Koseki, Simplifying macro definition in programming by demonstration, Proceedings of the 9th annual ACM symposium on User interface software and technology, p.173-182, November 06-08, 1996, Seattle, Washington, United States [doi>10.1145/237091.237118]
• 31: Brad Vander Zanden , Brad A. Myers, Demonstrational and constraint-based techniques for pictorially specifying application objects and behaviors, ACM Transactions on Computer-Human Interaction (TOCHI), v.2 n.4, p.308-356, Dec. 1995 [doi>10.1145/212430.212443]
• 32: Guijun Wang , Allen Ambler, Solving Display-Based Problems, Proceedings of the 1996 IEEE Symposium on Visual Languages, p.122, September 03-06, 1996
• 33: Nicholas Wilde , Clayton Lewis, Spreadsheet-based interactive graphics: from prototype to tool, Proceedings of the SIGCHI conference on Human factors in computing systems: Empowering people, p.153-160, April 01-05, 1990, Seattle, Washington, United States [doi>10.1145/97243.97268]
• 34: David Wolber, Pavlov: an interface builder for designing animated interfaces, ACM Transactions on Computer-Human Interaction (TOCHI), v.4 n.4, p.347-386, Dec. 1997 [doi>10.1145/267135.267142]
• 35: Yang, S. and Burnett, M. 1994. From concrete forms to generalized abstractions through perspective-oriented analysis of logical relationships. In Proceedings of the IEEE Symposium on Visual Languages (St. Louis, Mo., Oct. 4--7, 1994). IEEE Computer Society Press, Los Alamitos, Calif., 6--14.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.7 Visual Programming

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.1 Office Automation
          Subjects: Spreadsheets
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

General Terms:
Human Factors, Languages

Keywords:
Forms/3, Human-computer interaction, concrete programming, generalization, graphical programming, spreadsheet languages