A general scheme for the automatic inference of variable types

ABSTRACT

We present the best known algorithm for the determination of run-time types in a programming language requiring no type declarations. We demonstrate that it is superior to other published algorithms and that it is the best possible algorithm from among all those that use the same set of primitive operators.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 2: {B} Bauer, A. M. and H. J. Saal, 'Does APL really need run-time checking?', Software - Practice and Experience, Vol. 4, 1974, pp. 129-138
• 3: {D} Donnellan, T., Lattice Theory, Pergamon Press
• 4: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 5: Neil D. Jones , Steven S. Muchnick, Binding time optimization in programming languages: Some thoughts toward the design of an ideal language, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.77-94, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811542]
• 6: Matthew S. Hecht , Jeffrey D. Ullman, Analysis of a simple algorithm global data flow problems, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.207-217, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512946]
• 7: {Ka} Kam, J. B. and J. D. Ullman, "Monotone Data Flow Analysis Frameworks", Acta Informatica, Vol. 7, January 1977, pp. 305-317
• 8: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 9: {M} Muchnick, S. S., Private communication. August 1977
• 10: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 11: {S} Scott, D., Data Types as Lattices, Unpublished lecture notes, Mathematical Centre, Amsterdam, June 1972, see also a paper of the same name in SIAM Journal of Computing, Vol. 5, No. 3, September 1976, pp. 522-587
• 12: Tenenbaum, A., Type Determination for Very High Level Languages, Report NSO-3, Courant Institute of Mathematical Sciences, New York University. 1974