Ask not what an object is, but...

I can barely remember the days when objects were seen like a new, shiny, promising technology. Today, objects are often positioned between mainstream and retro, while the functional paradigm is enjoying an interesting renaissance. Still, in the last few months I stumbled on a couple of blog posts asking the quintessential question, reminiscent of those dark old days: “what is an object?”

The most recent (September 2012) is mostly a pointer to a stripped-down definition provided by Brian Marick: “It’s a clump of name->value mappings, some functions that take such clumps as their first arguments, and a dispatch function that decides which function the programmer meant to call”. Well, honestly, this is more about a specific implementation of objects, with a rather poor fit, for instance, with the C++ implementation. It makes sense when you’re describing a way to implement objects (which is what Marick did) but it’s not a particularly far-reaching definition.

The slightly older one (July 2012) is much more ambitious and comprehensive. Cook aims to provide a “modern” definition of objects, unrestricted by specific languages and implementations. It’s an interesting post indeed, and I suggest that you take some time reading it, but in the end, it’s still very much about the mechanics of objects ("An object is a first-class, dynamically dispatched behavior").

Although it may seem ok from a language design perspective, defining objects through their mechanics leaves a vacuum in our collective knowledge: how do we design a proper object-oriented system?

Cut the red wire!

We're all familiar with this scene: the good guys trying to save the day (or the world) by defusing a bomb. Quickly running out of time, they have to cut a wire. Failure is not an option. The red bar won't turn into a green bar.

What if you had to write code that works the very first time? What if you had no chance to test your code, let alone fixing bugs? You got only one chance to run your code and save the world. Would that change the way you write? The way you think? How? What can you learn from that?

Lest you think I'm kinda crazy: I'm not actually suggesting that you shouldn't test your code. I'm not actually suggesting that you stop doing your test-driven thing (if you do) or that you forget your test plan (if you have one), etc etc.
Consider this like a stretching exercise. We may learn something useful just by going outside our comfort zone. Give it a try.

Notes on Software Design, Chapter 13: On Change

We have a long history of manipulating physical materials. Cavemen built primitive tools out of rocks and sticks. I would speculate :-) that they didn't know much about physics, yet through observation, serendipity and good old trial and error they managed to survive pretty well, or we wouldn't be here today talking about software.

For centuries, we only had empirical observations and haphazard theories about the real nature of the physical world. The Greek Classical Element were Earth, Water, Air, Fire, and Aether, which is not exactly the way we look at materials today. Yet the Greeks managed to build large and incredibly beautiful temples.

Of course, today we know a quite a bit more. Take any kind of physical material, like a copper wire. In the real world, you can:

- apply thermal stress to the material, e.g. by warming it. Different materials react differently.

- apply mechanical stress to the material, e.g. by pulling it on both ends. Different materials react differently.

- apply electromagnetic forces, e.g. by moving the wire inside a magnetic field. Different materials react differently.

- etc.

To get just a little more into specifics, if we restrict ourselves to mechanical stress, and focus on the so-called static loading, we end up with just a few kind of stress: tension, compression, bending, torsion, and shear (see here and also here).

Although people have built large, beautiful structures without any formal knowledge of material science, it is hard to deny the huge progress made possible by a deeper understanding of what is actually going on with materials. Knowledge of forces and reactions allows us to choose the best material, the best shape, and even to create new, better materials.

The software world
Although we can build large, even beautiful systems, it is hard to deny that we are still in the dark ages. We have vague principles that usually can't be formally defined. We have different materials, like statically typed and dynamically typed languages, yet we don't have a sound theory of forces, so we end up with the usual evangelist trying to convert the world to its material of choice. It's kinda funny, because it's just as sensible as having a Brick Evangelist trying to convince you to use bricks instead of glass for your windows ("it's more robust!"), and a Glass Evangelist trying to convince you to build your entire house out of glass ("you'll get more light!").

Indeed, a key realization in my exploration on the nature of software was that we completely lack the notion of force. Sure, we use a bunch of terms like "flexibility", "heavy load", "fast", "fragile", etc., and they all seem to be somehow inspired by physics, but in the end it's just vernacular usage without any kind of theory behind.

As I realized that, I began looking for a small, general yet useful set of "software forces". Nothing too fancy. Tension, compression, bending, torsion, and shear are not fancy, but are incredibly useful for physical materials (no, I wasn't looking for similar concepts in software, but for something just as useful).

Initially, I focused my attention on artifacts, because design is very much about form, and form is made visible through artifacts. I got many ideas and explored several avenues, but most seemed more like ad hoc concepts or turned out to be dead ends. Eventually, I realized we already knew the fundamental forces, though we never used the term "force" to characterize them.

Interestingly, those forces are better known in the run-time world, and are usually restricted to data. Upon closer scrutiny, it turned out they also apply to procedural knowledge, and to the artifact world as well. Also, it turned out that those forces were intimately connected with the concept of entanglement, and could actually shed some light on entanglement itself. More than that, they could be used to find entangled information, in practice, no more philosophy, thank you :-).

So, let's take the easy road and see what we can do with run-time knowledge expressed through data, and build from there.

It's almost too simple
Think about a simple data-oriented application, like a book library. What can you do with a Book record? It's rather obvious: create, read, update, delete. That's it. CRUD. (I'm still thinking about the need for an identity-preserving Move outside the database realm, but let's focus on CRUD right now). CRUD for run-time data is trivial, and is a well-known concept.

CRUD in the artifact world is also relatively simple and intuitive:

Create: we create a new artifact, being it a component, a class, a function.

Read: this got me thinking for a while. In the end, my best shot is also the simplest: we (the contingent intepreter) read the function, as an act of understanding. More on the idea of contingent/essential interpreter in a rather whimsical :-) presentation by Richard Gabriel, that I already suggested a few years ago.

Update: we change an artifact; for instance, we change the source code of some function.

Delete: we remove an artifact; for instance, we remove a member function from a class.

