Anniversary Column

I reminded Jonathan Erickson, the youngster who's been holding the editorial reins here at DDJ for a mere 16 years, about the official DDJ policy that says that anyone who has been writing for the magazine for 20 years gets to devote one month's contribution to self-indulgent rambling about whatever comes into his or her head. I volunteered to show him the official September 1984 memo, if he could find an Osborne 1 to read the disk it was stored on. He said not to bother and that self-indulgent rambling about whatever comes into my head is what I always do anyway, and I said that then I'd be a fool to mess with a winning formula.

So this month, I'm going to review the hot topics of 1984, repeat some of my favorite words, and once again break the laws of technojournalism by discussing quantum computing without a degree in physics.

Hot Topics of 1984

They've been going in and out of style...

The printed and bound edition of DDJ Volume 9, which contains all the magazine issues from 1984, is a 4-pound tome that runs to just under a thousand pages. (For those doing the math, yes, that means that the magazine was already eight years old when I joined it.) I spent some pleasant hours with Volume 9 recently, building up my forearm muscles, getting my memory jogged, and learning some things I never knew. Like the fact that there are three different ways to spell Modula-2. The Modula-2 spelling controversy has cooled down now, but some of the hot topics of 1984 are still smoldering. Here are some of the subjects that we were obsessing about at DDJ in 1984:

WIMPiness was definitely a hot topic. The Apple Macintosh burst on the scene that year, offering to replace the existing command-line interface with a new interface of Windows, Icons, Menus, and a Pointing device. I was a Mac fanatic from the start, willing to kiss CP/M and my Osborne 1 a fond but final farewell, but I cleverly wrote a mildly antiMac editorial to see what reaction I'd get. The first response taught me never to try to second-guess DDJ readers: The writer neither defended the WIMP interface nor attacked it, instead kicking off what has so far been 20 years of speculation about the nature of the post-WIMP user interface.

The letters pages that year were filled with opinion, advice, and speculation on such topics as nondeterminism, indirect threading in Forth, the Fast Fourier Transform, Julian dates, compiler optimization, the Ackermann function, e-government, cryptography, company and product reviews, Standards, and a new Pascal compiler from a tiny company in Scotts Valley called Borland International.

But there was more about WIMPiness: Before Apple introduced the Macintosh and, er, invented the WIMP, you could WIMP around to your heart's content on a Xerox Star or Apple Lisa, or on an IBM PC using VisiON. And that year, we published Ed Mitchell's simple do-it-yourself windowing system for Z80-based microcomputers. To make life interesting, Ed wrote the system in Augusta, a subset of the Ada programming language that he wrote and published the year before in DDJ. After Tiny Basic and Small-C, it seemed only logical to publish a microcomputer-sized version of that monumental language developed by the DoD.

Soon we were getting Mac-oriented articles, although they didn't actually get into print until 1985, including a delightfully hackerish hardware article on extending the RAM capability of the early Mac, which more or less began, "First get out your hacksaw..."

That compiler from Borland International was, of course, Turbo Pascal, and it was truly revolutionary. But C was clearly the up-and-coming language for serious programmers. A number of articles extended Jim Hendrix's Small-C compiler, which had brought C to microcomputer users in the pages of DDJ in the two preceding years. Allen Holub, who would later write a long-running C column for DDJ, delivered a popular program in C, his version of the UNIX grep tool.

Other languages remained popular, though. For the year, the number of pages devoted to different languages broke down roughly as follows. Assembly language, 250; C, 180; Forth, 100; Pascal/Modula-2, 50; Fortran, 40; Basic, 30; and a few pages each to PL/C, Lisp, Prolog, APL, dBase, and Augusta. That emphasis on C and assembly sounds almost modern, but to truly get a sense of where computer languages were at the time, it helps to note that Namir Shammas pleased a lot of readers when he offered up a preprocessor, written in Basic, that added REPEAT-UNTIL and CASE structures and Fortran-like subroutine calls to Microsoft Basic and eliminated the need for line numbers in branching. Some of the interest in C was due to people's curiosity about it, rather than actual current usage, I think.

In 1984, DDJ introduced an article-refereeing program and an online bulletin board system for distributing code.

This was also the year that DDJ published C.E. Burton's microprocessor implementation of the RSA public key cryptography system. And before DDJ had me writing about science fictional paradigms in this column, it had Richard Grigonis. Richard stirred up controversy with his essays on Fifth Generation computing and Sixth Generation computing, the latter involving processor signals traveling faster than light and direct brain-computer links. The post-WIMP interface again. We're still waiting.

HyPerpWalk

