The Evolution of CS Papers

A blog post by Crista Lopes discussing the evolution of CS papers away from positions into the realm of science; excerpt:

Note this (Dijkstra's GOTO considered harmful) was not a letter to the editor, it was a full-blown technical, peer-reviewed paper published in a Mathematical journal. Seen in the light of current-day peer reviewing practices in CS, even considering the fact that the paper was proposing a clear solution for a clear problem, this paper would likely be shot down. First, the problem for which the solution was proposed was clear but not well motivated: how important was it for programs [of the time] to call routines recursively? — maybe it wasn’t important at all! If it was important, what were other people doing about it? Any paper with only 1 reference in the bibliography goes immediately to the reject pile. Second, given that the concept had already been proposed (in writing) by H. Waldburger, the author of this paper would at least be requested to express his ideas in terms of how they were different from those described in H. Waldburger’s paper rather than spending most of the paper describing how to do procedure calls using stacks. Finally, the work is borderline an “engineering issue” rather than a scientific one.

These are complaints often seen in today’s CS peer reviews.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

It's not the goto; but the assignment command that is at fault

It's not the goto command; but the assignment command that is at fault in "spaghetti" code.

A goto command represents a relatively harmless procedure call who's arguments are the current values of local variables, which is the way that many of us program today.

However, abuse of the assignment command can be really harmful. Only recently have programming languages developed constructs to regulate assignment commands.

Not the point of the

Not the point of the post....but....

We all know that the program instruction counter is really to blame here. Assignments are fine as long as they can be coordinated, but that damn sequencing PC makes life complicated.

Dijkstra had no problems with assignments

Dijkstra was a great admirer of the work of Tony Hoare and the use of program proving. If you use those techniques assignment statements are absolutely no problem. It is the goto that destroys any hope of having invariants, which are the basis of program proving.

Hoare gave up on Dijkstra's model of states with assignments

In his initial version of CSP, Hoare used Dijkstra's model of computation based on global states mutated using assignment commands.
In his revised model of CSP, Hoare gave up on gave up on Dijkstra's model because it had the problem of bounded nondeterminism. Bounded nondeterminism is incompatible with concurrency.

Your reply, like the last

Your reply, like the last one, is again not the point.

Sorry that you didn't understand.

Sorry that you didn't understand.

Do you have any particular questions?

Dijkstra had a problem with assignment, but didn't know it :-(

Dijkstra had a problem with assignment, but he didn't know it :-(

Assignment is intimately tied his global state model of computation, which Hoare initially adopted for CSP. But Dijkstra's model is incompatible with concurrency and so Hoare abandoned Dijkstra's model in a later revised version of CSP.


Here is a summary for those that wonder whether they want to read the (interesting) whole thing, built out of quotes.

It’s fascinating to browse through the earlier years’ issues of CACM: the sense of discovery and of chartering uncharted territory is palpable. Most of the articles were of the nature “I did this cool thing, and I think everyone should know about it!” or “I see this problem, and I have a cool idea for how to solve it! (I may or may not have done it)”. Things that were considered “cool” at the time were efficient algorithms, analysis of geeky details of programming languages (Algol seemed to attract a lot of attention for a few years), new language constructs, compilers and operating system structures.

With the exception of JACM, throughout the 1960s and 1970s, at least in the US, novelty and interest to readership seemed to be the main criteria for publishing technical computer science work. Whether the ideas were effective or sound or provable or broadly applicable was not a concern (if it was, the published papers don’t transpire it!).

By the mid-90s, however, things started to change. I’m old enough to remember this phase as a professional adult — I witnessed this transition. To a large extent, it was my generation that brought this transition about. Questions started to be raised: “This is cool but how are you going to validate your claims that your idea is good?” or “This is cool, but can you prove it?” or “Are you sure this is really novel? How is this different from that other thing?”, etc. One reason for this, I think, was the sheer volume of work being published;

I have mixed feelings about this state of affairs, but I already wrote about that in another post. I like some of those old papers a lot! Had they not presented the “what & how to” without much regard for scientific argumentation, progress would likely have been a lot slower. Communities have their ways of separating the wheat from the chaff over time.

Do not expect a rant: there is little judgment in this piece, it's mostly a description of how things changed.

logic vs rhetoric

While reading both this post and its companion, it struck me that they both circle around the distinction made by the ancients between Logic and Rhetoric.

Logic, in many ways, is much simpler: two people, settling down to tackle the same logical problem, agree upon axioms, and therefore —even if their derivations have different structures— will come to the same conclusion.

Rhetoric, on the other hand, deals with how to arrive at pragmatic conclusions between people whose viewpoints start so far apart that they don't necessarily even have to coordinate unless persuaded (let alone share axioms) and in this sense it's a much fuzzier subject. While rhetoric shares common ground with logic, it is more concerned with plausibility than proof (cf enthymeme vs syllogism), which parallels the notion from "Social Processes and Proofs of Theorems and Programs" (link infra) that while practitioners and theoreticians may have a common subject matter in theory, in practice the former are far more interested in reliability than in verification.

To the extent that Logic is "how to discuss things we (can) know" and Rhetoric is "how to discuss things we don't (or even: which may well be impossible to) know" (where "knowledge" is meant here in the categorical sense of mathematical proof or scientific law), it makes sense that the JACM would prefer the former to the latter, and sure enough, we find that Lopes' "design and implementation" papers are over on the rhetorical, not the logical, side of the historical syllabus: Science doesn't map so well onto "design and implementation", but Invention, Style, Arrangement, and Delivery do.

A concrete example:

A concrete example: Lamport's Checking a Multithreaded Algorithm with +CAL is essentially a war story. Its subject is model checking, in particular, a counterexample to a proven algorithm —and what could be more Logical than formal methods?— but its method is Rhetorical: what pieces are required and how should they be arranged, what was the overall strategy and what were the particular incantations needed, in this case, to deliver the results stated with a reasonable (NB. not minimum) use of resources: taking into account not just hardware space and time, but also wetware.


Is it possible to "formally" define logic in such a way that it is essentially rhetoric? This, I think, is the remarkable accomplishment of 20'th century logic expressed by the loss of the analytic/synthetic distinction. Even more remarkable is the fact that that this doctrine was taken seriously and used as the basis of the research agenda we know as "Hard" Artificial Intelligence.


Re-reading it, I find the ", at least in the US," ellipsis interesting. When discussing retrospectives, I've often heard people make the remark that the work in the US tended to be more engineering-inspired, more hands-on, and work from old Europe generally had more formalism.

An hypothesis one could make is that the author's observed move to science-inspired validation corresponds not only to a chronological development, but also to a move from a more US-centric communication channel to globalized research venues -- giving more weight to the Bourbakis of program semantics.

I find that hypothesis unconvincing because I've also heard European researchers remark that the papers they used to write at the beginning of their career were much shorter and quite simpler -- a typical remark is that the page limit wasn't painfully restrictive back then, and that you may even not reach it (!!).

Relatedly, I've read some old stuff from the CACM (specifically, reader's reactions to the fascinating and controversial article Social Processes and Proofs of Theorems and Programs), and I've been struck by the quality of the writing. I suspect the scientific content of today I consume may be written by, on average, less-native English speakers (while the CACM was more US+UK-centric at the time); but maybe first-half-of-century's eduction of future scientists was also more focused on literary qualities.

