The loop is broken

The inner loop

In this session we concluded the central section of the central section of “Literate Programming”. In sections 22-26 of the “woven output,” Knuth presents the “inner loop” of his program to print the first 1000 primes. The inner loop checks each candidate number $j$ to see if it is prime. It is the kernel of the program, the part that consumes the most computation time, and which performs the function closest to the program’s ultimate goal. And it does it all without performing a single multiplication or division…

We noticed again some common ticks in Knuth’s rhetoric. Once again we encounter “the remaining task” (which we had already met in section 11). Once again the program is “quite simple” and “straightforward” (as have been most parts of the program). Knuth’s program text unrolls like a function being optimised. It relentlessly converges on its solution, following a chain of logic whose links are joined each to each in an intuitive way. By this point in the program, the whole group were baffled by the mathematics. For this group of humanists, the refrain of straightforwardness had become rather humerous.

For my part, I find Knuth’s authorial persona amusing, his program elegant, and his presentation of it poetic—to the extent I was able to understand any of them. But others in the group found his authorial persona “judgey,” and his presentation of the program intolerably taxing on the powers of memory. What do all these auxiliary variables mean again? What exactly is the structure of that table? How are those different numbers combined? Who exactly was Eratosthenes, and what does his “sieve” have to do with any of this?

Way back in section 3, Knuth informed us that the program should be “reliable, well motivated, and reasonably fast.” We were all amused by the program’s final motivation:

Let’s suppose taht division is very slow or nonexistent on our machine. We want to detect nonprime odd numbers, which are odd multiples of the set of primes $\set{p_2, …, p_{ord}}$.

We have discussed at many points the exemplary nature of the program. Knuth does not intend to provide either a useful program listing (e.g. a prime number solver for use in production), or an exercise in programming style (e.g. an example of structured programming). He intends to provide a well-documented program using WEB, and one gets the impression at many points that the program has been made needlessly complicated simply to justify the need for WEB’s features. In this case, the computer’s lack of division requires explanation, which requires documentation, which requires—WEB.

A maze of strands

We took a moment, upon completing the program itself, to reflect on it as a literary work. Most in the group agreed that the WEB program has a remarkably “tangled” structure—to misuse Knuth’s own metaphor. You could say that the program is deeply intratextual. It constantly refers to itself. No part of the program can very easily be detached, and viewed independently on its own. To understand any part, it is necessary to recall the whole structure of variables and constants that govern its behaviour. The text of the explanation typically refers to code that has not been presented yet. To understand the “motivation” for each programming decision, you need to already understand the program, or at least programs like it. The text is topsy-turvey, round-about, splayed-across and liketty-split. I personally enjoyed the ride, but well-oiled labyrinths are not for everyone!

Upon reading section 27, the index, some of the group were dismayed. (Not really.) If only we had kept the index open the entire time, it might have been possible to keep track of all the quantities and arrays that comprise the program code! But as one member of the group observed, Knuth’s preference for mathematical symbolism makes the index unreadable on it’s own. What do $c$ and $cc$ mean? You already need an intimate knowledge of the program to understand that they mean “current column” and “columns per page.”

Another in the group observed the difficult role that time plays in “the plot of the code.” The program text has its own narrative time, marked out sequentially by the section numbers. It also refers to the serial time of the computation, and to the “parallel time” of certain “auxilary variables” which evolve in lockstep with the main variables of the program. On top of this, the reader is constantly aware of the way the program loops back on itself, providing a structure for WEB to reorder all the code as the PASCAL compiler demands. And then there is the overall evolution of the algorithm as a process when the program is run. Knuth’s program has the complex temporality of a Virginia Woolf novel, and a Woolfian quality of internal reflection. Perhaps for someone whose daily life is number theory, the program would also have those Woolfian qualities of sacredness and care that we were, for the most part, unable to draw from the text.

