A formal approach to undo operations in programming languages

ABSTRACT

A framework is presented for adding a general Undo facility to programming languages. A discussion of relevant literature is provided to show that the idea of Undoing pervades several areas in computer science, and even other disciplines. A simple model of computation is introduced, and it is augmented with a minimal amount of additional structure needed for recovery and reversal. Two different interpretations of Undo are motivated with examples. Then, four primitives are defined in a language-independent manner; they are sufficient to support a wide range of Undo capability. Two of these primitives carry out state saving, and the others mirror the two versions of the Undo operation. Properties of and relationships between these primitives are explored, and there are some preliminary remarks on how one could implement a system based on this formalism. The main conclusion is that the notions of recovery and reversal of actions can become part of the programming process.

REFERENCES

• 1: ANDERSON, T., AND RANDELL, B. Computing Systems Reliability., Cambridge University Press, New York, 1979.
• 2: APPLE COMPUTER, INC. LisaWrite. Cupertino, Calif., 1983.
• 3: James E. Archer, Jr. , Richard W. Conway, COPE: A Cooperative Programming Environment, Cornell University, Ithaca, NY, 1981
• 4: James E. Archer, Jr. , Richard W. Conway , Fred B. Schneider, User Recovery and Reversal in Interactive Systems, Cornell University, Ithaca, NY, 1981
• 5: James E. Archer, Jr. , Richard Conway , Fred B. Schneider, User Recovery and Reversal in Interactive Systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.1, p.1-19, Jan. 1984 [doi>10.1145/357233.357234]
• 6: James E. Archer, Jr. , Richard W. Conway , Andrew I. Shore , Leonard S. Silver, The CORE User Interface, Cornell University, Ithaca, NY, 1980
• 7: BALZER, R.M. EXDAMS--Extendable debugging and monitoring system. In AFIPS Proceedings Spring Joint Computer Conference, 34, AFIPS Press, Montvale, N.J., 1969, 567-580.
• 8: BENNETT, C. H. Logical reversibility of computation. IBM J. Res. Dev. 17, 6 (Nov. 1973), 525-532.
• 9: BENNETT, C. H. The thermodynamics of computation--A review. Int. J. Theor. Phys. 21, 12 (Dec. 1982), 905-940.
• 10: BRANSCOMB, L. M., AND THOMAS, J. C. Ease of use: A system design challenge. In Information Processing 83, Proceedings }FIP 9th World Computing Congress, R.E.A. Mason, Ed., Elsevier North-Holland, New York, 1983, 431-438.
• 11: BURKS, A. W., AND BURKS, A.R. The ENIAC: First general-purpose electronic computer. Ann. Hist. Cornput. 3, 4 (Oct. 1981), 310-399.
• 12: CARTER, W.C. Fault detection and recovery algorithms for fault-tolerant systems. In EURO IFIP 1979, P. A. Samet, Ed., North-Holland, Amsterdam, 1979, 725-734.
• 13: CARTER, W, C. Personal communication. May 1984.
• 14: DARLINGTON, J. An experimental program transformation and synthesis system. Artif. Intell. 16 (1981), 1-46.
• 15: Eduardo B. Fernandez , Rita C. Summers , Christopher Wood, Database Security and Integrity, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1981
• 16: FISCHER, C. N., JOHNSON, G., PAL, A., STOCK, D., AND MAUNEY, J. An introduction to Editor Allan Poe. In SOFTFAIR 83, Proceedings 1st Conference Software Development Tools, Techniques, and Alternatives (Washington, D.C., July 1983), IEEE, New York, 245-250.
• 17: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 18: FOLEY, J. D., AND WALLACE, V.L. The art of natural graphic man-machine conversion. Proc. IEEE 62, 4 (Apr. 1974), 462-471.
• 19: FORTUNE, S.J. Dynamic variables. IBM T. J. Watson Research Center internal document, Apr. 1981.
• 20: FREDKIN, E., AND TOFFOLI, T. Conservative logic. Int. J. Theor. Phys. 2l, 3/4 (Apr. 1982), 219-253.
• 21: GAINES, B. R., AND FACEY, P.V. Some experience in interactive system development and application. Proc. IEEE 63, 6 (June 1975), 894-911.
• 22: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 23: M. Good, AN EASE OF USE EVALUATION OF AN INTEGRATED EDITOR AND, Massachusetts Institute of Technology, Cambridge, MA, 1981
• 24: GOSLING, J.A. Unix Emacs Reference Manual. Carnegie-Mellon University, Pittsburgh, 1982.
• 25: Ralph E. Griswold , David R. Hanson , John T. Korb, Generators in Icon, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.144-161, April 1981 [doi>10.1145/357133.357136]
• 26: Michael Hammer , Richard Ilson , Tim Anderson , Edward Gilbert , Michael Good , Bahram Niamir , Larry Rosentein , Sandor Schoichet, The implementation of Etude, an integrated and interactive document production system, Proceedings of the ACM SIGPLAN SIGOA symposium on Text manipulation, p.137-146, June 08-10, 1981, Portland, Oregon, United States
• 27: HANSEN, W. J. User engineering principles for interactive systems. In AFIPS Conference Proceedings 39, AFIPS Press, Montvale, N.J., 1971, 523-532.
• 28: IBM CORP. IBM Virtual Machine/System Product: System Product Editor User's Guide. Endicott, N.Y., 1980.
• 29: IBM CORP. Personal editor. Boca Raton, Fla., 1982.
• 30: K Jensen , N Wirth , A B Mickel , J F Miner, Pascal user manual and report; 3rd ed., Springer-Verlag New York, Inc., New York, NY, 1985
• 31: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 32: Brian W. Kernighan , P. J. Plauger, Software Tools in Pascal, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1981
• 33: KORF, R.E. Inversion of applicative programs. In Proceedings 7th International Joint Conference on Artificial Intelligence, IJCAI-81 (Vancouver, Canada, Aug., 1981), 1007-1009.
• 34: KORF, R.E. Personal communication. Apr. 1984.
• 35: KOSINSKI, P.R. PEDIT, a programmable editor. IBM T. J. Watson Research Center internal document, June 1980.
• 36: KOSlNSKI, P.R. Personal communication. June 1979.
• 37: KRUSKAL, V.J. Managing multiversion programs with an editor. IBM J. Res. Dev. 28, I (Jan. 1984), 74-81.
• 38: KRUSKAL, V.J. P-EDIT, a text editor for parametric files; user guide. RC 8352, IBM T. J. 'Watson Research Center, July 1980. A substantial revision, called the P-EDIT Reference Manual, is available from its author.
• 39: KWAN, C. Y. K., AND SORENSON, P. G. A high-level user-interface prototype for office information systems. Rep. 83-15, Univ. of Saskatchewan, 1983.
• 40: LAMPSON, B.W. Bravo manual. In Alto User's Handbook, Xerox Paid Alto Research Center, Palo Alto, Calif., 1978, 31-62.
• 41: LANDAUER, R. Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 3 (July 1961), 183-191.
• 42: LEEMAN, G. B., JR. A formal approach to undo operations in programming languages. RC 10310, IBM T. J. Watson Research Center, Jan. 1984.
• 43: LEEMAN, G. B., JR. Building undo/redo operations into the C programming language. In Proceedings 15th Annual International Symposium on Fault-Tolerant Computing--FTCS 15, IEEE Computer Society Press, Silver Spring, Md., 1985, 410-415.
• 44: MCCARTHY, J. The inversion of functions defined by Turing machines. In Automata Studies, C. E. Shannon and J. McCarthy, Eds., Princeton University Press, Princeton, N.J., 1956, 177-181.
• 45: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 46: MEDINA-MORA, R., AND FELLER, P. An incremental programming environment. IEEE Trans. Softw. Eng. SE-7, 5 (Sept. 1981), 472-481.
• 47: POURNELLE, J. User's column: Epson QX-10, Zenith Z-29, CP/M-68K, and more. BYTE 8, 8 (Aug. 1983), 434-454.
• 48: PRAGER, J. M., AND BORKIN, S.A. POLITE project progress report. Rep. G320-2140, IBM Cambridge Scientific Center, Apr. 1982.
• 49: RADIN, G. The 801 minicomputer. IBMJ. Res. Dev. 27, 3 (May 1983), 237-246.
• 50: Steven P. Reiss, Graphical program development with PECAN program development systems, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.30-41, April 1984
• 51: Steven P. Reiss, PECAN: program development systems that support multiple views, IEEE Transactions on Software Engineering, v.11 n.3, p.276-285, March 1985 [doi>10.1109/TSE.1985.232211]
• 52: RUTKOWSKI, C. An introduction to the human applications standard computer interface, Part 1: Theory and principles. BYTE 7, 10 (Oct. 1982), 291-310.
• 53: SEYBOLD, J.W. Apple's Lisa: The "next generation" computer? Seybold Rep. Publ. Syst. 12, 10 ( Jan. 1983).
• 54: SEYBOLD, J.W. The Xerox Star, a "professional" workstation. Seybold Rep. Word Process. 4, 5 (May 1981).
• 55: SICKEL, S. Invertibility of logic programs. In Proceedings of the 4th Workshop on Automated Deduction (Austin, Tex., Feb. 1979), W. H. Joyner, Jr., Ed., 103-109.
• 56: STEPHENSON, C. J. EI) introduction, primitives, and macros. IBM T. J. Watson Research Center internal document, Oct. 1983.
• 57: STEPHENSON, C.J. Program notes and data structures for ED. IBM T. J. Watson Research Center internal document, Oct. 1983.
• 58: TEITELMAN, W. lnterlisp Reference Manual. 4th ed., Xerox Palo Alto Research Center, Palo Alto, Calif., 1978.
• 59: UNIVERSITY Or MICHIGAN. The Michigan Terminal System. Vol. 1, Ann Arbor, Mich., 1976.
• 60: Joost S. M. Verhofstad, Recovery Techniques for Database Systems, ACM Computing Surveys (CSUR), v.10 n.2, p.167-195, June 1978 [doi>10.1145/356725.356730]
• 61: Jeffrey Scott Vitter, US&R: A new framework for redoing (Extended Abstract), Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.168-176, April 1984
• 62: VITTER, J.S. US&R: A new framework for redoing. IEEE Softw. 1, 4 (Oct. 1984), 39-52.
• 63: Harald Wertz, The design of an integrated, interactive and incremental programming environment, Proceedings of the 6th international conference on Software engineering, p.157-165, September 13-16, 1982, Tokyo, Japan
• 64: XEROX CORP. 8010 Star Information System Reference Guide. Dallas, Tex., 1981.

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Checkpoint/restart

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.7 Database Administration
          Subjects: Logging and recovery

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

General Terms:
Design, Human Factors, Languages