You are making the wrong

You are making the wrong conclusions: US work is still more concrete than European work (on average, there are many exceptions). But there must be a "scientific evaluation", so maybe some theory, performance measurements, or bogus empirical user studies with like 5 data points will be thrown in to satisfy the rigor requirement without really being rigorous.

Now, Europeans are more genuine about rigor, but often fixate on it without providing anything else of value. At least for the US paper, you can skip the fake rigor section and still get something useful out of the paper, but for the European paper...that rigor is the contribution you are supposed to grock!

Ok, I'm exaggerating...just a bit. There are hones to goodness good papers in conferences on and people from both sides of the pond (and hey, maybe in Asia/Oceania also), just not 60 of them every year per conference.

English is a problem in my part of the world, but overall the biggest problems are still in story telling and wanting to "publish" badly rather than wanting to honestly communicate with your peers in the community, leading to lots of vacuous papers that pass the formula but will maybe be read by 2 or 3 people by accident.

I find that hypothesis

I find that hypothesis unconvincing because I've also heard European researchers remark that the papers they used to write at the beginning of their career were much shorter and quite simpler -- a typical remark is that the page limit wasn't painfully restrictive back then, and that you may even not reach it (!!).

Isn't this what you'd expect from any proof search process? The first outputs are low-hanging fruit that are short and sweet, and search becomes progressively more difficult as these get knocked off.

Some observations

* In the 60s, 70s, and 80s famous wellsprings of academic and semi-academic "cs" emerged from projects aimed at inventing commodity forms for computing systems to take.

Timesharing systems were built towards the vague idea of centrally administered "computing utilities". (One of the papers quoted in Crista Lopes' blog post even references the "computing utility" -- a term whose full meaning is, I suspect, lost in time for most of today's readers.)

Lisp machines were to be another form of commodity computing.

By 1990 I think this had changed: industry had settled on key commodity forms for computing and was able to (conservatively) amend and evolve these. Academics were pushed out of the business of inveting forms for commodities to take.

