Smartest recompilation

ABSTRACT

To separately compile a program module in traditional statically-typed languages, one has to manually write down an import interface which explicitly specifies all the external symbols referenced in the module. Whenever the definitions of these external symbols are changed, the module has to be recompiled. In this paper, we present an algorithm which can automatically infer the “minimum” import interface for any module in languages based on the Damas-Milner type discipline (e.g., ML). By “minimum”, we mean that the interface specifies a set of assumptions (for external symbols) that are just enough to make the module type-check and compile. By compiling each module using its “minimum” import interface, we get a separate compilation method that can achieve the following optimal property: A compilation unit never needs to be recompiled unless its own implementation changes.

REFERENCES

• 1: Shail Aditya , Rishiyur S. Nikhil, Incremental polymorphism, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.379-405, June 1991, Cambridge, Massachusetts, United States
• 2: William E. Aitken and John H. Reppy. Abstract value constructors. In A CM SIGPLAN Workshop on ML and its Applications, June 1992.
• 3: Maria Virginia Aponte. Typage d'un systeme de modules parametriques avec partage: une application de t'unification dans Its theories equationneIIes. Phi) thesis, Universite de Paris, February 1992.
• 4: Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In Martin Wirsing, editor, Third Int'l Syrup. on Prog. Lang. Implementation and Logic Programming, pages 1-13, New York, August 1991. Springer-Verlag.
• 5: Hans-Juergen Boehm , Alan Demers, Implementing RUSSELL, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.186-195, June 25-27, 1986, Palo Alto, California, United States
• 6: Luis Damas. Type Assignment in Programming Languages. PhD thesis, University of Edinburgh, Department of Computer Science, Edinburgh, UK, 1985.
• 7: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• 8: David K. Gkfford et al. FX-87 reference manual. Teclmical Report MIT/LCS/TR-407, M.I.T. Laboratory for Computer Science~ September 1987.
• 9: Stuart I. Feldman. Make - a program for maintaining computer prograans. Software - Practice and Experience, 9(4):255-265, Aplrl 1979.
• 10: Emden l~. Gansner. AT&T Bell Labs, personal communication, 1992.
• 11: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 12: Mark P. Jones, A theory of qualified types, Symposium proceedings on 4th European symposium on programming, p.287-306, January 1992, Rennes, France
• 13: Stefan Kaes, Type inference in the presence of overloading, subtyping and recursive types, Proceedings of the 1992 ACM conference on LISP and functional programming, p.193-204, June 22-24, 1992, San Francisco, California, United States
• 14: Bill Kalsow and Eric Muller. SRC Modula-3 version 1.6 manual, February 1991.
• 15: Butler W. Lampson , Eric E. Schmidt, Practical use of a polymorphic applicative language, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.237-255, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567090]
• 16: Daniel Leivant, Polymorphic type inference, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.88-98, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567077]
• 17: Xavier Leroy, Unboxed objects and polymorphic typing, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.177-188, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143205]
• 18: Michael R. Levy, Type checking, separate compilation and reusability, ACM SIGPLAN Notices, v.19 n.6, p.285-289, June 1984
• 19: Robin Milner , Mads Tofte, Commentary on standard ML, MIT Press, Cambridge, MA, 1991
• 20: Robin Milner, Mads Tofte, and Robert Harper. The Defini- 1990.
• 21: J. Mitchell, W. Maybury, and R. Sweet. Mesa language manual. Technical Report CSL-79-3, Xerox Palo Alto Research Center, Palo Alto, CA, 1979.
• 22: Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 23: Rishiyur S. Niklfil. Id version 90.0 reference manual. Technical Report TR-CSG-Memo 284-1, MIT Laboratory for Computer Science, 1990.
• 24: Atsushi Ohori, A compilation method for ML-style polymorphic record calculi, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.154-165, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143200]
• 25: D. Rémy, Type checking records and variants in a natural extension of ML, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.77-88, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75284]
• 26: 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]
• 27: Eugene J. Rollins. SourceGroup: A selective recompilation system for SML. in Th2rd International Workshop on Standard ML, Pittsburgh, September 1991. Carnegie Mellon University.
• 28: Nick Rothwell and Mads Tofte. import command source code. with Standard ML of New Jersey releases 0.65.
• 29: Robert W. Schwanke , Gail E. Kaiser, Smarter recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.627-632, Oct. 1988 [doi>10.1145/48022.214505]
• 30: Zhong Shao and Andrew W. Appel. Smartest recompilation. Technical Report CS-TR-395-92, Princeton Univ. Dept. of Computer Science, Princeton, NJ, October 1992.
• 31: Walter F. Tichy, Smart recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.273-291, July 1986 [doi>10.1145/5956.5959]
• 32: Mads Torte. Operational Semantics and PoIymorphic Type Inference. PhD thesis, University of Edinburgh, Edinburgh, UK, November 1987.
• 33: Mads Tofte, Principal signatures for higher-order program modules, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.189-199, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143206]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: ML
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines
      D.3.4 Processors
          Subjects: Code generation

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure; Functional constructs

General Terms:
Algorithms, Languages