The value of extensible format strings

Common Lisp's version of printf is the famously overpowered format. In addition to everything printf does, it has conditionals, iteration, recursion, case-folding, tabulation and justification, pretty-printing, English plurals and number names (cardinal and ordinal), and two kinds of Roman numerals. Surprisingly, in a language where almost everything is user-accessible, most of these features are not available separately, only through format. The complexity is such that there's a compiler to make format strings execute faster. Sadly (or not, depending on your perspective) it's not Turing-complete, but that's only because it has no way to store information.

Of course there's a way around that. None of format's features is quite as overpowered as ~/, which calls arbitrary functions: (format stream "~/package:function/" x) does (package:function stream x nil nil). (The two nils are for some other features not used in this case. Yes, there are more. Are you surprised? And yes, in practice the explicit package name is required.) User extensibility is a good principle, but this seems silly. Why would you ever want to call a function through format instead of doing so directly?

Well, the other day I had to generate some XML in C, and the obvious way was with printf:

fprintf(somefile, "<element attr=\"%s\" />", somestring);

But there might be XML-meaningful characters in the string, and I didn't want to mess around with fancy XML-generation libraries. So I had to either escape the string before printing...

char buffer[BIG_ENOUGH]; /* yeah, right */
escape_xml(buffer, BIG_ENOUGH, somestring);
fprintf(somefile, "<element attr=\"%s\" />", buffer);

...or give up on printf, which was what I ended up doing:

fprintf(somefile, "<element attr=\"");
print_xml_string(somefile, somestring);
fprintf(somefile, "\" />");

Either option destroys the clarity of the printf. What I really wanted was a custom printf operation, like this:

fprintf(somefile, "<element attr=\"%/escape_xml/\" />", somestring);

That's exactly what format's ~/ command does:

(format somefile "<element attr=\"~/xml:escape/\" />" somestring)

I guess it's not so silly after all. It is verbose (imagine repeating ~/xml:escape/ for each of a dozen attributes), but that's fixable. If there were an interface for defining new format commands, then any frequently used ~/ function could be given a one-character form, and all would be well, except possibly for readability. (Although in this case all of the obvious characters x e & < s are already taken.) Lisp being Lisp, you generally can get at the implementation's way of defining format commands, e.g. sb!format::def-format-directive, but depending on implementation internals is not usually a good idea. Exposing this interface would make format more malleable, like the rest of the language, and would also make its long feature list easier to swallow.

For new languages, though, I think I prefer string interpolation, which avoids the issue entirely:

(put somefile "<element attr=\"$(xml:escape somestring)\" />")

It would also be nice to have a choice of string delimiters, so the quotemarks don't require escaping. But that's a different, less interesting issue.

Abstract algebra with imperfect models

One more post before the end of the year:

Haskell users tend to be mathematically inclined, so it's no surprise that they should notice a mathematical application of typeclasses: they can represent abstract algebraic structures. You only get one model of the algebra structure per type (potentially annoying for common algebras structures like groups), but where applicable this makes a great (for some values of "great") way to show off your mathematical prowess. Indeed, some of the standard typeclasses are intended as abstract algebras algebraic structures: Monad and MonadPlus, at least.

There are probably quite a few Haskellers who have not only noticed this, but wished it were taken further. For instance, why isn't / defined like this?

(/) :: (Field a) => a -> a -> a

(Really mathematical Haskellers may also wish the return type was Maybe a.)

Isn't Num actually Ring, and Fractional Field?

Not quite. Integer is indeed a ring, but Int isn't because of overflow. Ratio is a field, but Float isn't, because of rounding. Abstract algebras Algebraic structures are useful only because it's possible to reason from their axioms and apply the conclusions to the models, and that doesn't work when the models don't actually satisfy those axioms. The reason Monad works is that its standard instances do correctly model it. The others are stuck with names less proudly abstract but less misleading (not to mention less opaque to non-mathematicians).

Of course, none of these models are really correct, because they all have the limitation of finite memory. But that's a less intrusive limitation than fixed-precision numbers. "Less intrusive" is a disappointingly vague description; I suspect the real difference is that finite memory afflicts virtually every operation in the language, while overflow and rounding are specific to certain types. So while assuming the monad laws work on lists, for example, will cause problems in some circumstances, it won't cause any more problems, because your programs would fail anyway in those cases. In contrast, it's pretty easy to write code that will work for any ring, but not for Int.

Defending against nonexistent problems

When do good programmers write bad code? There are a great many ways to do that, of course, and most of them aren't very illuminating. But there are some common syndromes that account for a lot of poor code. One is when the programmers are writing in a language they don't know very well. They can't use its less guessable features, and since they aren't sure what its pitfalls are, they guess, and end up defending against ones it doesn't actually have. For example, I often see C++ code like this:

