Incremental dynamic semantics for language-based programming environments

ABSTRACT

Attribute grammars are a formal notation for expressing the static semantics of programming languages—those properties that can be derived from inspection of the program text. Attribute grammars have become popular as a mechanism for generating language-based programming environments that incrementally perform symbol resolution, type checking, code generation, and derivation of other static semantic properties as the program is modified. However, attribute grammars are not suitable for expressing dynamic semantics—those properties that reflect the history of program execution and/or user interactions with the programming environment. This paper presents action equations, an extension of attribute grammars suitable for specifying the static and the dynamic semantics of programming languages. It describes how action equations can be used to generate language-based programming environments that incrementally derive static and dynamic properties as the user modifies and debugs th e program.

REFERENCES

• 1: AMBRIOLA, V., KAISER, G. E., AND ELLISON, R.J. An action routine model for ALOE. Tech. Rep. CMU-CS-84-156, Carnegie Mellon Univ., Dept. of Computer Science, Aug. 1984.
• 2: ARCHER, J. E., JR., AND DEVLIN, U.T. Rational's experience using Ada for very large systems. In First International Conference on Ada Programming Language Applications for the NASA Space Station (Houston, Tex., June 1986). NASA, 1986, pp. B.2.5.1-B.2.5.11.
• 3: Rolf Bahlke , Gregor Snelting, The PSG system: from formal language definitions to interactive programming environments, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.547-576, Oct. 1986 [doi>10.1145/6465.20890]
• 4: Robert Balzer, A 15 year perspective on automatic programming, IEEE Transactions on Software Engineering, v.11 n.11, p.1257-1268, Nov. 1985 [doi>10.1109/TSE.1985.231877]
• 5: BARBUTI, R., BELLIA, M., DEGANO, P., LEVI, G., DAMERI, E., SIMONELLI, C., AND MARTELL{, A. Programming environment generation based on denotational semantics. In Theory and Practice of Software Technology. North-Holland, New York, 1983.
• 6: James Bodwin , Laurette Bradley , Kohji Kanda , Diane Litle , Uwe Pleban, Experience with an experimental compiler generator based on denotational semantics, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.216-229, June 23-25, 1982, Boston, Massachusetts, United States
• 7: Norman M. Delisle , David E. Menicosy , Mayer D. Schwartz, Viewing a programming environment as a single tool, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.49-56, April 1984
• 8: Alan Demers , Thomas Reps , Tim Teitelbaum, Incremental evaluation for attribute grammars with application to syntax-directed editors, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-116, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567544]
• 9: 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
• 10: DESPEYROUX, V. Executable specification of static semantics. In Semantics of Data Types International Symposium, Lecture Notes in Computer Science 173. Springer, New York, 1984, pp. 215-233.
• 11: DONZEAU-GOUGE, V., HUET, G., KAHN, G., AND LANG, B. Programming environments based on structured editors: the Mentor experience. In Interactive Programming Environments, D. R. Barstow, H. E. Shrobe, and E. Sandewall, Eds. McGraw-Hill, New York, 1984, pp. 128-140.
• 12: V. Donzeau-Gouge , G. Kahn , B. Lang , B. Mélèse, Document structure and modularity in mentor, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.141-148, April 1984
• 13: ENGELS, C., GALL, R., NAGL, M., AND SCHAFER, W. Software specification using graph grammars. Computing 31 (1983), 317-346.
• 14: FARROW, R. Generating a production compiler from an attribute grammar. IEEE Softw. 1, 4 (Oct. 1984), 77-93.
• 15: Rodney Farrow, Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.85-98, June 25-27, 1986, Palo Alto, California, United States
• 16: Peter Hermann Feiler, A language-oriented interactive programming environment based on compilation technology, 1982
• 17: FELLER, P. H., JALILI, F., AND SCHLICHTER, J.H. An interactive prototyping environment for language design. In 19th Hawaii International Conference on System Sciences (Honolulu, Hawaii, Jan. 1986). pp. 106-116.
• 18: FELLER, P. H., AND MEDINA-MORA, R. An incremental programmingenvironment. IEEE Trans. Softw. Eng. SE-7, 5 (Sept. 1981), 472-482.
• 19: P. Freeman, A conceptual analysis of the Draco approach to constructing software systems, IEEE Transactions on Software Engineering, v.13 n.7, p.830-844, July 1987 [doi>10.1109/TSE.1987.233494]
• 20: GANZlNGER, H., RIPKEN, K., AND WILHELM, R. Automatic generation of optimizing multipass compilers. Information Processing 77 (New York, 1977). North-Holland, Amsterdam, 1977, pp. 535-540.
• 21: GARLAN, D. Flexible unparsing in a structure editing environment. Tech. Rep. CMU-CS-85- 129, Dept. of,Computer Science, Carnegie Mellon Univ., April 1985.
• 22: David Barnard Garlan, Views for tools in integrated environments, 1987
• 23: Carlo Ghezzi , Dino Mandrioli, Augmenting Parsers to Support Incrementality, Journal of the ACM (JACM), v.27 n.3, p.564-579, July 1980 [doi>10.1145/322203.322215]
• 24: A N Habermann , D Notkin, Gandalf: software development environments, IEEE Transactions on Software Engineering, v.12 n.12, p.1117-1127, Dec.1986
• 25: Peter Henderson , Mark Weiser, Continuous execution: the VisiProg environment, Proceedings of the 8th international conference on Software engineering, p.68-74, August 28-30, 1985, London, England
• 26: Roger Hoover, Dynamically bypassing copy rule chains in attribute grammars, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.14-25, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512646]
• 27: Roger Hoover , Tim Teitelbaum, Efficient incremental evaluation of aggregate values in attribute grammars, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.39-50, June 25-27, 1986, Palo Alto, California, United States
• 28: Susan Horwitz , Tim Teitelbaum, Generating editing environments based on relations and attributes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.577-608, Oct. 1986 [doi>10.1145/6465.6512]
• 29: Roger King , Scott Hudson, Implementing a user interface as a system of attributes, Proceedings of the second ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.143-149, December 09-11, 1986, Palo Alto, California, United States
• 30: Mehdi Jazayeri , William F. Ogden , William C. Rounds, The intrinsically exponential complexity of the circularity problem for attribute grammars, Communications of the ACM, v.18 n.12, p.697-706, Dec. 1975 [doi>10.1145/361227.361231]
• 31: G. F. Johnson, GL—a denotational testbed with continuations and partial continuations as first-class objects, Papers of the Symposium on Interpreters and interpretive techniques, p.165-176, June 24-26, 1987, St. Paul, Minnesota, United States
• 32: Gregory F. Johnson , Charles N. Fischer, Non-syntactic attribute flow in language based editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.185-195, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582174]
• 33: Gregory F. Johnson , C. N. Fischer, A meta-language and system for nonlocal incremental attribute evaluation in language-based editors, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.141-151, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318627]
• 34: JOHNSON, S. C., AND LEAK, M.E. Language development tools. Bell Syst. Tech. J. 57, 6 (July- Aug. 1978), 2155-2175.
• 35: KAmER, G. E. Semantics of structure editing environments. Ph.D. dissertation, Tech. Rep. CMU-CS-85-131, Carnegie Mellon Univ., May 1985.
• 36: G. E. Kaiser, Concurrent meld, Proceedings of the 1988 ACM SIGPLAN workshop on Object-based concurrent programming, p.120-122, September 1988, San Diego, California, United States
• 37: Gail E. Kaiser , Peter H. Feiler , Fahimeh Jalili , Joann H. Schlichter, A retrospective on DOSE: an interpretive approach to structure editor generation, Software—Practice & Experience, v.18 n.8, p.733-748, August 1988 [doi>10.1002/spe.4380180803]
• 38: KAISER, G. E., AND GARLAN, D. Melding software systems from reusable building blocks. IEEE Softw. (July 1987), 17-24.
• 39: KAISER, G. E., AND KANT, E. Incremental parsing without a parser. J. Syst. Softw. 5, 2 (May 1985), 121-144.
• 40: KAISER, G. E., AND KAPLAN, S.M. Rapid prototyping of concurrent programming languages. In 8th International Conference on Distributed Computing Systems (San Jose, Calif., June 1988). IEEE, New York, 1988, pp. 250-255.
• 41: KAISER, G. E., KAPLAN, S. M., AND MICALLEF, J. Multiuser, distributed language-based environments. IEEE Softw. (Nov. 1987), 58-67.
• 42: KASTENS, U., HUTT, B., AND ZIMMERMANN, E. GAG: A Practical Compiler Generator. Lecture Notes in Computer Science, 141. Springer-Verlag, Heidelberg, 1982.
• 43: KNUTH, D.E. Semantics of context-flee languages. Math. Syst. Theor. 2, 2 (June 1968), 127- 145.
• 44: David Alex Lamb, IDL: sharing intermediate representations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.297-318, July 1987 [doi>10.1145/24039.24040]
• 45: Raul I. Medina-Mora, Syntax-directed editing: towards integrated programming environments, 1982
• 46: David Samuel Notkin, Interactive structure-oriented computing, 1984
• 47: H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983 [doi>10.1145/356914.356917]
• 48: Lawrence Paulson, A semantics-directed compiler generator, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.224-233, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582178]
• 49: Martin R. Raskovsky, Denotational semantics as a specification of code generators, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.230-244, June 23-25, 1982, Boston, Massachusetts, United States
• 50: 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
• 51: Steven P. Reiss, An approach to incremental compilation, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.144-156, June 17-22, 1984, Montreal, Canada
• 52: 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]
• 53: 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
• 54: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 55: SCOTT, n., AND STRACHEY, C. Toward a mathematical semantics for computer languages. Tech. Rep. Tech. Monograph PRG-6, Oxford Univ. Computing Lab., Aug. 1971.
• 56: S. T. Shebs , R. R. Kessler, Automatic design and implementation of language data types, Papers of the Symposium on Interpreters and interpretive techniques, p.26-37, June 24-26, 1987, St. Paul, Minnesota, United States
• 57: Douglas R. Smith , Gordon B. Kotik , Stephen J. Westfold, Research on knowledge-based software environments at Kestrel Institute, IEEE Transactions on Software Engineering, v.11 n.11, p.1278-1295, Nov. 1985 [doi>10.1109/TSE.1985.231879]
• 58: Richard Snodgrass , Karen Shannon, Supporting flexible and efficient tool integration, An international workshop on Advanced programming environments, p.290-313, January 1986, Trondheim, Norway
• 59: Tim Teitelbaum , Thomas Reps, The Cornell program synthesizer: a syntax-directed programming environment, Communications of the ACM, v.24 n.9, p.563-573, Sept. 1981 [doi>10.1145/358746.358755]
• 60: TEITELMAN, W., AND MASINTER, L. The Interlisp programming environment. IEEE Comput. 14, 4 (April 1981), 25-34.
• 61: J. A. Walz , G. F. Johnson, Incremental evaluation for a general class of circular attribute grammars, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.209-221, June 20-24, 1988, Atlanta, Georgia, United States
• 62: Richard C Waters, KBEmacs: Where's the AI?, AI Magazine, v.7 n.1, p.57-61, March 1986
• 63: WEGMAN, M.N. Parsing for structural editors. In 21st Annual Symposium on Foundations of Computer Science (Oct. 1980). IEEE, New York, pp. 320-327.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Program editors
      D.2.5 Testing and Debugging
          Subjects: Debugging aids
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

General Terms:
Algorithms, Design, Languages, Reliability, Theory