Skip to main content



F-ing modules

Andreas Rossberg, Claudio V. Russo and Derek Dreyer

Discussion led by Xiang Long/Matthew Milano on December 3, 2014

Abstract:

ML modules are a powerful language mechanism for decomposing programs into reusable components. Unfortunately, they also have a reputation for being “complex” and requiring fancy type theory that is mostly opaque to non-experts. While this reputation is certainly understandable, given the many non-standard methodologies that have been developed in the process of studying modules, we aim here to demonstrate that it is undeserved. To do so, we give a very simple elaboration semantics for a full-featured, higher-order ML-like module language. Our elaboration defines the meaning of module expressions by a straightforward, compositional translation into vanilla System F-omega (the higher-order polymorphic lambda-calculus), under plain F-omega typing environments. We thereby show that ML modules are merely a particular mode of use of System F-omega. Our module language supports the usual second-class modules with Standard ML-style generative functors and local module definitions. To demonstrate the versatility of our approach, we further extend the language with the ability to package modules as firstclass values—a very simple extension, as it turns out. Our approach also scales to handle OCaml-style applicative functor semantics, but the details are significantly more subtle, so we leave their presentation to a future, expanded version of this paper. Lastly, we report on our experience using the “locally nameless” approach in order to mechanize the soundness of our elaboration semantics in Coq.

PDF