Smalltalk's small syntax

Smalltalk gets a lot of attention for its object-orientedness, which is fine, but I've already learned those lessons, thanks. What I think deserves more attention is its syntax. Much of what is distinctive about Smalltalk doesn't come from its semantics but from its unusually simple, clear syntax. There are several things language designers could learn from it.

Simple infix

In the perennial argument between infix and prefix syntax, almost everyone assumes infix is much more complicated. Smalltalk shows it needn't be. You can read most Smalltalk code with only three kinds of infix expressions, one postfix, and a few other constructs. There are no special features to support infix, because everything is infix, even ordinary user-defined messages.

It's still more complicated than S-expressions, but not by much. If you like infix or dislike superfluous parentheses, it doesn't look like a bad deal.

Keyword arguments

First, an implementation note: the simplest way to handle keyword arguments is to consider them part of the function's name, and have foo(bar=1) be syntax for foo_bar(1). A different set of keyword args calls a different function: foo(baz=1) is foo_baz(1). This approach doesn't work for large numbers of independent optional arguments, but most of the time it's simple and efficient. Calling a function with keyword arguments becomes equivalent to calling one with positional arguments. There's no overhead for passing or processing a table of keyword args. The downside is that you can't do things like pass keyword arguments to an unknown function: (lambda (f) (f :reverse t :silent-error nil)). On the other hand, you can pass functions that take keyword arguments as if they took positional arguments - because they do.

Smalltalk takes this approach thoroughly. All arguments except the receiver are keyword arguments, so all message sends use keywords, and therefore all methods have names like value:with:. Rather than having method definitions define multiple names (one for each combination of optional keyword arguments), Smalltalk just makes all keyword arguments required. If you want optional ones, you have to define each combination separately. That's a bit of an annoyance (and probably discourages people from using optional arguments) but overall this system is easy to understand, easy to implement, and easy to use.

Is it verbose? Yes, a bit. But it's a form of verbosity that lends itself well to self-explanatory code. For people like me, who don't know the language very well, Smalltalk can be surprisingly easy to read, because nearly every argument has a helpful label beside it. It might be slightly longer than in a keywordless language, but it's longer in the right place.

Multiple infix

All these keyword arguments mean that many message sends are multiple infix: arguments alternate with pieces of the operator. This sounds hard to read, like C's ternary operator: a ? b : c. But it's not actually a problem. This is puzzling: if multiple infix isn't hard to parse, why is the ternary operator so unreadable? Is it because ? and : are so short and easily overlooked next to their arguments? Because the ternary operator is the only multiple infix operator in C, and rare, so you don't look for it? Because many programmers forget its precedence and swaddle it in parentheses? Is it only unreadable when it is used in inconveniently large expressions, as seems to happen a lot?

λ

Lambda isn't common when it has a six-letter name, but if it's shorter it is much easier to use casually. Smalltalk uses syntax to abbreviate its lambdas, and it's hard to beat them for terseness, or ubiquity. It also calls them blocks to be less intimidating - remember, this was originally a language for children - and it works: Smalltalkers don't seem to have a lot of trouble learning the mysteries of anonymous functions.

Surprisingly, Smalltalk doesn't abbreviate function call. But lambda is very useful even when calling is verbose, because it's much more common to pass a function as an argument than to accept one. It's especially useful when it's as short as Smalltalk's. The easy lambda alleviates much of the pressure of not having macros. It easily handles three of the most common uses of macros: binding constructs, control structures, and laziness. It's not transparent like macros, and it introduces a distracting asymmetry in expressions like foo and: [bar], but it's a lot better than nothing, and some people prefer the explicit lambdas, at least when they're only two characters long.

Unfortunately, the use of square brackets doesn't mix well with deeply nested parentheses, because of the difficulty of keeping the parentheses matched when editing. Smalltalk doesn't have a lot of parentheses, so this is only a minor problem, and it wouldn't be a problem at all in a structure editor, but it means this approach to lambda doesn't mix well with S-expressions. The brackets are also sometimes easy to overlook, due to their similarity to parentheses. Maybe a different syntax would be better, or even a short name, like, say, λ.

The bad parts

