Hardware is hard, whereas software is soft; the people who named these things knew what they were talking about.

A while ago, I volunteered to help a friend upgrade the disk drive of an Apple iBook. My first clue that this was going to be a fun project was learning that we needed a special tool called a spudger just to pry open the case. As it turned out, the spudging part of the job wasn’t really that bad; the sleek, black, nylon implement worked quite smoothly. (But so did an old putty knife.) Following instructions , I removed 3 Torx screws, 41 Phillips screws, 1 magnet, 3 rubber feet, 2 greasy springs, 4 strips of sticky tape, the battery, the keyboard, the Airport card, the RAM shield, the lower case, the bottom shield, the DC-in board, the upper case, the top shield, a restraining bracket, and the hard drive. Then I plugged in the new drive and replaced the restraining bracket, the top shield, …, sticky tape, greasy springs, rubber feet, magnet, Phillips screws and Torx screws. Finally, all the parts were back in the box and the case was snapped together again where I had spudged it apart. But when I pressed the power button: Total absence of joy. I pressed it again: Not a peep from the speaker, not a glimmer of light in the screen. Yet again: Nothing but a blank stare.

My purpose in writing about this low point in my career as a high-tech handyman is not to rant about the frustrations of technology or our throwaway culture, where nothing’s worth fixing and nobody knows how to fix it anyway. On the contrary, I want to take a moment to marvel at the elegance and ingenuity of microelectronic technology. After all, it’s the wonder of our age.

I recently had occasion to pull an old book off the shelf: Introduction to VLSI Systems by Carver Mead (Caltech) and Lynn Conway (then Xerox PARC, now University of Michigan).

This is a hands-on, do-it-yourself guide to designing silicon chips—arguably the most complex artifacts ever created by human minds and hands. (When Mead and Conway were writing, “VLSI” meant thousands of transistors on a chip; now it’s hundreds of millions.) Intricate as the circuits might be, Mead and Conway leave you feeling that you can understand absolutely everything about them, from the physics of electrons drifting through doped silicon, to the operation of individual transistors and logic gates, to the organization of those gates into higher-level modules such as adders and shift registers, to the layout of the patterns for the various layers, to the process of fabrication. I’ve always been particularly fond of the colorful layout diagrams, which look nothing like engineering drawings and everything like textile patterns.

Things have changed somewhat since the late 1970s—the era of the circuits described by Mead and Conway. Chip layouts were then checked and documented by printing them out at enlarged scale with a multicolor pen plotter. Quite a few of those plots wound up decorating engineer’s offices. (Maybe that was their real purpose.) If you tried to make a similar plot of a modern chip layout, it would cover a square kilometer. Nevertheless, even though this book is 30 years out of date, it is still the guidebook I would choose to take with me on any visit to the world of digital devices.

In their preface, Mead and Conway write: “In any given technology, form follows function in a particular way.” Yet what’s most extraordinary about the design of silicon circuits is how function follows form. It’s magic: When you print those patterns of interwoven colored stripes onto the surface of a silicon wafer, they come to life! They become active agents rather than mere geometric figures, capable of computing—almost capable of thinking. It’s as if the printed words in a book began reading themselves aloud and commenting on the story in which they occur.

If it’s surprising that mere geometric patterns can be transformed into a computing machine, I sometimes find it equally astonishing that mere machinery can be made to compute. The objects of computation are abstract entities such as numbers, bits, sets, logical operations. These things all seem (to me) to have an existence independent of any specific physical embodiment. When I think of a logical formula—P AND (Q OR R), say—I don’t ordinarily have in mind the little series-and-parallel network of transistors that Mead and Conway would design to implement this function in nMOS technology. P, Q and R are variables, or truth values, not voltages and currents. So why does our universe offer this curious mapping between physical structures and computational ones? Why is it possible to build computers? Why do we need to build them? Why can’t we just compute with pure thought stuff?

A few years ago, if I had written a paragraph like the one above, I would now be awaiting a letter or a phone call from Rolf Landauer, a wonderfully irascible physicist at IBM, who would forcefully remind me that “Information is physical!” Landauer died in 1999, so I no longer have the benefit of his critiques, but I’ve just discovered that his views on this issue are very ably representing in the final chapter of Mead and Conway, a chapter I had not properly appreciated when I first encountered their book. They write:

Computation is a physical process. Data elements must be represented by some physical quantity in a physical structure, for example, as the charge on a capacitor or the magnetic flux in a superconducting ring. These physical quantities must be stored, sensed, and logically combined by the elementary devices of any technology out of which we build computing machinery.