We also discuss the personality of the text. Knuth argues from the start that “[p]rogramming is a very personal activity,” and suggests that the programmer’s personality should shine through the code. If you can see the person behind the code, you can understanding the reasoning behind the code, and therefore can understand the code itself. One member of the group suggested that this contradicts the common ideal of “egoless programming,” which is important for engineers working on complex projects in large teams over many years. How “egotistical” is Knuth’s idea of “personality”? Knuth himself is a master-craftsman. Perhaps for him there is no link between personality and ego, for the master-craftsman loses herself in the craft, and can bear any criticism of her work so long as it is in the cause of programming elegance. But perhaps ego and personality cannot so easily be separated.

We recommence next week in the fourth paragraph of D. How the example was specified.

A scripture language

Cultural literacy

A moment’s thought makes it clear that ord changes in a simple way when j increases, and that another variable square facilitates the updating process. (p. 101)

Literate programming requires literate programmers. Readability is relative. Readers must become literate before they can successfully decode a text, and enter the free world of interpretation.

In this quotation, Knuth once again draws attention to the rationality of his program, its unfolding according to agreed principles of thought. What kind of rationality is this? What principles have been agreed? What does the reader have to know in order to grasp after a “moment’s thought” that j, ord and square are related in the way Knuth implies?

Kunth presupposes a certain level of mathematical knowledge in his readers. We discussed the reasonableness of this assumption. Presumably The Computer Journal primarily has a readership of academic computer scientists, whose education includes at least one course in number theory. If we presume this audience, then Knuth’s gestures of understanding—”A moment’s thought makes clear”—are consistent with the literacy of his readers.

Number theory of course remains fundamental to programming in the twenty-first century. The entire edifice of internet communcation rests on encryption algorithms which derive from number theory. Students who undertake degrees in Computer Science surely still acquire this literacy.

But does this assumption square with Knuth’s aims? He seems to want literate programs to become part of general literature. He suggests that the program text should make explicit the programmer’s thought-process. How much of this thought-process can be left implicit, in a program destined for a general readership?

The audience of programmers is much wider than the audience of computer scientists. In 1984, the concept of “computer literacy” was in the air. Many governments, educational institutions, and visionary programmers believed it was essential for the general public to learn to program. The UK’s Computer Literacy Project was in full swing. Millions of Britons tuned into televisions programs such as The Computer Programme and Making the Most of the Micro, which taught viewers how to code in BASIC. More than 150,000 bought 30-Hour BASIC, a coding course that could be taken independently or via correspondence. Aside from BASIC, other programming languages such as Logo and Smalltalk had been developed for children and hobbyists to use. Number theory, it needn’t be stressed, was not a key component of 1980s “computer literacy.” It is notable that this notion of “computer literacy” seems not to have informed Knuth’s notion of “literate programming.”

Modern professional developers, of course, are often data scientists or web developers with little training in mathematics. A front-end developer trying to position a <div> correctly is unlikely to know many theorems about the cardinal numbers. Knuth’s program arguably makes incorrect assumptions about the professionalisation of programmers, even if it makes correct assumptions about the literacy of The Computer Journal’s readers.

It is probably unfair to criticise this one program of Knuth’s. He has selected a particular program which will appeal to a particular readership so he can demonstrate WEB. One could also make a Romantic/modernist argument in favour of Knuth’s text: there is a place in literature too for complex texts that address an intellectual few. The world can accomodate Ulysses as well as Treasure Island. But then, Knuth did seem to set out for the kind of crossover appeal of a Jane Austen…

One member of the group compared Knuth’s use of number theory to an eighteenth-century gentleman’s use of the Bible. It is simply assumed that the references will make sense. Where does the problem lie… Should we all know number theory? Or should we change religions?

On complexity

The main aim of sections 11-21 of Knuth’s program is to reduce the “time complexity” of the algorithm, as one member of the group noted. The naive algorithm for filtering the primes consumes far more time than is necessary. Knuth steps us through the derivation of Djikstra’s prime-number algorithm to explain how it will reduce the complexity of the calculation.