They're guaranteed to raise a smile...

So, I have been doing this for 20 years. Something in excess of 800,000 words. Not 800,000 distinct words, you understand, but still a lot of words. Some of them ought to be worth a second glance, if just for a chuckle. Maybe the hyperwords? Fascination with hypertext led me to write a book on Apple's HyperTalk scripting language, plus a column and a newsletter. But the most fun I had following the tangled thread of hypertext was producing a collection of about three dozen hyperterms, a selection of which follows:

Hyperception n. An altered state of consciousness induced by reading hypertext and characterized by the inability to focus on single, distinct ideas. Cognitive astigmatism.

Hyperenthetical adj. Characterized by being a digression within a digression (within a digression...). The variation in spelling is not arbitrary. The Indo-European root from which the par of parenthetical derives is spelled with an e, and means to grant reciprocally, with the idea of getting something back. The Indo-European tradition that one ought to be able to get something back, or just to get back, from a digression, perished with their culture.

Hyperimeter n. A multidimensional boundary separating the obvious from the irrelevant.

Hyperipheral adj. Lying beyond the hyperimeter, as opposed to ordinary lying.

Hypermute v.t. To rearrange hypertext links randomly. To engage in data annealing.

Hyperparallel adj. Skew.

Hyperpendicular adj. Skew.

Hypersian n. Persian poet Omar Khayyám, who wrote one of the oldest known nonlinear documents (later linearized by Edward Fitzgerald as the Rubiyat) and left this advice to readers of hypertext:

Drink! for you know not whence you came, nor why;

Drink! for you know not why you go, nor where.

Hyperu n. The Andes.

Hypuree n. Hypertext with the links removed.

Hypurpose adj. A noble ambition worthy of significant financial backing but incapable of being expressed in terms that mere linearists can understand.

Hypursuant adj. In accordance with in a higher dimension, as in, "Hypursuant to your directive that the staff dress more formally while in the office, I am taking Friday off to go to the beach."

The Shows

The act you've known for all these years...

I'm going to quote myself again, but for a different reason. During my first year with DDJ, I attended two very different conferences in the same week. The contrast between these events was stark, and I thought that it might be worthwhile to quote a couple of paragraphs from my editorial to show how the contrast, still relevant, felt at the time:

I'd been looking forward to this conference for months and wasn't about to let the power failure darken or the rain dampen my spirits. From the cheerful arguments going on around me as we stood dripping in line outside the dining hall, I gathered that others shared my enthusiasm. The organizers of the Hackers' Conference had brought a hundred-odd insanely great programmers and a few writers to this isolated stretch of the Marin headlands to discuss the future of the hacker ethic, and discuss the future of the hacker ethic we would; the weather was irrelevant...[T]here was consensus on several significant points: that hacking was worthy in and of itself, that the attendees ought to stay in communication with one another, and that it was important to pass the torch to the next generation of hackers. That those present shared something worthy of passing on to others. At the end of the conference, I walked out to the ocean and stood on the rocks above the surf, savoring the newfound sense of rational community, as though I had been through a Woodstock for grownups.

Three days later, in Las Vegas, cesspool of the human spirit, I stop midaisle to consult my Comdex program, but a heavy diet of suites has thickened my discriminative faculties until all the booths look alike, nor does the program identify the players, 80 thousand jaded innocents flown in from the undifferentiated heartland to dance the shuck and jive in tight suits, unsensible shoes, flat borrowed jargon. There are, an anonymous passerby pontificates as I pore through the program book, some Interesting Products here this year, though Nothing Revolutionary; this passing summary strikes me as the true smug theme of this year's Comdex. Some fashion war has been won, it seems: the pros, the working press, the veterans, having traded in last year's cynicism for smartmoney conservatism, even the quest for innovation now out of style, pose midaisle, sniffing out the Interesting Products.

Quantum Computing

It's getting very near the end...

And now for something completely different: I've been reporting sporadically in this column on developments in quantum computing, and I've sometimes done so in the spirit of Richard Grigonis's 1984 article on FTL signals and direct brain-computer links. Intriguing, probably just science fiction, but worth thinking about just in case there's something there.

But quantum computing is moving rapidly toward reality. Extremely limited demonstrations of key elements of quantum computing have been put together, and there are companies actually selling products that implement quantum computing in very specific ways. There is nothing like a general-purpose computer built on quantum-computing principles yet, and it seems that we're still a long way from that goal, if it is even a reasonable goal. It may be that the quantum computer is best implemented as a black box that performs the hard parts of the most challenging computations, leaving all the mundane work and the management of user interaction to a classical computer. But the computational power that quantum computers offer is keeping smart people busy trying to solve the formidable problems still remaining, and it starts to look like real quantum computing will be part of our world before too much longer.

