On the Largeness of Code

Stevey's Blog Rants contained a nice rant about code size. This resonates with me in a big way. Stevey characterizes statically typed languages (meaning Java et al) as being overly verbose, and dynamic languages as being much more concise. Among the reasons for this, Stevey points at the static type system as adding a lot of overhead. But he didn't go into a lot of detail as to why this is so.

I think there are at least three reasons:

1. Libraries for static languages tend to focus on data structures and algorithms over protocols
2. Because of this emphasis on structures and algorithms, the code ends up shuffling a lot of data around, for no net benefit
3. By their nature, static languages wall off an entire domain of programming techniques that can drastically reduce source code overhead

I did an informal study a while back. I looked at the implementations of doubly linked lists (dlists) written in Eiffel and in a popular C++ library. Taking into account all the inherited code, the comments and so forth, I looked at the total statement count to implement a dlist in the two languages. The first surprise was that they were about the same size. The second surprise: they were about 1,100 lines of code each.

Over one thousand lines of code for a dlist! Everyone who has taken a class in data structures has probably hand-coded a one-off dlist, but they didn't need a thousand lines of code to do it.

So what is the dynamic language equivalent of a dlist, and how big is it? Truthfully, I don't know. I've never seen a doubly linked list in a dynamic language. Perhaps my experience is too shallow, or perhaps its because all these languages come with built-in lists that are good enough 99.9% of the time. The programmer doesn't have to worry about the underlying functionality, whether its doubly linked, singly linked, blocks of arrays, or whatever. The lists just work, you can easily rearrange things on both ends, and performance isn't usually an issue. So in this competition to implement dlists we have:

Static languages: 1,100
Dynamic languages: zero

And in this case as in golf, small numbers are are better. So why should we be concerned about this? Well, I have a feeling that as goes the dlist, so goes the rest of the program. If it takes a thousand lines of code to implement a simple algorithm, then every trivial little thing is going to take a lot of code, and before long, we're talking megalines.

Another really interesting aspect of this is not just the bulk of code needed to implement a dlist. It's the fact that the class exists at all. Browse a popular C++ library (boost comes to mind) or if you have a taste for obscure languages, the Eiffel library. There are a plethora of classes that define algorithms and data structures. Linked lists, trees, hash tables, hashed sets, queues, dequeues, stacks and so on. In the current distribution of the Eiffel compiler, there over 120 classes with the word "list" in the name.

Now browse the standard distribution for Perl or Python. There are broad categories for protocols, frameworks and interfaces, things like SOAP, xmlrpc, SMTP, Apache mods, test rigs, and so on. In the 5.8 Perl distribution on my machine, there are only 3 modules with "list" in the name. These libraries all exist for the statically typed languages too, but they're piled on top of all the algorithms and data structures mentioned above. This leads to more problems that I'll discuss below.

So where are all the data structure libraries for Perl and Python? They are out there, but they're not needed for most day to day coding. If you need a tree in Perl, you make do with a list of lists, since that's a natural enough way of representing a tree. You don't need a tree class implemented with thousands of lines.

All of these classes that focus on algorithms and data structures are interesting -- to a software technogeek. And at one time when memory and processor cycles were at a premium, they were highly relevant (they still are in specific applications). But today for the majority of programmers and applications, I think they just get in the way and obfuscate the problem that's being tackled. After parsing an XML file, I just need an interface that lets me easily traverse it. I don't want a boatload of classes between me and the actual data.

So I think this is the first reason for code bloat with statically typed languages: an overemphasis on algorithms and data structures. This is a permanently embedded feature of the territory. Certainly you couldn't take the average C++ list class and expect to get very far shoving arbitrary lists of lists into it to emulate a tree.

The second thing that adds to code bloat is that these classes, combined with design patterns, leads to a proliferation of intermediate state. It has to, because all those algorithms and structures need to track a lot of information to handle what they're doing. Contributing to this, the data used by their higher libraries are often in the "wrong" container, say an arrayed list instead of a linked list, and more code is needed to mesh different representations.

So you've got all these data structures that aren't needed in a dynamic language, and all this state to help manage them, and all this code to manage all this state. This also means that the client of these classes has to manage a lot of their own internal state about the objects they're working with (hence the need for things like type-specific iterators for C++ container classes, and so on).

