association-list

Thesis

Lately, in addi­tion to spend­ing more time writ­ing fic­tion than read­ing it, I’ve been study­ing Haskell, a pro­gram­ming lan­guage. Famil­iar­ity with Haskell in this case is not really nec­es­sary, as the theory that that I’ve been for­mu­lat­ing while com­par­ing Haskell and Lisp has little to do with the prac­tice of pro­gram­ming. This might be old hat to old time pro­gram­mers, but I’ve never seen it for­mu­lated in quite this manner before. People often talk about ‘power’ and ‘expres­sive­ness’, when talk­ing of high-​​level lan­guages like Haskell and Lisp, but I wonder if this isn’t miss­ing the point, or express­ing the cor­rect point in a way that obscures what’s really going on. I’ve begun to think about pro­gram­ming as having two parts, Logic and Imple­men­ta­tion. This could be extended to have a third level, Run­time System, but even then, I’m think­ing of the Run­time as parts of the Imple­men­ta­tion that are so pop­u­lar and useful to users of a given lan­guage that they’ve cal­ci­fied into the sub­strate of that lan­guage; there is a level at which this dis­tinc­tion is impor­tant, how­ever, and that is com­pat­i­bil­ity. The thrust of the argu­ment that I’m putting for­ward is this: The looser the cou­pling between the Logic and Imple­men­ta­tion in a par­tic­u­lar pro­gram­ming lan­guage, the more pow­er­ful and expres­sive that pro­gram­ming lan­guage is. Which is to say, for those of you who abhor semi-​​circular def­i­n­i­tions, the looser this cou­pling is, the easier the lan­guage is to use for truly wiz­ard­tas­tic (tech­ni­cal term) uses of com­put­ing power.

DWIM, ye beastie!

At its most basic level, pro­gram­ming is the task of telling a com­puter what to do. Ide­ally we’d be able to tell a com­puter to ‘log all the incom­ing con­nec­tions to port 1337 and sue the sender’ or ‘reply to all the wfm post­ings on craigslist with that pic­ture of Brad Pitt with my face’ or just ‘fix that shit!’. It doesn’t work that way, for­tu­nately, which is why the rest of you pay those of us who can so very much money. So in get­ting a com­puter to do some­thing, you have to tell it what to do (Logic) and how to do it (Imple­men­ta­tion). In most lan­guages, telling the machine these things are so entan­gled that they’re essen­tially the same step. In C, pro­gram­ming is the process of telling the machine in really fuck­ing small, fiddly steps, do a then do b then do c with a and b.blerg. I make it sound hor­ri­ble, but it isn’t. C is a great imple­men­ta­tion lan­guage. It’s a ter­ri­ble lan­guage for express­ing high level pro­gram logic in a mod­u­lar way, though, because there is no clean sep­a­ra­tion between what you’re doing and how you’re doing it. In C, you are what you do. This is fine for pro­to­typ­ing, but it’s a pain in the ass when it comes to refac­tor­ing and main­te­nance. If, in a C pro­gram, some­thing that we’re doing is too slow, we actu­ally have to vis­i­bly change what we’re doing to alter what should rightly be an imple­men­ta­tion detail.

This is not to say that you cannot create this sep­a­ra­tion in C or any of the other lan­guages out there. They’re all Turing com­plete and can all do the same things. The prob­lem is that you have to think about it all the time, which means that you’re spend­ing less time think­ing about more impor­tant things, like how that obscure corner case on multi-​​core machines could really bite you when a switch port starts to flap, or whether the attrac­tive person in the office across the hall is avail­able this week­end for a date. Not having to think about the sep­a­ra­tion between what and how means it’s easier to design the system in a way that the Imple­men­ta­tion is as orthog­o­nal as pos­si­ble to the Logic, mean­ing that it’s easier to chunk it up and give dif­fer­ent parts to other people, or to improve per­for­mance with­out having to alter your under­stand­ing of how the entire system works. The ulti­mate expres­sion of this is moving to a com­piler that’s smarter about how it does things, and then turns out faster code with­out any effort on your part, but it func­tions on the appli­ca­tions level as well.

I would argue that it also makes it easier to reason about parts of your pro­gram as well. Not in the high level, formal cor­rect­ness rea­son­ing type of way, but just to break it into chunks and move them around in your head, think­ing of new ways to solve prob­lems, or better ways to do what you’re already doing. There’s noth­ing magic about this. The brain (oh, here he goes, appeal­ing to sci­ence…) can only hold so many parts of a com­pli­cated prob­lem at any one time. So the coarser chunks you can break a prob­lem up into, while still being able to use­fully think about the way that they inter­act and inter­re­late, the better off you are.

