Composition, delegation and interface -- a 20K ft critique of Noop

Someone just asked me to give my opinion on Noop's composition proposal. It reminds me a little bit of Self which found its way into JavaScript. It also reminds me a little of Haskell's type classes. In general, movement away from inheritance is good. The proposal, however, feels a bit like looking for the lost quarter where the light is good, rather than where you lost it. Before considering delegation machinery, let's consider the value of an interface. How many interfaces are there? One way to see that is just to consider all the sub interfaces of a single interface with n methods on it. Hmmm... that's 2^n interfaces. That's a lot. Does that give us any confidence that any one way of carving up functionality via interfaces is going to be sane? Further, in practice, do we see random distribution through this very large space?

What we see over and over again in practice is that the answer to these questions is 'no!'. That means that there is something that binds a collection of methods together. What might that something be? One place to look is mathematics. Which maths should we look at? The maths of category theory has been very fruitful both in explaining existing functional programming techniques and -- perhaps more importantly -- suggesting ways to improve them as well as wholly new techniques. What we find in category theory is that it is natural to collect maps (read functions) together. A good example of such a beast is a monad. A monad -- viewed categorically -- is

• a map, T, taking types to new types and functions on those types to new functions. Let's call the universe of types and functions expressible in our model of computation (as proscribed by our programming language), C. Then T : C -> C.
• a higher order map, unit. Just like T takes C to C, we can understand a "noop" like map that takes C to C, call it Id. Then unit : Id -> T. We intuitively think about it as putting basic types inside the container T, but it's really a higher order map.
• another higher order map, mult : T^2 -> T. We talk about it as a kind of flattening (and in Scala it's called flatMap), but it's a higher order map.

Now, one is not finished spelling out a monad when giving this collection of maps. One must also show that they satisfy certain constraints.

• T is functorial, meaning T g f = T(g) T(f)
  
• unit and mult are natural transformations, look up the meaning because unpacking it here would take to long
• mult( mult T ) = mult( T mult )
• mult( unit T ) = mult( T unit )

This set of constraints must go with the monad. This example provides a little more detail in terms of what binds a group of maps together, and hence of what might replace the notion of interface and explain what we see in practice. Good programmers invariably pick out just a few factorizations of possible interfaces -- from the giant sea of factorizations (read different ways to carve up the functionality). The reason -- i submit -- is because in their minds there are some constraints they know or at least intuit must hold -- but they have no good way at the language level to express those constraints. A really practical language should help the programmer by providing a way express and check the constraints that hold amongst the maps in an interface.

i submit that this idea is not the same as "design by contract". i am not proposing an Eiffel-like mechanism. Again, taking a functional approach to computation via category theory leads one towards modeling interfaces as categorical "situations" like monads, comonads, distribution laws, etc. This means that a large number of the constraints come down to

• functoriality
• naturality
• coherence

Language support for this approach might include keywords for these kinds of assertions. It is a gnarly beast to offer automatic and/or compiler support for checking general constraints. Even this limited family of constraints that i'm proposing can generate some very difficult computations, with very bad complexity. However, for those situations where a general purpose solution to check assertions of functoriality, naturality and coherence are infeasible, one can use these hints to generate tests to probe for possible failures. This idea follows in the same spirit of replacing proof with proof-checking.

[Note: just after i posted this Tony Morris posted some ScalaCheck code that lines up precisely with what i am talking about. Here are some checks for functoriality. Here are some checks for coherence.]

So, we might consider a specification of the form

situation Monad[T,A] {

unit : A -> T[A]

mult : T[T[A]] -> T[A]

functorial(T);

natural(unit);

natural(mult);

coherent(T,unit,mult);

}

Of course, this is not the only way to go. i've yet to be convinced that category theory offers a good account of concurrency. Specifically, categorical composition does not line up well with concurrent composition. So, interfaces organized around types for concurrency is also something to consider. In this case, one might find a natural beginning in interfaces in which -- roughly speaking -- the methods constitute the tokens of a formal language the constructors of which are given by the types for concurrency paradigm.

Regardless of whether the constraints associated with an interface are categorical in nature or derived from behavioral types the key point is that they are the principal value in the interface. Take a hint from the failure of inheritance. One of the central failings of inheritance was its bad interaction with concurrency. Documenting the issues around the inheritance-synchronization "anomaly" (tell tale name) was a cottage industry in the late '80's and throughout the '90's. The issue is that specialization can relax behavior relative to synchronization guarantees provided at a superclass. Because inheritance does nothing to support or enforce the synchronization constraints it is actually harmful in the concurrent setting. The moral -- again -- is that constraints make the interface. How about we look at that problem before we enable delegation through 2^n possibilities -- most of which -- let's face it -- are not going to work?