Hierarchical modularity

ABSTRACT

To cope with the complexity of very large systems, it is not sufficient to divide them into simple pieces because the pieces themselves will either be too numerous or too large. A hierarchical modular structure is the natural solution. In this article we explain how that approach can be applied to software. Our compilation manager provides a language for specifying where individual modules fit into a hierarchy and how they are related semantically. We pay particular attention to the structure of the global name space of program identifiers that are used for module linkage because any potential for name clashes between otherwise unrelated parts of a program can negatively affect modularity. We discuss the theoretical issues in building software hierarchically, and we describe our implementation of CM, the compilation manager for Standard ML of New Jersey.

REFERENCES

• 1: Adams, P. and Solomon, M. 1993. An overview of the CAPITL software development environment. Tech. Rep. CS-TR-93-1143, Computer Sciences Department, University of Wisconsin - Madison. 4.
• 2: 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]
• 3: Andrew W. Appel, Modern compiler implementation in ML: basic techniques, Cambridge University Press, New York, NY, 1997
• 4: Appel, A. W. and MacQueen, D. B. 1991. Standard ML of New Jersey. In 3rd International Symp. on Prog. Lang. Implementation and Logic Programming, M. Wirsing, Ed. Springer- Verlag, New York, 1-13.
• 5: Andrew W. Appel , David B. MacQueen, Separate compilation for Standard ML, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.13-23, June 20-24, 1994, Orlando, Florida, United States
• 6: Ken Arnold , James Gosling, The Java programming language (2nd ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 7: Barendregt, H. P. 1981. The Lambda Calculus: Its Syntax and Semantics. North-Holland, Amsterdam.
• 8: Bauer, L., Appel, A. W., andFelten, E. W.1999. Mechanisms for secure modular programming in Java. Tech. Rep. TR-603-99, Department of Computer Science, Princeton University. July.
• 9: Blume, M. 1995. Standard ML of New Jersey compilation manager. Manual accompanying SML/NJ software.
• 10: Matthias Blume, Dependency analysis for Standard ML, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.790-812, July 1999 [doi>10.1145/325478.325481]
• 11: Broder, A. 1993. Some applications of Rabin's ~ngerprinting method. In Sequences II: Methods in Communications, Security, and Computer Science, R. Capocelli, A. D. Santis, and U. Vaccaro, Eds. Springer-Verlag, 143-152.
• 12: Brown, M. R. and Ellis, J. R. 1993. Bridges: Tools to extend the Vesta conguration management system. Tech. Rep. 108, Digital Equipment Corp. Systems Research Center. 6.
• 13: Luca Cardelli, Program fragments, linking, and modularization, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.266-277, January 15-17, 1997, Paris, France [doi>10.1145/263699.263735]
• 14: Cardelli, L., Donahue, J., Glassman, L., Jordan, M., Kalsow, B., and Nelson, G. 1988. Modula-3 report. Tech. Rep. Research Report 31, DEC Systems Research Center, Palo Alto, CA.
• 15: Chiu, S.-Y. and Levin, R. 1993. The Vesta repository: A le system extension for software development. Tech. Rep. 106, Digital Equipment Corp. Systems Research Center. June.
• 16: Alonzo Church, The Calculi of Lambda Conversion. (AM-6) (Annals of Mathematics Studies), Princeton University Press, Princeton, NJ, 1985
• 17: Clemm, G. M. 1994. The Odin System | Reference Manual.
• 18: DoD 1980. Military standard: Ada programming language. Tech. Rep. MIL-STD-1815, Department of Defense, Naval Publications and Forms Center, Philadelphia, PA.
• 19: Paul DuBois, Software portability with imake (2nd ed.), O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 20: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: Feldman, S. I. 1979. Make - a program for maintaining computer programs. In Unix Programmer's Manual, Seventh Edition, Volume 2A. Bell Laboratories.
• 22: Bryan Ford , Godmar Back , Greg Benson , Jay Lepreau , Albert Lin , Olin Shivers, The Flux OSKit: a substrate for kernel and language research, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.38-51, October 05-08, 1997, Saint Malo, France
• 23: Carl A. Gunter, Abstracting dependencies between software configuration items, Proceedings of the 4th ACM SIGSOFT symposium on Foundations of software engineering, p.167-178, October 16-18, 1996, San Francisco, California, United States
• 24: Hanna, C. B. and Levin, R. 1993. The Vesta language for conguration management. Tech. Rep. 107, Digital Equipment Corp. Systems Research Center. June.
• 25: Harper, R., Lee, P., Pfenning, F., and Rollins, E. 1994b. A Compilation Manager for Standard ML of New Jersey. In 1994 ACM SIGPLAN Workshop on ML and its Applications. 136-147.
• 26: Robert Harper , Peter Lee , Frank Pfenning , Eugene Rollins, Incremental Recompilation for Standard ML of New Jersey, Carnegie Mellon University, Pittsburgh, PA, 1994
• 27: Ivar Jacobson, Object-oriented development in an industrial environment, Conference proceedings on Object-oriented programming systems, languages and applications, p.183-191, October 04-08, 1987, Orlando, Florida, United States
• 28: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 29: Butler W. Lampson , Eric E. Schmidt, Organizing software in a distributed environment, Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems, p.1-13, June 27-29, 1983, San Francisco, California, United States
• 30: 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]
• 31: Levin, R. and McJones, P. R. 1993. The Vesta approach to precise conguration of large software systems. Tech. Rep. 105, Digital Equipment Corp. Systems Research Center. June.
• 32: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 33: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 34: Mitchell, J. G., Maybury, W., and Sweet, R. 1979. Mesa language manual. Tech. Rep. CSL-79-3, Xerox PARC.
• 35: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 36: F. W. Scheifler , J. Gettys , R. Newman, X Window system: C Library and protocol reference, Digital Press, Newton, MA, 1988
• 37: Daniel C. Swinehart , Polle T. Zellweger , Robert B. Hagmann, The structure of Cedar, ACM SIGPLAN Notices, v.20 n.7, p.230-244, July 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

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

General Terms:
Design, Languages, Management

Keywords:
compilation management, linking, modularity, modules, name visibility, program structure