Denotational semantics is hard

Conal Elliott's blog makes me feel stupid. This isn't a difficult feat; any math I don't understand will generally do the trick. But usually the feeling is misguided, because the problem is ignorance, not stupidity — when I don't understand something, it's probably because I don't know the concepts, not because I can't follow the reasoning.

Conal's blog is different. He builds everything out of simple concepts I already know, and explains his reasoning in painstaking, executable detail, and often I still don't get it. After reading a few such posts, I start to think I'm just too stupid to understand. Or, at least, that denotational semantics with partially defined values is hard enough that I can't wing it by knowing the basic concepts and figuring out the rest as I read. (When I put it that way, I don't feel so bad.)

I think part of the problem, beyond simple unfamiliarity, is that Conal's reasoning is mostly algebraic, and I'm not used to relying on that. Whenever I'm uncertain, I fall back on operational reasoning: I work through the computation and check that the results are what I expect. But this only works when I know what to expect. A typical Conal post is a tower of abstraction so high that when I try to check something, I'm not sure what the results ought to be. I have nothing to anchor my operational rope to, so when I lose my grip on the tower, I fall.

Fortunately, Edward Yang has come to the rescue with some helpful background posts on the very tools Conal uses. He walks the reader through explicit bottoms and the definedness partial ordering and fixpoints and lubs in great detail, with plenty of illustrated examples. (I like the hand-drawn diagrams. They look silly at first, but the absence of typesetting constraints probably allows them to be clearer than machine-drawn pictures would be.) It's all textbook material, and so detailed that it almost seems an insult to the reader's intelligence, but it's a textbook I haven't read, and apparently I deserve the insult. The detail provides valuable practice both at thinking in terms of these concepts and at algebraic reasoning about them, which is just what I needed. Some of Conal's posts are looking a little less mysterious now.

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.

What's so cool about APL?

Why does APL have such a devoted following, despite its strange appearance? What have its users, since the 1960s, seen in it that made them embrace such an unpopular language?

I'm not one of those fanatical APLers, but I think I understand why. Imagine the year is 1965. All computing is on mainframes, and the only high-level languages you've ever seen are Fortran and Algol-60. And then one day you meet APL, and discover:

• It has a read-eval-print loop: you can type expressions in and see the results immediately, without running a compiler. It's a remarkably powerful calculator, in the days before calculators were common. (This may account for its popularity in finance.)
• It's mostly functional: most operations return a result rather than requiring you to specify a destination to modify, so you can easily combine many operations in one expression.
• It has built-in collections — specifically multidimensional arrays, but any decent collection support would do as well. We take collections for granted nowadays, at least in languages higher-level than C, but this wasn't always so. There's a reason many early languages (not just APL and Lisp) were built around a collection type.
• It has high-order operations: map is (often) implicit, and reduce, scan, and Cartesian product are single characters.
• It's terse, and not just because of its one-character names. You really can say in a line of APL what would take a page of Fortran.

Under these circumstances, wouldn't you be amazed by the powerful new language? Wouldn't you become a faithful user, and for decades wonder why all other languages were so uselessly primitive?

Complaining about defsystem

Xach wrote a tool to create boilerplate for ASDF projects. I winced to read this. It may be useful, sure, but it hurts to see “little projects” require three files and an ASDF registration.

I've never had the good fortune to work on a Common Lisp program large enough to need defsystem, and most other languages get by without it, so to me all this complexity looks not only unfamiliar but unnecessary. As a result, when I think about module systems and library loading and such, I tend to dismiss most of the potential features as esoteric. Separate compilation, compile-time circular dependencies, multiple versions, replaceable implementations, parameterised modules, analyzing dependencies without loading — these all seem less important than the mundane convenience of being able to write a library in a single file.

I suppose it's better to focus on problems I actually have than on ones I've only heard about. But I wonder which of the problems I'm ignoring are actually important.

The worst thing about viruses is...

Today I heard someone praising Linux as a desktop OS, on the grounds that it's not very susceptible to viruses. This, he said, was good because it “saves cycles” and cuts down on reinstalls.

Not because they're a security threat. That, apparently, was not on the radar.

I think the cycles he was talking about were those taken by antivirus software, not by the viruses themselves, but the point is clear: many users see viruses as an annoyance, not a threat. Performance and convenience — those are the things that matter.

The speaker was a programmer who is involved in designing network protocols. Maybe he was only giving the reasons he thought his audience would understand. I didn't ask; I'm afraid of what the answer would be.