Monthly Archives: November 2010

Encapsulation Considered Harmful

You heard me. Encapsulation is an obstacle to the reuse of code.

When I say encapsulation, I mean having a region of your program that knows or has access to some information about the implementation of something, and hiding that information from the rest of the program. If you have another definition of encapsulation, I’m not arguing against that.

Why do software engineers encapsulate? I claim it is for two major reasons: (1) to reserve the right to change the encapsulated code later without breaking anything, and (2) to minimize the propagation of assumptions through the program. To illustrate this, consider the following C code which uses a (supposedly) abstract List type:

int sum(List* list) {
    int i;
    int accum = 0;
    int length = List_length(list);
    for (i = 0; i < length; ++i) {
        accum += ((int*)list)[i];
    }
    return accum;
}

This code breaks encapsulation. It assumes that List is represented as an array. So if we wanted to go back and change List to a linked list because it is more efficient in the majority of cases for which we are using it, sum would break. (In this example, it would break very badly — i.e. it might not even segfault but instead return some nonsense number)

Here is an example of code that correctly respects encapsulation.

int sum(List* list) {
    int i;
    int accum = 0;
    int length = List_length(list);
    for (i = 0; i < length; ++i) {
        accum += List_get_elem(list, i);
    }
    return accum;
}

If you’re about to object that we should have exposed an iterator interface instead of a indexed get interface because we knew we wanted to change it to a linked list, I preemptively respond that we didn’t know that at the time — as in most code, when you are encapsulating, you don’t usually know what you’re going to come back to change — if you did, why didn’t you just write it like that in the first place?

The two reasons above are noble. They promote flexibility and simplicity, so that the minor decisions we make do not ripple their way through our architecture, making it impossible to change or understand. It takes the pressure off.

Although I agree with the goals, I believe this is the wrong solution. I think we should turn the barriers inside-out, and use only encapsulation’s dual: abstraction. When I say abstraction, I mean code that is defined polymorphically with respect to its assumptions. The above C code is abstract with respect to the list argument, since we can pass it any list we like. It is not, however, abstract with respect to the the List type and its operations — it fixes a single choice.

Encapsulation and abstraction are duals in the following sense: let’s say your program is defined in two parts A and B. A knows some information C, and B does not. There are two ways to look at this. A encapsulates C, or B is abstract with respect to C. That is, if you change C, you have only affected the specification of A, and B reacts polymorphically. So just divide your program at an information boundary — one side is encapsulating, the other side is abstracting.

While mathematically they are two sides of the same coin, there is a very real software engineering difference between them. Let’s say you are have three functions which use your abstract interface: sort, reverse, and frobnicate (some complicated business logic that can’t be written in 5 lines). With encapsulation, you might have this sort of usage graph:

And then, in one fell swoop, you can change it to:

That’s power, that’s flexibility. But… it’s lacking something. Now we have another part of our program which uses arrays, and I sure wish we could use that sort code we’ve already written. But we need that sort code for lists. Hmm, well we could copy and paste. But that sucks, maybe we could go back and make sort polymorphic in the list type. Yeah, that’s the right way to do it.

But, then why didn’t we just do that in the first place? Look what happens when we do:

Look at all those combinations. Those are the possibilities for code reuse without changing anything. Imagine if every encapsulation you made was an abstraction instead. Your usage graph would be basically black with arrows. But these aren’t bad dependency arrows, these are good reuse arrows. These are your possibilities for correctly using code that has already been written.

So I suggest: instead of advertising your guarantees and hiding details, advertise your assumptions and abstract over details. This has a pretty profound effect on the way your code is structured — like I said before, it turns all the encapsulation barriers inside-out.

My inspiration for this idea came from studying the form of mathematical theorems. They advertise their assumptions prolifically: “given a ring R with (+) and (*) as operations, …”, as opposed to “a real number has (+) and (*) and some implementation details”. This allows theorems to be maximally reusable, since although the mathematician was thinking about real numbers when he proved the theorem, he realized the same logic could work on any ring — including the integers, modular integers, matrices, and new things that were discovered later.

Object oriented programming seems to get close. One can consider a class (or an interface) as the specification of an assumption, and an instance the implementation of an assumption. Then you just take parameters that correspond to your assumptions, which are nicely bundled into classes so you don’t have to say “I use (+) and (*) and (-) and absolute value and …”. But this essential idea is muddied up by all sorts of crap, both in the language design and in popular usage.

I started to list the features we need to add/remove from OO languages to make them support this style, but it just got long and nitpicky. So I’ll just say this: I think we should be using objects differently. Objects as implementations of assumptions, not as “agents”. A natural number is not an object, The Natural Numbers is an object. As generics gurus are noticing, this:

interface Number {
    Number operator + (Number y);
}

has got to go. The assumptions are not specified properly — you are requiring that + take any kind of number whatsoever, when we probably mean the same kind of number as on the left side. What does it mean to add 2 (mod 4) to 7 (mod 13)? Instead we are learning to write:

interface Numeric<N> {
    N operator + (N x, N y);
}

That’s the right way. Notice that, although it is specified with different notation, N is just another abstract member of Numeric. We specify the set and its operations together, but the set is distinct from the interface. The interface is the name for the assumption of such a set. In some cases the interface and the set can be bundled into one, and it is these cases that provide most of the study material for OO design. But inside the soul of pop OO lies a form of modeling that is so much more powerful.

To reiterate, this is not breaking the guarantees of encapsulation — anybody who uses Numeric gets encapsulation for free. They are not allowed to see the details of N, just as if you had encapsulated it. It’s just that now you can swap out different N’s in the same code, where you couldn’t before.