Note that given the fractal nature of software, some operations are recursively identical (by deleting a component we delete all the sub-artifacts), while others change nature as we move into the fractal hierarchy (by creating a new class inside a component we're also updating the component). This is true in the run-time world of data as well.

Extending CRUD to run-time procedural knowledge is not necessarily trivial. Can we talk about CRUD for functions (as run-time, not compile-time, concepts)? We usually don't, but that's because the most common material and tools (programming languages) we're using are largely based on the idea that procedural knowledge is created once (through artifacts), then compiled and executed.

However, interpreted languages always had the possibility of creating, updating and deleting functions at run-time. Some compiled languages allow dynamic function creation (like C#, through Reflection.Emit) but not update/delete. The ability to update a function through reflection would be an important step toward AOP-like possibilities, but most languages have no support for that. This is fine, though: liquids can't be compressed, but that didn't prevent us from defining the concept of compression. I'm looking for concepts that apply in both worlds (artifacts and run-time) but not necessarily to all materials (languages, etc.). So, to summarize:

- Create, Update, Delete retain the usual meaning also for the run-time concept of functions. It means we're literally creating, updating and deleting a function at run-time. The same applies to the (run-time) concept of class (not object). We can Create, Update, Delete classes at run-time as well (given the appropriate language/material).

- Read, in the artifact world, is the human act of reading, or better, is the contingent interpreter (us) giving meaning to (interpreting) the function. At run-time, the equivalent notion is execution, with the essential interpreter (the machine) giving meaning to the function. Therefore, reading a function in the run-time world simply means executing the function. Executing a function may also update some data, but this is fine: the function is read, data are updated; there is no contradiction.

Where do we go from here?
I'm trying to keep this post short, so I'll necessarily leave a lot of stuff for next time. However, I really want to anticipate something. In my previous post I said:

Two clusters of information are entangled when performing a change on one immediately requires a change on the other.

I can now state that better as:

Two clusters of information are entangled when a C/R/U/D on one immediately requires a C/R/U/D on the other.

Yes, the two definitions are not equivalent, as Read is not a Change. The second definition, however, is better, for reasons we'll explore in the next few posts. One reason is that it provides guidance on the kind of "change" you need to consider. Just restrict yourself to CRUD, and you'll be fine. As we'll see next, we can usually group CD and RU, and in fact I've defined two concepts representing those groupings.

Entanglement through CD and/or RU is not necessarily a bad thing. It means that the entangled clusters are attracting each other, and, inasmuch as that specific force is concerned, rejecting others. In other words, they want to form a single cluster, possibly a composite cluster in the next hierarchical level (like two functions attracting themselves and creating a class). Of course, it might also be the case that the two clusters should be merged into a single cluster.

We'll see more about different form of CRUD-induced entanglement in the next few posts. We'll also see how many concepts (from references to database normalization) are actually just ways to deal with the many forms of entanglement, or to move entanglement from the artifact space to the run-time space. Right now, I'll use my remaining time to explain polymorphism through the entanglement perspective.

Polymorphism explained
Consider the usual idea of multiple shapes (circle, triangle, rectangle, etc.) that can be drawn on a screen. In the pre-object era (say, in ANSI C) we could have defined a ShapeType enum, a Shape struct with a ShapeType field and possibly a ShapeData field, where ShapeData would have probably been a union (with all fields for all different shapes). Draw would have been implemented as a switch/case over the ShapeType field.

We have U/U entanglement between ShapeType and ShapeData, and between ShapeType and Draw. U/U means that whenever we update ShapeType we need to update ShapeData as well. I add the Spiral type, so I need to add the relevant fields in the ShapeData union, and add logic to Draw. We also have U/U entanglement between ShapeData and Draw: if we change the way we store shape data, we have to change the Draw function as it depends on those data. We could live with that, but is not pretty.

What if we have another function that depends on ShapeType, like Area? Well, we need another switch-case, and Area will have the same kind of U/U entanglement with ShapeType and ShapeData as Draw. It is that entanglement that is bringing all those concepts together. ShapeType, ShapeData, Draw and Area want to form a cluster.

Note that without polymorphism (language-supported or simulated through function pointers) the code mass is organized into a potentially degenerative form: every function (Draw, Area, etc) is U/U-entangled with ShapeType, and is therefore attracting new procedural knowledge related to each and every ShapeType value. The forcefield will make those functions bigger and bigger, unless of course ShapeType is no longer extended.

Object-oriented polymorphism "works" because it changes the gravitational centers. Each concrete class (Circle, Triangle, etc) becomes a gravitational center for procedural and structural knowledge entangled with a single (ex)ShapeType value. In fact, ShapeType no longer needs to exist at all. There is still U/U-entanglement between the (ex)ShapeData portion related to Circle and the procedural knowledge in Circle.Draw and Circle.Surface (in a Java/C#ish syntax). But this is fine, because they have now been brought together into a new cluster (the Circle class) that then rejected the other artifacts (the rest of the ShapeData fields, the other functions). As I said in my previous post, entanglement between distant element is bad.

Note that we don't really change the mass of code. We just organize it differently, around different gravitational centers. If you draw functions as tall boxes in the switch-case form, you can see that classes are just "wide" boxes cutting through functions. The area of the boxes (the amount of code) does not change.

Object-oriented polymorphism in a statically-typed language also requires [interface] inheritance. This brings in a new form of U/U-entanglement, this time between the interface and each and every concrete class. Whenever we change the interface, we have to change all the concrete classes.

Interestingly, some of those functions might be entangled in the run-time world: they tend to be called together (R/R-entanglement in the run-time space). That would suggest yet another clustering (in the artifact space), like separating all the drawing operations from the geometrical operations in different interfaces.

Note that the polymorphic solution is not necessarily better: it's just a matter of probability. If the set of functions is unstable, plain polymorphism is not really a good answer. We may want to explore a more complex solution based on the Visitor pattern, or some other clustering of artifacts. Understanding entanglement for Visitor is indeed an interesting exercise.

Coming soon (I hope :-)
CD and RU-entanglement (with their real names :-), paving our way to the concept of isolation, or shielding, or whatever I'm gonna settle for. Oh guys, by the way: happy new year!

Notes on Software Design, Chapter 12: Entanglement

Mechanical devices require maintenance, some more than others. Maintenance is intended to keep them working, because mechanical parts tend to wear out. Maintenance is required so that they can still work "as new", that is, do the same thing they were built to do.

Software programs require maintenance, some more than others. Maintenance is intended to keep them useful, because software parts don't wear out, but they get obsolete. They solve yesterday's problems, not today's problems. Or perhaps they didn't even solve yesterday's problems right (bugs). Maintenance is required so that software can so something different from what it was built to do.

Looking from a slightly different perspective, software is encoded knowledge, and the value of knowledge is constantly decaying (see the concept of half-life of knowledge). Maintenance is required to restore value. Energy (human work) must be supplied to keep encoded knowledge current, that is, valuable.

Either way, software developers spend a large amount of their time changing stuff.

Change
Ideally, changes would be purely additional. We would write a new software entity (e.g. a class) inside a new artifact (a source file). We would transform that artifact into something executable (if needed; interpreted languages don't need this step). We would deploy just the new executable artifact. The system would automagically discover the new artifact and start using it.

Although it's possible to create systems like that (I've done it many times through plug-in architectures), programs are not written this way from the ground up. Plug-ins, assuming they exist at all, usually appears at a relatively coarse granularity. Below that level, maintenance is rarely additional. Besides, additional maintenance is only possible when the change request is aligned with the underlying architecture.

So, the truth is, most often we can't simply add new knowledge to the system. We also have to change and remove existing parts. A single change request then results in a wave of changes, propagating through the system. Depending on some factors (that I'll discuss later on) the wave could be dampened pretty soon, or even amplified. In that case, we'll have to change more and more parts as the wave propagates through the system. If we change a modularized decisions, the change wave is dampened at module boundary.

The nature of change
Consider a system with two hardware nodes. The nodes are based on completely different hardware architectures: for instance, node 1 is a regular PC, node 2 is a DSP+ASIC embedded device. They are connected through standard transport protocols. Above transport, they don't share a single line of code, because they don't calculate the same function.
Yet, if you change the code deployed in node 1, you have to change some (different) code in node 2 as well, or the system won't work. Yikes! Aren't those two systems loosely coupled according to the traditional coupling theory? Sure. But still, changes need to happen on both sides.

The example above may seem paradoxical, or academic, but is not. Most likely, you own one of those devices. It's a decoder, like those for DVB-T, sat TV, or inside DivX players. The decoder is not computing the same function as the encoder (in a sense, it's computing the inverse function). The decoder may not share any code at all with the encoder. Still, they must be constantly aligned, or you won't see squat.

This is the real nature of change in software: you change something, and a number of things must be changed at the same time to preserve correctness. In a sense, change is affecting very distant, even physically disconnected components, and must be simultaneous: change X, and Y, Z, K must all change, at once.

At this point, we may think that all the physical analogies are breaking down, because this is not how the physical world behaves. Except it does :-). You just have to look at the right scale, and move from the familiar Newtonian physics to the slightly less comfortable (for me, at least) quantum physics.

