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.

Belated impressions of Clojure

Clojure is over two years old, and only last week did I finally get round to writing something in it. Some reactions after writing a few hundred lines:

• Error reporting is often a bane of new languages, but Clojure's is pretty good — usually you get a Java stack trace. However, I did get a number of NullPointerExceptions without stack traces.
• I often made what must be a standard newbie mistake: using parentheses in place of square brackets. Some forms, like when-first, handle that well:

  user=> (when-first (x nil) 3)
  java.lang.IllegalArgumentException: when-first requires a vector for its
  binding (NO_SOURCE_FILE:0)

  But fn gives a singularly confusing error:

  user=> (fn (x) 2)
  java.lang.RuntimeException: java.lang.IllegalArgumentException: Don't know
  how to create ISeq from: clojure.lang.Symbol (NO_SOURCE_FILE:136)

  This could be easily fixed by checking the type in psig in fn's expander:

  (if (not (vector? params))
    (throw (java.lang.IllegalArgumentException.
            "fn requires a vector for its parameter list")))

• Accessing nonexistent fields of struct-maps gives nil instead of an exception. This is consistent with other dictionaries, but it means this error isn't detected reliably, even dynamically.
• doc is the first thing on the cheatsheet, but I didn't notice it until after I'd spent much of a day manually looking things up. :/
• The documentation for proxy says it “expands to code which creates a instance of a proxy class that implements the named class/interface(s) by calling the supplied fns”, which sounds complicated and potentially inefficient. So I was very suspicious of it until I realized it's just inner classes.
• Something like half of my total difficulties were about the Java libraries, not Clojure.
• Java's GUI libraries are not entirely easy to use, but it's still wonderful to be able to take GUI support for granted. I'm used to GUI being possible in theory but not in practice.
• for, doseq and range did exactly what I wanted, with no mental effort.
• dosync took some getting used to. ref, deref and alter aren't unfamiliar, but having to announce in advance that you're doing state is a little unnerving. I didn't have any problems with code that might or might not be called in a transaction, but I was afraid I might. I'm not used to keeping track of this.
• The inability to nest #(... % ...) is annoying. In about 200 nonblank noncomment lines, I used it five times. It would have been seven, but two of those would have been nested (immediately, in both cases) inside others. On the other hand, there were several other 1-argument fns that could have been written with #(... % ...), had I thought of it — which I didn't, because my pet language's equivalent only does partial application.
• (alter r f x) is equivalent to (alter r #(f % x)). This saves a little typing, but it's such an arbitrary convenience that I found myself worrying about whether it worked with each function's argument order.
• Clojure structures are dictionaries, but this isn't important; so far I've only used them like ordinary user-defined classes whose accessors happen to have names beginning with colons. It does mean they appear in a strange place in the documentation, though.
• assoc is obvious in retrospect. I have wanted such an operator for structures, and I'd probably want it for dictionaries too, if I ever used nondestructive dictionaries.
• Some functions I missed: abs, expt, union and intersection (they exist in clojure.set but not in the default namespace, and they don't work on lists), member? (on values, not keys), for-each (yeah, I know, I'm not supposed to want it), and a function that returns the first element of a list that satisfies a predicate.

Function of the day: scalar resolute

The language of mathematics is old and heavily explored, so its vocabulary tends to align well with what is asked of it. But occasional holes do turn up when parts of it are borrowed into programming languages and used for purposes different from those they were developed for. I ran into one of these twice recently, for unrelated reasons, while writing vector arithmetic code. In both cases, I had vectors a and b, and needed the component of a in the direction of b — the projection of a on b, except that I needed it as a scalar. My vector library provided norm, project, unit and dot, so I had a choice of norm (project a b) or dot a (unit b), neither of which is particularly clear.

A little googling reveals that while this operation isn't commonly taught, it is known to mathematicians, who call it the scalar resolute, by analogy to “vector resolute”, which is another name for the ordinary projection operation. It seems to me that I want it considerably more often than either project or dot, so it makes sense to include it in vector libraries. Unfortunately it has no common notation, and while one could be invented (scalar-project? along?), the operation is obscure enough that its would-be users might not recognize it by any name, because they wouldn't be looking for it.

Many uses of scalar resolute also want the component perpendicular to the base vector, i.e. norm (a - (project a b)), because they're really about converting from one coordinate system to another. A vector library could directly support this with a rotate or rebase function. However, a glance through my code suggests this wouldn't be very useful, because the point of the transformation is to obtain the individual components, so they can be operated on as scalars. Producing another vector as an intermediate step would not greatly help clarity. So I think these are most convenient as separate functions:

along : (vector, vector) → scalar
along v b = norm (project v b)

across : (vector, vector) → scalar
across v b = norm (v - project v b)