Some things never change

Mike Taylor is having a bad initial experience with Scheme. In particular:

As I continue to work my way through the exercises (using Scheme itself at least for now), I run into a problem: for exercise 2.9.3 I need set-car!, which the purity-fascist maintainers of PLT Scheme removed in release 4.0. No doubt there is a secret incantation to undo this change, but I can’t immediately see what it is.

As he has already figured out, this is because he's using an R5RS book with an R6RS-ish implementation, and R6RS DrScheme's dialect is not a superset of R5RS — not even of the commonly taught parts of R5RS. Such conspicuous backward incompatibilities occasionally strike other languages (Perl, certainly, and hasn't it happened to Python at some point?) but it's more embarrassing in a language like Scheme, which is supposed to be old and elegant and stable.

Correction: as Eli Barzilay points out, it's supposed to be an R6RS book. The use of set-c*r! without the necessary (import (rnrs mutable-pairs)) is probably an oversight, made easy by the fact that it still works in most R6RS implementations. So part of the problem here is that the book is buggy: it uses features that aren't in the language it's teaching. Also, DrScheme's main language isn't R6RS but a different dialect which also happens to lack set-car!.

It's also unfortunate in a language which already has a reputation for being impractical. Mike correctly attributed the problem to “purity-fascist maintainers”, but how many other students, on seeing that Scheme's most popular educational implementation doesn't (by default) support the examples used in popular tutorials, have concluded (or confirmed their prejudice) that Lisp is not useful outside of the ivory tower?

(I don't particularly mind immutable lists, but they're a strange thing to break backward compatibility over.)

Flattening list construction

Most beginning programmers expect lists (and other sequences) to behave something like this:

a = [1, 2, 3]
b = [4]
[a, b] => [1, 2, 3, 4]
[a, 5, b, 6] => [1, 2, 3, 5, 4, 6]

They expect the list construction operator to catenate lists, but not non-lists. As long as lists can't contain other lists (which rarely occurs to beginners), this is a well-behaved operator. Languages which don't allow lists of lists often have it as their default list construction operator: Perl, APL, and R, for example.

Languages which do allow lists of lists generally reject flattening construction on the grounds that it's unpredictable. Which is true — it's easy to write list functions using it that will work perfectly until they encounter nested lists, whereupon they quietly, mysteriously flatten them.

The trouble is, it's a very convenient operator. It's common (especially at the REPL) to construct a list ad hoc, out of some preexisting pieces, and when you do, you generally don't care which elements came prepackaged in lists and which were solitary. That's irrelevant; you just want to assemble them all into a list without worrying about where they came from.

For example, recently I was trying to control the undead menace with Clojure, and wrote this:

(def units (concat (for [y (range 1 20 3)]
                     (spawn zombie 1 y))
                   (list (spawn pixie 10 10)
                         (spawn pixie 15 10))))

I nearly forgot to include that list, because it was irrelevant detail. What I really wanted to write was something like this:

(def units (enlist (for [y (range 1 20 3)]
                     (spawn zombie 1 y))
                   (spawn pixie 10 10)
                   (spawn pixie 15 10)))

In a dynamically typed language, it's easy to define enlist (so I won't bother), but most don't, because it can't be made to work consistently for all inputs. I think this is a loss, because it's so very convenient when it does work.

Lambda: the discontinuity

I like functional programming, especially in points-free style: it allows amazingly terse expression, with minimal attention to plumbing. But there is an annoyance that often trips me up: there's a discontinuity between combinator expressions and lambda-expressions.

Consider the commonplace task of iterating over a list and, say, printing out the elements. There is an obvious points-free way:

(mapc #'print numbers)

More complex functions can be handled with combinators...

(mapc (compose #'print #'round) numbers)

...and partial application:

(mapc (compose (op format t "  ~S~%" _) #'round) numbers)

But for more complicated functions, points-free style gets awkward quickly, especially if you don't have other combinators like s. As soon as we want to use some variable twice, it's usually easier to switch to lambda:

(mapc (lambda (x) (format t "~S (really ~S)~%" (round x) x))
      numbers)

And that switch requires rewriting the whole function in a completely different way.

Having more than one way to write functions is not in itself a problem, of course. The trouble is that I often want to transform between them, when a points-free expression grows to the point where it needs a lambda. At this point I have to stop thinking about what I want the code to do, and instead think about the trivia of combinators and variables. It's only a minor annoyance, but it's a very common one. And it's more common in more points-free code, so it probably discourages good programming style.

Is there an alternative to lambda/combinator calculus that can express simple functions as tersely as combinator style, but without the discontinuity when they grow? In particular, I want to be able to name variables without reorganizing the code that uses them. This is a hard problem and I don't expect to find any good solution, but I'm still looking. Lambda and combinator calculus are wonderful things, but they're not perfect, and even a small improvement in expressiveness of simple functions would be a big deal.

C's safety problem

Tim Jasko wrote (over a year ago; sorry):

This got me thinking about how other languages tend to lend themselves to certain vulnerabilties. We're all aware of buffer overflow exploits; these are due almost entirely to the fact that C/C++ force you to waste time managing memory.

Most buffer overflows are due to C, but this isn't because of memory management, except in the very general sense that C doesn't allocate string space automatically. C's vulnerability to buffer overflows is almost entirely due to a peculiar fault of its standard library: many of its string functions do not operate on its standard string type.

C's standard mutable string type is a null-terminated fixed-size buffer. This isn't a great choice, for well-known reasons, but it isn't a vulnerability in itself, and it is at least easy to implement. But surprisingly, C's standard library doesn't. It has a variety of operations that write to string buffers, but many of them expect infinite buffers, so they're unsafe on ordinary C strings. These include strcpy, strcat, sprintf, *scanf with %s, and gets. Sadly, these functions have short names and are considered canonical, so they're used in far more than the rare cases where they're safe.

Furthermore, of the operations that do operate on null-terminated fixed-size buffers, most break the invariants of the type in error cases. In particular, strncpy, strncat, snprintf, etc. omit the null terminator on overflow, leaving an invalid string in the buffer. The callers of these functions are supposed to check their return values to discover whether the result fits in the buffer (and if not, give up or try again with a bigger one), but as usual, most callers don't check, and in the overflow case they receive an invalid string instead of a merely truncated one. So even switching to the length-aware string operations doesn't eliminate buffer overflow problems. (This may contribute to C programmers' tendency to use the unsafe ones.)

There are only a very few C functions that correctly write strings to buffers, preserving their invariants even on failure. In fact, the only one I can think of is fgets.

As Dan Bernstein put it:

I've mostly given up on the standard C library. Many of its facilities, particularly stdio, seem designed to encourage bugs.

Fortunately this problem is unique to C's standard library. There's no reason other languages at the same level of abstraction, or even other C libraries, need to have unsafe string operations. It's easy to write correct string operations, even in C, even for null-terminated strings in fixed-size buffers — and security-conscious C programmers often do. There's no reason but history for any language, even C, to have language vulnerabilities.

A surprising autoconversion

Autoconversion of types is a handy thing, and easy to miss when you don't have it. This is especially so in languages like C++ that have many static type distinctions, but don't do many of the conversions automatically. C++ has a built-in autoconversion mechanism, but it's too dangerous to use much, and the alternative of manually overloading every operation with type-converting wrappers is too tedious for anything but a few basic types, so in practice C++ is a non-autoconverting language.

That's the standard excuse, anyway. C++ actually does provide quite a lot of autoconversions, but some of them are bizarrely unhelpful. Take the most obvious autoconversion, for example: converting integers to strings. I ran into this one today:

string s;
int n = 40;
s = n;

A naïve (or even not-so-naïve) user might expect this to set s to "40", but it's actually "(". Assigning a single integer to a string is treated as assignment of a single character, not the decimal representation of the integer. But this is only for assignment; the constructor doesn't accept integers at all. I can think of some excuses for this (characters are sometimes (e.g. by getc) represented as ints; string should be consistent with other collections; base 10 is arbitrary; conversions between semantically different types shouldn't happen automatically; STL is supposed to provide a solid foundation, not be easy to use), but user expectation is so strong here that I'm still surprised.

I'm also surprised I've never run into this before. I habitually use printf-like functions for generating strings, but not always, so you'd think I'd encounter this more than once a decade, especially since += has the same surprising overloading. Do I really never generate strings from single integers? Is this most obvious of autoconversions really so rare in practice?

The switch loop as an expressive device

Consider the switch loop. It's a loop which iterates through the branches of a switch statement, so each iteration does something completely different:

for (int step = 0; step < 3; ++step) {
  switch (step) {
    case 0:
      //do one thing
      break;
    case 1:
      //do another thing
      break;
    case 2:
      //do something else
      break;
  }
  //maybe there's a little bit of common code here
}

It looks like blatant stupidity, and sometimes it is. An unreflective coder who hears a problem described in a way that sounds sort of like iteration may implement it as a loop, without considering whether that makes any sense.

Sometimes the same thing happens as an innocent result of maintenance. Maybe the loop did make sense once, before the switch grew to dominate its body, and no one has noticed that it no longer does.

But sometimes the switch loop serves an expressive purpose.

What do you do when a function needs to execute part of itself several times with different parameters? You make a local function, of course. But what do you do in a language like C that doesn't have local functions? Or a language like C++ that has them, but only in the awkward form of local classes?

The switch loop is one solution. It allows its body to be executed repeatedly with different parameters, and it avoids duplicating it or removing it from its local context. Loops are C's only portable way to locally express repeated execution, and the switch loop is a way to use one as the best available approximation to a local function.

It's not a good solution. Even in C, it's generally better to use a separate top-level function, even if it takes a lot of parameters and makes no sense outside the calling context. But to a programmer who is reluctant to create new top-level definitions (a rather common, and annoying, aversion), or who simply overvalues locality of expression, I can imagine the switch loop seeming the best of the bad options.

An Umeshism

Scott Aaronson described Umeshisms: aphorisms of the form “if you never have $problem, you're spending too much effort avoiding $problem”. He asked his readers for more, but despite their computer-scienciness, no one suggested the obvious:

If your programs never have bugs, you're being too careful.

Or, from a language viewpoint:

If your language never has runtime errors, it's rejecting too many correct programs.

There's obviously a mathematical point to this aphorism schema, but it's surprisingly hard to state it explicitly. Try it: you wind up with enough conditions of continuity and monotonicity (and maybe others I missed) to completely obscure the point. That's why we use aphorisms instead.