Quantum Entanglement
Note: if you really, really, really hate physics, you can skip this part. Still, if you never came across the concept of Quantum Entanglement, you may find it interesting. Well, when I first heard of it, I thought it was amazing (though I didn't see the connection with software back then).

You probably know about the Heisenberg Uncertainty Principle. Briefly, it says that when you go down to particles like photons, you can't measure (e.g.) both position and wavelength at arbitrarily high precision. It's not a problem of measurement techniques. It's the nature of things.

Turns out, however, that we can create entangled particles. For instance, we can create two particles A and B that share the same exact wavelenght. Therefore, we can try to circumvent the uncertainty principle by measuring particle A wavelength, and particle B position. Now, and this is absolutely mind-blowing :-), it does not work. As soon as you try to measure particle B position, particle A reacts, by collapsing its wave function, immediately, even at an arbitrary distance. You cannot observe A without changing B.

Quoting wikipedia: Quantum entanglement [..] is a property of certain states of a quantum system containing two or more distinct objects, in which the information describing the objects is inextricably linked such that performing a measurement on one immediately alters properties of the other, even when separated at arbitrary distances.

Replace measurement with change, and that's exactly like software :-).

Software Entanglement
The parallel between entangled particles and entangled information is relatively simple. What is even more interesting, it works both in the artifact world and in the run-time world, at every level in the corresponding hierarchy (the run-time/artifact distinction is becoming more and more central, and was sorely missing in most previous works on related concepts). On the other hand, the concept of entanglement has far-reaching consequences, and is also a trampoline to new concepts. This post, therefore, is more like a broad introduction than an in-depth scrutiny.

Borrowing from quantum physics, we can define software entanglement as follows:

Two clusters of information are entangled when performing a change on one immediately requires a change on the other.

A simple example in the artifact space is renaming a function. All (by-name) callers must be changed, immediately. Callers are entangled with the callee. A simple example in the run-time space is caching. Caching requires cache coherence mechanisms, exactly because of entanglement.

Note 1: I said "by name", because callers by reference are not affected. This is strongly related with the idea of dampening, and we'll explore it in a future post.

Note 2: for a while, I've been leaning on using "tangling" instead of "entanglement", as it is a more familiar word. So, in some previous posts, you'll find mentions to "tangling". In the end, I decided to go with "entanglement" because "tangling" has already being used (with different meaning) in AOP literature, and also because entanglement, although perhaps less familiar, is simply more precise.

Not your granpa coupling
Coupling is a time-honored concept, born in the 70s and survived to this day. Originally, coupling was mostly concerned with data. Content coupling took place when a module was tweaking another module's internal data; common coupling was about sharing a global variable; etc. Some forms of coupling were considered stronger than others.

Most of those concepts can be applied to OO software as well, although most metrics for OO coupling takes a more simplified approach and mostly consider dependencies as coupling. Still, some forms of dependency are considered stronger than others. Inheritance is considered stronger than composition; dependency on a concrete class is considered stronger than dependency on an interface; etc. Therefore, the mere presence of an interface between two classes is assumed to reduce coupling. If class A doesn't talk to class B, and doesn't even know about class B existence, they are considered uncoupled.

Of course, lack of coupling in the traditional sense does not imply lack of entanglement. This is why so many attempts to decouple systems through layers are so ineffective. As I said many times, all those layers in business systems can't usually dampen the wave of changes coming from the (seemingly) innocent need to add a field to a database table. In every layer, we usually have some information node that is tangled with that table. Data access; business logic; user interface; they all need to change, instantly, so that this new field will be put to use. That's entanglement, and it's not going away by layering.