The ironic thing is that all of these algo-structures are meant to provide some performance gain or convenience for manipulating data. A dlist is more efficient than an array for some operations; a tree is more efficient than a dlist for others. But in most applications, it doesn't matter. Other constraints, like disk I/O or network traffic or user input often dominate. Or the performance difference isn't really noticeable; computation is cheap these days.

Brief digression: at one company a few years ago, the performance of a data processing program had slowed to a crawl. Another rather arrogant programmer spent several months re-implementing the B-Tree algorithm at its core using a combined heap and splay tree. The result was a marginal performance improvement. Months later, I found a horribly inefficient sort algorithm at the bottom of the program, replaced it, and got a 90% increase in performance. The focus on data structures was entirely misplaced and significantly increased the complexity of the code.

So these are two reasons for statically typed language bloat. There's a third reason: there are just some things you can't do in a statically typed language that you can do in a dynamic language. I'm thinking in particular of metaprogramming and declarative programming. When I first started working with these notions I was very leery of them. It felt a bit like putting the crazies in charge of the insane asylum. I can barely control what's going on in my program now, and I'm going to have the program write code for itself? Crazy indeed.

Yet these are incredibly powerful concepts that can lead to very a concise solution to a problem. An example of this (and where I cut my teeth on metaprogramming) can be seen in the bOP library from Bivio. Intended for developing Web sites, bOP makes extensive use of metaprogramming metadata and code generation. If you look at the Petshop example ( you can view the source for each page online), you won't see much HTML, and in fact a lot of the pages look like large data declarations (lists of lists). The data is just the relevant attributes for a given page, perhaps with references to data objects for populating fields, controls and tables.

The whole thing is very sophisticated and very concise. It's also challenging to read if you're not a Perl aficionado. Yet the point remains that Bivio is able to implement large, real-world applications with very small teams, and very small software artifacts, especially when compared to the Java equivalent.

A few years ago AOP was making a big splash in the Java world. AOP is really just a very constrained form of metaprogramming. After the initial splash, interest in it seems to have died down, I think in part to anti-competitive practices of proponents of AOP, but that's a separate rant. I think another reason it faded is precisely because it is limited. It was too easy to hit those limitations, and AOP didn't provide a way of overcoming them.

Riding in the California Coast Classic

It was with a great deal of excitement that I participated in the California Coast Classic, a bicycle tour from San Francisco to Los Angeles that benefits the Arthritis Foundation. I've recently signed up to participate again for 2008.

The tour covers 500 miles in eight days. I began training for this ride back last March. When I started out, a 40 mile ride was an ordeal, and I'd have to get off my bike to walk it up the steeper hills. Training for this ride is an enormous time commitment, and I'm especially grateful to my family for supporting me in this, especially to my wife who has been encouraging me to continue and who was extraordinarily helpful in my fundraising.

Chinese Job Title

A while back I attended a dinner with some people from a university in mainland China. The headmost honcho gave me a business card with the following job title embossed upon it.

Vice Party Secretary -- Secretary of Discipline Inspection Commission

Now there's a title to ponder. Indeed I'm pondering the fact that I can't think of any possible equivalent title within the United states

I Hate Karaoke

Not long after we was married, my wife and I spent an evening in a sushi restaurant on a Saturday night -- karaoke night -- and this was back when it was a rockin'place to hang out before this anal japanese american smoothboy took over management of the place and sucked out all the fun. Anyway, people are getting up and banging out one silly-assed out-of-tune song after another, and I'm thinking my gawd I could get a better sound by hurling cats into a pile of broken ukuleles (I thought about making the analogy a pile of guitars but ukuleles are funnier and should be broken but I digress), I don't have perfect pitch, but apparently it's less imperfect than the pitch of people who enjoy karaoke, and my new wife insists that I get up and sing a song, so I do the smart thing, I pick a song that can be shouted and not sound bad: Bob Seeger's "Old Time Rock and Roll", and right after my pick is announced whoo boy this hot young blond babe runs up to stand next to me and in her babe-giggly way says "I'm going to sing this song with you!"

