Tuesday, July 27, 2010

Higher-Level versus Higher-Order Abstraction

Engineering in general, and software engineering in particular, is all about abstraction. The creation and utilization of abstractions is a core part of the daily activities of every good engineer, and many engineers are on a never ending quest to increase their level of abstraction. Abstraction both increases productivity and increases the complexity of problems that can be tackled. Few would argue that increased abstraction is a bad thing.

But people do argue about abstraction, and often condemn abstractions that they view as unfit or too complex. It is common to hear a software developer praise the merits of one means of abstraction and then demean another in the same breath. Some abstractions are too general. Some aren't general enough. Some are simply too complex or, ironically, too abstract. So while engineers almost universally agree that abstraction is good, and more abstraction is better; they often disagree fiercely about what genuinely constitutes "better."

What is an abstraction?

Simply put, an abstraction is something that hides the details involved in realizing a concept, and thus frees the engineer to focus on the problem at hand rather than the details of some other concern. This can take many, many forms. The simplest and most common, so common that the term is often used to describe almost all "good" abstractions, is higher-level abstractions.

Higher-level Abstractions

Higher-level abstractions are fairly simple: they encapsulate details so that they can be used without knowledge or concern about the details. Let's consider a simple example in Scala 2.8 (you can copy and paste these examples directly into the Scala 2.8 REPL):

scala> def sum(data: Array[Double]): Double = {
     |   var i = 0
     |   var total = 0.0 
     |   while(i < data.length) {
     |     total = total + data(i)
     |     i = i + 1
     |   }
     |   total
     | }
scala> def mean(data: Array[Double]): Double = sum(data) / data.length

So we have two functions: one that computes the sum of an array of doubles, and one that computes the mean. Pretty much any programmer (professional or otherwise) would feel confident both writing and using such functions. They are written in a modern multi-paradigm programming language yet I bet if you went back in time and showed them to programmers in some of the very first high-level languages they would recognize exactly what they do. They clearly encapsulate the details of performing certain computations. But what's more interesting about them is what's missing from them:

  1. Polymorphism
  2. Closures or first-class functions
  3. Usage or creation of higher-order functions
  4. Other Scala magic such as type classes and implicit parameters

In other words, they provide a simple, layered, hierarchical abstraction in a very bounded way. If we step away from software for a minute, you can imagine a digital designer placing a symbol for an adder or a register on a schematic without worrying about the arrangement of transistors that will be required to realize them in an actual circuit, or a mechanical engineer selecting a standard screw or clamp. These are parts that can be simply built, tested, and composed into larger devices.

Higher-Order Abstraction Take 1: The Mathematics of Fruit

Imagine I have some apples. But unfortunately I'm here, off in the internet, show I can't show them to you. I need an abstraction to tell you about them. For example, I could say I have two apples. Two is a number, and numbers are abstractions. I can use the same number two to describe the number of McIntoshes in my refrigerator or the number of Apple Macintoshes I own. Now let's say I also want to talk about my strawberries and blueberries. I have 16 strawberries and 100 blueberries. How many pieces of fruit do I have? 118! How did I figure that out? I used arithmetic, which is an abstraction of higher order than numbers. How let's say I want to know how many days it will be before I will have eaten all my strawberries. I can write an equation such as: current_fruit - pieces_per_day * number_of_days = fruit_after_number_of_days. I can do even more with this by solving for different variables. This is algebra, and it is a higher-order abstraction than arithmetic. Now let's say I want to build upon that so that I can study the dynamics of the amount of fruit in my refrigerator. I purchase fruit and put it in my refrigerator. I take fruit out and eat it. I forget about fruit and it gets moldy, the I remove it and throw it away. I can capture all of these as a system of differential equations, and using calculus describe all sorts of things about my fruit at any given point in time. Calculus is a higher-order abstraction that algebra. In fact, abstractions similar to the ones built with calculus are what I mean when I say "higher-order abstraction."

At each step up the chain of mathematics both the generality and number of concepts that can be conveyed by a single abstraction increased. In the case of calculus it becomes essentially infinite, and that's the essence of higher-order abstractions: they deal with the infinite or near-infinite. Also, observe that almost everyone from relatively small children on up understand numbers and arithmetic, most adolescents and adults can stumble through applying algebra, and only a very small portion of the population knows anything about calculus, much less can effectively apply it. Also observe that the functions I defined earlier are just below algebra in terms of their order of abstraction.