So, isn't entanglement just coupling? No, not really. Many systems that would be defined as "loosely coupled" are indeed "heavily entangled" (the example above with the encoder/decoder is the poster child of a loosely coupled / heavily entangled system).

To give honor to whom honor is due, the closest thing I've encountered in my research is the concept of connascence, introduced by Meilir Page-Jones in a little known book from mid-90s ("What Every Programmer Should Know About Object-Oriented Design"). Curiously enough, I came to know connascence after I conceived entanglement, while looking for previous literature on the subject. Stille, there are some notable differences between connascence and entanglement, that I'll explore in the forthcoming posts (for instance, Page-Jones didn't consider the RT/artifact separation).

Implications
I'll explore the implications of entanglement in future posts, where I'll also try to delve deeper into the nature of change, as we can't fully understand entanglement until we fully understand change.

Right now, I'd like to highlight something obvious :-), that is, having distant yet entangled information is dangerous, and having too much tangled information is either maintenance hell or performance hell (artifact vs run-time).

Indeed, it's easy to classify entanglement as an attractive force. This is an oversimplification, however, so I'll leave the real meat for my next posts.

Beyond Good and Evil
There is a strong urge inside the human being to classify things as "good" and "bad". Within each category, we further classify things by degree of goodness or badness. Unsurprisingly, we bring this habit into computer science.

Coupling has long been sub-classified by "strength", with content coupling being stronger than stamp coupling, in turn stronger than data coupling. Even connascence has been classified by strength, with e.g. connascence of position being stronger than connascence of name. The general consensus is that we should aim for the weakest possible form of coupling / connascence.

I'm going to say something huge now, so be prepared :-). This is all wrong. When two information nodes are entangled, changes will propagate, period. The safest entanglement is the one with the minimum likelihood of occurrence. Of course, that must be weighted with the number of entangled nodes. It's very similar to risk exposure (believe or not, I couldn't find a decent link explaining the concept to the uninitiated :-).

There is more. We can dampen the effects of some forms of entanglement. That requires human work, that is, energy. It's usually upfront work (sorry guys :-), although that's not always the case. Therefore, even if I came up with some classification of good/bad entanglement, it would be rather pointless, because dampening is totally context-dependent.

I'll explore dampening in future posts, of course. But just to avoid excessive vagueness, think about polymorphism: it's about dampening the effect of a change (which change? Which other similar change is not dampened at all by polymorphism?). Think about the concept of reference. It's about dampening the effect of a change (in the run-time space). Etc.

Your system is not really aligned with the underlying forcefield unless you have strategies in place to dampen the effect of entanglement with high risk exposure. Conversely, a deep understanding of entanglement may highlight different solutions, where entangled information is kept together, as to minimize the cost of change. Examples will follow.

What's next?
Before we can talk about dampening, we really need to understand the nature of change better. As we do that, we'll learn more about entanglement as well, and how many programming and design concepts have been devised to deal with entanglement, while some concepts are still missing (but theoretically possible). It's a rather long trip, but the sky is clear :-).

Notes on Software Design, Chapter 10: Run-Time Friction

So, here is the story. I keep a lot of notes. Some are text files with relevant links and organized ideas. Most are rather embarrassing scribbles on just about any piece of paper that is lying around when I need it. From time to time, I move some notes from paper to files, discard concepts that didn't prove themselves, and rearrange paragraphs to fake some kind of logical, sequential reasoning over a process that was, in fact, rather chaotic. Not surprisingly (since software is just another way to encode knowledge), David Parnas suggested long ago that we could do the same while documenting software design (see "A rational design process: How and why to fake it").
Well, it's not always easy. Sometimes, I try to approach the storytelling from an angle, see that it doesn't work out so well, and look for another. Sometimes I succeed, sometimes I don't (although, of course, the reader is the ultimate judge). This time, I have to confess, I feel like I couldn't find the right angle, the right way to start, to unfold a concept in a way that makes it look simple and natural. So I'll trust you to be smart enough to make sense of what follows :-). It's a very long post, and you may want to digest it in more than one session.

The physical world
I guess you all had to push some furniture around at one time or another. You have probably felt a stronger resistance in the beginning, followed by a milder form of resistance as soon as you got some movement.
The mild resistance is due to kinetic friction, while the initial, stronger resistance is usually due to static friction, that you have to overcome before moving the object (if you're not familiar with kinetic and static friction, wikipediawill tell you more than you want to know :-).

As you move your stuff around, friction makes you waste some energy, in a way that is basically proportional to the normal force, the distance, and the coefficient of kinetic friction (see the page above for the actual equation). I'll get back to this later, but if you move a constant mass on a flat surface, the energy you waste is proportional to the mass you move, the distance you go, and the magic coefficient of friction.

The beauty of all this is that it's simple and rather unambiguous. Friction is always present in mechanical engineering, but it's a well understood concept (as far as engineering is concerned; it's still blurry at the quantum level, at least for the uninitiated like myself), and there is usually no wishy-washy talking about friction. It's not a broad concept, that is, you won't be able to design the next-generation jet engine if all you have in your conceptual toolbox is friction, yet you won't be able to design an engine at all without an appreciation of friction.

The software world
I'm first and foremost a software design practitioner: I design software, almost every day. Sometimes by myself, most often with other people; therefore, I do a lot of "design talk". In many cases, at one point or another, someone is going to bring in "performance" or "efficiency" to support (or reject) a design decision.
We use those words a lot, with different meaning depending on who's saying it and why he's saying it. It seems like I'm never tired of linking wikipedia, so here is a page on computer performance. Just look at the initial list of different, context-dependent meanings. It's not surprising, then, to find out some people have very peculiar views of performance. "I use arrays because they're more efficient". Sure, except that then you do a linear search because you need multiple indexes; say "efficient" again :-)?

One might expect Computer Science (with capital letters :-) to come to the rescue and define terms more precisely, and hopefully with some relevance for practice. However, computer science is more concerned with computational complexity theory than with the nitty-gritty details of being "fast".
Now, don't get me wrong. You won't get too far as a programmer (and definitely not as a software designer) if you don't get the concept of complexity classes, if you can't see that an algorithm is O( n^2 ) and another is O( n log n ), or if you don't even know what the Big Oh notation is all about. You have to know this stuff, period. In a sense, complexity theory is part of the math of software, and there is little point in investigating a physics of software if you don't get the math first. But math alone won't cut it. However, once we get past the complexity class we get very little assistance from computer science (and I'm purposely ignoring the fact that just because an algorithm is in the O( n log n ) class in the average case doesn't mean I can't beat it with an O( n^2 ) algorithm in my practical cases).

On the "software engineering" side, the usual advice is to build the program and then use a profiler. Yeah, well, sure, beats banging your head against the wall :-), but it's not exactly like knowing what you're doing all along. Still, we make a lot of low-level design decisions while coding, and many of them will ultimately impact "performance". Lacking the basic terminology to think (and talk) about this kind of stuff is rather depressing, so why don't we try to move just a tiny step forward?