I am pleased to see software engineering practice slowly converging on this already. I just thought I would point out the uniform rule behind it. Next time you write an encapsulation, ask yourself, what would it look like to make the users of this code abstract instead? Is it a small enough notational burden to do it that way? If not, what kind of language would allow it to be?

Did that give you something to ponder about? Flattr this

Searchable Data Types

A few years ago, Martín Escardó wrote an article about a seemingly-impossible program that can exhaustively search the uncountably infinite "Cantor space" (infinite streams of bits). He then showed that spaces that can be thus searched form a monad (which I threw onto hackage), and wrote a paper about the mathematical foundations which is seemingly impossible to understand.

Anyway, I thought I would give a different perspective on what is going on here. This is a more operational account, however some of the underlying topology might peek out for a few seconds. I’m no topologist, so it will be brief and possibly incorrect.

Let’s start with a simpler infinite space to search. The lazy naturals, or the one-point compactification of the naturals:

data Nat = Zero | Succ Nat
    deriving (Eq,Ord,Show)
infinity = Succ infinity

Let’s partially instantiate Num just so we have something to play with.

instance Num Nat where
    Zero   + y = y
    Succ x + y = Succ (x + y)
    Zero   * y = Zero
    Succ x * y = y + (x * y)
    fromInteger 0 = Zero
    fromInteger n = Succ (fromInteger (n-1))

We wish to construct this function:

search :: (Nat -> Bool) -> Maybe Nat

Which returns a Nat satisfying the criterion if there is one, otherwise Nothing. We assume that the given criterion is total, that is, it always returns, even if it is given infinity. We’re not trying to solve the halting problem. :-)

Let’s try to write this in direct style:

search f | f Zero    = Just Zero
         | otherwise = Succ <$> search (f . Succ)

That is, if the predicate worked for Zero, then Zero is our guy. Otherwise, see if there is an x such that f (Succ x) matches the predicate, and if so, return Succ x. Make sense?

And it seems to work.

ghci> search (\x -> x + 1 == 2)
Just (Succ Zero)
ghci> search (\x -> x*x == 16)
Just (Succ (Succ (Succ (Succ Zero))))

Er, almost.

ghci> search (\x -> x*x == 15)
(infinite loop)

We want it to return Nothing in this last case. It’s no surprise that it didn’t — there is no condition under which search is capable of returning Nothing, that definition would pass if Maybe were defined data Maybe a = Just a.

It is not at all clear that it is even possible to get what we want. But one of Escardó’s insights showed that it is: make a variant of search that is allowed to lie.

-- lyingSearch f returns a Nat n such that f n, but if there is none, then
-- it returns a Nat anyway.
lyingSearch :: (Nat -> Bool) -> Nat
lyingSearch f | f Zero = Zero
              | otherwise = Succ (lyingSearch (f . Succ))

And then we can define our regular search in terms of it:

search' f | f possibleMatch = Just possibleMatch
          | otherwise       = Nothing
    where
    possibleMatch = lyingSearch f

Let’s try.

ghci> search' (\x -> x*x == 16)   -- as before
Just (Succ (Succ (Succ (Succ Zero))))
ghci> search' (\x -> x*x == 15)
Nothing

Woah! How the heck did it know that? Let’s see what happened.

let f = \x -> x*x == 15
lyingSearch f
0*0 /= 15
Succ (lyingSearch (f . Succ))
1*1 /= 15
Succ (Succ (lyingSearch (f . Succ . Succ)))
2*2 /= 15
...

That condition is never going to pass, so lyingSearch going to keep taking the Succ branch forever, thus returning infinity. Inspection of the definition of * reveals that infinity * infinity = infinity, and infinity differs from 15 once you peel off 15 Succs, thus f infinity = False.

With this example in mind, the correctness of search' is fairly apparent. Exercise for the readers who are smarter than me: prove it formally.

Since a proper Maybe-returning search is trivial to construct given one of these lying functions, the question becomes: for which data types can we implement a lying search function? It is a challenging but approachable exercise to show that it can be done for every recursive polynomial type, and I recommend it to anyone interested in the subject.

Hint: begin with a Search data type:

newtype Search a = S ((a -> Bool) -> a)

Implement its Functor instance, and then implement the following combinators:

searchUnit :: Search ()
searchEither :: Search a -> Search b -> Search (Either a b)
searchPair :: Search a -> Search b -> Search (a,b)
newtype Nu f = Roll { unroll :: f (Nu f) }
searchNu :: (forall a. Search a -> Search (f a)) -> Search (Nu f)

More Hint: is searchPair giving you trouble? To construct (a,b), first find a such that there exists a y that makes (a,y) match the predicate. Then construct b using your newly found a.

The aforementioned Cantor space is a recursive polynomial type, so we already have it’s search function.

type Cantor = Nu ((,) Bool)
searchCantor = searchNu (searchPair searchBool)

ghci> take 30 . show $ searchCantor (not . fst . unroll . snd . unroll)
"(True,(False,(True,(True,(True"

We can’t expect to construct a reasonable Search Integer. We could encode in the bits of an Integer the execution trace of a Turing machine, as in the proof of the undecidability of the Post correspondence problem. We could write a total function validTrace :: Integer -> Bool that returns True if and only if the given integer represents a valid trace that ends in a halting state. And we could also write a function initialState :: Integer -> MachineState that extracts the first state of the machine. Then the function \machine -> searchInteger (\x -> initialState x == machine && validTrace x) would solve the halting problem.

The reason this argument doesn’t work for Nat is because the validTrace function would loop on infinity, thus violating the precondition that our predicates must be total.

I hear the following question begging to be explored next: are there any searchable types that are not recursive polynomials?

Did you like this post? Flattr this