Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We introduce a new algorithm to analyze recursive, structured types. It derives information from object uses (accesser functions with type checking), as well as from object allocation. The type description is a form of graph grammar and is naturally finite even in the presence of loops. The intended use of the algorithm is to discover and remove unnecessary type checks, but it can be augmented to provide alias information as well.

REFERENCES

• 1: Henry G. Baker, Unify and conquer, Proceedings of the 1990 ACM conference on LISP and functional programming, p.218-226, June 27-29, 1990, Nice, France [doi>10.1145/91556.91652]
• 2: Randall D. Beer. Preliminary report on a practical type inference system for Common Lisp. Lisp Pointers, 1(2):5-12, June-July 1987.
• 3: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States [doi>10.1145/93542.93585]
• 4: Carsten K. Gomard, Partial type inference for untyped functional programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.282-287, June 27-29, 1990, Nice, France [doi>10.1145/91556.91672]
• 5: Philip Meadows Johnson , Jack Wileden , Victor Lesser, Type flow analysis for exploratory software development, 1990
• 6: 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]
• 7: Neil D. Jones and Steven S. Muchnick. Flow analysis and optimization of Lisp-like structures. In Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis: Theory and Applications. Prentice-Hall, 1981.
• 8: Marc A. Kaplan , Jeffrey D. Ullman, A general scheme for the automatic inference of variable types, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.60-75, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512768]
• 9: Marc A. Kaplan , Jeffrey D. Ullman, A Scheme for the Automatic Inference of Variable Types, Journal of the ACM (JACM), v.27 n.1, p.128-145, Jan. 1980 [doi>10.1145/322169.322181]
• 10: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States [doi>10.1145/53990.53993]
• 11: K.-L. Ma , R. R. Kessler, TICL—a type inference system for common Lisp, Software—Practice & Experience, v.20 n.6, p.593-623, June 1990 [doi>10.1002/spe.4380200606]
• 12: Robert A. MacLachlan, April 1991. Private communication.
• 13: Robert A. MacLachlan, CMU Common Lisp User''s Manual, Carnegie Mellon University, Pittsburgh, PA, 1992
• 14: Terrence C. Miller, Type checking in an imperfect world, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.237-243, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567775]
• 15: Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17(3):348-375, December 1978.
• 16: Prateek Mishra , Uday S. Reddy, Declaration-free type checking, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.7-21, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318603]
• 17: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Languages