* Labs (anyone remember labs?) of that era tended to do heavy amounts of "eating their own dogfood". Labs wrote or heavily customized their own operating systems, text editors, text formatters, compilers, inter-personal messaging systems, and so forth. I am thinking particularly of examples from MIT, CMU, Stanford, Bell Labs, and Xerox PARC.

Often labs had captive audiences of users upon whom to try out software: undergraduates, faculty, other divisions of Bell Labs.

In the 1990s, institutions that housed great labs began more and more to use off-the-shelf industrial commodity components instead of home-made components.

I find it interesting that as commodity software took over, users I know of who directly experienced the transition often describe it as a regression from better to worse computing systems.

* A fair amount of work prior to the 1990s seems to me predicated on the idea that the main thing about computing would be a steady, deep need for new programs to solve complicated problems. The programs would be needed quickly and should work well. After the 1990s, interest in writing programs as a way to solve a very wide range of complex problems dried up.

Rich lisp environments or unix, for example, were made by programmers who wanted luxurious, super-awesome power tools for solving novel problems better than other people. Yellow pages publisher wants to move from manual to computer paste-up? Lispers can solve it faster! The chemists down the hall need an on-line way to format organic chemistry developments? Watch the unix lab strut its stuff with a simple, elegant solution in just a few weeks.

Nowadays, it seems, solving a non-trivial problem by developing new software is more commonly regarded as a last resort to be avoided even at significant cost. When new code is called for hopefully it is something trivial like a little glue code or Yet Another Social Network Web Service.

* 1990 is also roughly the before/after split regarding legacy compatibility.

Do we know how to make a "nicer" OS than GNU/Linux or Windows? Yes but people aren't interested because nothing will run on it.

Similarly for chips, programming languages, and so forth.

* 1990 is roughly the before/after split between coding as an high-skill expert job vs. coding as a low-level, low-skill professional job.

Firms increasingly formed around the concept of a few experts who brought the innovation and a herd of commodity "line coders" who realize the software under the experts' direction.

In the 1990s I think the industry's attitude towards object oriented programming shifted from "that's an interesting way to organize software" to "aha, so a master architect can lay out the architecture of the applications, expressing them as a class hierarchy, and the line coders can fill in the subclasses as needed."

* "Science" CS gained credibility in the early days of commidified computing.

For example, academic work to make incremental improvements to a unix file system could (a) be published with sciencey-seeming empirical performance measurements; (b) be a large enough advance to appear in the bottom line of some companies that relied on having lots of unix servers.

There was effort (around the cusp of the 1990s) to try to similarly objectify / quantify U.I. quality in ways that somewhat echo the invention of "time study" analysis of factory production lines.

* The "cloud", in a way, realizes the "computing utility" vision behind (for example) Multics.

Except that instead of "democratizing" computing, as per the rhetoric from the 60s and 70s, it is now much more about subordinating users and legacy institutions (e.g. "cloudifying" email to increase opportunities to surveille users; "cloudifying" storage to take revenue away from the market for personal computing hardware and give it to projects built around surveilling users).

loosely disorganized fields

Some engineering fields like audio amplifier design or bridge construction are disorganized crafts and that seems to be their essential nature.

There is, in these fields, no over-arching, all-subsuming theory into which every practice fits in some important way. There may be big overarching theories that purport to achieve this but when it comes time to do the actual work, other learning is consulted -- not the big unifying theories.

The "theory" in fields like this is somewhat atomized, somewhat disorganized. "Got problem X? Sometimes you can solve that by doing Y or Z." or "Here's a list of usually-safe work-around when a joint you are supposed to weld has a gap larger than specified."

Engineering "field books" in such fields are encyclopedias of scattered solutions like that. My WWII-era army corp of engineering manual answers questions ranging from how to frame a roof on a command quarters to what range of radii are OK on train-tracks without having to worry about derailing cars. There is no need here to ground all these parts in some underlying grand theory of materials and structures.

If you read a lot of the early stuff as if it were written by people who thought of programming as analogous, it's often anecdotal nature isn't so surprising.

Practical theory

I am glad to see someone thinking about these things. I have a collection of obsolete engineering and handbooks that I use to decorate my living room. There is something important to be learned from these books about common sense and about technology itself. Some interesting points: these books do not exclude math or theory but teach it as a way to "think about" and organize the field. Theory serves the intuition of the practitioner, even if it is only occasionally used in a calculation. Handbooks for "Electricians and Radio Men" require a lot of algebra and trigonometry.

But the style is not only for technicians. Remarkably, a densely mathematical book like Hartmanis and Stearns, "Algebraic Structure Theory of Sequential Machines" is written for "practitioners". And it help if you can read the math!