Modules Divided: Interface and Implement

In a recent article, I described how anonymous modules avoid an entanglement problem, and sketched an approach to achieving this. Unfortunately, the approach I sketch seems verbose, and would tend towards high search costs. While those disadvantages can be mitigated by discipline and idiom, dependency on discipline and idiom stinks of design failure.

I would prefer that the path-of-least resistance avoid verbosity. And, while those expensive constraint-solving searches should be available (because they’re a very nice feature for adaptability, specialization, and meta-programming), I believe that extra verbosity should be required to ‘opt-in’ rather than ‘opt-out’.

By ‘avoid verbosity’ I mean:

1. import statements should be short one-liners; complex assertions or requirements should be separate.
2. module headers should be a short one-liner, even if there are a lot of parameters.
3. export should be implicit in the common case

I’ve been thinking about how to achieve this, and it occurs to me that limited use of names would be appropriate – i.e. to achieve these short one-liners, it would be convenient to simply provide a unique name. The trick will be to borrow the benefits of associated with names while avoiding problematic entanglements with the namespace.

Named Interfaces and Anonymous Implementations

What I propose is to partition modules into two distinct sets: interfaces and implementations. Implementations are anonymous. Interfaces are uniquely identified by reference or name.

There are constraints on the relationships between these sets:

1. Interfaces do not depend on implementations.
2. Dependencies between interfaces are linear and acyclic, e.g. based on a single-inheritance relationship (extends, weakens, adjusts).
3. Implementations each declare one interface they implement.
4. Dependency between implementations is indirect via ‘import’ of an interface. However, there are no limits on the number of imports. A linker must find an implementation for each imported interface.

This helps disentangle modules to some degree. To reuse an implementation-module M initially from project Q in project R, a developer would need to do the following:

1. copy module M to the new project.
2. copy the interface M implements to the new project.
3. copy the interfaces M imports to the new project.
4. copy the interface inheritance chains to the new project.
5. rename interfaces from project R whose names conflict with those already in project Q.
6. write implementation modules for any new interfaces M imports.

Fortunately, the first five steps would be finite, predictable, and simple. Each interface has a finite chain of dependencies. Renaming modules can be painful, but tends to be a one-time pain and should be easy to automate by such mechanisms as a refactoring browser or simple import-rule between independently maintained DVCS repositories.

The sixth step is, of course, to provide for M’s dependencies. If projects R and Q are already close, this might require only adding a few implementation modules as ‘glue’ between interfaces (saying how to take one set of interfaces and emit another). If not, developers of Q could grab a bit more of R’s implementation and repeat the process until closer to a common set of dependencies.

The advantage of these constraints is that each step is simple, predictable, and and under relatively easy control. Developers can decide just how much of one project to bring into another.

Parameterized Modules

Parameters offer developers more control and awareness of dependencies and relationships between modules. With implementation and interface divided, and with the new goals to reduce verbosity, parameterization needs a slight change in vision.

• To avoid redundant declaration of parameters in each interface module, be able to ‘inherit’ a useful set of parameters.
• To avoid redundant declaration of parameters in each implementation module, parameters must be a property of the interface being implemented.
• To avoid redundant specification of parameters at ‘import’, interfaces must provide default values for parameters.
• To avoid redundant specification of common non-default parameters, developers should be able to create new interfaces that override the defaults, yet use the existing implementation.
• To avoid redundant plumbing of parameters at ‘import’, developers shouldn’t need to name each parameter to propagate them.

These requirements direct me towards design based on records and keyword:

• An interface may declare named parameters, and optionally some default values.
• At each ‘import’, developers provide a record of keyword parameters, along with the interface name.
• Within an implementation module, parameters are accessible as a record. This makes it easy to delegate parameters, or provide the same parameters to multiple imports.
• Interface inheritance can override default parameters. If default parameters are the only property affected.
• Within an interface module, parameters are accessible by name – e.g. when describing assertions or invariants. It is easy to constrain that one parameter is greater than another, for example. Since the same parameters are available to the implementations, it is possible for modules to ‘adapt’ the implementation to the parametric requirements.

Interfaces don’t do much with parameters – no transforming them, for example. Most complexity is left to the implementation modules.

Encapsulation, Implementation Hiding, and Exports

An interface can declare exports. Outside of these declared exports, nothing defined in the implementation module is visible. Thus, there is no need to declare exports per implementation module. The exports list is also inherited, which avoids redundancy between interfaces.

It should be easy for an implementation module to ‘delegate’ exports to another module, i.e. importing the names then forwarding most of them as-is. This goal is a simple idiom for indirect ‘implementation inheritance’ by use of import.

Interface Inheritance

I’ve several times mentioned the possibility of interface inheritance. My goals with this are to:

• avoid verbosity from copy-and-paste programming of interfaces.
• allow the structure of interfaces to help direct a search for valid implementations.
• keep it simple and sufficient, and preferably familiar

A possible simple, sufficient model is to allow three forms of inheritance: extends/narrows/adjusts. Assuming interface Q inherits from interface P:

• extends – Q is ‘a kind of’ P, but can have more functions. When the linker is searching for an implementation of interface P, it might decide to use an implementation of Q.
• weakens – Q is ‘an abstraction of’ P; that is, P is ‘a kind of’ Q. This allows developers to relax constraints and lose exports or parameters. When the linker is searching for an implementation of Q, it can use a P.
• adjusts – Q is ‘similar to’ P. The operations from extension and weakening are both allowed. The linker won’t relate Q and P by interface name, though it will often be feasible for developers to create ‘implementation glue’ modules that can import P and export Q or vice versa.

