1

Usually, computer science papers describe algorithms in Algol-like pseudolanguage, similar to Pascal or even C/C++.

But Donald Knuth uses his own assembly language (MMIX).

Are there any good known algorithms inexpressible in Algol-like language but expressible in unstructured assembly code? Like coroutines, maybe?

2
  • 2
    They are both Turing complete and thus can express all of the same problems. It might be a bit more wordy or awkward in one style, but it can still be done.
    – user40980
    Commented Nov 9, 2014 at 22:24
  • 3
    @MichaelT Turing equivalence is about computability. In algorithm textbooks, we are also interested in complexity, which depends on the model of computation. Algol-style performance and machine code performance usually are within constant factors of each other. But not merely because both are Turing complete.
    – user7043
    Commented Nov 9, 2014 at 22:56

1 Answer 1

3

I believe that Knuth himself gives an answer in "The Art of Computer Programming".

He says:

High level languages are inadequate for discussing important low-level details such as coroutine linkage, random number generation, multi-precision arithmetic, and many problems involving the efficient usage of memory.

But the decision to use a machine-oriented language is probably due to the fact that:

New algebraic languages go in and out of fashion every five years or so, while I am trying to emphasize concepts that are timeless.

(Preface to TAOCP vol. 1)


Moreover, if I did use a high-level language, what language should it be? In the 1960s I would probably have chosen Algol W; in the 1970s, I would then have had to rewrite my books using Pascal; in the 1980s, I would surely have changed everything to C; in the 1990s, I would have had to switch to C++ and then probably to Java. In the 2000s, yet another language will no doubt be de rigueur. I cannot afford the time to rewrite my books as languages go in and out of fashion; languages aren't the point of my books, the point is rather what you can do in your favorite language. My books focus on timeless truths.


Expressing basic methods like algorithms for sorting and searching in machine language makes it possible to carry out meaningful studies of the effects of cache and RAM size and other hardware characteristics (memory speed, pipelining, multiple issue, lookaside buffers, the size of cache blocks, etc.) when comparing different schemes.

Indeed since '60 there were suitable notation for coroutines in ALGOL-like languages:

...coroutine linkage had already been noted briefly as a "programming tip" in an early UNIVAC publication [...] A suitable notation for coroutines in ALGOL-like languages was introduced in Dahl and Nygaard's SIMULA I [...] and several excellent examples of coroutines (including replicated coroutines) appear in the book Structured Programming [by Dahl, Dijkstra, and Hoare].

(TAOCP vol. 1, pp 229-230)

Not to mention high-precision / multiple precision routine in FORTRAN / ALGOL:

Extended precision subroutines for use in FORTRAN programs were described by B.I. Blum (1965) [...] and for use in ALGOL by M. Tienari and V.Suokonautio [...] Arithmetic on integers with unlimited precision, making use of linked memory allocation techniques, was elegantly introduced by G.E. Collins [...]

(TAOCP vol. 2, pg 279)

Same about random number generation: there are examples in C (TAOCP vol. 2, pp 185-188) and exercises in other high level languages (e.g. [EX10] pg 193).