I don't like how Smalltalk handles variable declarations - surely a form of internal define (infix, of course) would be better. I don't like that it requires special syntax for constructing arrays and hashtables. No one likes its syntax for putting definitions in files, which is so clumsy it makes working without the browser practically impossible. There is no need for other languages to repeat these things. But the core of Smalltalk's syntax, its blocks and messages, is clear and convenient and above all simple. If you're designing a syntax, you could do much worse than imitate Smalltalk.

The true meaning of type

I missed something in my previous post on the many meanings of type. Despite the profusion of seemingly incompatible senses, there is one that is consistent across languages. In every language I know of, type is the difference between an integer and a string.

Some languages, like Bliss and Forth, have no such distinction. Everyone agrees in calling them untyped. Of course they still handle integers and strings, but the language doesn't know which is which. They're distingushed only by how they're used (hence the alternate name operator-typed).

Most languages do distinguish, of course, but they do it in completely different ways. In each language, the mechanism it uses is called type. And this is where the confusion starts. In each language community, the word type becomes attached to the mechanism that language uses, and then to other uses of that mechanism - even those that have nothing to do with distinguishing integers from strings. Eventually users come to believe their sense is the real one, and that all the others must be bastardizations of it. And if they realize how different the senses are, they are tempted to think that they have nothing in common, and that type means nothing at all.

But all these senses reflect different answers to the same underlying problem. There is a common meaning to type across languages, and it is not any of the languages' senses. It is the ill-defined problem of having multiple types of data in one language: integers, floats, functions, arrays, lists, hashtables, strings.

Simple destructive quicksort

Programming languages have become more expressive over time. Consider quicksort. Hoare's original version was quite difficult to understand - IIRC it wasn't even recursive. Nowadays the two-line quicksort is an icon of Haskell:

qs [] = []
qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (>= x) xs)

Unfortunately it's also an icon of unrealistic examples - it makes too many passes over the lists, and conses far too much, so it isn't all that quick. The more efficient sorts don't make such impressive examples - especially the destructive ones, whose Haskell incarnations are infested with intimidating monads.

Here's a gem from the Pitmanual: a reasonably clear destructive quicksort in fifteen lines.

Date: 9 September 1981 18:44-EDT
From: George J. Carrette <GJC>
To:   KMP
cc:   JAR

I think that the QUICKSORT properly coded is even shorter and neater than
the BUBBLESORT. It is also better for showing students since it is
naturally recursive, divide&conquer.

(defmacro rplacd&pop (x &optional y)
  `(rplacd (prog1 ,x (setq ,x (cdr ,x))) ,y))

(defun quicksort (list judge)
  (if (null list)
      ()
      (do ((proof (rplacd&pop list))
           (goats ())
           (sheep ()))
          ((null list)
           (nconc (quicksort goats judge)
                  proof
                  (quicksort sheep judge)))
        (if (funcall judge (car list) (car proof))
            (setq goats (rplacd&pop list goats))
            (setq sheep (rplacd&pop list sheep))))))

rplacd&pop captures the idea of destructively removing the first element of a list. It sounds like a nice example, since it uses a macro to express a by-reference operation in a language without by-reference parameters. But it's not really good for showing students, because it's not safe - it evaluates x twice and its subforms (if any) thrice. (Update 6 April: it uses setq, not setf, so it's ok in Maclisp, because it only works on variables. Even in Common Lisp it would only be a problem when used with a symbol-macro.) I don't know how to do it right in Maclisp, but in Common Lisp it requires the sort of macrology that inspires fear and loathing:

(defmacro rplacd&pop (x &optional y &environment e)
  (multiple-value-bind (temps forms svars writeform readform)
                       (get-setf-expansion x e)
    `(let* (,@(mapcar #'list temps forms)
            (,(car svars) (cdr ,readform)))
      (prog1 ,readform
        (setf (cdr ,readform) ,y)
        ,writeform))))

This might be a good example of how to write setf-like macros, which is a confusing corner of Common Lisp that certainly deserves some examples. But it's no way to write a clear quicksort!

Of course, the simplest way for a language to make a realistic quicksort simple is to predefine partition. Is that cheating? I think it could be useful often enough to belong in a standard library. But to truly simplify quicksort down to a one-liner will require some advances in expressiveness, so we can write something closer to the natural definition: partition on the first element and recurse on both halves.

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.