Don't I like to hack Lisp?

I've noticed a disturbing pattern in my motivation to play with Lisp implementations. Now and then I fall prey to a new idea and start writing one, and it goes fast at first. I dash off the basic interpreter, perhaps an experimental representation of environments, a new macro system, modules, primitives... And then I get the the point where the kernel is basically working, and I need to write enough library - macros, mostly - to get some simple programs running.

And I stop. I like macrology. I like rebuilding the foundations of a language. I like seeing programs running on a tool I built myself. But as soon as I switch from writing the language to writing in the language, I lose interest.

This applies to implementations in an existing lisp, but even more to ones in C. I'll happily spend all day writing a garbage collector, even though I know it's an unoriginal waste of time. But when I start building library infrastructure, an understudied area where I could make a difference, I get bored.

Could it be that I actually enjoy low-level hacking? It is superficially rewarding, because it presents a constant supply of easy problems to solve, and they can be solved in familiar ways. It's programming candy - the fun of debugging without the pesky intellectual challenges. In C I can enjoy constant victories over my tools, whereas when growing a Lisp I'm confronted more directly with the problems. And they're sufficiently ill-defined and hard to think about that I recoil and go do something else instead.

I am not a good programmer when I prefer irrelevant problems to those I want to solve. I suspect this is a common tendency, and it may explain some of the puzzling lack of enthusiasm for more expressive languages. Who wants to face new challenges when you can keep solving the ones you know?

Fire and water and Frink

For the first time, Frink has failed me: it doesn't know the specific heat of water!

OK, that's easy:

water_heat = calorie / gram / kelvin

But Frink doesn't know the heat of vaporization of water! And that takes actual looking up! How will I ever show why water is better than liquid nitrogen for extinguishing fires?

OK, that's still easy:

water_heat = calorie / gram / K
water_vap = 2260 kJ/kg
steam_heat_cp = 2.080 J / g / K //at constant pressure


N2_vap = 5.56 kJ / (28 g) //199 kJ/kg
GN2_heat_cp = 1.04 J / g / K
LN2_temp = 77 K
LN2_density = 0.808 water

tank_temp = Celsius[20]
fire_temp = Fahrenheit[500] //The fire is hotter than this,
//but most of the coolant won't get so hot.

water_cooling = water * ((Celsius[100] - tank_temp) water_heat + water_vap + (fire_temp - Celsius[100]) steam_heat_cp)
LN2_cooling = LN2_density * (N2_vap + (fire_temp - LN2_temp) GN2_heat_cp)

water_cooling, for those who haven't been following along in Frink, is 2.9 GPa. (Yes, pascals: energy over volume is pressure.) LN2_cooling is 544 MPa. So despite its higher storage temperature, water absorbs more than five times as much heat as an equal volume of liquid nitrogen, because of its enormous heat of vaporization. And its lower molecular weight means it produces a larger volume of gas, and displaces more air. Not to mention it's cheap and storable. There's a reason we fight fire with water.

In the course of this, I noticed something odd: the Fahrenheit and Celsius functions are their own inverses. They determine which operation to do from the dimensions of their input. This is a use of dynamic dimension-checking that I hadn't thought of, but it doesn't give me a warm fuzzy feeling.

Quick and easy physical calculations, however, do. Especially when the language makes them simple enough that they work on the first try, as this one did.

It's bloat all the way down

High-level languages are wonderful to program in, but they do offend my aesthetic sense in one way: their implementations are complicated. All those valuable features - libraries, garbage collection, runtime compilation, continuations and so on - take complexity and space, even for programs that don't use them. They're worth it, of course. But they are an affront to perfectionism, because they bloat the distributed forms of programs.

It's tempting to believe that low-level languages don't have this problem, that they're an efficient paradise, where there is no overhead but what a program inflicts on itself, where everything is possible, even if nothing is easy. It is a myth, of course. Brian Raiter's tiny ELF executables show that there's bloat even in trivial C and assembly programs, because of how code is packaged. By stripping out most of this bloat, and then abusing ELF, he managed to shrink a trivial C executable by 98%.