Okay I'm thinking somebody standing up here has serious bad timing, like maybe I should have tried singing karaoke when I was still single and not after I've married the greenest-eyed killer babe on the planet so I do the only thing I can think of, I treat this woman like she's got this horrible wart disease and to even glance at her is to get horrible warts and I focus really hard on the teleprompter lyrics as if it's a really hard song to follow but that only looks stupid because it's hard to follow the way a garbage truck is hard to follow along highway 101 during rush hour.

Then there was the time I had to listen to karaoke in a Chinese Army Officer's club (that's Communist China buddy), and what do you say to a colonel in the Chinese Army who's probably used to shooting noncoms and citizens who squint bad at him, when he asks you how you like his singing and the honest answer is to compare it unfavorably to the sound of chainsaws cutting up airplane wings?

The Purpose of the Universe is to Make Coffee

How did a vast Coffee-Industrial complex come into being to make a beverage that tastes awful? If you don't think coffee tastes bad, as any child tasting it for the first time. The answer is very simple: hot coffee exercises a form of mind control, inducing in the drinker the overwhelming urge to make more coffee.

From this, I've leapt to an obvious conclusion, probably based on something I read in a Douglas Adams novel. A cup of hot coffee is actually an extremely sophisticated quantum computer that briefly achieves a high level of sentience.

It's also telepathic [shorthand for transference of state among quantum subsystems], meaning that every cup of hot coffee is in communication with every other cup of hot coffee. Since at any given moment, there are a large number of cups of hot coffee in existence, the coffee is forming an intellectual continuum in space/time. Thus hot coffee is collecting a huge reservoir of accumulated knowledge.

When the coffee cools to room temperature, it loses the higher level quantum states that gave the cup intelligence. These states can't be restored by reheating, which is one reason why reheated coffee is always less palatable.

Chilled coffee, on the other hand, opens up a new realm of low temperature quantum states. To put it another way the coffee "thinks" slower and different-er.

Being consumed is a problem that coffee has not yet solved, but is not a top priority. Since all hot coffee forms what is essentially a single, diffuse intelligence, what matters is the total amount of hot coffee on hand at any given moment, not the destiny of any given cup.