I’m not going to try to argue the contrary proposition—that computation is an abstract, mathematical process, which just happens to be modeled accurately by certain physical events and structures—but I would like to register my ongoing puzzlement at this close correspondence between the world of atoms and the world of numbers. I can believe it’s true that information is physical, but at a deep level I don’t get why it’s necessary.

Consider this: Since 1994, thanks to Peter Shor, we’ve had an algorithm for efficiently finding the prime factors of integers. But the algorithm only works on a quantum-mechanical computer; with a computer built according to the principles of classical physics, all known factoring algorithms require an effort that grows exponentially with the size of the integer. Someday, when the novelty has worn off, this situation will seem perfectly natural and unremarkable, but for now I am still bothered by the hint of a link between number theory and the laws of matter and energy. In this context, the quantum computer seems like a spudger—an overly specialized tool that you wouldn’t need if things were designed properly in the first place.

Mead and Conway is a terrific book, but it offers no useful advice on reviving an unresponsive iBook. For that I made an appointment at the Genius Bar of the local Apple Store. Quoth the genius: “Nevermore.” The cost of the repair would exceed the price of a comparable new iBook.

But this story has a happy ending, much to my surprise. Having already turned my friend’s computer into a plastic brick, I couldn’t do much further damage by spudging around inside it. And even if I failed to bring it back to life, performing an autopsy might teach me something. Over the next week I became adept at stripping the machine down to bare boards in half an hour. It didn’t take long to identify the cause of death. A small white plastic socket in the northeast corner of the circuit board was wobbling like a loose tooth. Evidently I hadn’t been gentle enough when I disconnected a cable during my first disassembly. That cable goes to the power button.

I fixed it with Krazy Glue and clothespins. Hardware is hard, but it’s no match for a well-practiced spudger.

As I was saying, I’ve been trying to get up to speed with Adobe Flash and ActionScript. I’ve also been looking into Processing, another programming language designed for creating interactive animations and visualizations that can be shared on the web. Processing was invented by Casey Reas and Ben Fry when they were at the MIT Media Lab.

It’s the only language I know whose name is a gerund.

There are other reasons for liking it, too. It’s free! And Processing is a big hit with graphic designers and artists, who have dreamed up an abundance of weird and wonderful stuff. A few samples: rubber, Ising eyes, sheep, Zip codes.

I haven’t yet done much in Processing myself, but I’ve been browsing in two new books on the subject:

• Ira Greenberg. Processing: Creative Coding and Computational Art. Berkeley: Friends of Ed. 2007.
• Casey Reas and Ben Fry. Processing: A Programming Handbook for Visual Designers and Artists. Cambridge: MIT Press. 2007.

Both recommended. Stay tuned for further word.

The last time I was ranting about spam, I inquired of Pfizer, the makers of Viagra, how they filter spam from their own incoming mail stream. They can hardly block all messages that mention their own product. They never got back to me with an answer. Now perhaps I know why. Wired News reports that zombies on Pfizer’s internal network are the source of a recent spam storm!

Reminiscing about Structure and Interpretation of Computer Programs led me to pull the book off the shelf, and I was taken in once more by the epigraph from the late Alan J. Perlis:

I think that it’s extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don’t think we are. I think we’re responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope we don’t become missionaries. Don’t feel as if you’re Bible salesmen. The world has too many of those already. What you know about computing other people will learn. Don’t feel as if the key to successful computing is only in your hands. What’s in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.

And then this from his foreword to the book:

In its semantic structure Scheme is as closely akin to Algol 60 as to early Lisps. Algol 60, never to be an active language again, lives on in the genes of Scheme and Pascal. It would be difficult to find two languages that are the communicating coin of two more different cultures than those gathered around these two languages. Pascal is for building pyramids — imposing, breathtaking, static structures built by armies pushing heavy blocks into place. Lisp is for building organisms — imposing, breathtaking, dynamic structures built by squads fitting fluctuating myriads of simpler organisms into place.

My love affair with the Scheme programming language began in the front seat of a 1976 Ford Mustang. I had just bought a copy of Abelson and Sussman’s Structure and Interpretation of Computer Programs, which uses Scheme as the vehicle for a course in computer science. On the way home from the bookstore I grabbed some lunch at the drive-thru window, and then I sat in the McDonald’s parking lot munching my fries and reading. I sat there all afternoon, beguiled by the sensuous elegance of this new language, a dialect of Lisp that seemed to be just what I’d been looking for all my life.

My infatuation with Scheme turned out better than most romances that begin in a parked car. Twenty-some years later I remain fondly devoted to the language, even if I haven’t always been faithful to it. Still, I’ve changed over the years, and so has the object of my affections—both of us, most likely, not for the better.

