Parallel and distributed incremental attribute evaluation algorithms for multiuser software development environments

ABSTRACT

The problem of change propagation in multiuser software development environments distributed across a local-area network is addressed. The program is modeled as an attributed parse tree segmented among multiple user processes and changes are modeled as subtree replacements requested asynchronously by individual users. Change propagation is then implemented using decentralized incremental evaluation of an attribute grammar that defines the static semantic properties of the programming language. Building up to our primary result, we first present algorithms that support parallel evaluation on a centralized tree in response to single edits using a singe editing cursor and multiple edits with multiple editing cursors. Then we present our algorithm for parallel evaluation on a decentralized tree. We also present a protocol to guarantee reliability of the evaluation algorithm as components of the decentralized tree become unavailable due to failures and return to availability.

REFERENCES

• 1: Evan W. Adams , Masahiro Honda , Terrence C. Miller, Object management in a CASE environment, Proceedings of the 11th international conference on Software engineering, p.154-163, May 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74587.74610]
• 2: Naser S. Barghouti , Gail E. Kaiser, Concurrency control in advanced database applications, ACM Computing Surveys (CSUR), v.23 n.3, p.269-317, Sept. 1991 [doi>10.1145/116873.116875]
• 3: Gregor V. Bochmann, Semantic evaluation from left to right, Communications of the ACM, v.19 n.2, p.55-62, Feb. 1976 [doi>10.1145/359997.359999]
• 4: BOEHM, H.-J., AND ZWAENEPOEL, W. Parallel attribute grammar evaluation. In 7th International Conference on Distributed Computing- Systems (Berlin, Germany, Sept.). 1987, pp. 347-354.
• 5: COOPER, E. C., AND DRAVES, R. r. C threads. Tech. Rep. CMU-CS-88-154, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa., June 1988.
• 6: 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]
• 7: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 8: FELDMAN, S. I. Make--A program for maintaining computer programs. Softw. Pract. Exper. 9, 4 (Apr. 1979), 255-265.
• 9: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 10: GARClA-MoL~NA, H. Elections in a distributed computing system. IEEE Trans. Comput. C-31, 1 (Jan. 1982), 48-59.
• 11: David Garlan, Views for tools in integrated environments, An international workshop on Advanced programming environments, p.314-343, January 1986, Trondheim, Norway
• 12: GEITZ, B. Asynchronous subtree replacement for language-based editors. Oberlin College and Cornell Univ., Dept. of Computer Science, Ithaca, N.Y., 1987.
• 13: Irene Greif, Computer-supported cooperative work: a book of readings, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 14: HARRISON, W. RPDE3: A framework for integrating tool fragments. IEEE Softw. 4, 6 (Nov. 1987), 46 56.
• 15: HENDERSON, P., ED. ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments. SIGPLAN Not. (ACM) 22, 1 (Jan. 1987).
• 16: M. Herlihy, A methodology for implementing highly concurrent data structures, ACM SIGPLAN Notices, v.25 n.3, p.197-206, Mar. 1990
• 17: R. Hoover, Incremental graph evaluation (attribute grammar), Cornell University, Ithaca, NY, 1987
• 18: Roger Hoover , Tim Teitelbaum, Efficient incremental evaluation of aggregate values in attribute grammars, ACM SIGPLAN Notices, v.21 n.7, p.39-50, July 1986
• 19: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 20: ~HSEUSH, W., AND KAISER, G.E. A network architecture for reliable distributed computing. ~IEEE Network 2, 4 (July 1988), 28-44.
• 21: Scott E. Hudson , Roger King, Cactis: a self-adaptive, concurrent implementation of an object-oriented database management system, ACM Transactions on Database Systems (TODS), v.14 n.3, p.291-321, Sept. 1989 [doi>10.1145/68012.68013]
• 22: ~KAISER, G. E., AND KAPLAN, S.M. Reliability in distributed programming environments. In ~6th Symposium on Reliability in Distributed Software and Database Systems (Kingsmill- ~Williamsburg, Va., Mar. 17-19, 1987). IEEE, New York, 1987, pp. 45-55.
• 23: ~KArSER, G. E., AND PERRY, D. E. Workspaces and experimental databases: Automated ~support for software maintenance and evolution. In Conference on Software Maintenance ~(Austin, Tex., Sept. 21-24, 1987). IEEE, New York, 1987, pp. 108-114.
• 24: ~KAISER, G. E., KAPLAN, S. M., AND MICALLEF, J. Multiuser, distributed language-based ~environments. IEEE Softw. 4, 6 (Nov. 1987), 58-67.
• 25: ~KAPLAN, S. M. Incremental attribute evaluation on node-label controlled graphs. Tech. ~Rep. UIUCDCS-R-87-1309, Dept. of Computer Science, Univ. of Illinois at Urbana- ~Champaign, May 1987.
• 26: Simon M Kaplan , Gail E Kaiser, Incremental attribute evaluation in distributed language-based environments, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.121-130, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10601]
• 27: ~KASTENS, U. Ordered attribute grammars. Acta Inf. 13 (1980), 229-256.
• 28: ~KNUTH, D.E. Semantics of context-free languages. Math. Syst. Theory 2, 2 (June 1968), ~127-145.
• 29: ~KNUTH, D. E. Semantics of context-free languages: Correction. Math. Syst. Theory 5, 1 ~(Mar. 1971), 95-96.
• 30: Butler W. Lampson , Eric E. Schmidt, Organizing software in a distributed environment, Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems, p.1-13, June 27-29, 1983, San Francisco, California, United States
• 31: David B. Leblang , Robert P. Chase, Jr., Computer-Aided Software Engineering in a distributed workstation environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.104-112, April 1984
• 32: ~LEBLANG, D. B., AND CHASE, R. P., JR. Parallel software configuration management in a ~network environment. IEEE Softw. 4, 6 (Nov. 1987), 28 35.
• 33: ~MAAREK, Y. S., AND KAISER, G.E. Change management for very large software systems. In ~7th Annual International Phoenix Conference on Computers and Communicattons (Scotts- ~dale, Ariz., Mar.). IEEE, New York, 1988, pp. 280-285.
• 34: ~MICALLEF, J. Incremental evaluation of ordered attribute grammars for asynchronous ~subtree replacements. Tech. Rep. CUCS-380-88, Dept. of Computer Science, Columbia ~Univ., New York, July 1988.
• 35: Josephine Micallef, Incremental attribute evaluation for multi-user semantics-based editors, Columbia University, New York, NY, 1992
• 36: ~MICALLEF, J., AND KAISER, G. E. Version and configuration control in distributed ~language-based environments. In International Workshop on Software Version and Config- ~uration Control, J. F. H. Winkler, Ed. German Chapter of the ACM Berichte, vol. 30. ~Teubner, Grassau, Germany, Jan. 1988, pp. 119 143.
• 37: Josephine Micallef , Gail E. Kaiser, Extending the MERCURY system to support teams of Ada programmers, ACM SIGAda Ada Letters, v.XI n.3, p.49-60, Spring 1991
• 38: J. Micallef , G. E. Kaiser, Support Algorithms for Incremental Attribute Evaluation of Asynchronous Subtree Replacements, IEEE Transactions on Software Engineering, v.19 n.3, p.231-252, March 1993 [doi>10.1109/32.221136 ]
• 39: ~NEUHOLD, E., ANn STONEBatKER, M., EDS. Future directions in DBMS research. SIGMOD ~Rec. 18, i (Mar. 1989), 17-26.
• 40: Stephen B. Peckham, Incremental attribute evaluation and multiple subtree replacements, Cornell University, Ithaca, NY, 1990
• 41: ~PERRY, D. E., AND EVANGELIST, W.M. An empirical study of software interface errors. In ~International Symposium on New Dtrecttons tn Computing (Trondheim, Norway, Aug.). ~IEEE, New York, 1985, pp. 32-38
• 42: ~PERRY, D. E., AND EVANCELIST, W.M. An empirical study of software interface faults An ~update. In 20th Annual Hawaz~ International Conference on Systems Sciences, vol. II (Kona, ~Hawaii, Jan. 6 9, 1987), Western Periodicals Company, North Hollywood, CA, 1987, pp. ~113 126.
• 43: Thomas Reps, Optimal-time incremental semantic analysis for syntax-directed editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.169-176, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582172]
• 44: Thomas William Reps, Generating language-based environments, 1982
• 45: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator: a system for constructing language-based editors, Springer-Verlag New York, Inc., New York, NY, 1989
• 46: 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]
• 47: 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]
• 48: ~ROWE, A. L. Report on the 1989 software CAD databases workshop. In 11th World ~Computer Conference IFIP Congress '89, (San Francisco CA, Aug 28-Sept. 1, 1989), ~Elsevier Science Publishers B.V, pp. 719-725.
• 49: Robert W. Schwanke , Gail E. Kaiser, Smarter recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.627-632, Oct. 1988 [doi>10.1145/48022.214505]
• 50: R. W. Schwanke , E. S. Cohen , R. Gluecker , W. M. Hasling , D. A. Soni , M. E. Wagner, Configuration management in BiiN SMS, Proceedings of the 11th international conference on Software engineering, p.383-393, May 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74587.74640]
• 51: 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]
• 52: ~SUN MICROSYSTEMS, INC. SunOS Reference Manual Sectton 3L Lightweight Processes ~L,brary, Nov. 1987.
• 53: Walter F. Tichy, RCS—a system for version control, Software—Practice & Experience, v.15 n.7, p.637-654, July 1985 [doi>10.1002/spe.4380150703]
• 54: Walter F. Tichy, Smart recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.273-291, July 1986 [doi>10.1145/5956.5959]
• 55: ~WINFREY, T. L., AND KAISER, G. E. Testing reliable distributed applications through ~simulated events. In 8th Symposium on Reliable Distributed Systems, (Seattle WA, Oct. ~1989), pp. 160 166.
• 56: Alan Keith Zaring, Parallel evaluation in attribute grammar-based systems, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Interactive environments

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Computer-aided software engineering (CASE); Modules and interfaces
      D.2.3 Coding Tools and Techniques
          Subjects: Program editors
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

General Terms:
Algorithms, Design, Languages, Reliability

Keywords:
attribute grammar, change propagation, distributed, incremental algorithm, parallel, reliability