I think most OO developers would also be familiar with these concepts.

The critical bit, I think, is that each constraint (assertion, invariant, etc.) will need to be named if we are to allow relaxation of them.

Module Versioning

Modules can easily be versioned, often with extends/weakens inheritance or a little implementation glue from a previous version. I think it feasible that interfaces could even be immutable after construction – i.e. named with their version or secure hash – or perhaps accessible in those terms.

Constraint-Based Linkers

There are several similarities to the prior system:

• Implementation modules are anonymous, ambiguous, subject to search.
• A search can fail due to failing an import or not finding a solution that meets invariants.
• Searches will be a function of parameters.
• The amount of search tends to grow with the number of modules.
• There is no way for an individual module to prevent use of search.
• Search based on preference heuristics is feasible (though not described in this article).
• Easy support for multiple versions of a module.

And there are also many advantages:

• Much less verbose. No need to increase verbosity to reduce ambiguity.
• Interface names will provide a decent record of human intent. It is unlikely that a search system will substitute one implementation module for another in a ‘bad way’, based on similar structure.
• Creating a new interface name is an easy way to control searches.
• Weakly ‘opt-in’ – developers can easily avoid importing interfaces known for heavy search.
• Effective indexing – interface names provide a common attribute for the majority of indexing requirements, which is much less ad-hoc.

I’m not sure whether this is the right balance of search and specification in any absolute sense, but I’m inclined to favor this two-tiered interface and implementation approach over the purely anonymous variation.

User-Defined Syntax

In an earlier article on user-defined syntax, I noted that use of parametric modules or search makes ‘import’ of a language module an impossibility (assuming a requirement to statically parse the modules).

The module system described here has an interesting property whereby every module either inherits or implements exactly one interface module. This opens the possibility of defining the syntax in the interface.

I have not explored this possibility very thoroughly, but my first inclination is rejection: the language of implementation is not, properly, a concern of the interface being implemented.

At the moment, I continue to favor that each module header is actually two lines: one to specify the language module, one to specify the semantic structure of the module (e.g. interface vs. implement).

Wiki Integration?

When I gave up on names a while back, I cried a tear because one my vision of a wiki-based IDE was dead in the water. Granted, I’ve had much time to re-envision that concept, and have some nifty ideas for distributed development that don’t rely much on names.

The clean mix of named interfaces and anonymous implementations, however, will serve very nicely and can bring back a lot of wiki-like features. Each interface could provide an automated set of backlinks to the implementations and related interfaces. Each implementation would provide links to interfaces.

Grammar?

Here’s a sketch, ignoring user-defined syntax.

Start = Interface | Implement
InterfaceName = Name('.'Name)*
Name = [A-Za-z][a-zA-Z0-9_]*
Interface = 'interface' InterfaceName IFRest
IFRest = 'weakens' InterfaceName (WeakensDecl*)
       | 'extends' InterfaceName (ExtendsDecl*)
       | 'adjusts' InterfaceName (WeakensDecl | ExtendsDecl)*
ExtendsDecl = '\n' (ProvideDecl | RequireDecl | DefaultDecl | SpecifyDecl)
WeakensDecl = '\n' (ExcludeDecl)
RequireDecl = 'require' Name 
DefaultDecl = 'default' Name VExpr 
ProvideDecl = 'provide' Name 
SpecifyDecl = 'specify' Name SpecRule 
ExcludeDecl = 'exclude' Name 

Implement = 'implement' InterfaceName Args? (ImplementDecl*) Export?
Args = '(' Name ')' -- optional, to capture args as record
ImplementDecl = '\n' (Define | Import)
Import = 'import' InterfaceName VExpr? 'from' VExpr ('as' Name)?
Define = 'define' Name VExpr
Export = 'export' VExpr 

Notes on the grammar:

1. As the grammar is defined, interface inheritance is not optional. I’m assuming an empty root interface ‘Void’ will be provided for bootstrap. (i.e. interface Foo extends Void)
2. There is no enforced relationship between interface names and interface inheritance. Interface names are not namespaces. The dotted structure is only meaningful to developers.
3. Uniqueness of interface names, and acyclic inheritance, would be externally enforced (by compilers, IDEs, databases, etc.). Within each registry, interface names should be unique.
4. `require` specifies a parameter, and `provide` specifies an export. These are simply names.
5. Parameters, and possibly exports too, can be set with a `default` value. A value expression is allowed, and an interesting possibility is to specify defaults as an expression from other parameters or exports. In Awelon, values are acyclic and I’d probably require redefining any inherited defaults that would introduce a cycle based on the new definition.
6. An implementation module is required even if the interface defaults everything. It could be very trivial, though: the simplest implementation module is simply `implement InterfaceName`
7. Specifications cover assertions, types, heuristic preferences, and similar. Specifications are named mostly so they can be weakened (excluded).
8. Within an implementation module, I’m assuming name pollution is controlled by the 'as' Name option. Developers will probably receive a warning in case of name shadowing.
9. The 'from' VExpr in imports is for matchmakers or search-spaces. I described these in the earlier article. I still need to consider how matchmakers or search spaces will interact with the interface names. Different search spaces might act as ‘true’ namespaces, unlike interface names.
10. The Args is to capture parameters in a named record. Otherwise the names will be provided as part of the initial environment – which isn’t very convenient when forwarding those parameters to another import.
11. The Export option is to specify exports via record. Otherwise, the names would be taken from the final environment. Export offers a lot of precise control.