Atomic file replacement and unpredictable primitives

Many programs need to update files atomically, so they don't corrupt them if they crash while writing. The usual primitive for this is an atomic replacement operation like POSIX rename, which allows programs to implement atomic updates by writing to a temporary file and then replacing the real file with it. Typical use is as in this C macro:

#define ATOMIC_WRITE(filevar, path, mode, body)         \
  do {                                                  \
    const char *realpath = path;                        \
    char temppath[PATH_MAX];                            \
    if (snprintf(temppath, PATH_MAX, "%s.temp", realpath) >= PATH_MAX) \
      die("path too long: %s", realpath);               \
    FILE *filevar = fopen(temppath, mode);              \
    if (!filevar)                                       \
      die("unable to write file: %s", temppath);        \
    body                                                \
      fclose(filevar);                                  \
    if (rename(temppath, realpath)) {                   \
      remove(temppath);                                 \
      die("unable to replace file: %s", realpath);      \
    }                                                   \
  } while (0)

...but it's not usually written as a macro, because of a common problem of C: there's no good way for the macro to communicate errors to its caller, or to clean up when the caller has an error. It can be written as three functions — one to generate the temporary name and open the file, and two for successful and unsuccessful close, but this is complex enough that we seldom think of it. Instead we just write the same code over and over with different error handling, and different bugs, each time.