Wasting energy in software
So, here I have this piece of software (executable knowledge). For most practical applications, what I need is to get some data (interactively, from a DB, through some kind of device, whatever), transform it in a meaningful way (which could be a complex process encoded in thousands of lines), and spit out some results (which is still data, anyway). The transformation is the Function.

On the artifact side, our software may be using global variables all around, or be based on a nice polymorphic structure, yet the Function doesn't care. The structure we provide on the artifact side is the domain of Form (by now, you're probably familiar with all this stuff).

Now, transformation is a process, and no real-world process is 100% efficient; it's always going to waste something. Perhaps we should look better at that "waste" part. Something I learnt a long time ago, while pondering on principles and patterns, is that overly general concepts (like "performance") must give way to more specialized notions.

Some code, please :-)
Consider this short portion of C code. I'm using C because it's a low-level language, where the implications of any given choice are relatively easy to understand.

double max( double x, double y )
  {
  if( x > y )
    return x;
  else
    return y;
  }

double max3( double x, double y, double z )
  {
  double d = max( x, y );
  d = max( d, z );
  return d;
  }

The code is pretty obvious. In a common, stack-based CPU architecture, max3 will copy x and y on the stack and call max; then it will copy d and z and call max again. The return value might be stored in a CPU register or in RAM, depending on the compiler.

Copying those values is a waste of energy, of course. I could manually inline max inside max3 and get rid of that waste. I would sacrifice reusability and perhaps clarity for "higher performance" or "higher efficiency" or "reduced waste". Alternatively, the compiler could inline the function on my behalf (see Chapter 6 for the role of languages on balancing the two worlds).

What if I'm working on some large data structure? The Fortran guy down the corner will suggest that by keeping your structures in the common area / global memory, you won't even have to pass parameters around: every function knows exactly where to get input and where to store output! Again, we'll sacrifice reusability, and perhaps duplicate large portions of code, for sake of efficiency. As you go through most literature on High Performance Computing (see, for instance, The Ideal HPC Programming Language, recently reprinted in Communications of ACM), you'll see that the HPC community is constantly facing the problem of wasted cycles, and is wasting a lot of LOC to prevent that.

Moving data around is not the only way to waste energy. Consider this portion of real-world code, written by a (supposedly) performance-conscious "little meritocracy":

static int is_rfc2822_header(char *line)
{
int ch;
char *cp = line; 
if (!memcmp(line, "From ", 5) || !memcmp(line, ">From ", 6))
  return 1;
while ((ch = *cp++)) { 
  if (ch == ':')
    return cp != line;
  if ((33 <= ch && ch <= 57) ||
     (59 <= ch && ch <= 126))
    continue;
  break;
  }
return 0;
} 

yeah, it's ugly as hell, but it's also wasteful (which is funny, for reasons that are too long to explain here). If you read it carefully, you'll find a way to optimize the "while" body quite a bit, and while you're at it, you can easily make it more readable. Also, the two memcmp in the beginning are wasting cycles (going through the first 5 characters twice), but just like the coefficient of friction must be measured in practice, at this level any alternative should really be measured on a real-world CPU.

Note: as we optimize code, we have to assume that is correct. We don't change Form unless we know that the Function is right. Before posting this, I checked for any update to the codebase (I got that code a few years ago, and it never looked right to me). The code is still the same, but now there is also a comment explaining what the function is intended to do. Unfortunately, it's not what it's doing, which is even more ironic, for the same unspoken reasons above. Anyway, we could easily fix the bug and still optimize the code.

Run-time Friction
Just like in the physical world we move object around, in the run-time world of software we move knowledge around. More exactly, we move data around (we call it data flow) and we move the execution point around (we call it control flow). We move that stuff around to calculate some Function. In the process of calculating the Function, we usually waste some cycles. We waste cycles because we have to copy data on the stack, or from one data structure to another. We waste cycles because we do unnecessary comparison, computations, jumps. We waste cycles because we process the same data more than once. Most often, we waste those cycles because we get something in exchange in the Form (artifact) domain. Sometimes, we waste cycles just because of bad coding.

