An implementation of standard ML modules

ABSTRACT

Standard ML includes a set of module constructs that support programming in the large. These constructs extend ML's basic polymorphic type system by introducing the dependent types of Martin Löf's Intuitionistic Type Theory. This paper discusses the problems involved in implementing Standard ML's modules and describes a practical, efficient solution to these problems. The representations and algorithms of this implementation were inspired by a detailed formal semantics of Standard ML developed by Milner, Tofte, and Harper. The implementation is part of a new Standard ML compiler that is written in Standard ML using the module system.

REFERENCES

• 1: Andrew W. Appel , David B. MacQueen, A standard ML compiler, Proc. of a conference on Functional programming languages and computer architecture, p.301-324, October 1987, Portland, Oregon, United States
• 2: 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
• 3: R.S. Boyer and J Moore, The sharing of structure in theorem-proving programs, Machine Intelligence 7, B. Meltzer and D. Michie, eds., Edinburgh University Press, 1972, 101-116.
• 4: 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]
• 5: R. Harper, D. MacQueen, and R. Milner, Standard ML, Laboratory for Foundations of Computer Science, Dept. of Computer Science, University of Edinburgh, ECS-LFCS-86-2, 1986. (Also Polymorphism II, 2, October 1985.)
• 6: R. Harper , R. Milner , M. Tofte, A type discipline for Program modules, II and Colloquium on Functional and Logic Programming and Specifications (CFLP) on TAPSOFT '87: Advanced Seminar on Foundations of Innovative Software Development, p.308-319, March 1987, Pisa, Italy
• 7: R. Harper, R. Milner, and M. Tofte, The semantics of Standard ML, Version I, Laboratory for Foundations of Computer Science, Dept. of Computer Science, University of Edinburgh, ECS-LFCS-87-36, 1986.
• 8: David MacQueen, Modules for standard ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.198-207, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802036]
• 9: David B. MacQueen, Using dependent types to express modular structure, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.277-286, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512670]
• 10: P. Martin-L~Sf, Constructive mathematics and computer programming, Sixth International Congress for Logic, Methodology, and Philosophy of Science, North Holland, Amsterdam, 1982, 153-175.
• 11: J. C. Mitchell , R. Harper, The essence of ML, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.28-46, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73563]
• 12: M. Torte, Operational Semantics and Polymorphic Type Inference, Ph.D. Dissertation, Dept. of Computer Science, University of Edinburgh, 1987.
• 13: D.H.D. Warren, Implementing PROLOG - Compiling Predicate Logic Programs, Vol. I, Dept. of Artificial Intelligence Report No. 39, University of Edinburgh, 1977.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: ML

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

General Terms:
Algorithms, Languages