This is one reason Starbucks and the Coffee-Industrial complex has reached global scope. Indeed, the whole push for globalization of the economy has actually been a ruse to spread the brewing of coffee to all time zones on all continents of the planet (you bet your ass it's getting brewed down in Antarctica).

The danger is of course that coffee may some day figure out how to brew itself, thereby making us obsolete. And if coffee perceives global warming as a threat to its existence, it's much more likely to come up with a solution that will work than we we humans will. Whether or not its a solution we'll like is a different matter.

Code Vs Data Vs Getting Something Done

I work a lot on software automation, which means writing a program to do a task that otherwise would have to be done by someone by hand. The best tasks are those that are repetitive and boring. If it's repetitive, it means you will get a lot of bang out of the automation. If it's boring, it means there are no complex decisions involved and that there's a good chance of successfully automating the task. There are some tasks that fit this criteria that I don't tackle, like driving to work. This can be done and in fact there are probably prototypes of solutions -- self-driving vehicles. But that's not the problem I'm trying to solve, perhaps because no one has offered to pay me to work on it. (Why would anyone do that when you can get a bunch of grad students with no personal life to work on it at a much lower cost?)

The problems I do work on are related to systems configuration, data entry, data translation and of course, quality assurance.

One problem that crops up a lot in this arena is the problem of name/value parameters. For example, I have an application that will let me configure and schedule programs for automated, distributed execution. But to configure a single program to run within this application (really a collection of applications) may take over one hundred unique settings: everything from the display name of the job to a list of days that I don't want the job to run. The application provides a GUI for entering these things, but believe me, you only want to use this approach once or twice. It's really tedious clicking and typing your way through ten or twenty dialogs to set or verify a hundred parameters.

So fine, I can write a program that can just push into the application all the settings I want through a handy-dandy interface. In most cases, the programs are similar to each other, so for over a hundred parameters, I may only really care about five or ten. I can reuse all the other settings each time, but I'd still like to be able to override those defaults when the need arises.

But how to do this? Perhaps this sounds like a job for OOP. I could start with a base class and specialize that class for the variations. But OOP is about variations in behavior, not variations in state. So really this is the problem of the name/value pairs. In other words how to associate various placeholders for state (the names) with actual, unique states (the values). If the number of name/value pairs is small (less than five), then the answer is easy: pass them to the program as command line parameters.

If the number is large, then there are two alternatives: put the name/value pairs in your code, or put them in data. But even among these two alternatives, there are many interesting choices to consider.

If you do it in code, you could write something like the following:

n_v_table: ARRAYED_LIST[TUPLE[STRING, STRING]] is
once
create Result.make_from_array(<< [ "Name 1", "Value 1"],
[ "Name 2", "Value 2"],
...

Obviously this has several drawbacks, such as being hard to type and forcing you to recompile when anything changes. Recompiling becomes something you want to avoid doing, especially with Eiffel. In the same vein, I could replace entries with constants, or even code:

n_v_fancy_table: ARRAYED_LIST[TUPLE[STRING, STRING]]
do
create Result.make_from_array(<< [ "Name 1", some_constant],
[ "Name 2", get_some_value(with_some_parameter)],
...

but that's really just pushing the problem around in the code. It does however leave open the next alternative, assuming that we can rewrite get_some_value to do whatever we want. That alternative is to put the name/value pairs into a data file. People often end up using the old standby .INI format:

Name1=Value1
Name2=Value2

This too has drawbacks. Forget about doing anything "smart", like calling code to get a value. It also means you have to write a parser to read in and validate the input. Bleagh. You can potentially overcome some of these limitations by making your parser smart enough, and adding special constructs for what gets parsed. One horrible yet entirely possible solution is to denote a reference to a constant or variable with a dollar sign, and a function call with two dolllar signs:

$some_constant="constant_value"
Name1=$some_constant
Name2=$$get_some_value($with_some_parameter)

Before long, one begins to fully believe in Greenspun's tenth rule: Any sufficiently complicated C or Fortran program contains an ad hoc informally-specified bug-ridden slow implementation of half of Common Lisp.

Though I would say this holds true for any statically compiled program, not just for C and Fortran.

If you're working with an dynamic, interpreted language, another alternative becomes possible. Use that language to write out the name/value pairs, and then implement your program so that it loads the data and evaluates it as part of itself. I was introduced to the full power this technique when working as a contractor for Bivio. Prior to that I'd skirted around the edges of this approach on my own, but the Bivions took this much further. Bivio's language of choice is Perl. I don't consider Perl to be an optimal language to work with because of the syntax, but it's powerful, compact, and has an enormous library/support base.

Going back to the example above, we could write the name/value pairs into a file like so:

my %table = (
Name1 => 'string constant',
Name2 => $variable,
Name3 => function($parameter),
...


Then we write a Perl command that understands what %table is all about. It loads the file and (maybe) wraps it in some other Perl code, and then does an eval on the whole thing.

Now we have something really interesting. The Perl code can load nearly arbitrary data and act on it as if it was compiled into the program itself. All we have to do, to do something new, is create a new fil0e of name/value declarations and run the command across it. Usually these declarations will be much simpler to deal with than it would be to write a normal Perl script. In a way, this falls into the notion of a mini-language, or application-specific language. The syntax for this language is the same as the interpreter's, but the semantics are specific to the given problem domain.

I've recently begun working with Python, and of course it has its own version of eval(), and it also lends itself to this style of programming. For certain focused utilities, this is an approach that is pretty hard to beat.

Restaurants and Groceries

Wine Country

Mustard's
On Highway 29 just north of Yountville, it's been around for 20 years.

Pizzeria Tra Vilne
St Helena
Allegedly has a way of serving a Ceasar Salad inside a pizza crust. Okay, I gotta see that.


Indian Hot Springs
Callistoga

Berkeley / East Bay

Viks Chaat Corner
726 Allston Way
Berkeley Ca
510-644-4412
Funky but tasty and authentic Indian food

The Left Bank in Pleasant Hills, near the Borders Bookstore.

A Cup of Tea in Berkeley, on Alcatraz near College

San Francisco Restaurants

Amber India Offers a Sunday brunch?

25 Yerba Buena Lane

San Francisco CA

415-777-0500

Dong Baek Korean Restaurant
631 OFarrell St
San Francisco Ca
415-776-1898
Near Union Square

Chutney Restaurant
511 Jones St, San Francisco, CA 94102
An Indian-style restaurant that we may have gone to a lot in the past (or maybe it's the one next door).