Editing by example

ABSTRACT

An editing by example system is an automatic program synthesis facility embedded in a text editor that can be used to solve repetitive text editing problems. The user provides the editor with a few examples of a text transformation. The system analyzes the examples and generalizes them into a program that can perform the transformation to the rest of the user's text. This paper presents an overview of the design, analysis, and implementation of a practical editing by example system. It studies the problem of synthesizing a text processing program that generalizes the transformation implicitly described by a small number of input/output examples. A class of text processing programs called gap programs is defined and the problems associated with synthesizing them from examples are examined, leading to an efficient heuristic that provably synthesizes a gap program from examples of its input/output behavior. The editing by example system derived from this analysis has been embedded in a production text editor. By developing an editing by example system that solves a useful class of text processing problems, this work demonstrates that program synthesis is feasible in the domain of text editing.

REFERENCES

• 1: AHO, A. V., KERNIGHAN, B. W., AND WEINBERGER, P.J. AWK--A pattern matching and scanning language. Softw. Pract. Exper. 9, 4 (April 1979), 267-280.
• 2: ANGLUIN, D. Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21 (1980), 46-62.
• 3: ANGLUIN, D., AND SMITH, C. A survey of inductive inference: theory and methods. Res. Rep. 250, Dep. Computer Science, Yale University, Oct. 1982.
• 4: BIERMANN, A. W., AND FELDMAN, J. A. A survey of results in grammatical inference. In Frontiers of Pattern Recognition, Academic Press, New York, 1972.
• 5: Gael Alan Curry, Programming by abstract demonstration., 1978
• 6: ELLIS, J. R., MISHKIN, N. W., NIX, R. P., AND WOOD, S.R. A BLISS programming environment. Res. Rep. 231, Dep. Computer Science, Yale University, June 1982.
• 7: ELLIS, J. R., MISHKIN, N. W., VAN LEUNEN, M.-C., AND WOOD, S.R. Tools: An environment for timeshared computing and programming. Softw. Pract. Exper. (Oct. 1983).
• 8: Fu, K. S., AND BOOTH, T.L. Grammatical inference: Introduction and survey, parts I and 2. IEEE Trans. Syst. Man, Cybern. SMC-5 (1975), 95-111 and 409-423.
• 9: GOLD, E.M. Language identification in the limit. Inf. Control 10 (1967), 447-474.
• 10: Daniel Conrad Halbert, Programming by example, 1984
• 11: D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
• 12: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 13: James W. Hunt , Thomas G. Szymanski, A fast algorithm for computing longest common subsequences, Communications of the ACM, v.20 n.5, p.350-353, May 1977 [doi>10.1145/359581.359603]
• 14: Edgar T. Irons , Frans M. Djorup, A CRT editing system, Communications of the ACM, v.15 n.1, p.16-20, Jan. 1972 [doi>10.1145/361237.361244]
• 15: Donald E. Knuth, The TEXbook, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 16: Henry Lieberman , Carl Hewitt, A session with Tinker: Interleaving program testing with program design, Proceedings of the 1980 ACM conference on LISP and functional programming, p.90-99, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802794]
• 17: David Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM (JACM), v.25 n.2, p.322-336, April 1978 [doi>10.1145/322063.322075]
• 18: Norman Meyrowitz , Andries van Dam, Interactive Editing Systems: Part II, ACM Computing Surveys (CSUR), v.14 n.3, p.353-415, Sept. 1982 [doi>10.1145/356887.356890]
• 19: James H. Morris , Eric Schmidt , Philip Wadler, Experience with an applicative string processing language, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-46, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567450]
• 20: NIx, R.P. Editing by example. Ph.D. dissertation, Dep. Computer Science, Yale University, 1983; also appeared as Yale University Dep. Computer Science Res. Rep. 280.
• 21: Robert Nix, Editing by example, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.186-195, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800530]
• 22: NIX, R. P., AND MISHKIN, N.W. U Editor user's and programmer's manual. Internal memo., Dep. Computer Science, Yale University, 1983.
• 23: Jonathan A. Rees , Norman I. Adams IV, T: a dialect of Lisp or LAMBDA: The ultimate software tool, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.114-122, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802142]
• 24: REES, J. A., AND ADAMS, N.I. T user's manual. Internal memo., Dep. Computer Science, Yale University, 1982.
• 25: Brian K. Reid, A high-level approach to computer document formatting, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.24-31, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567449]
• 26: Takeshi Shinohara, Polynomial Time Inference of Extended Regular Pattern Languages, Proceedings of RIMS Symposium on Software Science and Engineering, p.115-127, January 1983
• 27: SHINOHARA, T. Polynomial time inference of pattern languages and its application. In Proc. 7th IBM Syrup. Mathematical Foundations of Computer Science, 1982.
• 28: SMITH, D.C. Pygmalion: A computer program to model and stimulate creative thought. Ph.D. dissertation, Computer Science Dep., Stanford University, 1975; also appeared as AIM-260, June 1975, and as a book from Birkbauser Verlag, 1977.
• 29: Richard M. Stallman, EMACS the extensible, customizable self-documenting display editor, Proceedings of the ACM SIGPLAN SIGOA symposium on Text manipulation, p.147-156, June 08-10, 1981, Portland, Oregon, United States
• 30: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 31: Steven R. Wood, Z - the 95% program editor, Proceedings of the ACM SIGPLAN SIGOA symposium on Text manipulation, p.1-7, June 08-10, 1981, Portland, Oregon, United States

INDEX TERMS

Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.1 Office Automation
          Subjects: Word processing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing
      I.5.5 Implementation
          Subjects: Interactive systems
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Languages**

General Terms:
Algorithms, Design, Languages, Theory