Dynamic data polyvariance using source-tagged classes

ABSTRACT

The DDP (Demand-driven/Pruning) analysis algorithm allows us to perform data-flow analyses of programming languages that are dynamically typed and have higher-order control flow, such as Smalltalk or Scheme. Because it is demand-driven and employs search pruning, it scales to large code bases. However, versions of the algorithm previously described [19] do not handle data polymorphism well, conservatively merging separate data flows that go through distinct instantiations of a collection type. In this paper, we describe a new extension to DDP that helps to disentangle these flows, permitting more precise results. The extension is based on source-tagging classes so that each reference to a class in the source code yields a subdivision of the type associated with that class. An initial implementation of this polyvariant analysis has been added to the DDP-based tool Chuck, a part of the integrated Squeak program-development environment; we show examples of the tool in action.

REFERENCES

• 1: N. I. Adams, IV, D. H. Bartley, G. Brooks, R. K. Dybvig, D. P. Friedman, R. Halstead, C. Hanson, C. T. Haynes, E. Kohlbecker, D. Oxley, K. M. Pitman, G. J. Rozas, Jr. G. L. Steele, G. J. Sussman, M. Wand, and H. Abelson. Revised⁵ report on the algorithmic language Scheme. SIGPLAN Notices, 1998.
• 2: Ole Agesen. The cartesian product algorithm: Simple and precise type inference of parametric polymorphism. In European Conference on Object-Oriented Programming (ECOOP), 1995.
• 3: Ole Agesen. Concrete Type Inference: Delivering Object-Oriented Applications. PhD thesis, Stanford University, 1995.
• 4: American National Standards Institute. ANSI NCITS 319-1998: Information Technology --- Programming Languages --- Smalltalk. American National Standards Institute, 1430 Broadway, New York, NY 10018, USA, 1998.
• 5: Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In SIGPLAN Conference on Programming Language Design and Implementation, pages 242--256, 1994.
• 6: Erich Gamma, Richard Helm, Ralph Johnson, and John Vlisside. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, Massachusetts, 1995.
• 7: James Gosling, Bill Joy, and Guy Steele. The Java Language Specification. Addison Wesley, Boston, MA, 1996.
• 8: David Grove, Greg Defouw, Jeffrey Dean, and Craig Chambers. Call-graph construction in object-oriented languages. In ACM Conference on Object-Oriented Programming, Systems, Language, and Applications (OOPSLA), 1997.
• 9: Michael Hind. Pointer analysis: Haven't we solved this problem yet? In ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE), Snowbird, Utah, 2001.
• 10: Dan Ingalls, Ted Kaehler, John Maloney, Scott Wallace, and Alan Kay. Back to the future: The story of Squeak, A practical Smalltalk written in itself. In ACM Conference on Object-Oriented Programming, Systems, Language, and Applications (OOPSLA), 1997.
• 11: Alan C. Kay. The early history of Smalltalk. In The second ACM SIGPLAN Conference on the History of Programming Languages, pages 69--95. ACM Press, 1993.
• 12: Flemming Nielson, Hanne Riis Nielson, and Chris Hankin. Principles of Program Analysis. Springer-Verlag, Berlin, 1999.
• 13: Nicholas Oxhøj, Jens Palsberg, and Michael I. Schwartzbach. Making type inference practical. In European Conference on Object-Oriented Programming (ECOOP), pages 329--349, 1992.
• 14: John Plevyak and Andrew A. Chien. Precise concrete type inference for object-oriented languages. In ACM Conference on Object-Oriented Programming, Systems, Language, and Applications (OOPSLA), pages 324--340, 1994.
• 15: Micha Sharir and Amir Pnueli. Two approaches to interprocedural data-flow analysis. In Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis: Theory and Application. Prentice Hall Professional Technical Reference, 1981.
• 16: Olin Shivers. Control-flow analysis in Scheme. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1988.
• 17: Olin Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, Carnegie Mellon University, 1991.
• 18: Olin Shivers. The semantics of Scheme control-flow analysis. In Partial Evaluation and Semantic-Based Program Manipulation, pages 190--198, 1991.
• 19: S. Alexander Spoon and Olin Shivers. Demand-driven type inference with subgoal pruning: Trading precision for scalability. In European Conference on Object-Oriented Programming (ECOOP), 2004.
• 20: S. Alexander Spoon and Olin Shivers. Semantic navigation of large code bases in higher-order, dynamically typed languages. In Proceedings of the 12th Working Conference on Reverse Engineering (WCRE 2005), Pittsburgh, Pennsylvania, November 2005.
• 21: Frank Tip, Chris Laffra, Peter F. Sweeney, and David Streeter. Practical experience with an application extractor for Java. In ACM Conference on Object-Oriented Programming, Systems, Language, and Applications (OOPSLA), pages 292--305, New York, NY, USA, 1999. ACM Press.
• 22: Peter von der Ahé. Applications of concrete-type inference. Master's thesis, University of Aarhus, 2004.
• 23: Tiejun Wang and Scott F. Smith. Precise constraint-based type inference for Java. Lecture Notes in Computer Science, 2072:99--117, 2001.