Towards a New Model of Abstraction in Software Engineering

Abstraction is of the most important concepts in engineering. Without abstraction, large projects become unable to handle. Imagine writing a word processor in 1's and 0's. You can't do that. Therefore you use the abstraction of a compiler that translates a human readable language into 1's and 0's that a computer can understand. However, abstractions are sometimes "leaky":http://www.joelonsoftware.com/articles/LeakyAbstractions.html. A leaky abstraction is an abstraction that doesn't always act as you expect it to. For example, if you program using two-dimensional arrays it doesn't really seem to matter which dimension is chosen as the first index and which as the second:

int[,] array = new int[255,16];

You could loop over it like so (loop 1):

int sum = 0;
for(int i = 0; i < 255; i++) {
   for(int j = 0; j < 16; j++) {
      sum = array[i,j];
   }
}

or like so (loop 2):

int sum = 0;
for(int i = 0; i < 16; i++) {
   for(int j = 0; j < 255; j++) {
      sum = array[j,i];
   }
}

The result would be the same. Yet, depending on how two-dimensional arrays are implemented, the performance of one of those two will be dramatically better than the other.

As you know memory basically is a big one-dimensional array of bytes. Because RAM memory is a bit slow, many processors use caches. When you want to retrieve the Xth byte from your RAM memory, byte X+1, X+3, X+4 (and some others) are loaded aswell and stored in the cache, which is a much faster memory. So when you access memory sequentially (0, 1, 2, 3, 4), many bytes can just be obtained from the cache, which is much faster than from the RAM memory.

How are two-dimensional arrays stored in memory? That depends on the compiler of your programming language. Let's assume the following array:

int a[2,4];

This could either be layed out in memory like this (lay-out A):

|a[0,0]|a[0,1]|a[0,2]|a[0,3]|a[0,4]|a[0,5]|a[1,0]|a[1,1]|a[1,2]|...

or like this (lay-out B):

|a[0,0]|a[1,0]|a[2,0]|a[3,0]|a[4,0]|a[5,0]|a[0,1]|a[1,1]|a[2,1]|...

Now let's look at the the two loops I mentioned before. How will loop 1 be executed on memory layout A? The second index changes faster (because it's in the inner loop). So with memory layout A it would first access array[0,0], then array[0,1], then array[0,2] etc. This means that with memory layout A it would access memory the quick way: sequentially. But what if memory layout B is used? Then it would jump from one place in the memory to the other (first memory address 0, then 255, 512 etc.). This is much slower as the memory cache isn't utilized.

Conclusion: in order to use two-dimensional arrays with an as high performance as possible you still have to know the underlying implementation. Therefore the abstraction of the multi-dimensional array is leaky.

In this case the solution lies in just switching the order of the indices, but in some cases you simply have to reimplement the abstraction to make it work for you. "This is an insteresting paper":http://www2.parc.com/csl/groups/sda/publications/papers/Kiczales-IMSA92/for-web.pdf about this leaky abstraction problem that also offers a solution for it. The example that's mentioned in this paper is writing a spreadsheet using the existing abstraction of a window system. You would say that cells in a spreadsheet are like little windows. So you can use the existing window functionality to render cells. However, apparantly the window abstraction is built to be used for only a couple of windows, not thousands as you would need with a spreadsheet. Therefore you end up reimplementing window-like components that do scale up the way you use them.

The solution proposed consists of using a dual-interface:

What begins to emerge is a "dual-interface" picture something like that shown in Figure 5. A high-level system(i.e. CLOS) presents two coupled interfaces: base- and meta-level. The base-level interface looks like the traditional interface any such system would present. It provides accessto the system’s functionality in away that the application programmer can make productive use of and which does not betray implementation issues.

The client programmer can work with it without having to think about the underlying implementation details. But, for those cases where the underlying implementation is not adequate, the client has a more reasonable recourse. The meta-level interface provides them with the control they need to step in and customize the implementation to better suit their needs. That is, by owning up to the fact that users needs access to implementation issues (i.e. instance implementation strategy), and providing an explicit interface for doing so, the metaobject protocol approach manages to retain what is good about the first two principles of abstraction.

Interesting read. You can find "the paper here":http://www2.parc.com/csl/groups/sda/publications/papers/Kiczales-IMSA92/for-web.pdf.