The charter of this space in the magazine has always been to look at the new, the unusual, the downright bizarre paradigms of programming. Or something like that.
But some old paradigms are bizarre enough for the most jaded taste, and some new paradigms can look surprisingly familiar when viewed in the right light.
Such is the case in this month's effort to cast some light on Forth and standards and chaos and life.
"Standard Forth." Sounds like an oxymoron, doesn't it? The joke goes, "If you've seen one Forth, you've seen, well, one Forth."
Yet the maverick language does have its very own ANSI X3 standards committee, earnestly enunciating the defining characteristics of the Official Standard Version. This is an effort that one might reasonably expect to be less assured of success than, say, the standardization of the Defense Department's official language, Ada. (And perhaps this is not an inappropriate place to thank the DoD for clearing that up. It had always been a bit of a mystery to me in just what language the DoD communicated, although I knew it wasn't English.)
That's what one might expect, that is, until one reflected on the applications in which Forth is the language of choice. Like government work.
One of the differences between conversation and writing-for-publication is that in writing-for-publication you have to make one message work for many (or at least several) recipients; and you can't count on these recipients having the same background. It would make my job a lot easier if you all knew exactly the same things. Then I wouldn't have to include brief sotto voce asides like this one:
I'm about to describe Forth for readers unfamiliar with it. If you know enough about Forth to know that the "government work" I mentioned above was a reference to the fact that Forth was the first high-level language on NASA's Massively Parallel Processor that the Goddard Space Flight Center used for image processing, or some other NASA application, then you may want to skip this part.
There are, I'm sure, readers of this magazine who are not at all familiar with Forth, although it's available on pretty much any platform. They've been missing the splendid ironies in this column so far. The next 500 words or so are to help them get the jokes.
Toward the end of this description of Forth I'll pass along some second-hand observations on the standard. The best source on the standard itself is The American National Standards Institute Inc. (11 West 42nd Street, New York, NY 10036). A very good source for some perspective on the standard, and the first-hand source of the aforementioned observations, is Jack Woehr's book, Forth: The New Model (M&T Books, 1992).
For those as yet untouched by the magic of Forth, then here is some background. It's an interpreted language (though compilers exist) whose interpreter grabs one word (space-delimited string) at a time from the input stream, looks for it in a dictionary of words, and, if successful, executes the action associated with it. If not, it tries to interpret the word as a number and push it onto a stack.
This stack is central to Forth. A word (unless it's a number) names a function, and the parameters of any function are passed via this same stack. The output of a function is pushed onto this stack and every function expects to find its parameters on this stack when it's invoked.
Word-at-a-time immediate execution, the dictionary, the stack: That pretty much describes the essentials of the language. It's very simple.
This all leads to a style of programming familiar to users of certain electronic calculators. To add 2 and 2 and view the result, you type "2 2 + .".
There are four distinct items here for the interpreter to examine: two numbers and two functions. The word "+" performs the obvious function, but the syntax is postfix, as it always is in Forth. This code causes two numbers to get pushed onto the stack, then "+" eats them, pushing the result ("4" for ANSI-standard implementations) onto the stack. The word "." causes the item on top of the stack to be printed.
You program in Forth by adding new words to the dictionary, defined using the ":" and ";" words. When the interpreter searches the dictionary, it stops when it finds the most recent definition of the word, so you can change the definition of any Forth word, for example rerouting output to a printer by redefining ".". You can also extend the definition of a word by writing the new definition using the word itself: ": + 1 + + ;". The words ":" and ";" bracket the definition, the first "+" is the name of the word being defined, and the rest is the definition. This new "+" returns "5" as the result of "2 2 + ." which some Forth programmers would consider incorrect.
This definition looks like recursion; that is, defining a function in terms of itself, but the "+" inside the definition is really the old "+". Recursion is possible in Forth, but you have to explicitly say that you're recursing.
Forth is the kind of language in which you can define your own floating-point packages. Forth has also sometimes been the kind of language in which you must define your own floating-point packages, although the standards effort may change that.
Forth got its start in astronomy, having been invented by Chuck Moore as a language for controlling telescopes. Its early experience was a good predictor of how it would come to be used. It is today an official standard of the International Astronomical Union for exchanging procedures for controlling telescopes and related equipment. It's popular with space types at NASA. And it's used heavily in embedded systems and controllers.
Its inventor was a good model for its current users, too. Moore is a cowboy-hatted iconoclastic individualist, and Forth people today tend to be pretty individualistic. A language that requires programmers to define their own floating-point packages attracts programmers who prefer to define their own floating-point packages.
Which, naturally, raises some difficulties when it comes to settling on a standard. Some would like to see a more architectural standard; the current effort specifies Forth syntactically. The standard does bring floating-point math into Forth, but not without ruffling feathers. The standard also defines a "block" to be 1024 characters, rather than bytes. This, as Woehr points out, eliminates what was "the one truly portable file format in the whole computer universe." Sigh.
It was, of course, unfair of me to say that "standard Forth" sounds like an oxymoron. Forth has had many standards over the years (79-STANDARD, 83-STANDARD, FIG-Forth, polyFORTH) and now it has another. In much the same way, far from being lawless, the Old West was a place and time where the law was a gun, and everybody had one.
Forth code can be remarkably small: A Forth program will normally be a lot smaller than the equivalent C program, and often smaller than the equivalent assembly language program. It can also be very fast.
That's why it was the language of choice for a machine designed specifically to support cycle-chewing research in cellular automata, or CA.
Cellular automata were introduced almost 50 years ago by John von Neumann and rediscovered repeatedly since, for example by Stephen Wolfram, who discovered that working in one dimension rather than two simplified things.
The particular CA model that nearly everyone knows, and that I can explain without getting confused, is John Horton Conway's "game" of Life. Life is "played" on a grid of squares, or cells, each cell being either "alive" or "dead." The grid is usually thought of as being infinite, usually implemented as a finite torus. A simple rule, which is simultaneously applied to every cell, defines which cells will "live" or "die" in the next "generation," much like the rules that define transitions in finite-state machines. The rule for Life is: A live cell with two or three neighbors stays alive, while any other live cell dies; a dead cell with three neighbors gives birth, while any other dead cell stays dead. The neighbors of a cell are the eight adjacent cells (including those diagonally adjacent).
Life, with its simple rule, generates a universe of interesting patterns. Other rules can model physical systems or computational processes or biological systems, but Life itself is sufficiently powerful that it can be used to produce logic gates and perform calculations.
Life is not a game, although it can be treated like one. And CAs are serious science. von Neumann took CAs very seriously as a model of computing. And work with CAs has led to some serious results.
But the problem in doing CA research is that it is very demanding on the processor. The action is all at a macroscopic, long time interval, statistical level, but you've gotta build the microscopic structure to see the macroscopic.
So, of course, you need a CA machine. You need to scrap those high-level-language implementations of the CA grids and replace them with some grid iron.
So some guys did that. Tommaso Toffoli and Norman Margolus were the guys and the machine was called "CAM," originally built at MIT's computer science lab, later marketed as a roughly $1500 PC card by Systems Concepts of San Francisco. The machine is described in their book, Cellular Automata Machines: A New Environment for Modeling (MIT Press, 1987). For CA computations, CAM is faster than a suitably-programmed Cray-1.
And they programmed it in Forth.
This was natural, since Forth is so extensible. Writing Forth code involves writing new Forth words, and it is easy to use the relatively low-level Forth words supplied in the CAM software to create powerful higher-level words: ": BBM CENTER CW CCW OPP + + + >PLN0 ;" defines the rule for an interesting and useful billiard-ball model of collisions of molecules in a gas.
But this is all, in a sense, ancient history. CA and its successors have advanced beyond T&M's book, processors beyond CAM, and programmers beyond billiard-ball models.
The creators of cellular automata systems are trying to create living beings.
Cellular automata have spawned Artificial Life.
It starts with the gliders in Life. A glider is a pattern of cells that reproduces itself after some generations, but in a different location on the grid. Alternatively, it's a pattern that walks across the grid. Realizing that this self-reproduction was part of what he needed to prove Life capable of universal computation, Conway ran a contest to find the other critical component: a glider gun, a pattern that would shoot out gliders.
The glider gun was found, Life was shown to be capable of universal computation, and a group at MIT executed the tour de force of creating an adder in Life. The adder gobbled up streams of gliders representing input numbers and spit out a glider stream that represented the sum. This was more or less the end of the story, mathematically, and, as Steven Levy tells it in his book, Artificial Life: A Report from the Frontier where Computers Meet Biology (Pantheon Books, 1992), researchers were asking whether CA was worth any further study.
One researcher in particular who asked the question was Tommaso Toffoli, and given that he went on to invest considerable time and effort in CA, apparently his answer was yes.
The answer was yes, however, not for mathematical reasons. Toffoli agreed that the area was sterile mathematically. He thought it was interesting for its applications to reality. Of course CAs could be used to model physical systems, but Toffoli had something bolder in mind. CAs are themselves actual dynamic systems, and can be studied directly, not as models of something else, but as a way of directly observing the behavior of complex systems.
One person who understood that idea was Stephen Wolfram, who sees CAs as a path to understanding complexity. Wolfram also saw a striking similarity between time plots of some of his one-dimensional CAs and patterns on certain seashells.
What happened then was probably inevitable. The best-known CA was "Life," described as a game, there were all these seashell analogies being drawn, and predictably the workers in this developing field began to attract ridicule from the scientific establishment.
And the practitioners invited it. They spoke loosely of their creations as critters and ants, and of themselves as studying the essence of life, or as gods in the process of creating living beings.
They would have been ridiculed even if they hadn't literally meant what they said, as some in the developing field absolutely did.
The field in question is now known as "Artificial Life."
The field became official in 1987 when the first a-life conference was held at Los Alamos. The announcement, quoted in Levy's book, described a-life as "the study of artificial systems that exhibit behavior characteristic of natural living systems. It is the quest to explain life in any of its possible manifestations, without restriction to the particular examples that have evolved on earth.... The ultimate goal is to extract the logical form of living systems."
Although the work grew from Von Neumann's cellular automata, the concerns of a-life researchers are quite different from Von Neumann's and some assumptions have changed radically, too.
A-life systems now exist that exhibit most of the behaviors one would like to associate with life. That in itself is not so impressive, but what is impressive is that the artificial organisms, evolving over rapid generations, encounter many of the problems that confront living systems and evolve to deal with them. A-life systems have been built that evolve strategies for dealing with predators and parasites, learn to compete and to cooperate, explore the options in game-theory situations, and learn Kepler's laws of planetary motion. A-life research provides an answer to the old Woody Allen question, is sex necessary? (The answer: yes, sex is a means of getting down from a local maximum when doing evolutionary hill-climbing.)
And then somebody thought of applying the evolutionary processes of a-life to computer programs. Rather than write 'em, let's grow 'em, was the seemingly wacko notion. It's coming to seem less wacko, since some programs grown in this way have come up with solutions comparable to the best human programming.
The self-replication of patterns of cells in early CAs was only a hint of these populations of programs that spawn new, better-evolved programs that are today being grown on a Connection Machine at UCLA.
Genetic algorithms, this subdiscipline is called. While the freakiest a-life work is the kind that creates the most lifelike behavior in the most creature-like creatures, the concept of genetic algorithms is plenty scary if you're one of the lifeforms with which such systems would ultimately compete.
It's hard to think of a running program as a living being, and unnerving if you succeed in doing so. It's a little easier--but unnerving enough--to think of these things as programs that reproduce themselves, evolving new and better-adapted kinds of programs, written in new, weird, inhuman code.
Wait a minute. Weird code?
Is it possible that when--you may say "if"--that if or when these chaos-born, self-defining grid-livers attain the sophistication and intelligence of the average beginning computer science student, they will choose to program in Forth?
Hmm.
Copyright © 1993, Dr. Dobb's Journal