The energy waste is not a constant: copying an integer is different from copying an array of integers (that's weight, of course). Also, if your array has been swapped out to the paging file, the copy is going to cost you more: that's the contribution of distance, and I'll get back to this later. Right now, remember that wasted energy is a consequence of friction, but is not friction.

Causes and types of software friction
We have already seen a few cases of software friction: when you copy data, you waste cycles. Max3 didn't strictly need to copy data: the Function didn't care about reusing max, only Form did. Before we try do define friction more precisely, it's interesting to see how deep the analogy with real-world friction really is. Indeed, we even have static software friction, and kinetic software friction!

Consider a Java (or .NET) virtual machine. When you hit a function for the first time, the code is compiled just in time. This has nothing to do with Function. It is a byproduct of a technological choice. It will cost you some cycles: that's friction. Also, it happens only once, to "put things in motion": that's static friction. In general, static friction will increase latency, while kinetic friction will reduce throughput. Good: we just sorted out the two main components of "performance".

Consider a web service. Before you can call the server, you go through a relatively lengthy process, from high-level stuff (marshaling your data) to low level stuff (establishing a network connection). This is all friction: the Function is happening on the other side, inside the service code. Here we see both static and kinetic friction at play: establishing a connection adds latency, exchanging data over the network reduces throughput.

Consider stored procedures. The ideal stored procedure takes little data in input, does significant CRUD inside, and returns little. This way, we have minimal waste due to kinetic friction, as we exchange little data with the database. Of course, this is not the only way to minimize energy waste: another approach would be to reduce distance, by bringing the database itself in-process. Interestingly, most real-time databases use the second approach.

So, what is causing friction in software? Friction is caused by:

• A copy of data from one place to another (e.g. parameter passing, temporary variables, etc), as this adds no meaning to data, and therefore is useless as far as Function is concerned.


• Syntactical transformation of data (e.g. marshaling) which adds no semantics (as above: this processing is not part of the Function). This includes any form of data transformation needed to talk over a non-native protocol.


• Unnecessary statements (like those that could be removed in the C function above).


• Redundant access / processing (some will be removed by the compiler, but some won't)


• Bookkeeping (allocation, deallocation, reference counting, heap defragmentation, garbage collection, paging, etc). All this adds no semantics, and it's irrelevant for the Function: indeed, a well-written garbage collected program should behave properly under the so-called null garbage collector.


• Unnecessary indirection. This is a long story and I'll leave for another time, as I've yet to talk about indirection in the physics of software.


• In general, everything that is not strictly necessary to calculate the Function, but has been added because of Form, or because of the programmer's inability to streamline the code to the mere Function, is a source of friction and will waste run-time energy.

Defining friction
At this stage in my understanding of the physics of software, it's still hard to come up with numbers, coefficients, sometimes even formulas. Actually, I'm usually happy when I get some concept right. Still, let's look at a simplified formula for the energy wasted through friction (in the real world):

Normal Force * Coefficient of Friction * Distance.

That would hold pretty well in the software world as well, both at the qualitative (easier) and probably quantitative (not there yet) level. At the qualitative level, it tells us what we can control and perhaps leverage. I'll explore this in the next paragraph. At the quantitative level, it could help to evaluate low-level choices. First, however, we have to define Normal Force, Coefficient of Friction, and Distance.

I've defined distance in the run-time world in Chapter 9. Unfortunately, it's an ordinal scale, so we can't do math with distance. This sort of rules out any chance to have a quantitative definition of friction, but we can also look at it from the other side: a better understanding of friction energy (like: wasted cycles) could shed light on the right measurement scale for distance!

Assuming a flat world (I have no reason to think otherwise) the Normal Force is just weight. Weight could be easily defined as the number of bytes involved. For instance, the cost of a copy is linear with the number of bytes you copy.

The coefficient of friction is a dimensionless parameter. Interestingly, if we decide to measure energy in cycles (which makes some sense, although we usually think of cycles as time, not energy) that would imply that unit of measurement for Distance is cycles/byte. I'll have to think more about this.

Although the coefficient of friction, in the real world, cannot be predicted but only measured, we have some intuitive grasp of it being related to the materials. As the aforementioned wikipedia page explains, it's a relatively complex "system property", depending on many factors. The same applies in the software world. The cost to move a bunch of bytes from one position to another dependes on a bunch of factors. If we want to raise the abstraction level and think in terms of objects, and not bytes, things become more complex. The exact copy semantics (reference, shallow, deep) kicks in. That's fine: a software material with shallow copy semantics would have a different coefficient of friction than one with reference copy semantics.

Overall, I think we have little control over the coefficient of friction (I might be wrong), so for any practical purpose, distance and weight are the most interesting parameters.

Is it useful, anyway?
A good theory, and a good concept, must have a good explanatory power, that is, we should be able to use them to explain known phenomena, explain why something works, rationalize widespread practice or beliefs, etc.

As I've already discussed, the evolution of programming languages can be largely seen as an attempt to balance the world of artifact / form with the run-time / function world. In this sense, we can look for instance at the perfect forwarding problem, solved by right value references in the next C++ standard, as a further attempt to remove some energy waste, by avoiding unnecessary copy of data. C++ provides many ways to control friction energy, mostly in the area of generic programming and also template metaprogramming. The Curiously Recurring Template Pattern, for instance, provides a form of static polymorphism exactly to avoid some friction due to unnecessary indirection (virtual dispatch).

More generally, the simple equation for energy waste provides a clue on what we can actually control: weight, distance, coefficient of friction. This is it. As we shape software, this is what we can actually change if we want to reduce friction energy.

Consider HTTP compression: distance couldn't be changed, so we had to change weight.

Also, understanding the difference between static and kinetic friction explains a lot of existing practices. Think of the Nagle's algorithm. It works by increasing static friction (therefore latency) in exchange for lower kinetic friction (therefore throughput). Once you get your concepts right, so many things unfold so easily :-).

Finally, the analogy holds to the extremes: just like excessive friction in mechanical systems can lead to jam, excessive friction due to paging can jam a software system. This is commonly known as Trashing.

I think a caveat is in order: friction in the physical world is not necessarily evil. Wasn't it for friction, we couldn't even walk. Mechanical devices have to deal with friction all the time, but they also exploit friction all the time. It's harder to exploit friction in software (although the Nagle's algorithm does). Most often, we must see friction as a trade/off with other properties, mostly in the artifact side. Still, an understanding of the different types of friction, and of the constituents of friction energy, can help evaluate alternatives and even generate new, better ideas in a more systematic and (dare I say it :-) scientific way.

A different angle
I choose friction as a physical analogy because it's a simple, familiar concept. Intuition and everyday experience can easily compensate any lack of engineering knowledge. Still, I've been tempted to use different analogies, like hydraulic or electrical analogies. Indeed, there are several analogies between electrical, mechanical, hydraulic and even acoustic and optical systems (see here for a start), so it's always possible to choose a different reference system.

Anyway, my alternative would have been to model everything after resistance and current. Current would be the equivalent of throughput, or "performance", and resistance would cause thermal dissipation. In the end, I didn't go this way for a number of reasons; for instance, one-shot stuff like JIT would require something like a thermistor (think of a PTC in CRT degaussing), but I would lose a few readers that way :-).

Still, if you followed so far, there is an interesting result I'd like to share. Consider a trivial circuit where we apply 1V to a 1 ohm resistor, resulting in 1A current. Now, I'll replace the resistor with a series of 2, with resistance (1-P) and P ohms. Nothing changes, same current. Resistors represent processes.

Now say that we have this concept of parallel execution, so the process carried out by P can be parallelized. By way of the analogy, to increase throughput (current) I can simply add up to N resistors in parallel. Now the circulating current is obviously 1 / (1-P + P/N) A. Guess what, I just rediscovered Amdahl's Law using Ohm's Law. That's cute :-).

Ok guys, next time I'll have a much shorter post on the artifact-side notion of friction. If we survive that, we'll be ready for tangling.

Notes on Software Design, Chapter 7: a better Forcefield Diagram

In my previous post in the NOSD series, I mentioned how an improved forcefield diagram was needed to model the kind of reasoning I'm trying to bring in software design. I also discussed the artifact-run/time dualism, and how many concepts in language design were born out of the fundamental need to balance conflicting forces between these two worlds. I also mentioned the role of some patterns in resolving the same kind of conflict.

Here I'll show you a practical example, introducing the improved forcefield notation as we go. It's quite simple, and as usual, the reasoning is more important than the drawing. I'll use new colors and shapes, but it's all very informal, the notation is not cast in stone, and it will probably evolve and change over time.

A common problem
You have two classes (Class1, Class2); as we learnt in Chapter 6, that usually means you have two artifacts, and right now I feel like blue is a good color for artifacts, so I'll color them in blue.

Now, those classes have some commonality in behavior; for instance, they both represent a geometrical object, and can provide you with a bounding box.
Behavior is a run-time concept, and I'll color that information in pink.

Commonality in behavior is an attractive force; I haven't talked about this yet, but trust me : ), or just rely on your intuition that "things that do similar things are close to each other".

Commonality in behavior also attracts a natural desire in the artifact space: polymorphic/uniform access to such behavior. While writing calling code, I'd like to ask for a bounding box in the same way, perhaps polymorphically through a base class / interface. That would make my client (partially) unaware of the specific classes.

Unfortunately, Class1 and Class2 have been written with different conventions. They don't share a base class; they don't use the same naming for functions; they may not even use the same types for parameters. Different conventions are an artifact issue, so I'll color this in blue again. Of course, different conventions are keeping Class1 and Class2 apart, and actively rejecting polymorphic / uniform access. So here is the forcefield, representing our problem:



Note that there is nothing here about a solution. At this stage, the forcefield is a representation of the problem. Still, we have a conflict between forces, and somehow we have to deal with it. What if we don't? I'll keep that as last.

Enter decisions
A missing concept in my previous attempts at modeling the forcefield was the very important notion of decision. Although I'm trying to keep concepts to a bare minimum, the Decision Space is an important piece of the puzzle, and there can't be a Decision Space without Decisions. I'm using a yellow hexagon to represent a decision.

So, how can we deal with those conflicting forces? A simple, technically sound decision is to refactor Class1 and Class2 to a common base class (or interface, or a hierarchy of both). That decision has a strong impact on "Different Conventions", effectively removing it from the forcefield, including the rejection lines. I think the diagram speaks for itself:



So, decisions can alter the forcefield, for better or worse. Still, we may choose to keep the artifacts unchanged. Perhaps Class1 and Class2 come from third-party libraries, or perhaps they're shared with a lot of existing code, and refactoring may impact that code as well (remember Mass and Inertia). Again, it's useful to represent this decision explicitly, although it's just an intermediate step. I colored "Different Conventions" in green to say that we deliberately decided to keep it inside the forcefield.



Patterns
Design patterns are now mainstream, with dozens of books and hundreds, if not thousands, of papers describing the problem / context / solution triad.
Now, the solution is usually represented using a UML diagram and/or some source code. Problem and context are described using text, or an example in UML/code. That's because we don't (didn't :-) have any proper way to describe a problem (forcefield) and context (mostly, pre-made decisions).
Still, look at the picture above once again: that's (of course :-) the problem/context setting for a well-known pattern: adapter. So let's look at the adapter in action, or how using adapter will impact the forcefield:



Adapter "simply" breaks the rejection between Different Conventions and Polymorphic / Uniform Access, therefore allowing client code to ignore the specific interface of Class1 and Class2. It is very interesting to observe what the forcefield is telling us: we didn't completely remove conflict. There is still an attraction/rejection between Class1 and Class2. In this sense, Adapter is less effective than refactoring (which, however, requires us to change the artifacts).
That conflict will emerge over time; for instance, adding common functionality will take more time, possibly some duplication of code, etc. This kind of "consequence" is not very well documented in the GoF book.

Note: there is no redundancy with code here: we're talking about the problem space and the decision space. Contrast this with the usual redundancy between a UML diagram and code (with pros and cons, as usual). Also, isn't this diagram much better at communicating design problems, decisions, and impact than the largely ignored design rationale tools and notations?

What else?
There is also a different decision we can make; it's a particularly bad decision, therefore it's also very popular :-) wherever code quality is easily ignored. We can just forgo uniform access, and have clients deal with a non-uniform interface (through if, switch/case, whatever). This is what I meant by "not dealing with conflict" earlier. I called that decision "Tangled Clients" for reasons that will become clear in a future post.



Time out
Last time I said I would provide some examples of conflicting forces in the non-software world. I'll have to cut this post short, because the forcefield diagram I've come up with would take too much to explain. But I'll offer a few pointers for those of you with some time to spare:

- Very simple: the adapter is extremely frequent in the real world as well, as the well-known socket adapter. The forcefield is remarkably similar, but finding the exact translation of every concept is not necessarily trivial. Try this out :-).

