Editing by example
Robert P. Nix · ACM Transactions on Programming Languages and Systems · 1985
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.
Cited by 101 works. doi:10.1145/4472.4476 Open-access PDF
Authors
References
- Introduction to automata theory, languages and computation
- The String-to-String Correction Problem
- Language identification in the limit
- A linear space algorithm for computing maximal common subsequences
- Frontiers of Pattern Recognition
- A fast algorithm for computing longest common subsequences
- The TeXbook
- Finding patterns common to a set of strings
- EMACS the extensible, customizable self-documenting display editor
- The Complexity of Some Problems on Subsequences and Supersequences