“Complexity” is a word that is used so often in so many different contexts that it is virtually meaningless. Knuth, it must be said, does not actually use the word in this paper.

The naive way to find the primes would result in a more “complex” program, because the program would need to perform more calcuations. But the naive algorithm would result in a much simpler program text: it could be written in fewer lines, and would require much less effot on the part of the reader to understand.

Knuth is a pioneer in the analysis of algorithms, which focusses on the space- and time-complexity of algorithms: that is, how simple they are for the computer to execute. There are other kinds of complexity that computer scientists care about, such as the Solomonoff–Kolmogorov–Chaitin complexity, which is related to how “big” the program is as a set of instructions.

Neither kind of complexity quite explains the readerly experience of programs. The simple-complex distinction is only useful in certain domains. The distinction established by Erich Auerbach between parataxis and hypotaxis as literary styles may be more important. Knuth’s text can be hard for a nonspecialist to follow because it is highly hypotactic. Each part of the program radically depends on every other. He uses WEB to manage this hypotaxis, by putting interdependent parts of the program near each other. But if he had found a paratactic style for his program, that required the reader to keep less information in their heads, perhaps our little group of readers may have had an easier time navigating his program text.

We recommence in a fortnight at section 24.

All that remains

The three-act structure of the literate program

The remaining task is to fill table p with the correct prime numbers.

Halfway through Knuth’s program, we find the algorithm for generating primes. To this point, his program has focussed on controlling the machine. He has defined the global parameters for the program, and some complicated routines for placing numbers in a printed table. Thus far, we have read about variables such as row_offset, being the number of rows that have already been printed, and constants such as cc, the number of columns that can be accomodated on a single page of the table.

In the group, we spoke about the relationship between the programmer and the machine. In Digital Humanities, we only rarely interact with the machine in this direct and geometric way. Gone is the age of the early microcomputer, when the computer in ‘text mode’ would allow the user to display a certain number of characters on a screen of fixed column and row dimensions. Today we take flowing text for granted. Gone also are the days when printing a simple heading at the top of each page would require six statements:

begin print_string(`The First `);
print_integer(m);
print_string(` Prime Numbers --- Page `);
print_integer(page_number); new_line; new_line;

In Python, this could be accomplished with string interpolation:

print(f"The First {m} Prime Numbers --- Page {page_number}\n")

To complicate things, Knuth’s heading-printing code is actually written using a series of macros defined in a previous section. When the macros are applied, the resulting PASCAL code is as follows (see Figure 3 in Knuth’s text):

WRITE('The First '):WRITE(M:1);
WRITE(' Prime Numbers --- Page ');
WRITE(PAGENUMBER:1);WRITELN;WRITELN;

Only after several pages of this complicated programming does Knuth arrive at the ‘task’ of actually generating the first m prime numbers, which would seem to be the point of the program. Although of course, generating the first m primes is not the point of this program. The point of this program is to illustrate the concept of ‘literate programming’ and to demonstrate the WEB system. The inner purpose, to generate the first m primes, is a fictional purpose. Knuth is telling a story about a fictional version of himself, who needs to generate the primes, and wishes to write a readable program for doing so.

In this context, his heading code is very good. It gives him scope to demonstrate WEB’s macro system. It gives him scope to interleave code and explanation. It gives him scope to reflect on the proper narrative flow of a literate program.

In Knuth’s view, the program should have a three-act structure. Act 1, declare the basics. Act 2, do the housekeeping. Act 3, implement the algorithm. He is a Shandyan narrator, who includes many digressions—e.g. how to print a heading—on the way towards his ultimate goal. The digressions have caused some level of frustration in our group, but perhaps this is the point. Act 2 creates suspense. Knuth establishes the fictional purpose of his program in the first block of code, and then waylays the reader, whetting their appetite for the ‘real’ programming to come. It was some relief in our group to finally reach section 11, when the ‘remaining task’ of generating the primes recurred. Act 3 begins with a bang.