Scheme has just gone through quite a major change. The document that defines the language is known as the Revisedⁿ Report on the Algorithmic Language Scheme, where n has taken values ranging from 2 through 5 in successive versions of the standard. A year ago, a proposal for the Revised⁶ Report was published, and the Scheme community was invited to comment and eventually vote on it. (I mentioned the draft standard in an earlier post.) After much discussion, the votes are now in: The R6RS standard has been adopted, 67 to 35.

I have mixed feelings about the outcome. The language has put on a lot of weight, as reflected in the bulk of the standard document. In 1978 the first Revised Report ran to 34 pages. The final draft of R6RS comes in four parts that total 186 pages. The additions and changes to the language arguably make it more mature and robust—but those are not necessarily qualities you seek in a romantic partner. (And now I promise to set aside this annoying teenage-romance metaphor.)

As I see it, the driving force behind many of the major changes in Scheme was Python envy. It’s not that Schemers think highly of the Python programming language or want to adopt its syntactic and semantic features; what they covet is the highly organized and enthusiastic community of Python programmers, who have created thousands of freely available, ready-to-run libraries and modules. If you want to do something with Fourier transforms or sparse matrices or regular expressions, someone has probably written a Python package that will save you a lot of work, and that package will probably install and run with little fuss in the Python system on your computer. Scheme also has its cadre of enthusiasts, who have written and generously shared lots of useful code. But don’t count on getting that code to work in any Scheme system other than the one it was intended for. There are dozens of incompatible interpreters and compilers.

The reason for this state of affairs is not just that Scheme programmers are a bunch of anarcho-individualists who can’t be bothered to conform to anyone else’s standards. From the outset, Scheme was a language lab, a medium for exploring new ideas in the expression and control of computational processes. Experiments with variant notations were the whole point. At the same time, of course, Scheme devotees also wanted the language to be a practical tool for everyday use. Those two goals are not easily reconciled.

Questions of compatibility and portability are exactly what standards are supposed to address, and many of the innovations in R6RS aim squarely at improving this situation. For example, Scheme has long had a “tower” of numeric data types, starting with integers at the bottom, then rational numbers, reals, and finally complex numbers; numbers can also be exact or inexact and they can be represented as “fixnums,” “flonums” or “bignums.” Supporting all of these variations is quite a challenge, and so earlier versions of the standard allowed implementors considerable leeway. R6RS insists that every Scheme must have the entire numeric tower.

While enforcing uniformity in some respects, however, the standard also breaks with the past in other areas. Most notably, Scheme has always been a case-insensitive language: foo, Foo and FOO were the same symbol. No more.

Apart from issues of program portability, it seems to me that the main thrust of the new standard is to make Scheme a more serious environment for software development—a programming language for grownups. There are facilities for precompiled libraries and for “namespace management.” Libraries have version numbers, and there’s a whole minilanguage just to parse those numbers. Another minilanguage handles errors and exceptional conditions.

Another addition is a record data structure, with named fields. The idea is hardly a novelty, and you might think that every variation on it might have been tried by now, but the R6RS authors have assembled a marvelous Swiss Army Knife version like nothing else in this sector of the galaxy. R6RS records can be mutable or immutable; they have parents and protocols; they can be flagged as sealed, opaque or nongenerative. There are two entirely separate (and incompatible!) mechanisms for creating records, one based on macros and the other on procedures. Wow! It takes eight and a half pages to describe all this. A cynic might suggest that the hidden agenda of the report is to make the language so complicated that at most one implementor will succeed in building a compiler, thereby mooting all questions of portability.

The part of the new standard that I find most curiously out of character is the concept of a “top-level program.”

A Scheme program is invoked via a top-level program. Like a library, a top-level program contains imports, definitions and expressions, and specifies an entry point for execution. Thus a top-level program defines, via the transitive closure of the libraries it imports, a Scheme program.

Except for the hifalutin’ stuff about transitive closures, this idea should sound familiar and unremarkable to Pascal or C programmers; to many Schemers and other Lispers, however, it introduces an alien way of life. Speaking for myself, I almost never write a Lisp “program”—a monolithic body of code that gets encapsulated and launched as a free-standing application. Within the Lisp environment, I write a procedure definition, and then I evaluate or compile it, test it, debug it, run it on some arguments and get back some values. Then I write another procedure, and another. All this happens in the REPL—the read, eval, print loop. The process is incremental, iterative, exploratory; I don’t know where I’m going until I get there. After a while I’ve got a bunch of procedures, and they interact with one another in complicated ways, but they don’t constitute a “program”—certainly not a “top-level program.”

Nothing in the standard abolishes my kind of exploratory programming, and I don’t expect the REPL to disappear, but the authors of R6RS do seem to favor a different style of programming. Call it software engineering vs. hacking.

