Unification in many-sorted algebras as a device for incremental semantic analysis

ABSTRACT

Language-specific editors for typed programming languages must contain a subsystem for semantic analysis in order to guarantee correctness of programs with respect to the context conditions of the language. As programs are usually incomplete during development, the semantic analysis must be able to cope with missing context information, e. g. incomplete variable declarations or calls to procedures imported from still missing modules. In this paper we present an algorithm for incremental semantic analysis, which guarantees immediate detection of semantic errors even in arbitrary incomplete program fragments. The algorithm is generated from the language's context conditions, which are described by inference rules. During editing, these rules are evaluated using a unification algorithm for many-sorted algebras with semi-lattice ordered subsorts and non-empty equational theories. The method has been implemented as part of the PSG system, which generates interactive programming environments from formal language definitions, and has been successfully used to generate an incremental semantic analysis for PASCAL and MODULA-2.

REFERENCES

• 1: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 2: /Aust83/ Austermühl, B.: Ein relationaler Ansatz zur Beschreibung der statischen Semantik von Programmiersprachen. PhD thesis, Technische Hochschule Darmstadt 1983
• 3: Rolf Bahlke , Gregor Snelting, The PSG - Programming System Generator, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.28-33, June 25-28, 1985, Seattle, Washington, United States
• 4: 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]
• 5: /Hab82/ Habermann, N. et al: The second compendium of Gandalf documentation. Dept. of Computer science, Carnegie Mellon University 1982
• 6: Wolfgang Henhapl , Gregor Snelting, Context Relations - a Concept for Incremental Context Analysis in Program Fragments, Programmiersprachen und Programmentwicklung, 8. Fachtagung, veranstaltet vom Fachausschuß 2.1 der GI und der Schweizer Informatiker Gesellschaft, p.128-143, March 08-09, 1984
• 7: /HuSc83/ Hunkel, M., Schmitt, H.: Ein System zur Bezeichneridentifikation und dessen Integration in ein strukturorientiertes Ediersystem. Diploma thesis, Technische Hochschule Darmstadt 1983.
• 8: /Miln78/ Milner, R.: A theory of type polymorphism in programming. J. Computer and system sciences 17 (1978), pp. 348--375
• 9: /PSG85/ Bahlke, R., Hunkel,M., Klung, M., Snelting, G.: Language definers guide to PSG. Report PU2R3/85, Technische Hochschule Darmstadt, 1985.
• 10: /Plo72/ Plotkin, G.: Building in equational theories. Machine intelligence 7 (1972), pp. 73--90
• 11: 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]
• 12: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 13: Jörg H. Siekmann, Universal Unification, Proceedings of the 7th International Conference on Automated Deduction, p.1-42, May 14-16, 1984
• 14: /Snel85/ Snelting, G.: Inkrementelle semantische Analyse in unvollstandigen Programmfragmenten mit Kontextrelationen. PhD thesis. Technische Hochschule Darmstadt 1985.