Not so isomorphic

Vesa Karvonen defends static sums:

In this particular case, we have functions whose behavior depends on the values of their arguments. But the sets of argument values that invoke the different behavior also have disjoint sets of types. So, one can treat the functions as if their behavior would depend on the types of their arguments. What part of this kind of reasoning do you disagree with?

One can treat them as if their behavior depends on their types - but that's not how it actually works, and many changes can expose the difference. If we turn off the typechecker and run on dynamic semantics, the static sum still works. In a type system where the types aren't disjoint, it still works. If a weakness in the type system allows passing inL with inR's type, then the value, not the type, controls the result. Only in very restricted conditions does the isomorphism tell the whole story.

This is a general weakness in reasoning by isomorphism. Two things may be equivalent in a circumscribed context, but that doesn't make them equivalent in general. In programming languages, it's easy to extend semantics in ways that expose implementation details, so this happens a lot. This doesn't make isomorphism useless; it only means one shouldn't apply it as freely as in math.

Correction: You can apply it just as freely as in math, of course. For some reason it seems to be more tempting to overestimate the scope of the isomorphism in programming. But maybe I only think that because I don't do enough math to know better.

Compare to typeclasses, which really do allow overloading on static type. They don't keep working when the static types change, and they do keep working when the values change. A static sum built with a typeclass might be equivalent to the vanilla Hindley-Milner version, but it extends completely differently.

First impressions of Arc

New Lisps seem to be thick on the ground lately. Graham and Morris have just released an implementation of theirs, Arc. My initial impressions, based on reading the tutorial and the source, not on actually using the language:

• There are a lot of novel names for familiar operators, but many of them are good. I will be stealing best and most and several others. The bad ones are too short: I don't like mac and rem; they're not common enough to require such short names, and they risk colliding with other things. There are also some cryptic compounds like w/uniq.
• in is very convenient. I wish I'd thought of it.
• There's syntax for op, complement and compose. (The latter two, oddly, are implemented as magic on symbols, not forms - that is, the compiler understands some naming conventions.) Would short names (op, o not, and o) suffice?
• There are no user-defined types. Well, there are (see tag) but they only have one slot. This separates the identification and encapsulation aspects of user-defined types from the representation aspect. I'm not sure I like it, though.
• The first libraries are aimed at web apps - not surprising, given the authors.
• Assignment and define are the same operator. No, they're not! assignment is set. Do we never learn? And that apparently isn't confusing enough, so it's called =. Ugh.
• Macros are distinguished dynamically: the function, not the variable, is tagged as a macro. This means a call to a variable can be compiled differently depending on what value its global binding happens to have at macroexpand time. This will become a problem. There's a comment (warn when a fn has a parm that's already defined as a macro) that suggests the authors are aware of the problem.
• Scheme distinguishes #f from () from nil. Arc doesn't. Since lists are often passed back and forth between Scheme and Arc, this is a significant implementation headache. I think in situations like this its's best to just let the host language's data show through, since it makes little difference to the quality of the language. (And what is nil doing in there anyway?)

I find all this rather encouraging, because I think I can do better. I'd better go work on my new Lisp.

It's not homoiconicity

Lisp, say inumerable introductions, is a homoiconic language: its programs are represented in the same data structure they operate on.

I'm not bringing this up to complain about how often introductory material is copied uncritically. (I suspect that's because introductions tend to be conservative, and what's more conservative than repeating something other people have said before?) I'm bringing it up because it is so often repeated, even though everyone knows it is wrong.

It's commonplace to point out that C is homoiconic, and so is Perl, and every language that can process text. They can generate and manipulate their own code. It is often overlooked that this is actually useful, even in C. It's possible for a C program to generate and compile C code - this is how Goo is implemented. And of course many languages have self-hosted REPLs and other tools. Homoiconicity matters.

So why is Lisp better for metaprogramming? It's because the representation of code is a convenient one. Lisp trees are terse and closely reflect the abstract structure of programs, so they are easy to work with. This convenience isn't a simple, formalizable quality (although attempts to do so could produce some interesting papers). Like so many questions in programming languages, convenience is not a matter of adding some interesting new power, but of minimizing the amount of work spent doing uninteresting things.