In this article, the programmer is like an eighteenth-century stage manager. The script of the play is only secondary. What matters is the scenery, the special effects, the footlights and the songs. We watch the play from the wings, as the stage manager summons up the mechanisms of the theatre. Flood the stage! Bring on the horses! Swing in the heroine on the trapeze! Knuth is a poet-hacker of the old school, the plot of whose text is the unfolding of the machine. In his hands, the abstract purity of Djikstra’s algorithm for finding the primes becomes concrete. As one in the group said: you can’t have a table of numbers if you haven’t got a way of printing the table. Knuth may well agree.

Conventions

〈 Output a line of answers 8 〉≡
  begin for c ← 0 to c - 1 do
    if row_offset + c * rr ≤ m then
      print_entry(p[row_offset + c * rr]);
  new_line;
  end

A second theme of our discussion this week was literary convention. Few in the group find Knuth’s naming conventions easy to understand. Knuth likes his code to look like algebra, and uses a host of unstated convention when he names variables. To someone with a background in discrete mathematics, it must seem obvious that n is how many primes we currently have, and m is the maximum number we’d like to reach. It must seem normal that j is the current number we are testing, and k is the index of the current prime number in the table. It must seem normal too that r, c, and w mean the current row, column and word position, while rr, cc and ww mean the maximum number of rows, columns and word positions. But in our group we don’t all have this background, and these choices of name are not so obvious!

Many in the group would maybe have preferred the above code if it looked like this:

〈 Output a line of answers 8 〉≡
  begin for column ← 0 to column - 1 do
    current_prime_index ← row_offset + column + num_rows;
    if current_prime_index ≤ max_number_of_primes then
      print_entry(primes[current_prime_index]);
  new_line;
  end

Most of us have done most of our coding in Python, where it is common to label variables explicitly as above. Indeed, pylint will highlight single-letter variable names like c or r, recommending the coder to expand them. Most of us do our coding in a humanistic context, where algebra is an uncommon acquirement. Mathematical formulae tend to look forbidding rather than familiar, even in Digital Humanities.

This is all to say that conventions are strong in coding as well as in other kinds of writing. These conventions are generally used unconsciously: even Knuth, the most self-aware of programmers in this most self-aware program, doesn’t note the algebraism of his own style!

On Writing Itself

Now that appropriate auxiliary variables have been introduced, the process of outputting table p almost writes itself.

What does it mean for code to ‘write itself’. On a commonsensical level, it is obvious what Knuth means. When appropriate variables have been defined, then it is plain how they should be combined to express the programmer’s intent. Knuth effectively makes a prediction: any programmer worth their salt could see how the next part of the code should be written. As one of our members observed, however, lurking beneath this commonsensical supposition is a host of metaphysical presuppositions. What makes the code obvious? Why does the writer feel that the code has become autonomous, and is running off in its own direction?

There are many different agents in the ‘assemblage’ of the WEB system as Knuth writes. The PASCAL language, with its grammar and vocabulary. The WEB system itself, with its various (rather quirky) affordances. The presumed reader of the Computer Journal for whom is code is really being written. The logical force of mathematics and the algorithm. The beauty of the program, which is put there by the programmer but then turns back on its creator to bewitch their senses. When the the ‘code writes itself’, it is really some combination of these forces acting together to educe the code.

What code? This code:

〈 Print table p 8 〉≡
    begin page_number ← 1; page_offset ← 1;
    while page_offset ≤ m do
        begin 〈 Output a page of answers 9 〉;
        page_number ← page_number + 1;
        page_offset ← page_offset + cc * rr;
        end;
    end;

The code that has ‘written itself’ has offloaded its job to another part of the program! The actual code that ‘writes itself’ is essentially just a piece of housekeeping that keeps track of which page we’re up to in the printing loop. We discussed for some time Knuth’s decision to leave the actual outputting of a ‘page of numbers’ to another part of the program. No doubt his judgement is good. He strives for a certain kind of modularity, where each module is highly concrete and can be summed up in a verb phrase (“Output a page of answers”).

