Browse Prior Art Database

Efficient Abstractions for the Implementation of Structured Editors

IP.com Disclosure Number: IPCOM000128270D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 7 page(s) / 25K

Publishing Venue

Software Patent Institute

Related People

Robert Hood: AUTHOR [+3]

Abstract

This paper investigates the use of abstract recursive data structures and operations in the implementation of a structured program editor. The value-oriented semantics of paths simplify the implementation of important features such as version control and an unbounded undo operation. Since paths can be implemented efficiently, their use in the structured program editor does not significantly affect its performance.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 20% of the total text.

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Efficient Abstractions for the Implementation of Structured Editors*

(summary)

Robert Hood

Rice COW TR84-3 October 1984

Department of Computer Science Rice University P.O. Box 1892 Houston, TX 77251-1892

(713) 527-8101

*This research has been supported in part by National Science Foundation grants ISMS 78- 05850, NICS-8104006, and MCS-8121884 and by International Business Machines Corporation under -a Faculty Development Award.

Abstract

This paper investigates the use of abstract recursive data structures and operations in the implementation of a structured program editor. The value-oriented semantics of paths simplify the implementation of important features such as version control and an unbounded undo operation. Since paths can be implemented efficiently, their use in the structured program editor does not significantly affect its performance.

1. Introduction

In conventional high-level languages, the implementation of structured program editors is complicated by the lack of appropriate abstract data structures and operations for describing and manipulating an abstract syntax tree. As a result, programmers are forced to use pointers an . d records (or a simulation of, pointers and records using arrays) explicitly to represent the tree, an'd destructive operations to manipulate it. Even in languages like Lisp or Algol 68 that support abstract recursive data structures, implementors typically resort to "impure" (destructive) pointer operations (such as rplaca) in an attempt to make their programs more efficient.

Destructive pointer operations make it significantly harder to reason about the program, both forTnally and informally. Since abstraction is not being provided at the prog z gramming language lev-el, anyone who wants to understand the program must map the machine representation back into the abstract data object. When a programmer implements such an object with destructive opera-tions, he is responsible for ensuring that those operations are well- defined at the abstract level.

In a structured editor, pointers are usually used in a disciplined way: to select and modify unshared values within the abstract syntax tree. In a previous paper[4], we proposed an abstract alternative to pointers, the path, which captures such uses. Paths provide an

Rice University Page 1 Dec 31, 1984

Page 2 of 7

Efficient Abstractions for the Implementation of Structured Editors

abstraction for the disciplined uses of pointers in a manner similar to the way that do loops provide an ab-z-;raction for the disciplined use of go to's.

In the next section we discuss a collection of high-level language features including paths that would ease the burden on the structured editor implementor. In the third section we investigate how the use of those features would impact the structured- editor. In the fourth section we discuss strategies for implementing the language features described.

!This...