What is the ML Module System?, Part 1

Browsing through the heated Scala mail list discussion from 2009 on OOP versus functional programming, I ran into a number of messages which indicate some confusion as to the role and mechanism of the ML module system. The natural question that was raised is how is a module system different from a "low-level" object system. I am not entirely sure what a "low-level" object system is but in this post I would like to compare and contrast the ML module system and object systems, principally class-based object system but also classless object systems. First, what role do these language features serve? There is some overlap in purpose but also significant differences. The ML module system was originally designed to serve to roles:

1. To support programming-in-the-large organization of large system architecture
2. To facilitate the construction of a type-safe container library

In contrast, OOP is typically defined as supporting design goals of encapsulation, inheritance, and subtype polymorphism. On the surface, this suggests some overlap. Programming-in-the-large may sound like encapsulation, but as I will discuss, the reality is considerably more nuanced.

Symmetric Type Sharing in ML

In the Standard ML language, there are two primary mechanisms for refining a module signature after the fact. One is a symmetric mechanism called type sharing and the other called where type, aka fibration. These are useful for facilitating modular programming by enabling reuse of module signatures (i.e., the syntactic "type" of a module).

Firestorm

The past few days have seen a veritable firestorm of flames between the Java and Scala communities. The proximate cause was a leaked private email outlining what the Yammer folks disliked about Scala. An official post from Yammer followed but not before many bloggers had a field day with the leaked email. What is interesting is that one such discussion on Stephen Colebourne's blog pointed that the the lack of a "module system" is a principal deficiency of Scala. This point, mind you, was not part of the Yammer email. In fact, it preceded the email by a few days. The post cited the Scala's community's response to an inquiry about Scala and "module systems" [Google Groups]. That inquiry initially resulted in some misunderstanding.

Semantics of Nested Classes

Although nested classes are widely adopted in many popular programming languages (e.g., C++, C#, Java, Python, Ruby), I have yet to see a good treatment giving the motivation, use cases, and architectural issues associated with the feature. Moreover, another undocumented aspect is how the semantics of nested classes vary from language to language. They appear to be useful for namespace management (though C++ namespace and Java packages also cover this), simulating closures, and callbacks for GUIs and event handling (basically a variant of closure simulation).
First thing is first, what are nested classes?

class A {
  class B { }
}

In essence, they are scoped type declarations and definitions. Instead of defining a class B at the top-level of the program source, one declares a locally scoped one within the definition of another class, A in this case. One immediate consequence of this is a form of namespace management for user-defined aggregate types (i.e., classes).
There are a lot of gotchas due the language design here. The scoping discipline is incomplete. C/C++'s restriction on shadowing prohibits the following code:

 
class B; 

class A {
  B something;
  class B { };
}  

In contrast, the following code compiles:

class A {
  private:
    class B {};
  public:
    B makeB();
}

Despite the fact that A::B is unnameable outside an instance of A, A exports the member function makeB which yields a value of type A::B. Though one cannot name the return value of makeB outside of A, the value can still be used as is in the case in the following:

class A {
  private:
    class B { 
      int x;
       public: 
      B add(B _x) { x += _x; }
    };
  public:
    B makeB();
};

int f() {
  A a0, a1;
  a0.makeB().add(a1.makeB());
}

The above illustrates an important point. C++ nested classes do not declare distinct types for each instance. Although one cannot annotate them as static, they are exactly that. In the example, a0.B and a1.B are of the same type. This is why a0.makeB().add(a1.makeB()) type checks. This means that writing a nested class is equivalent to lifting that class definition out to the top-level and selectively hiding the name of the nested class.
Between different languages, there is a design chasm. In C++, there is only the unitary nested class and its associated semantics. Java distinguishes between static nested classes (similar to the C++ nested class) and inner classes. Java actually has a number of variants of nested classes (https://blogs.oracle.com/darcy/entry/nested_inner_member_and_top). The above C++ example translated into Java fails type checking because of A.B is private.

class A {
      private class B {

        public B add(B rhs) { val += rhs.val; return this; }
        private int val;

      }

      public B makeB() { return new B(); };
}

public class Nested0 {

   public static void main() {
     A a0 = new A();
     A a1 = new A();
     a0.makeB().add(a1.makeB());
   }
}

The call to add is flagged as a problem because a0.makeB()'s type (i.e., A.B) is inaccessible. If A.B were public or protected, however, the type checker is satisfied despite a0.B and a1.B supposedly denoting two distinct inner classes. Thus, at least at this point, inner classes do not provide abstract types in the sense of generative types.

On the other hand, as this discussion on Java decompilation (javap) shows, the semantics of inner classes are such that have a kind of C++

friend

relationship with their outer enclosing class. The discussion on TheServerSide shows how this is implemented: the compiler generates a static method that "breaks the encapsulation wall" to permit accessing private members of the outer class.

References

1. Herb Sutter wrote an article on nested classes in C++.