- Harder, some engineering knowledge is required. Rotating pumps may leak (why? hint: some empty space is needed if you want something to rotate freely :-). Old pumps just used a seal, which wasn't really good at preventing leaks. At some point (I think around 1940) the end face mechanical seal has been adopted as a better seal for rotating pumps. However, the fluid can still leak, which ain't that good in a number of cases. An interesting solution here is the magnetic drive pump (look it up, guys :-). Draw the forcefield for the problem, and represent how using a magnetic field to transmit movement can compensate otherwise conflicting forces. By the way, this is the example I was thinking about when I wrote my previous post.

- Manufacturing is actually full of great examples of conflicting forces and different approaches to compensate or overcome conflict. Think about thermal grease, just to give a starting point. The list is endless. Trying to model some forcefield in detail is a fascinating exercise.

- If you want to stay on the software side, here is an interesting one. Take some programming language feature (for instance, if you use .NET, you may consider partial classes or attributes; if you use Java, annotations) and identify which tension between the run-time world and the artifact world they're meant to solve. Partial classes are a simple, but interesting exercise: most criticism I've heard about them is stemming from a very partial :-) understanding of the surrounding forcefield, just like the common abuse I've seen (split a large class in two files :-)).

As usual, there is much more to say about compensating forces, the artifact/run-time dual nature of software, and so on, including an unexpected intuition on economy of scale that I got just yesterday while running. See you soon, and drop me a line if you try this stuff out :-)