When abstract code is hard to work with, it loses its metaprogramming benefits. Scheme, for instance, virtually requires a more elaborate representation of code in order to implement syntax-rules. Many Schemes expose that representation, but hacking it hasn't caught on, because it's quite inconvenient. This isn't a necessary problem with richer abstract syntax; it's just that this one is done badly. (In retrospect, it's a bad sign when you have an important type called syntax-object.) I think there could be better alternatives to S-expressions that preserve their all-important convenience.

By the way, a language needn't be homoiconic to benefit from a good representation of programs. Imagine a language whose domain does not include its programs, but which is hosted in another language which does. The host language can manipulate the trees, so it can metaprogram the embedded language - easily, if the representation is a good one. This is the case for many DSLs embedded in Lisp. They benefit from their convenient representation, even though they themselves can't manipulate it.

Please, Lispers, stop telling people what's special about Lisp is homoiconicity! If you want another fancy Greek word, you could speak of euiconicity. But let's not. Much as text is an inconvenient representation for programs, these big words are inconvenient for simple concepts. Just say S-expressions make metaprogramming convenient because they match the abstract structure. That's easier to understand, and as a bonus it transfers well to other data structure questions.

Pitfalls for who?

SISC has a test suite for R⁵RS Pitfalls. Most of these are ordinary compliance tests, that test the implementation's completeness or robustness or up-to-date-ness. But several are tests of perverse implications of the standard, where a reasonable person might say R⁵RS is overspecified or even wrong. In particular, the first two test the interaction of letrec with call/cc — letrec is supposed to evaluate all the init-forms before setting any of the variables, effectively requiring an extra layer of variables. This is not obviously better than the simpler definition which initializes one variable at a time. This is less a test of the implementation's quality than of what lengths it's willing to go to to follow the letter of the standard.

The existence of tests like these — and the number of implementations that fail them — says something about how clean a language is. When expert users are surprised by something in a language, and implementors often get it wrong, this suggests a problem in the spec. In these cases, compliance tests can illuminate what parts of the language are ugliest, and why. For Scheme, it looks like the problems are in details that would ordinarily be invisible, but that are exposed by call/cc or syntax-rules. This is a situation where it's easy for language designers to make mistakes, because they don't even realize what they're specifying.

Sometimes, if a spec is widely agreed to be buggy, everyone will just ignore it. SISC's test suite contains a test for whether let-syntax creates a contour for internal define. The test follows the consensus of implementors in saying that R⁵RS is wrong, and that a good implementation should ignore it on this point. Scheme culture values formality, but apparently there is a limit to how much inconvenience they are willing to put up with for it. Language designers, take note.

Uncheckable bugs

Here's a bug that's hard to find automatically:

fib :: Num a => a -> a
fib 1 = 1
fib n = n * fib (n - 1)

See the bug? No typechecker can. More precisely, no checker (whether of type or anything else) can detect the problem without further information about what the function is supposed to do, because it does something reasonable. It's the wrong reasonable thing, but an uninformed checker has no way of knowing that.

This is why tests are useful: they provide constraints specific to the program. There are other kinds of checkable declarations (e.g. invariants, reference implementations) that are even more powerful. I suspect they're not used much only because they're harder to implement and harder to use.

Edit: fixed type declaration. That wasn't the intended bug.

The value of minimal tests

According to legend, Dijkstra-子 said: Testing cannot show the absence of bugs, only their presence. This is true only in the narrowest interpretation: testing cannot generally show that there are no bugs. It can, however, show the absence of a huge class of bugs: all those which cause the program to always fail.

I submit that these are a significant fraction of all bugs. When you implement something, how often does it work on the first try? When you track down a bug in the wild, how often is the affected code so completely broken that it couldn't work for any input?

Of course the answers to these questions depend on whether those bugs get caught earlier, whether by manual testing or static checkers or automated tests. I think much of the value of automated tests is that they are so good at catching those bugs. A single test case takes very little work, yet catches these bugs quickly, reliably, and (unless the test overspecifies the result) with no false positives. That set of virtues is hard to approach by any other means.

Other uses of automated tests are less impressive. Some people write laborious tests for boundary cases and other possible bugs. I'm not terribly enthusiastic about these tests, because each one normally catches only one bug. They still show the absence of specific bugs, but they don't have the power of the most basic tests.

A keyword argument

I want to believe keyword arguments are an extravagance. They're unnecessary complexity, I tell myself. They complicate function call. The most naïve implementation is inefficient, and the most efficient requires multiple entry points. Why bother, for a feature that's hardly ever used?

But I do use them. When I have a rarely used optional argument, I write it with a keyword, when I'm writing in pseudocode or in a language that supports them. When I don't have keywords, I resort to including the keyword in the function name, like (sort-by score < nodes) for (sort < nodes :key score). That's nice and simple, but it's easy to get confused about the argument order. Maybe a reliable convention would help: head-marked keyword arguments always go first, or always last.

Or maybe I should stop trying to fight the pseudocode.