Addi­tion­ally, I would like to put for­ward that OO-​​type imple­men­ta­tion hiding isn’t really a useful exem­plar of this strat­egy all on its own. This may have noth­ing to do with what it’s capa­ble of and more to do with the way that it is used, which seems to me to be overly focused upon code shar­ing and ‘defin­ing good APIs’. I am an OO skep­tic in gen­eral and I don’t think much of code shar­ing as a target in and of itself (‘First, order within. Second, order within the familiy…’).

How I think it works.

In Lisp, you have macros. Not like crappy C pre­proces­sor macros that take code as input and return text to be parsed, but func­tions that take ASTs and then can manip­u­late them in arbi­trary ways. A triv­ial exam­ple is some­thing like with-mutex which you pass a chunk of code, pre­sum­ably con­tain­ing stuff that per­tains to the mutex that you’ve grabbed. The macro then grabs the mutex that you’ve spec­i­fied, exe­cutes the code that you’ve passed in, and releases the mutex. More com­plex uses loop a deeply com­plex mini-​​language within Lisp having to do with simply express­ing really hairy loop­ing con­structs. It’s code that writes other code.

In Haskell, you have monads. Dis­re­gard­ing their cat­e­gory theory use, monads are a really clever way of abstract­ing away state changes in a purely func­tional lan­guage, which oth­er­wise does not allow the muta­tion of values. A monad returns actions which then can be taken by a pro­gram, which may then alter the program’s state. Exam­ples include IO, parser state, and most of the other inter­est­ing things that you want to do with a pro­gram. It’s code that expresses actions in a pack­agable, cleanly reusable way.

Although their imple­men­ta­tion could not be more dif­fer­ent, I say that these two mech­a­nisms are doing more or less the same thing, which is enabling the sep­a­ra­tion of what you’re doing from how you’re doing it. They’re both often cited as things in these lan­guages that are hard to wrap your head around, which I think stems from the fact that this sep­a­ra­tion isn’t always an easy one to make, at least on the level of think­ing about a pro­gram. Once you get it, though, they seem almost like mag­i­cal tools, allow­ing you to act as if your lan­guage arbi­trar­ily pow­er­ful prim­i­tives. You can define things that act like new con­trol con­structs or oper­a­tors. This is a huge win because once you have them right you don’t have to think about them any­more. On the flip side, if I need to change some­thing about how some­thing is done, either for robust­ness or effi­ciency, I can change it in one place, with­out having to worry about the rest of the pro­gram. We, as pro­gram­mers, like to think of our­selves as smart people, per­haps uniquely skilled, but it all comes back to our lim­i­ta­tions. The smaller bits of the pro­gram that we can work with, the better we are at it.

This, I would argue, is why more excel­lent pro­gram­mers are drawn to lan­guages with these prop­er­ties (lest I be accused of arro­gance, I am explic­itly not an excel­lent pro­gram­mer. I am, how­ever, quite good at learn­ing from the mis­takes that other, smarter people make). It allows them to elide away the nig­gling details of the huge prob­lems that they’re hack­ing away at, build­ing a struc­ture for rea­son­ing more effec­tively about the prob­lem that they are trying to solve. Paul Graham has talked about bottom up pro­gram­ming, which, I sup­pose is the root of the ideas that I’m trying to express here, but I think that it’s useful to re-​​express the process as defin­ing what you’re trying to do, then defin­ing how to do it, which sounds top down, but which has a lot of bottom-​​up parts, mostly because if you find that the way that what you’re doing is wrong, you can often re-​​use parts of the imple­men­ta­tion of the pre­vi­ous strat­egy with­out having to change them. Instead of spend­ing a lot of time defin­ing a spec and inter­faces and objects, you just write a quick spec right there in the code, then write the code that imple­ments that code right under it.

This method of pro­gram­ming, I think, eludes a quick, visual metaphor like an arch or a lintel or a blue­print, mostly because its con­se­quences are so subtle. Most of the work is done in the bottom-​​up style, but there are many top-​​down aspects, as they allow you to better reason about which bits at the base are impor­tant to get to first. Per­haps a good metaphor would be found in Haskell’s default of lazy eval­u­a­tion. The top level spec defines a mas­sive solu­tion space com­prised of all of the pos­si­ble pro­grams that you could write to do the thing that you’re trying to do, and then you only write just the bits that you need to write to get it work­ing, much as Haskell can define a list or matrix of the­o­ret­i­cally infi­nite extent and then pluck out just the values it actu­ally needs, rather than pre­com­put­ing the entire thing. By expos­ing the shape of this solu­tion space, the high level spec allows us to better reason about what low level chunks of the pro­gram we need to attack first.