This makes it a good candidate for standard libraries, at least in languages that don't suffer C's error-handling deficiencies. It could be conveniently provided as an open mode (or a separate operation, if your language don't have modes) that writes to a temporary and atomically replaces the file when it's closed.

Common Lisp's :if-exists :supersede option to open sounds like it does this...

The existing file is superseded; that is, a new file with the same name as the old one is created. If possible, the implementation should not destroy the old file until the new stream is closed.

...but the replace-on-close behavior is optional, and not necessarily atomic. :supersede is also the only portable way to request that the file be truncated when opened, so AFAIK no implementation actually gives it a meaning beyond that.

Why is this so hard in Common Lisp?

I initially gave the example in Common Lisp instead of C, so it could handle errors properly. That part is easy, but it's much more complicated for other reasons:

(defun make-temp-pathname (path)
  "Append .temp to the name of a file, before the extension (if any).
Unlike /temp, this keeps it on the same filesystem, so renames will be cheap."
  ;;Simply appending .temp to the namestring doesn't work, because
  ;;operations like rename-file “helpfully” misinterpret it as a file
  ;;type and use it for defaulting, so e.g. (rename-file "a.temp" "b")
  ;;renames a.temp to b.temp.
  (make-pathname :name (format nil "~A.temp" (pathname-name path))
                 :defaults path))

(defmacro with-atomic-output-file ((streamvar pathname) &body body)
  "Execute BODY with STREAMVAR bound to an output stream, like WITH-OPEN-FILE,
but update the file atomically, and only if BODY returns normally."
  (alexandria:with-gensyms (ok? tempfile realfile)
    `(let* ((,ok? nil)
            (,realfile ,pathname)
            (,tempfile (make-temp-pathname ,realfile)))
      (unwind-protect
        (with-open-file (,streamvar ,tempfile :direction :output :if-exists :supersede)
          ,@body
          (setf ,ok? t))
        (if ,ok?
          (rename-file ,tempfile ,realfile #+clisp :if-exists #+clisp :overwrite)
          #-sbcl (delete-file ,tempfile)))))) ;SBCL deletes it automatically and complains that it doesn't exist

It also isn't portable, because Common Lisp doesn't specify that rename-file will replace an existing file. SBCL does, but Clisp doesn't (even on Unix, surprisingly — it goes out of its way to break this) unless it's reassured with :if-exists :overwrite. Also, with-open-file might automatically delete the temporary on abnormal exit, and delete-file might complain if it doesn't exist. These unreliable semantics, together with the perverse conveniences of pathnames, make it harder to write atomic replace portably in CL than in C.

So when you provide access to system primitives like rename, don't change their semantics. Users will not be surprised by the system's native behaviour, and sometimes they need it.

Sinful total division

You know how annoyingly often you want to display a ratio — a percentage or framerate or some such — and you don't care what happens if you divide by zero, because the result isn't meaningful then anyway? But you don't want it to crash, so you end up writing things like this, over and over...

printf("did %d things (%d%% hard) at %d/s\n",
       n, n ? nhard * 100 / n : 0, dt ? n / dt : 0)

If you're writing it over and over, it should be a function, of course:

div0 a b = if (zero? b) 0 (a / b)

This is a sinful function: it doesn't help you do the Right Thing, only helps you be sloppy more conveniently. Programmers tend to feel guilty about writing such functions, and especially about including them in public interfaces, lest they encourage someone else to be sloppy. Often that guilt deters us from writing them at all, even when we plan to be sloppy anyway, so there would be no harm in it. Language designers avoid such features even more scrupulously, and lament the ones they're forced to include for backward compatibility. Even if div0 is frequently useful, you won't see it in many languages' standard libraries¹.

On the other hand, a large class of language features are valuable because they support seemingly sloppy practices. Garbage collection lets you leak memory with impunity, dynamic redefinition lets you modify a program while it's running, automated tests let you use code you can't prove correct — so rejecting features that promote sloppiness is not a very good heuristic. I suspect a better understanding is possible here, but I don't have it yet.

¹ Although there probably is some language which lacks a good way to report exceptions, and therefore has div0 as the standard division operator.

Divides?

Here's another trivial convenience function:

divides? : int → int → boolean
divides? a b = mod b a == 0

This makes divisibility tests read more like the mathematical a | b notation:

prime? n = n ≥ 2 && not (some (2 .. isqrt n) (divides? _ n))

Argument order and name are debatable. (I find the ? suffix surprisingly uncomfortable, perhaps because divides? is a binary mathematical predicate, so I expect it to be a single-character infix operator like < ≤ ∈ ⊂, not an “ordinary” function.)

I initially wrote divides? off as a feature useful only in toy problems. It certainly comes up a lot in Project Euler problems, since those (as befits their name) are heavy on number theory. But even in real code, many (most?) uses of mod are divisibility tests. So divides? may be worth having, because it expresses this directly rather than via a slightly awkward use of mod.

(Real-world divisibility tests, incidentally, are often used to do something every nth iteration, e.g. updating a progress indicator, flushing a buffer, updating a cache. This pattern is so common that it might deserve an abstraction of its own. However, it's often a mistake — many periodic operations should be periodic in time, not number of iterations. So there's another useful operation: periodically interval timer.)

Square in R7RS

It's one of the most trivial library functions ever:

(define (square x) (* x x))

But I've written it many times, and I'm not alone. So it was a pleasant surprise to see that WG1 recently voted to add it to R7RS.

The request gave the (weak) reason that it could have an optimized method for bignums, but voter comments suggest they were more interested in symmetry with sqrt. They also added make-list for symmetry with make-vector. I don't think symmetry is a good reason in either case, let alone sufficient reason to add features to Small Scheme, but square is attractive as a convenience.

It's not the most important feature (and it probably belongs in Big Scheme, not Small Scheme), but it's a small step forward. Every language that aims to be convenient should have square in its standard library.

Closures of sets

Some operations are common in mathematical reasoning, but are not traditionally used in programming, even when they make sense. I stumbled on one of these recently: I described something as the closure of a set under an operation, and then sought some other way to compute it, because the mathematical description didn't sound like an implementation. After a few minutes I realized there was no reason it shouldn't be:

(defn closure-unary "Closure of a set under a function." [f xs]
  (loop [done #{}
	 pending xs]
    (if (empty? pending)
      done
      (let [x (first pending)]
        (if (contains? done x)
	  (recur done (rest pending))
	  (recur (conj done x) (cons (f x) (rest pending))))))))

user=> (closure-unary - (range 3))
#{0 1 2 -2 -1}
user=> (closure-unary #(mod (inc %) 10) [0])
#{0 1 2 3 4 5 6 7 8 9}
user=> (defn collatz [n] (if (even? n) (quot n 2) (inc (* n 3))))
#'user/collatz
user=> (closure-unary collatz [27])
#{160 1 161 577 2 1154 1186 322 866 2051 35 4 2308 484 1732 5 3077
 325 4102 70 3238 71 103 167 263 8 40 488 4616 41 137 233 425 10
 6154 106 650 107 395 1132 364 46 2158 142 206 334 526 2734 47 175
 719 911 16 9232 80 976 433 593 82 242 274 466 754 850 1619 20 244
 1300 1780 53 182 214 310 502 566 790 23 1079 1367 7288 184 1336
 121 377 122 4858 890 27 91 155 251 283 92 124 1276 412 3644 668
 700 61 2429 445 62 94 350 1438 638 1822 958 31 319 479}

That was the version I wanted, but closure under a binary operator is probably more common:

(defn closure-binary "Closure of a set under a binary operator." [f xs]
  (loop [done #{}
	 pending xs]
    (if (empty? pending)
      done
      (let [x (first pending)]
	(if (contains? done x)
	  (recur done (rest pending))
	  (recur (conj done x)
		 (concat (map #(f x %) done)
			 (map #(f % x) done) ;in case it's not associative
			 (list (f x x))
			 (rest pending))))))))

user=> (closure-binary #(not (or %1 %2)) [false])
#{true false}
user=> (closure-binary #(mod (- %1 %2) 11) [1])
#{0 1 2 3 4 5 6 7 8 9 10}

The two variants are identical except in how they generate new elements. The common part could be factored out...

(defn closure* "Closure of a set under a function generating new elements:
(children element old-elements) should return a seq of elements to add."
  [children xs]
  (loop [done #{}
	 pending xs]
    (if (empty? pending)
      done
      (let [x (first pending)]
        (if (contains? done x)
	  (recur done (rest pending))
	  (recur (conj done x) (into (rest pending) (children x done))))))))

(defn closure-unary [f xs]
  (closure* (fn [x done] (list (f x))) xs))

(defn closure-binary [f xs]
  (closure* (fn [x done]
	       (concat (map #(f x %) done)
		       (map #(f % x) done)
		       (list (f x x))))
	    xs))

...but passing done to children is not very intuitive.

Macro of the day: build-list

Some operations are rare in “real” programs but common in throwaways and toys. One of these is creating lists of random data. Toy programs frequently use random input, simply because it's easier than getting real data. Usually this takes the form of evaluating some (random-thing) expression over and over and returning a list of the results:

(map (λ (x) (random-thing)) (range n))

The unused x here offends me. The randomly generated things usually don't depend on where they end up in the list, so why should the function that generates them receive the index as an argument?

I only find the unused argument annoying if it's in an explicit λ. Doing the same thing with Clojure's for doesn't feel nearly as sinful, since it doesn't explicitly say the index is being passed to a function:

(for [x (range n)] (random-thing))

That's acceptably simple. But what I really want to write is something like this:

(build-list n (random-thing))

...which evaluates (random-thing) n times and returns the results as a list. This is a straightforward macro:

(defmacro build-list
  "Return a seq of the results of evaluating EXPR N times."
  [n expr]
  `(for [i# (range ~n)] ~expr))

Or, in CL (which, even using loop, doesn't look good in comparison):

(defmacro build-list (n body)
  (with-gensyms (i)
    `(loop for ,i from 1 to ,n collect ,body)))

Clojure's built-in repeatedly is the functional equivalent of build-list: it's map over range, but without passing the argument. With # as a one-character λ, this approaches the ideal:

(repeatedly n #(random-thing))

These tools are simple and frequently useful, especially in the throwaway programs that most benefit from library support, but few standard libraries offer them. Some come close, but can't resist including the index as an argument. Racket, for instance, has a build-list function which is equivalent to map over a range, but it's barely an improvement for this use:

(build-list n (λ (x) (random-thing)))

I suspect this is because of cultural dissonance. Calling something repeatedly without passing it an argument is obviously useful only if it's not purely functional, and functional programmers tend to be suspicious of that. We (well, except for the Haskellers) accept impurities like randomness, but not so enthusiastically that we're comfortable including additional library functions to help with them. We expect our libraries to do the Right Thing, and some of our trusted heuristics tell us that making lists of random data is not the Right Thing. So, useful or not, we don't really try to make it easy.

Function of the day: sum

Most folds are sums — either (fold + 0 ...) or (fold + 0 (map f ...)). In math and pseudocode, they're written as Σ or sum, not as folds. So programming languages should support writing them the same way. In Clojure:

(defn sum "Add the elements of a collection, or some function of them."
  ([xs] (reduce + xs))
  ([f xs] (reduce (fn [a x] (+ a (f x))) 0 xs)))

This is one of those trivial conveniences that I use with surprising frequency — more than many more familiar operations. Counts from a 286-line Clojure program:

Count	Operation
11	sum
11	#(...) (op or abbreviated λ)
5	format (I/O is everywhere)
4	fn (λ)
4	count
3	map
3	reduce (counting the two to implement sum)
2	filter

sum may be trivial, but at least in this program, it's more common than map, reduce, and filter combined. Isn't that enough to deserve a place in the library?

(For performance reasons, Clojure's + isn't an ordinary generic function and thus can't be taught to work on vectors, so sum doesn't either. This program does vector arithmetic, so I had to duplicate various arithmetic operations for vectors, so three of these uses of sum were actually of a separate vsum. But this distinction would not be necessary in an ideal language.)

Pipe for functions

One of the minor annoyances of prefix notation for function call is that it gets the order of operations backwards. When you compose several functions into an expression, you generally have to write the last step first:

(handle-message (decrypt (receive socket) key))

If you explained this to a computer the same way you explain it to a human, you'd probably write the steps in the order they're performed. If you're used to Unix pipelines, you might write it like this:

receive socket | decrypt _ key | handle-message

In a language with user-defined infix operators, it's easy to support exactly this. You can define a | operator which simply applies its right argument to its left — the same as Haskell's $, but with the arguments reversed. It looks and feels very like the Unix |: it connects the output of one expression to the input of the next. The channels used are return value and arguments rather than stdout and stdin, but the effect is the same.

I can't remember where (edit 16 Feb 2011: here, at least, and also |> in F#), but I think I've heard this operator suggested before for Haskell — presumably with a different name, since | is taken. Ignoring that inconvenient detail, its Haskell definition is simple:

infixl 0 |
(|) :: a → (a → b) → b
x | f = f x
-- Or, to make the similarity to $ clearer:
(|) = flip ($)

Like $, this is a contemptibly trivial operator. All it does is apply one argument to the other, which doesn't sound like it could possibly be worth spending an infix operator on. But I find myself using it constantly in pseudocode, because it lets me write operations in the right order. It doesn't make code shorter, but it significantly reduces the distance between the code I write and the representation in my head. That's important enough to be worth a one-character infix operator.

Like any high-order operator, | is much more useful when you have a terse way to write simple functions. Usually this means partial application, either in the form of currying, or an explicit partial application operator, or op, or implicit op (as in the example above). Combinators are nice by themselves, but they need partial application to be really useful.

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.

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)

Function of the day: lerp

In response to clamp, a commenter unerringly pointed out another function whose common name I didn't know: lerp, for linear interpolation. You know the operation - you have two points and you want a line:

lerp :: (Num a, Num b) ⇒ (a, b) → (a, b) → a → b
lerp (x1,y1) (x2,y2) x = y1 + (x - x1) * (y2 - y1) / (x2 - x1)

? foo = lerp (1,1) (10,4)
? foo 4
2
? foo -5
-1

What if you have more than two points? The obvious generalization is to interpolate between successive pairs of points:

polylerp :: (Num a, Num b) ⇒ [(a, b)] → a → b
polylerp [] _                              = error "domain"
polylerp ((x1, _):ps) x          | x1 > x  = error "domain"
polylerp ((x1, y1):ps) x         | x1 == x = y1
polylerp ((x1, y1):(x2, y2):_) x | x2 > x  = lerp (x1, y1) (x2, y2) x
polylerp (_:ps) x                          = polylerp ps x

(Apologies for the explicit recursion. I wanted to write this with combinators to more closely resemble the natural-language description, but even with made-to-order combinators, I can't find anything clearer. This sort of iteration - a fold that operates on more than one element at once - is often awkward to express.)

The commenter mentioned that lerp, like clamp, is used a lot in graphics. This use is more specific than interpolating arbitrary functions between points: it's used to mix two pixels, for applications like antialiasing or transparency. This doesn't require arbitrary X-coordinates, so a simpler variant of lerp is common:

lerp :: (Num a, Num b) ⇒ b → b → a → b
lerp y1 y2 s = y1 + s * (y2 - y1)

As with clamp, I've used this form of lerp before, but didn't know its standard name - I called it mix. Can you tell I'm not a graphics person?

Now for a question. The examples above are in (untested) Haskell, but the type signatures are not the real ones, since Haskell requires in all of them that a == b. I wrote them this way to make the distinction between X and Y coordinates clear, since the types would be unreadable otherwise. Is this a good idea?

Function of the day: clamp

It's trivial and useful: clamp restricts a number to a range.

clamp val low high = min (max val low) high

Argument order varies, of course. This particular order has the convenient property that if you forget and write clamp min val max, it still works.

I wanted this function years ago, in an application where I'd written a great many calls to min and max, with a number of mistakes because of the counterintuitive usage (min to impose a maximum, max a minimum). I almost replaced them with clamp, but I couldn't think of a good name for it. Then recently I stumbled across it in some language's standard library (I have already forgotten which) and was delighted to finally be able to put a name to the concept; I must have been (so I ashamedly imagine) the only mathematically inclined programmer in the world who didn't know what it was called.