6
$\begingroup$

Question:

To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms?

I'm interested in citations, interviews, articles, links, or any other sort of evidence. It could also be evidence of the form of A and B here suggest that Moore might have borrowed or influenced C and D from Knuth here, or vice versa. (Opinions are of course welcome, but references / links would be better!)

Context:

Until fairly recently, I have been primarily familiar with Knuth's work on algorithms and computing models, mostly through TAOCP but also through his interviews and other writings.

However, the more I have been using Forth, the more I am struck by both the power of a stack-based machine model, and the way in which the spareness of the model makes fundamental algorithmic improvements more readily apparent.

A lot of what Knuth has done in fundamental analysis of algorithms has, it seems to me, a very similar flavour, and I can easily imagine that in a parallel universe, Knuth might perhaps have chosen Forth as his computing model.

That's the software / algorithms / programming side of things.

When it comes to "ideal computing machines", Knuth in the 70s came up with the MIX computer model, and then, collaborating with designers of state-of-the-art RISC chips through the 90s, updated this with the modern MMIX model and its attendant assembly language MMIXAL.

Meanwhile, Moore, having been using and refining Forth as a language, but using it on top of whatever processor happened to be in the computer he was programming, began to imagine a world in which the efficiency and value of stack-based programming were reflected in hardware. So he went on in the 80s to develop his own stack-based hardware chips, defining the term MISC (Minimal Instruction Set Computers) along the way, and ending up eventually with the first Forth chip, the MuP21.

Both are brilliant men with keen insight into the art of programming and algorithms, and both work at the intersection between algorithms, programs, and bare metal hardware (i.e. hardware without the clutter of operating systems).

Which leads to the question as headlined...

Question: To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms?

$\endgroup$
  • 2
    $\begingroup$ Wouldn't most answers be idle speculation? Also very open ended. And aren't meta tags like "soft-question" advised against? $\endgroup$ – The Unfun Cat Nov 13 '12 at 9:14
  • 2
    $\begingroup$ I don't remember that Knuth wanted to design an ideal processor but he wanted something typical of machine of the time (as is hinted by the fact that MIX and MMIX can considered as roman numerals for the means of the number of a set of computers of the same area). $\endgroup$ – AProgrammer Nov 13 '12 at 10:04
  • $\begingroup$ @TheUnfunCat Looking for anyone who may have more than idle speculation. This would be potentially three kinds of answers: (1) Direct influence: reference to articles, interviews, etc. in which one mentions the work / ideas of the other. (2) Suggestive influence: reference to ideas / characteristics in each's work, possibly time-lag, to sugegst influence. (3) Personal knowledge: Some among us may be separated from these individuals by a few degrees of separation and may know from personal communications the views of the two. $\endgroup$ – Assad Ebrahim Nov 13 '12 at 15:32
  • 1
    $\begingroup$ Knuth came up with MIX in the early 1960s, not in the 70s. First ed of Vol 1 of TAOCP (then abbreviated ACP) was published in 1968. Section 1.3 on MIX starts: In many places throughout this book we will have occasion to refer to a computer’s “machine language”. The machine we use is a mythical computer called “MIX.” MIX is very much like nearly every computer now in existence […]. This number was found by taking 16 actual computers which are very similar to MIX and on which MIX can be easily simulated, then averaging their numbers with equal weight: ⌊(360 + 650 + … + PDP4 + II)/16⌋ = 1009. $\endgroup$ – ShreevatsaR Jun 7 '17 at 16:54
  • 1
    $\begingroup$ ...But it should be noted that Knuth's account of how "this number was found" is extremely tongue-in-cheek; MIX is the numerological equivalent of a backronym. Fascicle 4a explains that MMIX's number, 2009, "was found by taking 14 actual computers very similar to MMIX and on which MMIX can be easily simulated ..." namely the 88K, Cray 1, IBM 801 & 601, RISC II & Power 2, Clipper C*300*, AMD 29K, Intel i*960*, Alpha 21164, MIPS R*4000*, SuperH*4*, StrongARM 110, Sparc*64*. $\endgroup$ – Quuxplusone Sep 20 '17 at 21:40
9
$\begingroup$

There is some evidence: This paper was presented at the ACM SIGPLAN History of Programming Languages Conference (HOPL II, April, 1993), co-authored by myself, Chuck, and Don Colburn, an erstwhile colleague now unfortunately deceased. It references, in turn, a very early work that Chuck wrote when Forth was in what might be called an "alpha" form, "Programming a Problem-oriented Language".

I worked with Chuck from 1970 until 1982, when he left FORTH, Inc. to pursue chip-level implementations of Forth. I know that he referenced Knuth's books and papers for specific algorithms from time to time, but do not believe Knuth influenced the design of Forth in any way. In the time I worked with him, the two men never met. Whether Knuth was aware of Forth or of Chuck I cannot say.

$\endgroup$
  • $\begingroup$ Thanks Elizabeth. Was aware of the 2nd paper, but the first is new to me -- very interesting history. Cheers for this. (Had been hoping that a former colleague of either man would find this and be able to provide some insight!) $\endgroup$ – Assad Ebrahim Nov 15 '12 at 12:27
  • $\begingroup$ In an interview in 2013, Knuth was asked about whether he or Chuck was influenced by the the other. Knuth's answer: "We haven't intersected at all, as far as I know." (search for Moore in the link provided to find the quote). $\endgroup$ – Assad Ebrahim Jul 15 '18 at 4:51
2
$\begingroup$

A 60 response thread on comp.lang.forth (Knuth, MMIX & Forth) provides an interesting contrast between Charles Moore's Forth / stack machines in general and Knuth's MIX/MMIX and register machines in general.

The takeaway is that Knuth's thinking was driven by other objectives (predictable run time, representing the majority of computing architectures, abstracting away specific constraints into a 'super-machine') rather than those that drive Forth and stack machines (simplicity of design, minimality, realizability).

So Knuth pursued register designs with MIX and doubled-down on register designs (256 of them) with MMIX.

The following comments are highlighted:

  • foxchip (Jeff Fox) (#3, #7 in the thread)
  • Anton Ertl (#14, #41),
  • Rick Hohensee (#17, #29),
  • Bernd Paysan (#30, #39)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.