I'm going to continue to report on quantum-computing developments, to the extent of my limited understanding of the physics. Among the quantum-computing research topics I may look into in the coming months are quantum cellular automata, quantum neural networks, topological quantum computing, quantum artificial intelligence, and the Quantum Zeno Effect.

This month, in the brief space I've left after all the prose recycling, I'd just like to summarize some general points about quantum computing, culled from a recent (January 2004) paper called "Quantum Artificial Intelligence," by Bassam Aoun and Mohamad Tarifi that I found on arxiv.org, a scientific e-publishing service maintained, I think, at Cornell University.

• The minimum-cleverness approach to solving any problem is exhaustive search. In classical computing, you can't do better than O(n) time to search a solution space of size n. In quantum computing, the limit is O(sqrt(n)). For those cases where no better approach than exhaustive search is known and n is very large, quantum computing is not only more powerful, it may be the only way to solve such problems, period.
• You're in better shape if you can somehow exploit the problem structure to short-cut blind exhaustive search. This suggests two additional ways in which quantum computing can beat classical computing to a solution. First, if you can reduce the search space by your understanding of the problem, quantum computing can reduce the search time in exactly the way just mentioned. Second, there may be cases where a way is known to use the problem's structure in quantum computing but not in classical computing. Deutsch's problem (which calculates the value of a particular function for two different inputs, and allows the two values to be compared) is one such case.
• Heuristics can sometimes be used to find solutions much more quickly than strict algorithmic approaches. The trade-off is that heuristics are not guaranteed to find a solution at all. So far, the work done in quantum heuristics consists of developing quantum-computing versions of classical heuristics. It is plausible to think that strictly quantum heuristics could be developed as well.
• Most discussion of quantum computing is based on ideal two-state quantum systems, like photons with either vertical or horizontal polarization or electrons with spin either up or down. Such systems physically represent the qubit, which is the quantum analog of the bit in classical computing. Other quantum systems could possibly be used in constructing quantum computers, but these can be modeled by two-state systems.
• The key properties of qubits are:

1.A qubit can be in a superposition of two states.

2.Measurement of a qubit in such a superposition of states yields probabilistic results.

3.Measurement of a qubit changes the state to that which was measured.

• 4.As the number of qubits increases linearly, the amount of information stored increases exponentially.

• Every quantum gate must implement a reversible computation. Given just the output(s) of the gate, it must be possible to retrieve the input(s).

And this last intriguing contention, attributed to R. Josza:

• Entanglement, not superposition, is what gives quantum computing its power.

More next month.

Acknowledgments

So let me introduce to you...

I've been quoting from the Beatles' Sgt. Pepper's Lonely Hearts Club Band throughout this piece. One of the memorable features of the memorable Sgt. Pepper album was the cover, featuring a collage of famous people. As you read the following fragmentary list of some of the people who have affected my life or work in some way, try to picture them in a collage:

Bob Albrecht, Dennis Allison, Jane Austin, Rob Barnaby, John Barth, Jorge Luis Borges, Ray Borrill, Stewart Brand, John Campbell, Maggie Canon, Alan Cooper, Charles Darwin, Steve Ditko, John Draper, John Dvorak, Bob Dylan, Will Eisner, Doug Engelbart, Lee Felsenstein, Paul Freiberger, Martin Gardner, Bill Gates, Nancy Groth, Hal Hardenburgh, Anders Hejlsberg, Joseph Heller, George Herriman, Andy Herzfeld, Paul Hewson, Thom Hogan, Bill Holman, Peter Jackson, Steve Jobs, Philippe Kahn, Alan Kay, Walt Kelly, John Kemeney, John Kennedy, Gary Kildall, Jack Kirby, Art Knepp, Don Knuth, Stanley Kubrick, Thomas Kurtz, Don Lancaster, Ursula LeGuin, Stanislav Lem, John Lennon, Scott Mace, John Markoff, Bob Marley, George Morrow, Vladimir Nabokov, Ted Nelson, Adam Osborne, Tom Paine, Tom Pittman, Jef Raskin, Dennis Ritchie, Ed Roberts, Art Salsberg, Clive Sinclair, Les Solomon, Rex Stout, Randy Sutherland, Ken Thompson, Betty Toole, Linus Torvalds, Jack Tramiel, Tim Trickett, Bob Wallace, Jim Warren, Rennie Wiggins, Stephen Wolfram, Steve Wozniak, and Roger Zelazny.

DDJ