This is impressive, but depressing, because it shows that even at this level, there is arbitrary waste. And so it is everywhere - in hardware, in network protocols, in the problems computers are used to solve. No level of abstraction is a bloatless Utopia, but fortunately we can pretend they are, because the imperfections of one level don't greatly affect the level above.

(Via Randy Owens, who pointed out that one of Brian's tricks, overlapping data, is also used by some very small viruses.)

Chris Smith on type

Chris Smith has a good article on static and dynamic typing. It is clear about the terminological confusion:

I realize that may sound ridiculous; but this theme will recur throughout this article.  Dynamic and static type systems are two completely different things, whose goals happen to partially overlap.

It does overstate the confusion is a few places (weak and strong typing do have widely accepted definitions) but in general it's very good until the last third, when it falls into the very trap it warns about: supposing that all type systems have the single goal of proving correctness. That is not a goal of dynamic typing at all, and it's not even a major goal of static typing for most users, because the properties ordinary type systems prove are rarely the ones programmers care about. The main point of static typing, at least for me, is not to prove anything, but to find bugs. I don't care if the type system proves that a particular bug doesn't exist, because that's rarely information I can use. But when it locates a bug - or even suspects one - that is valuable, because it saves time. Proofs may help find bugs by narrowing the search space, but the proofs themselves are not why we use typecheckers. We use them to find bugs faster.

Losing data made easy

In the Save As... dialog box in Mac OS X, it is possible to select an existing file, in which case that file will be overwritten. Just like Windows, in other words. (Is there a single feature Mac OS X has adopted from Windows that's good?) Actually it's more dangerous than the Windows equivalent, because there's no obvious indication that you've selected a file, and the filename field is at the top of the dialog, where you won't look after clicking on the file list below it. So it's easy to misclick and not notice that your carefully typed filename has just been replaced by the name of an existing file you do not want to lose. And if you thoughtlessly press return when asked "Are you sure you want to overwrite this file?", it will.

I had noticed this could be a problem, but I wasn't careful enough, and today I did it for the first time. Fortunately I was using Aquamacs, which helpfully made a backup of the file before clobbering it, so I didn't lose anything. (The backups can be annoying, but this is not the first time they've saved me. I should really be using a versioning filesystem.) But the same problem affects virtually every OS X application, and very few of them make backups. So here, in a system designed for ease of use, is a subtle feature with a rather unlikely intended use (usually the Save command does all the overwriting you want), and a very easy accidental use that loses data.

As the old joke goes:

How do you shoot yourself in the foot with Mac OS?

It's easy - just point and shoot!

The cost of macros

I had a tool problem while reading obfuscated Lisp: I wanted automatic refactoring. In particular I wanted to be able to α-rename the obnoxious variables to something that didn't look so much like brackets. But I had to do it by hand, because there are no good refactoring tools for Lisp. This is partly because Lisp culture values tools for expression more than tools for maintenance, but partly because automating most refactorings is hard in the presence of macros.

Most Lisps have macros in their purest form: they're arbitrary functions that transform new forms to old ones. That means there's no general way to walk the arguments, because neither the function nor the expansion will tell you what parts of the call are forms, let alone what environment they belong in. There is no way to be sure the macro doesn't implement a different language, which makes analysis nearly impossible.

You can almost do it by observation: if part of a macro call appears as a form in the expansion, you can treat it as a form in the call — and you even know its environment. (Note that this requires eq, because you want to detect that it's the same value, not another identical one.) Unfortunately this fails when the same form appears more than once in the original — and this is normal for symbols, so this technique doesn't get you very far. Even if the representation of code were different, so variable references appeared as (ref x) rather than being abbreviated to x, it would still break when a form appears more than once in the same tree. And in the presence of macros, partial sharing is actually rather common, because multiple calls to the same macro often share part of their expansions. So reliably walking macro calls requires having more information about a macro than just how to expand it.

This is an advantage of more restrictive macro systems: they're easier to analyze. In a strict template-filling system like syntax-rules, you can always determine the role of a macro argument. DrScheme takes advantage of this for its fancy (but not very useful IME) syntax-highlighting. It doesn't work for procedural macros (Update: yes it does; see comments) but it could, if there were a way for macro definitions to supply the analysis along with the expander. Of course it would still be necessary to support unanalyzable mystery macros, because some macros are too hard to analyze, and because many authors won't bother.

I don't think procedural macros are a bad feature — on the contrary, I think they are the best and purest form of one of the four most important abstraction methods in any language (the other three are variables, functions, and user-defined datatypes). But they do have a cost. And I think the cost is mostly in what other tools they interfere with, not in any difficulty humans have with them.

A digression from obfuscation to representation of code

Faré has a nice obfuscated program in his signature:

(labels(({(] &rest [)(apply([
])[))([(>)(elt(]())>))(](<)(do-external-symbols(] :cl)(push ] <))(sort
<`string<`:key`string))(}({ + ^)({`816`1/5)({`688({`875({`398()"~{~A~^
~}"(]())){(+ { +)))({`381)^))(do*(({`5248({`584 }`36063))([`874({`395
{`6))(]`4({`584 {`6))(}`#36RH4G6HUTA1NVC1ZHC({`395 }`36063)))((} [ ]
({`977 ]))({`902)({`381))))

Whitespacelessness is nice for fitting programs into signatures (although this one is still not strictly McQ), but as a tool of obfuscation it has been obsolete since pprint was invented:

(LABELS (({ (] &REST [)
           (APPLY ([ ]) [))
         ([ (>)
           (ELT (] NIL) >))
         (] (<)
           (DO-EXTERNAL-SYMBOLS (] :CL) (PUSH ] <))
           (SORT < 'STRING< ':KEY 'STRING))
         (} ({ + ^)
           ({ 816 1/5)
           ({ 688
              ({ 875
                 ({ 398
                    NIL
                    "~{~A~^
~}"
                    (] NIL))
                 {
                 (+ { +)))
           ({ 381)
           ^))
  (DO* (({ 5248 ({ 584 } 36063))
        ([ 874 ({ 395 { 6))
        (] 4 ({ 584 { 6))
        (} 3785580492276528215065056 ({ 395 } 36063)))
       ((} [ ] ({ 977 ])) ({ 902) ({ 381))))

So in addition to the formatting, this program has — well, I won't spoil it. Check out that { operator, though.

Wait a minute — what happened to the backquotes and #36r? They're both purely read-time constructs, so there's nothing left of them to pretty-print. This is fine for purposes of reading obfuscated code, but annoying to anyone trying to build editing tools, because the canonical representation of code does not contain the whole program.

Many CL implementations (including SBCL, evidently) expand backquote at read time, because it's slightly simpler to implement. They try to preserve it by expanding into something distinctive (e.g. using sb-impl::backq-list instead of list) so they can unexpand it when pretty-printing, but this doesn't always work — there are lots of holes and ambiguous cases. Fortunately there's a better way: make backquote a simple abbreviation for (quasiquote ...) (as in Scheme), and do the expansion in a macro.

Number representations are harder to preserve. One could read #16rF00 as something like (radix 16 "F00"), and define radix as a macro. But this doesn't work for unevaluated data. In a system where code is more than just lists (like syntax-case), radix could be preserved along with the other extra information (line numbers etc.). The same approach can preserve #. and comments, but the conceptual cost is high — programs are no longer as simple as they appear.

I think it's worth investigating anyway. It is possible to have a richer representation of code than lists without going to the opaque lengths of syntax-case. By avoiding structural abbreviations, it may even be possible to make something easier to work with than lists. There are obviously a lot of challenges here, but the possibility of improving what Lisp does best — metaprogramming — is worth spending some effort on.

And think of the possibilities for obfuscated code!