Editing by example

• Published in: ACM transactions on programming languages and systems 1985-10, Vol.7 (4), p.600-621
• Main Author: Nix, Robert P.
• Format: Article
• Language: English
• Subjects: Applied computing; Applied sciences; Artificial intelligence; Arts and humanities; Computer science; control theory; systems; Computer-assisted instruction; Computers in other domains; Document management and text processing; Document preparation; Document scripting languages; Education; Exact sciences and technology; Human computer interaction (HCI); Human-centered computing; Interactive systems and tools; Language translation; Pattern recognition. Digital image processing. Computational geometry; Personal computers and PC applications; Word processors
• ISSN: 0164-0925; 1558-4593
• DOI: 10.1145/4472.4476

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.