George B. Leeman
Skip Abstract Section
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.
- 1 ANDERSON, T., AND RANDELL, B. Computing Systems Reliability., Cambridge University Press, New York, 1979.Google Scholar
- 2 APPLE COMPUTER, INC. LisaWrite. Cupertino, Calif., 1983.Google Scholar
- 3 ARCSER, J. E., JR., AND CONWA~, R. COPE: A cooperative programming environment. TR-81- 459, Cornell Univ., June 1981. Google ScholarDigital Library
- 4 ARCHER, J. E., JR., CONWAY, R., AND SCHNEIDER, F.B. User recovery and reversal in interactive systems. TR 81-476, Cornell Univ., Oct. 1981. Google ScholarDigital Library
- 5 ARCHER, J. E., JR., CONWAY, a., AND SCHNEIDER, F.B. User recovery and reversal in interactive systems. ACM Trans. Program. Lang. Syst. 6, 1 (Jan. 1984), 1-19. Google ScholarDigital Library
- 6 ARCHER, J. E., JR., CONWAY, R., SHORE, A., AND SILVER, L. The CORE user interface. TR 80- 437, Cornell Univ., Sept. 1980. Google ScholarDigital Library
- 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.Google Scholar
- 8 BENNETT, C. H. Logical reversibility of computation. IBM J. Res. Dev. 17, 6 (Nov. 1973), 525-532.Google ScholarDigital Library
- 9 BENNETT, C. H. The thermodynamics of computation--A review. Int. J. Theor. Phys. 21, 12 (Dec. 1982), 905-940.Google ScholarCross Ref
- 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.Google Scholar
- 11 BURKS, A. W., AND BURKS, A.R. The ENIAC: First general-purpose electronic computer. Ann. Hist. Cornput. 3, 4 (Oct. 1981), 310-399.Google ScholarDigital Library
- 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.Google Scholar
- 13 CARTER, W, C. Personal communication. May 1984.Google Scholar
- 14 DARLINGTON, J. An experimental program transformation and synthesis system. Artif. Intell. 16 (1981), 1-46.Google ScholarDigital Library
- 15 FERNANDEZ, E. B., SUMMERS, R. C., AND WOOD, C. The Systems Programming Series. Database Security and Integrity, Addison-Wesley, Reading, Mass., 1981. Google ScholarDigital Library
- 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.Google Scholar
- 17 FLOYD, R.W. Nondeterministic algorithms. J. ACM 14, 4 (Oct. 1967), 636-644. Google ScholarDigital Library
- 18 FOLEY, J. D., AND WALLACE, V.L. The art of natural graphic man-machine conversion. Proc. IEEE 62, 4 (Apr. 1974), 462-471.Google ScholarCross Ref
- 19 FORTUNE, S.J. Dynamic variables. IBM T. J. Watson Research Center internal document, Apr. 1981.Google Scholar
- 20 FREDKIN, E., AND TOFFOLI, T. Conservative logic. Int. J. Theor. Phys. 2l, 3/4 (Apr. 1982), 219-253.Google ScholarCross Ref
- 21 GAINES, B. R., AND FACEY, P.V. Some experience in interactive system development and application. Proc. IEEE 63, 6 (June 1975), 894-911.Google ScholarCross Ref
- 22 GOLOMB, S. W., AND BAUMERT, L. D. Backtrack programming. J. ACM 12, 4 (Oct. 1965), 516-524. Google ScholarDigital Library
- 23 GOOD, M. An ease of use evaluation of an integrated editor and formatter. MIT/LCS TR 266, Massachusetts Institute of Technology, Nov. 1981. Google ScholarDigital Library
- 24 GOSLING, J.A. Unix Emacs Reference Manual. Carnegie-Mellon University, Pittsburgh, 1982.Google Scholar
- 25 GRISWOLD, R. E., HANSON, D. R., AND KORB, J.T. Generators in Icon. ACM Trans. Program. Lang. Syst. 3, 2 (Apr. 1981), 144-161. Google ScholarDigital Library
- 26 HA ME , M., SO , R., ANDERSON, T., GILBERT, E., GOOD, M., NIAMIR, B., ROSENSTEIN, L., AND SCHOICHET, S. The implementation of Etude, an integrated and interactive document production system. In Proceedings ACM SIGPLAN/SIGOA Conference on Text Manipulation, ACM, New York, June, 1981, 137-146. Google ScholarDigital Library
- 27 HANSEN, W. J. User engineering principles for interactive systems. In AFIPS Conference Proceedings 39, AFIPS Press, Montvale, N.J., 1971, 523-532.Google ScholarDigital Library
- 28 IBM CORP. IBM Virtual Machine/System Product: System Product Editor User's Guide. Endicott, N.Y., 1980.Google Scholar
- 29 IBM CORP. Personal editor. Boca Raton, Fla., 1982.Google Scholar
- 30 JENSEN, K., AND WIRTH, N. Pascal User Manual and Report, Springer Verlag, New York, 1974. Corrected printing, 1978. Google ScholarDigital Library
- 31 KERNIGHAN, B. W., AND RITCHIE, D.M. The C Programming Language, Prentice-Hall, Englewood Cliffs, N.J., 1978. Google ScholarDigital Library
- 32 KERNIGHAN, B. W., AND PLAUGER, P.J. Software Tools in Pascal, Addison-Wesley, Reading, Mass., 1981. Google ScholarDigital Library
- 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.Google Scholar
- 34 KORF, R.E. Personal communication. Apr. 1984.Google Scholar
- 35 KOSINSKI, P.R. PEDIT, a programmable editor. IBM T. J. Watson Research Center internal document, June 1980.Google Scholar
- 36 KOSlNSKI, P.R. Personal communication. June 1979.Google Scholar
- 37 KRUSKAL, V.J. Managing multiversion programs with an editor. IBM J. Res. Dev. 28, I (Jan. 1984), 74-81.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 40 LAMPSON, B.W. Bravo manual. In Alto User's Handbook, Xerox Paid Alto Research Center, Palo Alto, Calif., 1978, 31-62.Google Scholar
- 41 LANDAUER, R. Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 3 (July 1961), 183-191.Google ScholarDigital Library
- 42 LEEMAN, G. B., JR. A formal approach to undo operations in programming languages. RC 10310, IBM T. J. Watson Research Center, Jan. 1984.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 45 MCCARTHY, J., ABRAHAMS, P. W., EDWARDS, l). J., HART, T. P., AND LEVIN, M.I. LISP 1.5 Programmer's Manual, MIT Press, Cambridge, Mass., 1973. Google ScholarDigital Library
- 46 MEDINA-MORA, R., AND FELLER, P. An incremental programming environment. IEEE Trans. Softw. Eng. SE-7, 5 (Sept. 1981), 472-481.Google ScholarDigital Library
- 47 POURNELLE, J. User's column: Epson QX-10, Zenith Z-29, CP/M-68K, and more. BYTE 8, 8 (Aug. 1983), 434-454.Google Scholar
- 48 PRAGER, J. M., AND BORKIN, S.A. POLITE project progress report. Rep. G320-2140, IBM Cambridge Scientific Center, Apr. 1982.Google Scholar
- 49 RADIN, G. The 801 minicomputer. IBMJ. Res. Dev. 27, 3 (May 1983), 237-246.Google ScholarDigital Library
- 50 REISS, S. P. Graphical program development with PECAN program development systems. SIGPLAN Not: Proceedings ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments 19, 5 (Apr. 1984), 30-37. Google ScholarDigital Library
- 51 REISS, S.P. PECAN: Program development systems that support multiple views. IEEE Trans. Softw. Eng. SE-II, 3 (Mar. 1985), 276-285. Google ScholarDigital Library
- 52 RUTKOWSKI, C. An introduction to the human applications standard computer interface, Part 1: Theory and principles. BYTE 7, 10 (Oct. 1982), 291-310.Google Scholar
- 53 SEYBOLD, J.W. Apple's Lisa: The "next generation" computer? Seybold Rep. Publ. Syst. 12, 10 ( Jan. 1983).Google Scholar
- 54 SEYBOLD, J.W. The Xerox Star, a "professional" workstation. Seybold Rep. Word Process. 4, 5 (May 1981).Google Scholar
- 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.Google Scholar
- 56 STEPHENSON, C. J. EI) introduction, primitives, and macros. IBM T. J. Watson Research Center internal document, Oct. 1983.Google Scholar
- 57 STEPHENSON, C.J. Program notes and data structures for ED. IBM T. J. Watson Research Center internal document, Oct. 1983.Google Scholar
- 58 TEITELMAN, W. lnterlisp Reference Manual. 4th ed., Xerox Palo Alto Research Center, Palo Alto, Calif., 1978.Google Scholar
- 59 UNIVERSITY Or MICHIGAN. The Michigan Terminal System. Vol. 1, Ann Arbor, Mich., 1976.Google Scholar
- 60 VERHOFSTAD, Z. S.M. Recovery techniques for database systems. ACM Comput. Surv. 10, 2 (June 1978), 167-196. Google ScholarDigital Library
- 61 VITTER, J. S. US&R: A new framework for redoing. SIGPLAN Not. Proceedings ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments 19, 5 (Apr. 1984), 168-176. Google ScholarDigital Library
- 62 VITTER, J.S. US&R: A new framework for redoing. IEEE Softw. 1, 4 (Oct. 1984), 39-52.Google ScholarDigital Library
- 63 WERTZ, H. The design of an integrated, interactive, and incremental programming environment. In Proceedings 6th International Conference on Software Engineering (New York, Sept. 1982), IEEE, New York, 157-165. Google ScholarDigital Library
- 64 XEROX CORP. 8010 Star Information System Reference Guide. Dallas, Tex., 1981.Google Scholar
Index Terms
- A formal approach to undo operations in programming languages
Recommendations
Undo as concurrent inverse in group editors
As an important mechanism for error recovery and exploration of alternatives in interactive and collaborative applications, an undo facility should have the capability of undoing any operation at any time. However, supporting undo in collaborative ...
Comments