Pavel Pevzner has mastered the art of transforming cabbage into turnip. The key to this vegetable metamorphosis is a process in which a sequence of genes is spontaneously snipped out of a chromosome, flipped end-for-end, then spliced back into the genome at the same place. Thus the reversed genes are in the opposite order and also have the opposite orientation along the DNA strand. After many such random reversals, the genes become throughly mixed up. The number of reversals needed to convert one genome into another serves as a measure of evolutionary distance.
If you want to know more about the biology of gene reversals, see the “Computing Science” column in the new September-October issue of American Scientist. Here I want to talk about how I got sidetracked—or sideswiped—while working on that column.
When I set out to explore the gene-reversal process, I found pencil-and-paper methods tedious. You can represent a sequence of n genes by a signed permutation of the natural numbers 1, 2, 3, …, n, where each number has either a plus or a minus sign to indicate the orientation of the corresponding gene. When you reverse a segment, you also invert the sign of each gene. For example, in the signed permutation +2 –3 –5 +4 +1, reversing the first three genes yields +5 +3 –2 +4 +1. How many reversal steps does it take to transform this sequence into the identity permutation +1 +2 +3 +4 +5? When I tried working out problems of this kind, I found myself doing too much scribbling and making too many mistakes. Could software come to the rescue?
What I had in mind was a program that would display a signed permutation and allow you to select a subsequence of contiguous elements; then the selected segment would be reversed before your eyes. The underlying computation—the transformation of +1 +2 +3 into –3 –2 –1 —is trivial; the only challenge is in the interface. It seemed selfish to keep such a program to myself. In order to make it available on the Web I was led to the Adobe Flash player and its scripting language, called ActionScript, which would allow the program to run within a browser window. I had never touched Flash and ActionScript before, and this seemed like a good opportunity to get acquainted.
Flash animations can be very flashy indeed. I am awestruck by the fluid creations of Andre Michelle, such as Unstable Connections and the sensuous Cable Clock. These are examples of software as art. I would be delighted to achieve something on the same level, but for this first project I was ready to be satisfied with software that merely doesn’t crash too often. You can judge the result here. (And please report crashes here—not that I can promise to fix them.)
My initial impression of ActionScript programming is hard to describe. It was neither pure fun nor all pain. Over the years I’ve had a few passionate love affairs with programming languages, but that’s not what happened this time. Learning ActionScript wasn’t like falling in love; it was more like breaking in a new psychotherapist.
I was working with release 3.0 of ActionScript, which is said to be a major departure from earlier versions. I think what “3.0” means is that there are at least three incompatible ways of doing everything. ActionScript 3.0 comes with a full kit of OO baggage—classes, inheritance, objects, instances, methods—but you can also write procedures in an imperative style, and there are even a few odds and ends from functional programming. There’s a new “Sprite” class for interactive graphic objects, but you are still welcome to use the MovieClip structures of earlier Flash versions. The main collective data structure is called an array, but it can also serve as a linked list or a stack or a queue or even an associative memory. There’s compile-time type checking, but there are also mechanisms for defeating or ignoring it. There’s automatic memory management, but some data elements still require you to take out the trash manually. In other words, this is not a language for purists and ideologues; it’s a mudball rather than a diamond.
The syntax and overall structure of ActionScript put it in the mainstream of modern programming languages, but it has one key feature that sets it apart from the crowd: All the Action in ActionScript happens in response to asynchronous “events.” The classical model of computer programming is purely sequential: Things happen one after another in a definite order. The order is not necessarily fixed at the moment the program is written—there may be loops and branch points where the path chosen depends on data to be supplied later—but you can always trace the process of execution step by step. If you follow along on a flow chart, you can do it with one finger. Admittedly, this unicursal mental model of programming has long been outmoded; computer operating systems have been multitasking since the 1960s, and today programs can have multiple “threads” of execution. Nevertheless, the underlying principle of sequential computing—always finish one thing before you start the next—is still a common and useful framework for thinking about software.
ActionScript requires a different mindset. There’s no sense trying to think in terms of “flow of control”; instead, a program becomes a collection of loosely coupled modules, some of which “dispatch” events and some of which “listen” for those events. Crucially, the events have no definite ordering; they can be interleaved and overlapped in arbitrary ways. Multiple events can be going on at the same time.
Consider a program whose function is to twirl an object on the screen through an angle of 180 degrees. The conventional approach to this task would be a loop of some kind, stepping through various intermediate angles in a precalculated sequence. The speed of the rotation could be controlled by inserting delays between redrawing steps. The program might look like this (k is the angular increment, m is a delay in milliseconds):
for (theta=0; theta< =180; theta+=k)
{
draw(theta);
delay(m);
}
A loop of this kind could be written in ActionScript, but that is not the language's natural idiom. The preferred approach is a two-part solution. First you set up a timer, which dispatches a "tick" event every m milliseconds. Then you write an event handler, or listener, that responds to each tick by rotating the graphic object by an appropriate amount.
twirlTimer = new Timer(m, totalTicks);
twirlTimer.addEventListener(TimerEvent.TIMER, twirlTimerTick);
twirlTimer.start();
.
.
.
function twirlTimerTick(event:TimerEvent):void
{
theta += k;
draw(theta);
}
The event-driven ActionScript code does pretty much the same thing as the simple loop, but it requires much more complex apparatus to achieve it. What's the point of all this rigmarole? Why bother? I'm too new to the Flash world to give an authoritative answer, but I can suggest three possible advantages.
- First, liberation from the sequential model. In the loop program, nothing else happens from the moment the loop is entered until the final iteration completes. If you need to manage other actions at the same time---perhaps something else is supposed to be bouncing elsewhere on the screen---you have to rejigger the loop to accommodate those events. This gets to be a mess, and may well lead you to implement your own timer-based solution.
- Second, events in the ActionScript style are a good match to those in the physical world and therefore make the language well suited to modeling and simulation. Recreating Newtonian mechanics is straightforward.
- Third, events create a whole new scheme for intermodule communication. The call-and-return discipline of procedural languages enforces a treelike pattern of communication (and the message-passing protocols of object-oriented languages don't fundamentally change that topology). A calls B, then B calls C, then C returns a value to B, and finally B returns something to A. A and B are frozen while C performs its computation; A cannot call D until B finishes. Communicating via events is much more flexible. A can dispatch an event that both B and D listen for; A can continue working while B, C and D are running.
Of course any sharp tool can cut your fingers if you're not careful. Let me tell the story of a beginner's bug. In my gene-flipping program, I wanted to highlight a selected set of genes before setting the genes to twirling on the screen; then I wanted to remove the highlight once the genes had come to rest in their new position. In the loop-based program, this is easy: Call highlight(on) just before the loop and highlight(off) just after. In my event-driven program, my first attempt at creating this effect looked like this:
highlight(on); twirlTimer.start(); highlight(off);
Needless to say, it doesn't work. I was thinking procedurally and sequentially; I was following the path of execution with my finger on the flowchart. Another misconception got me into even deeper trouble. At one point I had the program working reasonably well: Dragging the mouse pointer across a series of arrows (which represent genes) would select and highlight the arrows, and they would then make a stately pirouette through 180 degrees. But I discovered it was possible to select and rotate more arrows while the first set was still twirling, creating a spectacular train wreck of colliding arrows. Fun, but not quite the effect I was seeking. Again I had been thinking sequentially: I had forgotten that a selection event could be dispatched and received even while a rotation event was still in progress.
The idea of event-driven programming is hardly new. Events are a staple of almost all user-interface code; back when the Macintosh was a new toy, I learned to write every program as a big loop that repeatedly called WaitNextEvent() to get something to do. Event processing has become more sophisticated since those days, and ActionScript events provide a highly versatile mechanism, but the basic principle hasn't changed.
Whether the idea is new or old, though, it looks like it's going to be the wave of the future. I have two reasons for believing this. One is the multicore processor chip. At the moment, all the concurrency in ActionScript programs is actually a fiction; the programs execute in a single thread, and it's only through the magic of time-sharing that they seem to do many things at once. But multicore processors will soon be everywhere, and they will allow for real parallelism; indeed, to make effective use of the new hardware, we're all going to have to do a lot of nonsequential thinking.
The other reason is simply that the World Wide Web has finally ensnared everyone and everything in the Whole Wide World. Creating software for mere computers---the kind of software you have to download and unpack and install and doubleclick---seems like a quaint and wasteful self-indulgence. These days, if it doesn't run in a browser window, who can be bothered? ActionScript programs run in a browser, and that fact is more important than any other feature or deficiency of the language. ActionScript is officially a dialect of ECMAScript; the other main member of this language family is JavaScript, which is also a clientside Web language. These are languages with very modest origins; JavaScript began as an add-on to the Netscape browser. But they're taking over the world.