Type Inference and Static Analysis for Object-Oriented Software

Jens Palsberg

We are developing type inference, type matching, and flow analysis algorithms for object-oriented software which are practically useful for tool developers and language designers. We are also investigating the relationship between types and flow information, and ways of combining them. The benefits include easier correctness proofs and faster flow analyses without sacrifice of precision. Additionally, several program transformations preserve a certain flow analysis.

The project has been supported by a National Science Foundation CAREER Award.

Book

Jens Palsberg and Michael I. Schwartzbach. Object-oriented type systems, John Wiley & Sons, 1994.

Papers on Type Inference

Jens Palsberg. Normal forms have partial types. Information Processing Letters, 45:1-3, 1993.
Dexter Kozen, Jens Palsberg, Michael I. Schwartzbach. Efficient inference of partial types. Journal of Computer and System Sciences, 49(2):306-324, 1994. Preliminary version in Proceedings of FOCS'92, 33rd IEEE Symposium on Foundations of Computer Science, pages 363-371, Pittsburgh, Pennsylvania, October 1992.
Jens Palsberg. Efficient inference of object types. Information and Computation, 123(2):198-209, 1995. Preliminary version in Proceedings of LICS'94, Ninth Annual IEEE Symposium on Logic in Computer Science, pages 186-195, Paris, France, July 1994.
Jens Palsberg, Mitchell Wand, and Patrick M. O'Keefe. Type inference with non-structural subtyping. Formal Aspects of Computing, 9:49-67, 1997.
Jens Palsberg and Trevor Jim. Type inference with simple selftypes is NP-complete. Nordic Journal of Computing, 4(3):259-286, Fall 1997.
Trevor Jim and Jens Palsberg. Type inference in systems of recursive types with subtyping. Manuscript, 1999.
Jens Palsberg, Tian Zhao, and Trevor Jim. Automatic Discovery of Covariant Read-Only Fields. ACM Transactions on Programming Languages and Systems. To appear. Preliminary version in Informal Proceedings of FOOL'02, Ninth International Workshop on Foundations of Object-Oriented Languages, Portland, Oregon, January 2002.
Jens Palsberg and Tian Zhao. Type Inference for Record Concatenation and Subtyping. Information and Computation, 189:54-86, 2004. Preliminary version in Proceedings of LICS'02, IEEE Symposium on Logic in Computer Science, pages 125-136, July 2002.

Papers on Flow Analysis

Jens Palsberg and Michael I. Schwartzbach. Object-oriented type inference. In Proceedings of OOPSLA'91, ACM SIGPLAN Sixth Annual Conference on Object-Oriented Programming Systems, Languages and Applications, pages 146-161, Phoenix, Arizona, October 1991.
Nicholas Oxhoj, Jens Palsberg, and Michael I. Schwartzbach. Making type inference practical. In Proceedings of ECOOP'92, Sixth European Conference on Object-Oriented Programming, pages 329-349. Springer-Verlag (LNCS 615), Utrecht, The Netherlands, July 1992.
Jens Palsberg. Closure analysis in constraint form. ACM Transactions on Programming Languages and Systems, 17(1):47-62, January 1995. Preliminary version in Proceedings of CAAP'94, Colloquium on Trees in Algebra and Programming, Springer-Verlag (LNCS 787), pages 276-290, Edinburgh, Scotland, April 1994.
Ole Agesen, Jens Palsberg, and Michael I. Schwartzbach. Type inference of Self: Analysis of objects with dynamic and multiple inheritance. Software - Practice & Experience, 25(9):975-995, September 1995. Preliminary version in Proceedings of ECOOP'93, Seventh European Conference on Object-Oriented Programming, Springer-Verlag (LNCS 707), pages 247-267, Kaiserslautern, Germany, July 1993.
Frank Tip and Jens Palsberg. Scalable Propagation-based Call Graph Construction Algorithms. In Proceedings of OOPSLA'00, ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, pages 281-293, Minneapolis, Minnesota, October 2000.
Christian Grothoff, Jens Palsberg, and Jan Vitek. Encapsulating objects with confined types, with In Proceedings of OOPSLA'01, ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, pages 241-253, Tampa Bay, Florida, October 2001.
Neal Glew and Jens Palsberg. Type-safe method inlining, In Proceedings of ECOOP'02, European Conference on Object-Oriented Programming, pages 525-544. Springer-Verlag (LNCS 2374), Malaga, Spain, June 2002.
Jens Palsberg and Mitchell Wand. CPS Transformation of Flow Information. Journal of Functional Programming, to appear.

Papers on relating Types and Flow Information

Jens Palsberg and Michael I. Schwartzbach. Safety analysis versus type inference for partial types. Information Processing Letters, 43:175-180, 1992.
Jens Palsberg and Michael I. Schwartzbach. Safety analysis versus type inference. Information and Computation, 118(1):128-141, 1995.
Jens Palsberg and Patrick M. O'Keefe. A type system equivalent to flow analysis. ACM Transactions on Programming Languages and Systems, 17(4):576-599, July 1995. Preliminary version in Proceedings of POPL'95, 22nd Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 367-378, San Francisco, California, January 1995.
Jens Palsberg. Equality-Based Flow Analysis versus Recursive Types. ACM Transactions on Programming Languages and Systems, 20(6):1251--1264, 1998.
Jens Palsberg and Christina Pavlopoulou. From polyvariant flow information to intersection and union types, Journal of Functional Programming 11(3):263-317, May 2001. Preliminary version in Proceedings of POPL'98, 25th Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 197-208, San Diego, California, January 1998.

Papers on Type Matching

Dexter Kozen, Jens Palsberg, and Michael I. Schwartzbach. Efficient recursive subtyping. Mathematical Structures in Computer Science, 5(1):113-125, 1995. Preliminary version in Proceedings of POPL'93, Twentieth Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 419-428, Charleston, South Carolina, January 1993.
Jens Palsberg and Tian Zhao. Efficient and Flexible Matching of Recursive Types. Information and Computation 171:364-387, 2001. Preliminary version in Proceedings of LICS'00, Fifteenth Annual IEEE Symposium on Logic in Computer Science, pages 388-398, Santa Barbara, California, June 2000.
Somesh Jha, Jens Palsberg, and Tian Zhao. Efficient type matching. In Proceedings of FOSSACS'02, Foundations of Software Science and Computation Structures, pages 187-204. Springer-Verlag (LNCS 2303), Grenoble, France, April 2002.