Generating editing environments based on relations and attributes

ABSTRACT

The ability to generate language-based editors depends on the existence of a powerful, language-independent model of editing. A model is proposed in which programs are represented as attributed abstract-syntax trees with an associated relational database. Relations can depend on the state of the attributed tree, and attributes can depend on the values in relations, provided there are no circular dependencies. The power and the limitations of relational operations are demonstrated with respect to the support of static-semantic checking, anomaly detection, an interrogation facility, and the ability to define alternative program displays. The advantages of the hybrid system over both the purely relational and purely attribute-based systems are presented, and new algorithms are given for query evaluation and incremental view updating motivated by the efficiency requirements of interactive editing under the defined model. A prototype implementation of an editor generator is described, and suggestions for future research are made.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 2: George McArthur Beshers , Roy Harold Campbell, Maintained and constructor attributes, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.34-42, June 25-28, 1985, Seattle, Washington, United States
• 3: Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
• 4: W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
• 5: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 6: Alan Demers , Anne Rogers , Frank Kenneth Zadeck, Attribute propagation by message passing, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.43-59, June 25-28, 1985, Seattle, Washington, United States
• 7: DONZEAU-GOuGE, V., HUET, G., KAHN, G., AND LANG, B. Programming environments based on structured editors: The MENTOR experience. INRIA Rapports de Recherche 26 (July 1980).
• 8: Stefan M. Freudenberger, On the use of global optimization algorithms for the detection of semantic programming errors (setl, data flow, type finding), 1984
• 9: Will Dean Gillett, Iterative global flow techniques for detecting program anomalies., 1977
• 10: Susan Beth Horwitz, Generating language-based editors: a relationally-attributed approach, 1985
• 11: JOU~SON, G. An approach to incremental semantics. Ph.D. thesis, Univ. of Wisconsin- Madison, 1983.
• 12: KASTENS, U. Ordered attribute grammars. Acta Inf. 13, 3 (1980), 229-256.
• 13: KNUTH, D. E. Semantics of context-free languages. Math. Syst. Theor. 2, 2 (June 1968), 127-145.
• 14: KNUTH, D.E. Correction. Math. Syst. Theor. 5, i (Mar. 1971), 95-96.
• 15: KOENIG, S., AND PAIGE, R. A transformational framework for the automatic control of derived data. In Proceedings of the 7th International Conference on Very Large Data Bases (Cannes, France, Sept. 1981), 306-318.
• 16: Mark A. Linton, Implementing relational views of programs, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.132-140, April 1984
• 17: Larry Melvin Masinter, Global program analysis in an interactive environment, 1980
• 18: OSTERWEIL, L. J., AND FOSDICK, L.D. DAVE--A validation error detection and documentation system for FORTRAN programs. Softw. Pract. Exper. 6 (1976), 473-486.
• 19: RAIHA, K., AND SAARINEN, J. Testing attribute grammars for circularity. Acta Inf. 17, 2 (June 1982), 185-192.
• 20: Steven P. Reiss, Graphical program development with PECAN program development systems, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.30-41, April 1984
• 21: Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 22: Thomas Reps , Tim Teitelbaum, The synthesizer generator, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.42-48, April 1984
• 23: Thomas W. Reps , Carla Marceau , Tim Teitelbaum, Remote attribute updating for language-based editors, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-13, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512645]
• 24: Oded Shmueli , Alon Itai, Maintenance of views, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 25: Richard Snodgrass, Monitoring in a software development environment: A relational approach, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.124-131, April 1984
• 26: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 27: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Program editors
  D.3 PROGRAMMING LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Documentation, Languages