Dependency analysis for Standard ML

ABSTRACT

Automatic dependency analysis is a useful addition to a system like CM, our compilation manager for Standard ML of New Jersey. It relieves the programmer from the tedious and error-prone task of having to specify compilation dependencies by hand and thereby makes its usage more user friendly. But dependency analysis is not easy, as the general problem for Standard ML is NP-complete. Therefore, CM has to impose certain restrictions on the programming language to recover tractability. We prove the NP-completeness result, discuss the restrictions on ML that are used by CM, and provide the resulting analysis algorithms.

REFERENCES

• 1: Martín Abadi , Butler Lampson , Jean-Jacques Lévy, Analysis and caching of dependencies, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.83-91, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 2: Ada 1980. Military standard: Ada programming language. Tech. Rep. MIL-STD-1815, Department of Defense, Naval Publications and Forms Center, Philadelphia, PA.
• 3: Rolf Adams , Walter Tichy , Annette Weinert, The cost of selective recompilation and environment processing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.1, p.3-28, Jan. 1994 [doi>10.1145/174634.174637]
• 4: Appel, A. W. and MacQueen, D. B. 1991. Standard ML of New Jersey. In 3rd International Symposium on Programming Language Implementation and Logic Programming, M.Wirsing, Ed. Springer-Verlag, New York, 1-13.
• 5: Ken Arnold , James Gosling, The Java programming language (2nd ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 6: Blume, M. 1995. Standard ML of New Jersey compilation manager. Manual accompanying SML/NJ software.
• 7: Matthias Blume, Hierarchical modulatory and intermodule optimization, Princeton University, Princeton, NJ, 1998
• 8: Matthias Blume , Andrew W. Appel, Hierarchical modularity, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.813-847, July 1999 [doi>10.1145/325478.325518]
• 9: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• 10: Paul DuBois, Software portability with imake (2nd ed.), O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 11: Hanna, C. B. and Levin, R. 1993. The Vesta language for configuration management. Tech. Rep. 107, Digital Equipment Corp. Systems Research Center. June.
• 12: Harper, R., Lee, P., Pfenning, F., and Rollins, E. 1994. A Compilation Manager for Standard ML of New Jersey. In 1994 ACM SIGPLAN Workshop on ML and its Applications. 136-147.
• 13: Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
• 14: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 15: A. J. Kfoury , J. Tiuryn , P. Urzyczyn, An analysis of ML typability, Journal of the ACM (JACM), v.41 n.2, p.368-398, March 1994 [doi>10.1145/174652.174659]
• 16: Levin, R. and McJones, P. R. 1993. The Vesta approach to precise configuration of large software systems. Tech. Rep. 105, Digital Equipment Corp. Systems Research Center. June.
• 17: Harry G. Mairson, Deciding ML typability is complete for deterministic exponential time, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.382-401, December 1989, San Francisco, California, United States [doi>10.1145/96709.96748]
• 18: Robin Milner , Mads Tofte, Commentary on standard ML, MIT Press, Cambridge, MA, 1991
• 19: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 20: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 21: John H. Reppy, CML: A higher concurrent language, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.293-305, June 24-28, 1991, Toronto, Ontario, Canada
• 22: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 23: R. D. Tennent, Principles of Programming Languages, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 24: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985
• 25: N. Wirth, From modula to Oberon, Software—Practice & Experience, v.18 n.7, p.661-670, July 1988 [doi>10.1002/spe.4380180706]
• 26: N. Wirth, The programming language Oberon, Software—Practice & Experience, v.18 n.7, p.671-690, July 1988 [doi>10.1002/spe.4380180707]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Modules, packages

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Languages, Theory

Keywords:
NP-completeness, compilation management, dependency analysis