This issue marks the beginning of the 14th year of continuous publication for Dr. Dobb's Journal. That makes this the 13th anniversary issue, and in honor of the occasion I offer this Janus view of the paradigms of programming, past and future. As you know, this is just the sort of schmaltzy occasion on which, writers feel free to indulge in the most shameless journalistic excesses: homespun anecdotes, romanticizations of the past, prognostications on the future, and filling space with other people's words.
"The more often a problem has been solved on a desk machine, the more certain it is that the methods developed need reexamining before translation into a computer programme." --R.K. Livesley, An Introduction to Automatic Digital Computers, 1957.
R.K. Livesley, in his little book about programming the Manchester computer in the 1950s, cautions the reader that some of our favorite desk calculator algorithms may be ridiculously inappropriate when implemented on a computer. His book was one of the first to discuss programming techniques. I somehow overlooked its sound advice, and similar advice in thousands of programming books over the succeeding decades, and had to learn the lesson the hard way.
In the mid-70s, I was a graduate student picking up some extra money writing statistical analysis programs in Fortran for faculty members and other graduate students. All the conventional studies lent themselves to analysis with the standard statistical packages such as SPSS, so the jobs I was picking up were all a little unusual.
One day a graduate student brought me a magtape full of data and a book with an equation circled and asked me to apply the latter to the former. I set to work implementing the algorithm that the equation implied, tested it on very small data sets against hand calculation from the book equation, scrutinized boundary conditions, pronounced the program ready, and turned in the tape to be loaded.
Insufficient memory. I banged my head against "insufficient memory" messages far too long -- probably because after seven years on campus I knew too many tricks for "finding" more core in the university's computer system -- before I finally did some calculations and convinced myself that the data set I was working with was not too large for my core allotment. I could load the entire input data set into memory, as well as all the output matrices. Between input and output, something was eating memory like a Core Wars champion. At that point I saw what should have been obvious from the outset: that the book equation made use of huge sparse matrices, ballooning the data out before collapsing it back to manageable size at output. It was simply an inappropriate algorithm for computer implementation.
So, having learned my lesson, I reworked the equation and everything was fine -- at least until the student's dissertation committee discovered that her analysis was based on my unpublished (therefore suspect) version of the equation. There was a lesson in that, too, but I'm not sure I ever really learned it.
But that's how I learned the lesson about the need to recast the algorithm closer to the machine's desire. When I acquired my first personal computer a couple of years later (a TRS-80 Model with Basic in ROM and 4K of user RAM), the first thing I wrote for it was a set of sparse-matrix collapsing routines. Just in case I had to do some heavy statistical analysis.
"The Ural II was exactly like a personal computer because it was just you and the machine.... With 4K of memory and the slow speed, it was very similar to the Altair, which was introduced in 1974. The excitement I experienced with the Ural II in 1964 was the same kind of excitement that Bill Gates experienced with the Altair in 1974." --Charles Simonyi, in Programmers at Work by Susan Lammers.
My TRS-80 experience was well into the personal computer era. You could do a lot with 4K of memory if you had Basic in ROM. It was harder earlier. Charles Simonyi gave himself headaches programming in octal absolute on that Ural II. And who, besides a hacker like Bill Gates, would have attempted to write a Basic interpreter for the Altair back in 1975? A bunch of hackers, that's who.
Toward the close of 1975, when the typical personal computer programmer was someone who had a friend across town with an Altair, the San Francisco Bay Area-based People's Computer Company had a runaway project on its hands. It wasn't an unusual situation; the group was filled with creative, energetic, intelligent people who were fired up by the possibilities of computers for empowering individuals, and had lots of projects to pursue. The group was, after all, an offshoot of the same group that produced the Whole Earth Catalog, subtitled Access to Tools.
The runaway project was a portable Basic interpreter that would run in the remarkably small memory space of the Altair, or on one of the other micro-computers then being designed. It was the famous Tiny BASIC, brainchild and bandwagon of Dennis Allison and Bob Albrecht, and raison detre of this magazine in its early days.
Those early days began in January 1976, and the magazine was originally titled Dr. Dobb's Journal of Tiny BASIC Calisthenics and Orthodontia (Running Light without Overbyte). The title said it all (a title that long had better say it all): memory is tight, and code must be equally tight. Dr. Dobb's readers and writers (then, as now, overlapping sets) were spending a lot of time recasting their algorithms closer to the machine's desire. And what the machine desired was tight code, memory-frugal algorithms. It was a time for running light without overbyte.
It's always that time. Dr. Dobb's subhead could still be Running Light without Overbyte. It's a paradoxical fact of programming life that memory space remains precious, efficiency remains valuable, no matter how much RAM you have. It's one of the two fundamental resources: The truism among programmers is that the only commodities are time and space. Cycles and core. Ticks and bits. And in some times and in some places, the truism is the only relevant truth.
Elsewhen and -where, though, it becomes appropriate to pay more attention to the human commodity: The programmer. Rather than focusing exclusively on the program and efficiencies with regard to its operation, to look at overall effectiveness of the programming effort. To allocate programming effort economically. It's not a new idea, of course.
I'm always pitching the importance of knowing many paradigms. That's the subtext (at least) of this column. I'm not alone in promoting this. One reason often put forth is that the separate streams of existing paradigms are currently converging. It's not entirely clear whether the streams are converging, though some, say, C. The truth is probably not so simple. In fact, it may, to muddy the metaphor, be more coagulation than convergence.
In any case, things are getting clumpier. Nobody wants to sell you a compiler anymore. What you need, you are told, is an environment. Well, you probably do; who am I to scoff. But "environments" are more complicated than compilers, and one of the ways in which they show signs of getting further complicated is in terms of support for different paradigms, and that's my beat.
The future in C programming environments, for example, seems to include a C++ front end. C programmers can use C++ to work in an object-oriented paradigm without quite leaving C, and while there may be arguments about whether C++ is fully object-oriented, it certainly brings in non-procedural programming considerations: Moving from C to C++ requires a paradigm shift.
Two products that have come across my desk recently, neither of which is a programming language, but both of which include programming languages, seem particularly catholic in their embracing of alternative paradigms. These are Mathematica from Wolfram Research in Champaign, Ill. and HyperBase from Cogent Software in Framingham, Mass.
Mathematica is an environment for doing mathematics. It is designed to run on many machines, notably the Sun, Macintosh, and NeXT machines. It handles the basically arithmetic calculations that spreadsheets know how to do, but it also solves algebraic and calculus problems. You can integrate a function symbolically or numerically. It supports arbitrary precision math. And it embodies, according to its creator, Stephen Wolfram, several different programming paradigms.
As a procedural language, Mathematica supplies the syntactic elements if, while, and for to direct flow of control, as well as the dreaded goto. But the language is more effectively used as a functional language like Lisp or APL. The thought processes that go on when building a functional program are different from those behind procedural development. Functional programming makes little use of control structures or named variables. In fact, Mathematica encourages eliminating names even for functions. Functional programs can look extremely concise:
exprod[n_Integer] := Expand[ Product[x + i, {i, n}] ].
Possibly the most powerful paradigm supported by Mathematica, though, is rule-based programming. This paradigm allows the programmer to build a database of rules like these mathematical rules for differentiation:
This technique brings with it a distinctly nonprocedural approach to programming. It's easy, using this approach, to develop a program by a process of successive approximations to the ultimate program. You simply add rules to deal with additional cases.
An even more disorienting paradigm, from the procedural point of view, is the approach of constraint propagation. In this approach (supported by Mathematica) you specify constraints that variable must satisfy, but don't tell the program how to satisfy them. Constraints like
make no assumptions about the direction of the relationships they define. The solve function does its best to pull a solution out of the constraints. This approach has similarities with using a spreadsheet, but with fewer, constraints on the form of the constraints. Spreadsheets in effect implement linear constraints, but Mathematica lets you define non-linear dependencies among variables.
Both the rule-based and constraint propagation approaches sound like logic programming a la Prolog, and in fact Mathematica supports something like the logic programming paradigm. It differs, though, in being more directed, more explicit, in the order in which it tries its rules.
Another consequence of Mathematica's aggressive ordering of its rules shows up in its implementation of recursion. A recursive solution to a problem always consists of at least one recursive (self-invoking) condition and at least one non-recursive, terminal condition. Mathematica lets you drop these conditions in as independent rules, like
without worrying about the order in which the rules should be applied. Mathematica understands enough about recursion to recognize, usually, the terminal condition and to apply it first.
HyperBase is a system for creating, what its author calls, intelligent documents. It runs on MS-DOS machines. Intelligent documents are text and graphics documents with attached code. The code is associated with elements of the text or areas of the graphic images, and when the code effects jumps to other nodes in the document, the system can be described as an implementation of HyperText. But the code can be pretty much anything, including commands that modify the text and graphics, in which case the system can be described as an adaptive document. The underlying language is a full Prolog system.
The result is a system that feels on the surface something like a word processor, and something like HyperCard or Owl International's Guide, while digging deeper into the product takes you squarely into logic programming. That's got to be a paradigmatic jolt.
Copyright © 1989, Dr. Dobb's JournalThe Runaway Algorithm: A True Story
Beyond Space and Time
Environmental Action
diff(x^n,x) = nx^(n-1) diff(log(x),x) = 1/x.
va = = vo r1 / (r1 + r2)
va = = vi
g = = vo / vi
factorial[n_Integer] := n factorial[n-1]
factorial[1] = 1,