Monday, July 25, 2011

Adapting one interface to implement another

We bumped into an interesting problem in ParaSail recently.  We have an abstract module Countable which has the following interface:
abstract interface Countable<> is
    op "+"(Left : Countable; Right : Univ_Integer) -> Countable;
    op "+"(Left : Univ_Integer; Right : Countable) -> Countable;
    op "-"(Left : Countable; Right : Univ_Integer) -> Countable;
    op "-"(Left, Right : Countable) -> Univ_Integer;
    op "=?"(Left, Right : Countable) -> Ordering;
end interface Countable;
This interface is used when defining a "countable interval" such as "X .. Y" where you want to be able to iterate from X up to Y, even though X and Y are not themselves of an integer type. For example, if X and Y are characters, it makes sense to define an interval such as 'a' .. 'z' and there is a desire to be able to go from 'a' to the next character in the interval, so by using the "+" operator from Countable that is easy to do. Just add 1. Similarly, we can iterate through the interval in reverse by subtracting 1. Or we can find out how big is the interval X..Y by computing (Y - X) + 1, where we are using the second "-" operator.

Other examples of "countable" types are representations of time, where you can add and subtract some number of clock ticks, or compute the number of clock ticks between two times, even if the "time" type itself isn't necessarily represented as a single integer. And in general any ordered enumeration type (such as Enum<[#monday,#tuesday,#wednesday, ...]>) might want to be considered Countable, so that intervals can be defined and manipulated.

A Countable_Set abstraction would be useful as a way to represent sets of Countable elements, while still efficiently representing contiguous ranges of values such as "1..1000" as part of the set. For example:
interface Countable_Set<Element_Type is Countable<>> is
    op ".."(Left, Right : Element_Type) -> Countable_Set;
    op "|"(Left, Right : Countable_Set) -> Countable_Set;
    op "in"(Left : Element_Type; Right : Countable_Set) -> Boolean;
    func Count(CS : Countable_Set) -> Univ_Integer;
    ...
end interface Countable_Set;
Implementing the Count function clearly will need to make use of the "+" or "-" Countable operations. But this now brings us to the question, is Integer itself a Countable type? Can we legally write Countable_Set<Integer>? Well if we look at the binary "+" and "-" operators for Integer we see:
interface Integer<...> is
    op "+"(Left, Right : Integer) -> Integer;
    op "-"(Left, Right : Integer) -> Integer;
    ...
end interface Integer;
These don't actually match the operators expected for a Countable type. And if we were to simply add the missing operators, we would create significant ambiguity, since "X + 1" could either resolve to the existing Integer,Integer->Integer "+" or to the added Countable one, Integer,Univ_Integer->Integer "+". Not ideal.

More generally, we can see a situation where a useful abstraction, such as a Countable_Set, expects a type parameter such as Countable<>, and the type we have is close but is missing some of the required operations, and we don't really want to add the missing operations for general use because of ambiguity, or they don't quite do the right thing, or whatever. Ideally we would want to make them available for implementing a given interface or interfaces, but not for general use.

Some languages provide mechanisms for addressing problems like these. In Eiffel, as part of inheriting from another class the derived class can rename some of the operations. With that approach, on inheriting these Countable operations we would rename them to something like "Countable_Plus" and "Countable_Minus" and then define them to do whatever we want. In C++ it is possible to disambiguate particular operations by specifying from which base type they are inherited.

In ParaSail we are pursuing somewhat of a different approach. Essentially we are allowing a module to publicly declare that it is implementing various operations that might be needed to be considered "Countable" or "Hashable" or whatever, while not making them available for "general" use. Here is how the ParaSail Integer module solves the Countable conundrum:
interface Integer<...> is
    op "+"(Left, Right : Integer) -> Integer;
    op "-"(Left, Right : Integer) -> Integer;
    ...
  implements
      for Countable
    op "+"(Left : Integer; Right : Univ_Integer) -> Integer;
    op "+"(Left : Univ_Integer; Right : Integer) -> Integer;
    op "-"(Left : Integer; Right : Univ_Integer) -> Integer;
    op "-"(Left, Right : Integer) -> Univ_Integer;
end interface Integer;
You can also omit the "for Countable" part and then the operations are available to implement any other module's interface.  But the key thing is that you cannot call these operations directly on an Integer type.  You can only invoke them when "viewing" an Integer as a "Countable" object.  You can have multiple sections after "implements" each section starting with "for Interface1, Interface2, ..." if there are several different sets of operations that need to be implemented to satisfy the needs for different sets of interfaces.  In general situations like this are expected to be rare, but when you bump into one, it is useful to have a way to avoid the ambiguity and still satisfy the needs of the other interface.

4 comments:

  1. This happens to be the same solution C# uses -- see http://stackoverflow.com/questions/143405/c-interfaces-implicit-and-explicit-implementation#143425. There, it's called explicit interface implementation.

    ReplyDelete
  2. Thanks for pointing that out. The C# mechanism is a little different, in that either you implement implicitly, or you implement a given operation for exactly one other interface. The mechanism in ParaSail is a bit more flexible, though it is not clear whether that added flexibility is a big deal. Also in ParaSail, a group of operations can all be treated the same way, rather than having to respecify on each operation.

    ReplyDelete
  3. In Ada, the solution to the problem is to define local subprograms that provide the missing operations. If I find myself needing the same subprograms in another place, I move them to a child package, so they can be shared.

    I think the equivalent here would be a derived interface Countable_Integer, declaring the missing ops and hiding the rest of the ops.

    That doesn't require editing the original class whenever this situation is encountered, which is a good thing.

    Hiding the undesired ops is not strictly necessary; is there a way to hide inherited operations in Parasail (I didn't search the manual)?

    ReplyDelete
  4. Stephe asks: "Hiding the undesired ops is not strictly necessary; is there a way to hide inherited operations in Parasail (I didn't search the manual)?"

    The feature described above effectively hides the operations declared following the "implements" reserved word. These operations cannot be called directly.

    As far as inheritance, ParaSail doesn't require a module to specify in advance all of the other modules it might implement. A check is made that a module has the necessary operations in its interface (either before or after the "implements") when it is used as an actual type to match some formal type in an instantiation.

    If the user chooses to explicitly specify the intent to "implement" another module, the compiler will make sure that the necessary operations are there. This can help with maintenance, and as a way to express intentions. But if at some point some new interface is defined, there is no need and add it to the list of interfaces "implemented" by a given module. When it comes to instantiation, "if the shoe fits you can wear it."

    Note that this isn't going all the way to what is sometimes called "duck" typing. Inside the class for a ParaSail module, the code can only use operations that are defined on the formal types specified in the interface, and when the module is instantiated, a check is made that each actual type has all of the operations expected of the corresponding formal type. It is just that the actual type does not have to name explicitly the formal type as one of the modules it implements.

    See http://parasail-programming-language.blogspot.com/2010/08/ad-hoc-interface-matching-in-parasail.html for more discussion of this issue.

    ReplyDelete