Notes on Software Design, Chapter 6: Balancing two Worlds

Back in my time, computer science students were introduced to the distinction between syntax and semantics from day one. That distinction is central in understanding programming languages from the algebraic perspective.

When you are looking for a theory of software forces, however, you'll find another distinction more useful. We have artifacts, and we have run-time instances of artifacts.

Software is encoded knowledge, and as software developers we shape that knowledge. However, we can't act on knowledge itself: we must go through a representation. Source files are a representation, UML diagrams are a representation, and so on.
Source files represent information using a language-specific syntax; for instance, if you use Java or C#, you encode some procedural and structural knowledge about a class inside a text file. The text file is an artifact; it's not a run-time thing. Along the same lines, you can use UML and draw a class diagram, encoding structural knowledge about several classes. That's another artifact. Often, when we say "class C" or "function foo" what we mean is actually its representation inside an artifact (a sequence of LOCs in a source file, where we encode some knowledge in a specific language).
Artifacts can be transformed into other artifacts: without mentioning MDA, you can just compile a bunch of source files and get an executable file. The executable file is just another artifact.

At that point, however, you can actually run the artifact. Let's say that you get a new process: the process is a run-time instance of the executable file artifact. Of course, you may start several run-time instances of the same artifact.

Once the process is started, a wonderful thing happens :-). Your structural and procedural knowledge, formerly represented through LOCs inside artifacts, is now executable as well. Functions can be called. Classes can be instantiated. A function call is a run-time instance of a function. An object is a run-time instance of a class.

We never shape the run-time instances directly. We shape artifacts (like a class described through textual Java or C++) so as to influence the run-time shape of the instances. Sometimes we shape an artifact so that its run-time instances can shape other run-time instances (meta-object protocols, dynamically generated code, etc).

Interestingly, some forces apply at the artifact level, while other forces apply at the instance level. If we don't get this straight, we end up with the usual confusion and useless debates.

A few examples are probably needed. As I haven't introduced enough software forces so far, I'll base most of my examples on -ilities, because the same reasoning applies.

Consider reusability: when we say that we want to reuse "a class" what we usually mean is that we want to reuse an artifact (a component, a source file). Reusing a run-time instance is a form of object caching, which might be useful, but is not what is meant by reusability.

Consider efficiency: when we say "this function is more efficient" what we usually mean is that its run-time instances are faster than other comparable implementations.

Consider mass and gravity (the only software property/force I've introduced so far). Both are about the artifacts.

I guess it's all bread-and-butter so far, so why is this distinction important? In Chapter 1, I wrote: a Center is (in software) a locus of highly cohesive information. in order to create highly cohesive units, we must be able to separate things. so this is what software [design] is about: keeping some things near, some things distant.

Now here is something interesting: in many cases, we want to keep the artifacts apart, but have the run-time instances connected. This need to balance asymmetrical forces in two worlds has been one of the dominant forces in the evolution of programming languages and paradigms, although nobody (as far as I know) has properly recognized its role.

Jump on my time machine, and get back to the 70s. Now consider a sequence of lines, in some programming language, encoding some procedural knowledge. We want to reuse that procedural knowledge, so we extract the lines into a "reusable" function. Reusability of procedural knowledge requires physical separation between a caller and a (reusable) callee (that's basically why subroutines/procedures/functions had to be invented). So, we can informally think of reusability as a force in the artifact world, keeping things apart.
Now consider the specular world of run-time instances. Calling a function entails a cost: we have to save the instruction pointer, pass parameters, change the IP, execute the function's body, restore the IP and probably do some cleanup (details depend on language and CPU). Reusability on the artifact side just compromised efficiency on the run-time side. In most cases, we can ignore the side-effect in the run-time world. Sometimes, we can't, so we have two conflicting forces.
Enter the brave language designer: his job is to invent something to bring balance between these two forces, in two different worlds. His first invention is macro expansion through pre-processing (as in C or macro assemblers). C-style macros may solve the problem, but they bring in others. So the language designer gets a better idea: inline expansion of function calls. That works better. However is done, inlining is a way to keep things apart in the artifact world, and strictly together in the run-time world.

Move along time, and consider concepts like function pointers, functions as first-class objects, or polymorphism: again, they're all about keeping artifacts apart, but instances connected. I don't want the artifact defining function/class f to know about function/class g, but I definitely want this instance of f to call g. Indeed (as we'll explore later on) the entire concept of indirection is born out of this basic need: keep artifacts apart and instances connected.

Consider AOP-like techniques: once again, they are about separating artifacts, while having the run-time behavior composed.

Once you understand this simple need, you can look at several programming concepts and clearly see their role in balancing forces between the two worlds. Where languages didn't help, patterns did. More on this next time.

At this point, however, we can draw another conclusion: that a better forcefield diagram would allow us to model forces (in the two worlds) and how we intend to balance those forces (which is how we intend to shape our software), and keep these two aspects apart. After all, we may have different strategies to balance forces out. More on this another time (soon enough, I hope).

Interestingly, software is not alone in this need to balance forces of attraction and rejection. I'll explore this in my next post, together with a few more examples from the software world. I also have to investigate the relationship between the act of balancing forces and the decision space I've mentioned while talking about inertia. This is something I haven't had time to explore so far, so it's gonna take a little more time.