The process that led to ratification of the Revised⁶ Report was not painless. The authors and editors labored mightily, and so did the critics. The procedure took twice as long as expected. There were intermediate drafts numbered R^5.91, R^5.92, R^5.93, R^5.94, R^5.95, R^5.96 and R^5.97, in some cases reflecting substantial changes. My archive of the discussion list has 3,276 messages (I may have missed a few, and I haven’t read them all) and amounts to 14.3 megabytes. Some of the controversies that erupted on the mailing list could not have been avoided: The Lisp community has been feuding for generations over the semantics of macros and the morality of an eval procedure. There were plenty of other disputes as well. The usual law of committee action was in effect: Time spent on an issue is inversely proportional to its importance. (We had quite a spirited debate over whether 0.0 = –0.0. The final draft punts on this issue.)

In an unusual voting procedure, those who opposed ratification were required to state their reasons; some of those casting votes in favor also appended explanations. (You can read all the statements here.) The dissenters’ reasons vary, and I hesitate to summarize, but one theme comes up so often that it bears mentioning here. Many of the no-voters complain that the new standard repudiates a philosophy of minimalism that guided the early growth of Scheme. The principle was stated eloquently by Will Clinger in a preamble that has led off all the versions of the Scheme standard since R3RS:

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary. Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.

Almost a third of the nay votes allude to this passage. One of those votes comes from Clinger himself.

As for me, I didn’t vote. This wasn’t a principled abstention; I simply missed the deadline. I do have an opinion. I’m not convinced that R6RS is an improvement over R5RS. And I’m pretty sure the new language is not going to be as much fun in the front seat of a ’76 Mustang.

We learn so early in life about +, −, × and ÷ that we tend to see these operations as the unique foundation stones of arithmetic, on which everything else must be built. But there are other operators we can apply to pairs of numbers. In a paper recently posted on the arXiv, Shinji Tanimoto of Kochi Joshi University asks if there might be some operation that lies between addition and multiplication.

Here’s what between means. Suppose the operation exists, and assign it the symbol ◊. (Tanimoto chooses a different symbol, but that one is harder to encode in HTML.) Now, for all positive a and b:

if  a+b  <  a×b,   a+b  <  a ◊ b  <  a×b;

if  a+b  >  a×b,   a+b  >  a ◊ b  >  a×b;

if  a+b  =  a×b,   a+b  =  a ◊ b  =  a×b;

Can we actually find an operation that has these properties? As a strategy for searching, Tanimoto suggests looking at the various definitions of a mean. Associated with addition is the arithmetic mean, defined as (a+b)/2. Likewise multiplication has the geometric mean, √ab. The hypothetical new operation ◊ should also have an associated mean, which for all a and b would lie between the arithmetic and the geometric means of a and b. And such a mean does exist! It was studied at length by Carl Friedrich Gauss, who called it the arithmetic-geometric mean, or AGM.

The AGM is defined as the limit of an iterative process:

function agm(a, b) =
  if a == b return a
  else return agm( (a+b)/2, sqrt(a*b) )

Viewed as a computer program, this is one of those weird malformed algorithms that ought to run forever but actually—if a and b are finite-precision floating-point numbers—returns a value quite promptly. Gauss proved that the iterates of a and b converge on the same value; furthermore, that value is always between the arithmetic and the geometric means (in the sense of “between” given above).

So now we have a mean that lies between the arithmetic mean and the geometric mean. How do we get from there to a binary operator ◊ that interpolates between addition and multiplication? Consider the following two identities, where AM is the arithmetic mean and GM is the geometric mean:

a+b = AM(a, b) + AM(a, b)

a×b = GM(a, b) × GM(a, b)

These equations can be taken as definitions of the + and × operators; in other words, we can define addition and multiplication as the unique operations that make the identities valid. And we can write the same kind of equation for the ◊ operator and the AGM:

a◊b = AGM(a, b) ◊ AGM(a, b)

Again, the ◊ operation is to be defined as the unique operation that satisfies the identity. Tanimoto transforms this equation into the form:

AGM(1, (a◊b) ) = AGM(a, b),

which can be “solved for ◊” by iterative methods.

At this point a numerical example will help. Suppose a = 3 and b = 5. AGM(3, 5) evaluates to approximately 3.936, and so the ◊ operation needs to be defined in such a way that AGM(1, (3◊5) ) will also have the value 3.936. It turns out that AGM(1, 9) yields the correct result, and so it follows that 3◊5 must be equal to 9. Note that 3◊5 = 9 lies between 3+5 = 8 and 3×5 = 15, as required. Pretty cool, eh?

No doubt the ◊ operation will soon be added to the elementary-school curriculum, alongside the standard quartet of ambition, distraction, uglification and derision.

Update 2007-09-03: Please see the comments for important corrections.