Higher-Order Abstraction Take 2: Programming in Scala

Let's see if we can sprinkle some higher-order abstraction into our previously defined functions:

scala> def sum(data: Traversable[Double]) = data.foldLeft(0.0)(_ + _)

This definition of sum exposes one higher-order abstraction (polymorphism - it now can use any Traversable[Double] instead of just an Array[Double]), and it uses higher-order functions in its implementation to perform the summation. This new definition is both much shorter and much more general, but it's still relatively approachable, especially for use. Calling it with an Array[Double] works as before, and now it can be used with any number of collections, so long as the collections contain doubles. But forcing the collections to contain doubles is very limiting, so let's see if we can do better:

scala> def sum[T](data: Traversable[T])(implicit n: Numeric[T]): T = {                                  
     |   import n._
     |   data.foldLeft(zero)(_ + _)
     | }

Ahhh, that's better! Much more general. Not only will this work for any numeric type defined in the Scala standard library, but for any numeric type for which the Numeric type class has been defined! It doesn't even need to be in the same class hierarchy! In order to introduce this new level of generality, we've also introduced the following higher-order abstractions:

  1. Classic polymorphism (Traversable instead of Array)
  2. Parametric polymorphism (the type parameter T for various classes)
  3. Higher-order functions and closures (foldLeft and it's argument that does addition)
  4. Type classes (well, Scala's flavor of type classes, e.g. Numeric)

Now, this is the point where people start screaming that abstraction has gone too far. Many professional programmers would look at it and think "WTF?" They could still guess what it does, but the mechanics are quite elusive for anyone that doesn't know Scala reasonably well. That being said, the code is still far more compact than the original imperative version and is extremely general (to which someone replies "Yes, but it's slow a heck compared to the original!"). At this point I would say the order of abstraction has went from being just below algebra to being on par with integral calculus. Just like with mathematics, we see a significant drop off in the number of people who readily understand it.

Higher-Order Abstraction Take 3: Conclusions

Let's consider a short, incomplete list of higher-order abstractions, means of abstraction, and fields that rely upon higher-order abstractions:

  1. Higher-order functions
  2. Polymorphism and parametric polymorphism
  3. Metaclasses such as in Python and Smalltalk
  4. Rich macros such as in Lisp or C++ Templates
  5. Calculus and all the mathematics built upon it (and various other forms of advanced math)
  6. First-order Logic and its kin, and all the higher-order logics
  7. Any physics or other sciences that are built upon calculus
  8. Any engineering or other applications that are built upon physics

Higher-order abstractions tend to exhibit one or more of the following traits:

  1. They deal in infinities (e.g. integration and differentiation in calculus, universal and existential quantification in first-order logic, polymorphism and type classes in programming)
  2. They deal in transformations (e.g. integration and differentiation in calculus, metaclasses and macros in programming)
  3. They rely upon composition rules (e.g. chain rule and integration by parts in calculus, higher-order functions in programming)
  4. Learning to use any given form of higher-order abstraction requires significant effort and discipline, therefore they tend to be the tools of specialists
  5. They form the foundation of our modern, technological society.

The last two can be converted into conclusions:

  1. Higher-order abstractions are critical for most interesting forms of science and technology
  2. You can't expect a colleague or customer from another field to understand the higher-order abstractions in your field, even if his own field is totally immersed in higher-order abstraction

Sphere: Related Content

Saturday, July 24, 2010

Windows 7 Upgrade (so far)

A few weeks ago my wife's Lenovo laptop caught a really nasty virus. Symantec antivirus couldn't clean it up. But I had recovery media (although it was Vista instead of XP), so I used Knoppix to low-level the HD and flashed an updated BIOS (I've had previous experience with viruses that could be stopped via nothing less). Unfortunately the restore media didn't work...it would boot up, think a while, and the reboot. I also tried a XP install using an old XP disk I had laying around, but the XP installer doesn't get along with the new SATA controller in the laptop, so it BSODs. Working around this problem seems to require creating a special driver disk, which seems to require Windows, which creates a problem because all I have are Leopard (about 2 crashes in almost 3 years, a no viruses, versus what seems like a plague on my wife's laptop every 6 months), and Knoppix. So, being a person who value's his time more than his money, I went out and bought a Windows 7 Professional upgrade. All the Microsoft related blogs assured me this would work, and indeed I have a working install the went almost a smooth as butter. The "almost" is the activation process. I have yet to successfully activate. Going into this my assumption was I would have to call Microsoft in order to activate. What I didn't realize is that their human systems don't seem any smarter than their automated systems. So first I called the phone number that Microsoft's support website told me to call. Several layers deep this told me to call a special activation line. I want to commend Microsoft at this point for avoiding such advanced technology as call transfers. You really can't trust technology that's decades old. It's better to let people transfer themselves. So I call the line, and speak to a very friendly automated system. It's asking me for my "installation id," but there isn't one. There isn't one because the computer is connected to the internet, and some genius decided that if one has the internet one would never use the phone system, which would normally be true if some brilliant licensing policy maker hadn't decided that the only way to activate a "clean install" is via the phone system. Anyway, the nice automated system transfers me to a human being. Guess what the human asks me for? An installation id. I tell him I don't have one. I read the various things on my screen to him. He then asks if I am connected to the internet. I say yes. He tells me to disconnect. I disconnect and start over, ultimately ending up in the same place with no installation ID. The support person gives up and tells me I have a deep technical problem, which will require technical support, not activation support (I'm now imaging myself setting up a conference call with tech support, activation support, and the nice automated system lady). Tech support is of course only a US working hours affair, not a Saturday evening affair. It turns out the automated support guy just wasn't persistent enough. After hanging up, I reboot the computer and try again without internet. It appears to get me to the same place, except when I hit the magic "next" button, instead of receiving a message telling me that my product key is not valid, I receive an installation ID and am told to call the activation line (which is a 3rd phone number, but gets me to the same place as the first). I want to take a moment to point out some huge flaws here:

  1. The automated system just assumed I would have an installation ID, and had no explanation of how I was supposed to obtain one or why I might not see one, while the activation software is explicitly designed to not provide one to someone connected to the internet
  2. The human being had a vague idea that being connected to the internet was a problem, although he didn't realize it until repeating his requests half a dozen times, and even though he had a vague idea how to induce Windows 7 into providing one, he didn't actually know and gave up quickly
  3. About 2 minutes would of poking after 30 minutes of bouncing around on the phone rewarded me with an installation id
Ok, so let's try again. This time I provide the installation id to the automated system, and the automated system informs me that it is invalid, and sends me to another human being. After 5 or 10 minutes the human being informs me that I need to have a Microsoft OS already installed in order to use an upgrade, and that I cannot use a clean install. He says it is impossible that Windows XP would refuse to install, and thinks it's completely reasonable that I would install one OS just to install another. I rant at him for a few minutes about how my product packaging says nothing about not being able to do a clean install (in fact, it's the only way to upgrade from XP according to the included instructions, although maybe it does some magic if the installer reformats the HD instead of the user already doing it). Anyway, I explain this all to him while trying to remain calm. He puts me on hold. Then when he comes back he tells me that he gave me wrong information because a server is down, and that I need to call back in 30 minutes when the server is up. So I did that. This time after I read my installation ID to the support person, which he told me was invalid. He told me to exit activation and enter my product key again. I dutifully did this, then he put me on hold while he waited for my product key to come up. This of course would never happen, because I wasn't connected to the internet, and it fact cannot obtain an installation id when connected to the internet. After a few minutes on hold, I was transfered to Microsoft technical support, which of course was closed. So let's recap so far:
  1. None of the Microsoft activation people or systems know what you need to do in order to obtain an installation id, all of them expect you to just have one
  2. In order to obtain an installation id, as far as I can tell you can't be connected to the internet (certain options only appear if you are not connected)
  3. Some support people seem to assume that you are connected to the internet, even though the information they request will never come up if you are not connected to the internet
  4. Support people will transfer you to a line that will not answer without even telling you that you are being transfered
  5. That line seems to only be open during US business hours, which would mean they seem to assume that either you professionally support Microsoft products or are unemployed.
If I can't make this work tomorrow, I think I'm going to obtain an updated version of MS Office for my Mac and give it to my wife, then just install Ubuntu on her laptop.

Sphere: Related Content