Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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!)


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?

share|cite|improve this question

migrated from Nov 12 '12 at 19:55

This question came from our site for theoretical computer scientists and researchers in related fields.

Wouldn't most answers be idle speculation? Also very open ended. And aren't meta tags like "soft-question" advised against? – The Unfun Cat Nov 13 '12 at 9:14
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). – AProgrammer Nov 13 '12 at 10:04
@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. – Assad Ebrahim Nov 13 '12 at 15:32
@AProgrammer: Agree that his computing model has always been "typical" machines -- which means the addressed register model, whether CISC or RISC. And then he did lots of deep algorithmic investigations on these typical machines. Was he aware of MISC and stack machines? – Assad Ebrahim Nov 14 '12 at 11:27
up vote 8 down vote accepted

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.

share|cite|improve this answer
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!) – Assad Ebrahim Nov 15 '12 at 12:27

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)
share|cite|improve this answer
Thanks, that was very helpful! – D.W. Jan 17 at 21:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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