if (somepointer)
    delete somepointer;

This is unnecessarily explicit - delete is defined to do nothing if its argument is null, precisely so you don't have to check. (And every implementation I've ever used has done this correctly.) It should be just:

delete somepointer;

But someone new to C++ won't know that unless they've learned it explicitly. Until then, a reasonable programmer may continue to defend against the obvious mistake of deleting null.

Programmers who switch between related languages are prone to infelicities like this:

FILE *f = NULL;
f = fopen(filename, "r");

This is quite reasonable in C, because there might be (or might previously have been) something between these two lines - and in most dialects of C, declarations have to precede statements, so you can't always combine the two. C++, like recent C dialects, lacks this annoying restriction, but a C programmer won't necessarily know that.

They should know better than to read lines from a file like this, though:

char line[MAXLINELENGTH];
while (!feof(somefile)) {
  memset(line, 0, MAXLINELENGTH);
  if (fgets(line, MAXLINELENGTH, somefile)) {
    //do something with line...
  }
}

instead of the shorter equivalent:

char line[MAXLINELENGTH];
while (fgets(line, MAXLINELENGTH, somefile)) {
  /* do something with line... */
}

It's easy to understand why someone might write the longer version. The C standard library is full of functions which are difficult or impossible to use safely (gets, for instance), or which require unnecessarily tedious checks when calling them (malloc, free). Someone familiar with C, but not with the details of fgets, might reasonably doubt it would work correctly without the explicit feof and memset. (And once you've learned to fear uninitialized buffers, it may be easier to memset everything than to think about whether it's necessary.) But fgets is actually well designed. It always null-terminates the buffer, and its return value is well-behaved at EOF. Neither of these defensive additions is necessary.

In fact, the shorter version of that loop actually has slightly better error behavior: if some error (loss of network connectivity?) prevents fgets from reading the file, but doesn't cause eof, the longer code might loop forever, while the shorter one will stop. So in this case the defenses have made things worse, although it's unlikely to matter. I suppose the truly paranoid answer would be to call ferror too...

I'm not complaining that the authors don't know the language they're writing in. It would be nice if they did, but in practice it's often necessary for people to work in languages they don't know very well, and in that situation they'll inevitably work around limitations in their knowledge the same way they work around limitations in the language. This will usually be more efficient than scouring the documentation for shortcuts that might exist. Most of the time their code will still work, and if they keep using the language, they'll learn the details soon.

But sometimes they're unwilling to learn. I've seen all three of these bugs in C++ code written by experienced C++ programmers - people who should really know the commonly used parts of the language by now. Most programmers will simply learn these features when they're pointed out, but some don't want to. They find excuses (sometimes rather contrived ones) to discount the new information and keep programming the way they were. I don't understand what's going on here. Are they accustomed to feeling confident in their skills, and don't want to disrupt the situation by venturing into unfamiliar territory? But how does someone become a programmer without being generally curious about the subject?

A combinator for a familiar operation

While playing with an interpreter, I noticed I had several functions that iterated some operation until they reached a fixed point, the way macroexpand repeats macroexpand-1 until its return value is eq to the original form. [1] You can capture this behaviour for any function by a simple combinator:

iterate-until-fixed f x =
  let x' = f x in
    if (eq x' x)
      x
      iterate-until-fixed f x'

(I used eq instead of some other equality test because it avoids the difficulty of comparing arbitrary or circular structures.)

I was going to ask if anyone had a better name for this function, but iterate-until-fixed is not bad. Unfortunately it's not as useful as I thought. Most of these iterated operations (macroexpansion, many optimizations, etc.) are most useful when they're recursively applied to subforms, not just to the top level. This is much uglier, and it depends on the specific language, so it doesn't make a very reusable combinator. The language could be parameterized out by taking a map-subforms function as an argument, which makes it a little less ugly:

;map-subforms f exp -> another similar exp
recurse-until-fixed f map-subforms exp =
  let results = map-subforms
                  (λ x → recurse-until-fixed f map-subforms x)
                  (iterate-until-fixed f exp) in
    if (every eq results form)
      form
      recurse-until-fixed f map-subforms results

This has some holes - it doesn't handle environments, and the every eq test doesn't work for forms with non-top-level subforms (e.g. let). But (given a suitable map-subforms) it makes a nice simple macroexpand-all:

macroexpand-all exp =
  recurse-until-fixed macroexpand-1 map-subforms exp

[1] In Common Lisp, macroexpand returns a second value to indicate whether it did anything, for historial reasons: in some ancient lisps, macroexpansion could side-effect forms, so mere equality didn't mean nothing had changed. The side effects were only done for performance reasons, and are not present in any modern lisp, so the second return value is not necessary. It is helpful at the REPL though.

You can never be too sure

Programmers can be compulsively paranoid. Yesterday I encountered some code that was very careful about closing a file once it was done with it:

FILE *fp = NULL;
while (a loop which is worth a post in its own right) {
  fp = fopen(somefile, "r");
  if (fp) {
    //Read from fp...
    fclose(fp);
    fp = NULL;
  }
  if (fp) {
    fclose(fp);
    fp = NULL;
  }
}
if (fp) {
  fclose(fp);
  fp = NULL;
}

There were no breaks or anything else that might evade the first fclose. But the extra fcloses were separated by a page or two of other cr^Hode, so it wasn't entirely obvious that they weren't necessary. And this was in a long-running process, so it wouldn't do to leak file descriptors. The author was just being careful! Yeah, that's it.

If closing a file requires that much care, what about opening one? A lot of programs just charge reckessly ahead and read from a file once they've opened it. Not this one. Instead it did this:

FILE *fp = fopen(filename, "r");
if (fp) {
  //But what if the file doesn't exist?
  stat stats;
  if (!stat(filename, &stats)) {
    //OK, read from fp...
  } else
    fprintf(stderr, "Error: stat failed for %s", filename);
  fclose(fp);
}

Yes, it used stat to verify the existence of a file it had just opened. I have no idea what the author thought this was supposed to accomplish.

It should come as no surprise that despite this excruciating attention to imaginary problems, this code was infested with real ones.

Arbitrary overloading isn't always confusing

I have always accepted the conventional wisdom about overloading: that while it's very nice for operations that are conceptually identical, overloading two unrelated operations, like + for catenation, is just an invitation to mistakes. But I have to revise this opinion, because there's a conspicuous counterexample in C++. It uses << and >> for both shifting and I/O, and I've never found this confusing. Why?

I suspect what's going on here is that the shifting and I/O operators are seldom used together, or even in similar contexts. I/O code doesn't look anything like bit-crunching code, so opportunities for confusion are few and far between. The problem with + may be that addition and concatenation have a vague semantic similarity (which is what inspired the overloading in the first place), which leads them to appear in similar contexts. (It seems to me that it's much easier to be uncertain about whether some expression is a number or a string than whether it's an integer or a stream.) It probably doesn't help that they're both very common operations found in all sorts of code. And programmers rely on the associativity of both operations, so the non-associativity of the overloaded combination is not just a theoretical problem. But C++'s shift-or-stream operators show that overloading unrelated operations isn't intrinsically confusing. It depends on how they're used.

Not that I'm advocating arbitrary overloading. But maybe we shouldn't be too paranoid about it - which is good because it turns up surprisingly often. Some familiar operations are traditionally overloaded in semantically dubious ways, including good old +. Integer and (fixed-precision) floating-point arithmetic have different mathematical and practical properties, because one rounds and the other doesn't. Theoretically they should be separate, as they are in OCaml, but most languages unify them anyway. Is this a problem? Maybe a little, when someone forgets they're doing floating-point. But for the most part the two (or more) +es coexist fine.

But addition and catenation don't. But shifting and I/O do. What's the pattern here?

The cost of naive scheduling

The other day one of my coworkers expressed alarm at the condition of one of his servers: it was running at 100% CPU usage! Obviously, he said, something was wrong. I resisted the urge to say that what was wrong was that it was a Windows machine. He's a longtime Windows user, after all. And like a lot of Windows users, he thinks of a busy processor as a bad thing, a sign of a machine about to fail. On any other platform, it's a normal situation. Of course there's work to do!

But my coworker was right. Full processor usage is a bad sign on a Windows machine, because it performs remarkably badly under load. Where a loaded Unix machine simply feels slower, a loaded Windows machine is unpredictably unresponsive. Why?

I understand the Windows scheduler is pretty simpleminded - it simply runs the highest-priority available process, and doesn't try very hard to schedule fairly or prevent starvation. The strange thing is that Windows has had this problem for years, even though there are many well-known solutions. Is there some other goal that conflicts with good scheduling?

There seems to be a similar problem with I/O. One process reading a lot of files can starve all the others - even of virtual memory, because their page faults are not given higher priority than ordinary I/O. As it happens, one of the programs I maintain at work is memory-intensive and I/O-bound, so when it's running, other processes' memory gets paged out, and they can wait a long time for it to be paged back in. The result is to make my 2 GHz machine feel slower than my pocket calculator.

My coworker felt the same way about his server. He tried to stop the offending services, but the machine was so unresponsive that his Remote Desktop session was repeatedly disconnected before he could do so. I think he eventually gave up and walked over the server room to hit the power switch. But as it turned out, there was nothing wrong with the machine. Only with the Windows scheduler.