Luke Welsh writes:
>The author tried to write two books at once. He really wanted
>to explain to the novice that the modern PC is essentially the
>same as the SWAC, built in 1950. By this, Rutland means that
>both are "stored program machines", and I skipped over sections
>where he tried to make this point. But I did learn that the
>credit does not all go to John von Neumann!! That was a huge
>surprise to me.
>From what I've heard, von Neumann was one of those towering figures
who made outstanding contributions in many areas, but whose reputation
was such that he also got credit for many things he was only peripherally
involved in - much like Newton and Gauss.
The stored-program idea goea back at least to 1805, when Jacquard used
strung-together sequences of hole-punched wooden cards to control the
weaving patterns of his famous loom. A few years later, Babbage used
the same stored-program idea (also with puched cards) for his difference
engine. Von Neumann himself usually credited the idea to Turing, who
advocated its use years before.
Thanks for the book review, Luke - another computer-oriented book
folks might want to check out (this one concerned more with algorithms
and models of computation) is "Out of Their Minds: the Lives and Discoveries
of 15 Great Computer Scientists," by Dennis Shasha and Cathy Lazere, 1995.
Now the fact that I like this book doesn't mean I agree with all the
points it (or the people whose work it describes) make. But that's good,
because it gets one thinking things like, "hmm, why is it that such-and-
such an idea never caught on? It seems so elegant in theory...". Example:
an interesting point I noted in rereading the section on John Backus, who
(among other things) led the IBM team that developed the first Fortran
compiler back in the 1950s, is that Backus was unhappy with many aspects
of his own creation, especially with its use of the so-called von Neumann
style of coding, which (for example) might compute an inner product of
two length-n vectors a and b using a scalar variable c to accumulate the
partial sums and an explicit loop structure like (I quote from the book)
" c := 0
for i := 1 step 1 until n do
c := c + a[i]*b[i]
Backus criticizes this formulation on several counts, but espe-
cially the following two. First, c is repeatedly updated, so that the
only way to understand the program is to understand that each update
serves to add one more product to a running total. Thus, one must be
able to mentally execute the code in order to understand it.
Second, the formulation names its vector arguments (a and b) and
their length (n). To work for general vectors, these must be passed
as "reference" parameters - a tricky issue in most languages. In
FP [a language Backus proposed to remedy the perceived drawbacks
of the von Neumann style], by contrast, the inner product operation
would be defined as follows:
Def Innerproduct = (Insert +)(ApplyToAll *)(Transpose)
This must be read right to left. Transpose pairs up the appro-
priate elements of the two vectors. In the above example, a[1] should
be paired up with b[1], a[2] with b[2], and so on. '(ApplyToAll *)'
replaces each pair by its scalar product. '(Insert +)' sums up those
products.
This has three principal advantages, according to Backus. First,
there is no hidden state (the variable c in the program above). Second,
it works for any two vectors of the same size because it does not name
its arguments (thus eliminating the parameter-passing issue). Third,
there is no notion of repeated calculation; each step, or {\it function}
(Transpose, ApplyToAll, and Insert,) is applied exactly once to the re-
sult of the previous step in a process known as {\it composition}."
In my opinion, many of the above arguments are spurious. For one thing,
what better way is there of defining "to understand" a code than to be
able to mentally execute it, i.e. to follow it step-by-step in one's head?
The argument about the passing of array dimensions is also spurious - to
set aside storage for the arrays, the computer must know their dimension
at allocate time, and thus n is not a "problematic" parameter to keep around.
The FP inner product definition also has its drawbacks - for instance, why
would a computer need the notion of an array transpose, especially for a
one-dimensional array? A human might need to know about this to do a pencil-
and-paper computation of an array product, but a computer doesn't care,
as long as the algorithmic rules for matrix multiplication are well-defined.
The "hidden state" argument is questionable - any decent compiler (human
or machine) can see that c is just a name for a place to store the partial
sums, and its accumulative nature is obvious from the assignment c := c +...
The naming issue is equally bogus - in practice, we have these things called
"dummy arguments," and writing their names down makes it a whole lot easier
to follow what is going on - can you imagine trying to generalize Backus'
name-less syntax to a problem involving many arrays? It's barely under-
standable for two!
The book mentions that functional programming languages like FP have not
caught on for various reasons, one the main ones being that they would
make it difficult for a compiler to generate efficient code. This seems
a rather spurious argument - in fact I would argue that many (if not most)
high-level languages already possess the functional composition features
Backus likes so much (A more modern term for it is "object orientation.")
Consider the successor to Backus' own baby, Fortran-90,
(which is not generally considered to create slow-running code) with its
whole-array syntax. In f90, one could do the inner product of vectors a and
b without imposing a particular loop structure or explicitly giving the
array dimensions, via
InnerProduct = sum(a*b).
This in fact works for arrays of any allowable number of dimensions,
as long as they they have the same shape and size. If one desires a
true matrix product, one has the spiffy matmul intrinsic, which
allows the details of the underlying computation to be done as the
compiler writers see fit, i.e. the user has a reasonable expectation
that the computation will be done in some manner that is well-matched
to the underlying hardware, whether it be an x86, Alpha or SPARC (or
whatever), and a single or multiple-processor machine - the latter
aspect is referred to as "inherent parallelism."
My point with the preceding example is, it's often quite illuminating
to compare the good initial ideas people had with the form they wind
up with in the real world of computation.
Happy Thanksgiving to our American viewers,
-Ernst
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