Reading the code again, it does have a feature I find disquieting. Presumably 〈 Output a page of answers 9 〉 uses some of the variables we have already encountered, including page_offset, but the way this code is written, you have no idea which variables will be used or altered by 〈 Output a page of answers 9 〉. Is this a deficiency of PASCAL, or of Knuth’s code, or of WEB itself? Pascal supports subroutines with named parameters (at least, it does so today). Why not write a subroutine here that explicitly shows in its signature which variables will be usd to 〈 Output a page of answers 9 〉?

This raises the additional question of ‘readability’. This is one of the major aesthetic criteria of modern programming, but what it means is debatable. Knuth argues that his code above is readable because it clearly states the programmer’s intention, and states it in (roughly) the order that the programmer thought up their intention. But from another perspective, the code above is not especially ‘readable’ because it doesn’t clearly indicate the flow of data through different parts of the program.

Knuth’s judgments about what to include, exclude, abstract or concretise are in every case fascinating. As another member noted, he seems to strive for ‘modularity’ in all aspects of the WEB code, even the prose components, which are carefully fenced off into discrete modules by square brackets and section numbers.

We resume next session at section 9 of his program for printing the first 1000 prime numbers.

Explanation and Motivation

We continue our reading of Literate Programming, by Donald Knuth.

In this session, we completed up to the end of section 5. Knuth has by now given the ‘plan’ of his program to print the first m prime numbers, and has commenced his explanation of the program’s ‘output phase’.

Our discussion focussed on the link between ‘motivation’ and explanation in Knuth’s vision for WEB. Knuth essentially argues that the prose of a WEB program ought to ‘motivate’ the programming decisions expressed in the code. His model for this process is the essay, which he perceives as a literary form in which the writer records their own thought-process. The source of a WEB program thus ought to reflect the programmer’s own creative process.

This is a powerful model of composition. From a literary studies perspective, it recalls the approach of the late Helen Vendler, who famously interpreted poems as records of their own creative process.

But many in the group objected to aspects of Knuth’s argument.

In the first case, does an essay ever accurately reflect the writer’s thought-process? Is there not an element of revision, polishing, and rhetoric in any essay? This doesn’t invalidate Knuth’s point, but thus far he does not seem to recognise the fictionality of the creative process. His WEB code is a story about how he wrote the program. What is the relationship between this story and the reality? Is there any reality that is not the story?

In the second case, his particular pattern of explanation didn’t work for everyone. In Knuth’s view, each part of the code should be preceded by the prose that ‘motivates’ the decision. Some in the group felt that it would be better to present the code, and follow it with a commentary, at least in some cases. But this would undermine the fiction that that code is emerging from a reasoning process that is reflected in the source.

Of course, we in the group bring our own assumptions and biases to the discussion. Knuth’s idea of the ‘essay’ may be perfectly valid, although it conflicts with ideas about literary composition that are popular in English departments. In particular, we dicussed the familiar nostrum of the ‘intentional fallcy’. Knuth makes little distinction between the programmer’s intention (or motivation) and the ‘meaning’ of the program. In Literature departments, we habitually distinguish the intention and the meaning: what the writer intended to say has really nothing to do with what they actually manage to say. As one member of the group observed, this notion of the ‘intentional fallacy’ reflects certain limitations in literary scholarship, especially the dominance of the nineteenth-century novel as a model for literature in general. Perhaps Knuth is right to tightly couple meaning and intention in the context of computer programming. The ‘author’ of a program is typically many people in conversation, unlike the distant ‘author’ of a triple-decker novel.

Against against intention: Amerikkkka, by Peli Grietzer.

An entire book written in WEB (or rather CWEB): MMIXware: A RISC Computer for the Third Millenium