The Evolution of CS Papers

gotoconsidered

This post was prompted by a Facebook interaction regarding Dijktra’s famous “GO TO Statement Considered Harmful” article, a letter he sent to the editor of CACM back in 1968. Seen through the lens of currently accepted research reporting practices, Dijsktra’s article reads like a technical rant, something that we might find in today’s blogs, but that have been essentially abolished from peer-reviewed research publications. Here’s a person stating his strong opinion about a language construct that he dislikes, starting with a strong premise about the negative effects of that construct without presenting any data whatsoever supporting that premise! As far as anyone can tell, the premise was based entirely in his own experience and intuition — which happened to go against opinions of other famous Computer Scientists at the time like Knuth. Granted, this was just a letter to the editor, not a full-blown technical article. However, the influence of this letter is unquestionable! Following Dijsktra’s rage against GO TOs, practically all programming languages that came after it avoided that construct, and the ones that didn’t, work hard at hiding it from programmers, sort of like “oops! sorry! there’s goto, but try to avoid it, ok?” (Also, this letter was single-handedly responsible for starting the meme “X considered harmful” that has been going on in CS since then, although credit for that meme goes, not to Dijkstra, but to the CACM editor, who spiced the title a little bit from its original “A case against the GO TO statement.”)

Whether GO TO is harmful or not, is besides the point. In the process of writing my upcoming book, I spent a considerable amount of time over the past year looking through old CS literature. It’s fascinating! The topic of this post is the evolution of methods in Computer Science research for the past 60 years, and the changing ways by which ideas are considered well-argued for.

Let me start in 1960, because I believe the papers of the time represent a fork in the road.

dijkstraBack in 1960, Dijkstra published a very influential technical paper with the title “Recursive Programming” in the mathematical journal Numerische Mathematik, where he put forward the idea of using a stack in the implementation of subroutine calls. Up to that point, subroutines in the PLs of the time, specifically Algol, were given fixed blocks of memory, so it was impossible to call them recursively. Using an activation record pushed onto a stack every time a subroutine was called solved this problem.

To set the record straight, Dijkstra was not the first person to suggest that stacks might be a useful data structure for computation. Back in 1946, Turing had already put forward that idea in an internal report, although, because of restrictions from the British Secret service, it’s questionable that anyone had seen it; but it’s likely that Turing talked about it. Using stacks for computing arithmetic expressions was well known at the time. By the mid-1950s some German professors had described using stacks for subroutines calls, including filing for a patent, and the idea was independently developed by 2 Australians and another Professor at ETH. Dijkstra’s paper has the grand total of… 1 reference to a paper by one of his close collaborators. It’s interesting to analyze the context of the citation to that work:

[After presenting arithmetic expressions using stacks]
“The above is well know (see for instance [1]) and so elegant that we could not refrain from trying to extend this technique by consistent application of its principles(*). [...]

(*) Without doubt, in view of the vivid interest in the construction of compilers, at least some of these extensions have been envisaged by others but the author was unable to trace any publication that went further than [1]. The referee was so kind to send him a copy of the report ‘Gebrauchsanleitung fur die ERMETH’ of the Institut fur Angewandte Mathematik der ETH, Zurich, a description by Heinz Waldburger of a specific program organization in which similar techniques as developed by Professor H. Ruthishauser in his lectures are actually incorporated. The author of the present paper thinks, however, that there the principle of recursiveness has not been carried through to this ultimate consequences which leads to logically unnecessary restriction like the impossibility of nesting intermediate returns and the limitation of the order of the subroutine jump (cf. section F 44 of the report).”

This is the entirety of “related work” in Dijkstra’s paper — a footnote! The passage also discloses Dijsktra’s attraction to stacks: a technique “…so elegant that we could not refrain from trying to extend [it]…” (ooook!)

Note this 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.

But this obviously misses the cultural context of the mid-20th century. Things were very different back then!

turingLet’s go even further back to 1936, an important year for the emergent field of computing. In that year, two foundational papers were published, one by Alonzo Church and the other by Alan Turing (picture on the left: page 28 of Turing’s paper). Church’s paper described the lambda calculus, a model of computation that influenced the design of the Lisp system 2 decades later; Turing’s paper described the Universal Turing Machine, which influenced the architecture of computing machines that were built 1 decade later. Both papers focused on the issue of computability of functions; they both had Gödel’s earlier work as the stepping stone. Turing referred to Church’s paper, which had been published just a few months earlier. Turing’s and Church’s papers are both Mathematical in nature: the ideas are argued with theorems and proofs. They read like today’s Mathematical papers.

jacmBetween 1936 and 1955, work in the computing field was published in Mathematical journals, as there were no publications dedicated to it. One of the first publications dedicated to this emerging field was the Journal of the ACM (JACM). Started in 1954, its first issues focused primarily on numerical methods that could be given to a computer for solving algebra problems, differential equations, etc. Those papers were Mathematical, using theorems and proofs as the method of argumentation (the figure on the left shows a page from a paper published in 3(3) 1956). One could call that work Computational Mathematics. Over the years, JACM consistently continued to focus on the Mathematical aspects of Computer Science, although  in the earlier years, and from time to time, it also carried non-Mathematical, design-oriented, papers, some of which resulting from work presented orally at the Society’s annual meetings — but those were the exception, and their methods were clearly at odds with the ones in the Mathematical papers.

For example, one short non-Mathematical paper published in 1961 describing a language for symbol manipulation ends with “The examples in the text and appendices are adapted from an ALGOL translator which the author is programming for the UNIVAC 1105 in the notation described. It appears that a translator can be described compactly and precisely in this notation, and that it is not difficult to translate the productions into symbolic assembly language.” Another one published in 1965 describing an architecture for a multiprogramming computer ends with “The ideas presented in this paper have grown from experience gained while implementing general purpose time-shared computer systems at MIT [5, 6], together with and our desire to create a second generation of computer utility with greater power and efficiency of operation. It is our conviction that these concepts are applicable to the design of online systems in general [7].” These papers had a completely different nature from the Mathematical papers, of which the picture above is one example.

Soon, the few design and implementation papers disappeared from JACM. Fast forwarding to 2014, and browsing through the most recent Table of Contents of JACM, it is not surprising to find papers that are Mathematical in nature, and that could very well have been there in 1955! Advances in human knowledge in the past 60 years not withstanding, the ways of arguing accepted at the JACM have been fairly homogeneous: formal systems, theorems and proofs.

But by the late 1950s, “Computer Science” had grown from pure Mathematics to the various ways of programming computers and of processing programs written in various programming languages. Dijkstra’s work follows this new trend, and his “Recursive Programming” is a good example. He was not the only one. For example, John McCarthy’s “Recursive functions of symbolic expressions and their computation by machine, part I“, published in the same year as Dijsktra’s “Recursive Programming”, describes the Lisp system — a system intended to carry out instructions using “common sense”. Even though the work was based on Church’s lambda-calculus, McCarthy’s paper has no theorems or proofs; also, there aren’t any illustrative applications, as he hoped to do that in another paper (which was never written!). The paper is entirely a [dry] description of the Lisp system, with no further justification for it other than they wanted to build it in order to support automatic deductions.

In order to cope with this non-Mathematical material, in 1957 the ACM started a monthly magazine called Communications of the ACM (CACM). CACM featured a mixture of algorithms, language designs, recipes for using computers efficiently, and opinions on topics that were important at the time, including what to call the emerging field. McCarthy’s Lisp paper was published there in 1960. 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.

quicksortCACM illustrates the fork in the road that happened around 1960: while some papers stayed within Mathematics,  more and more material was being communicated that wasn’t Mathematical, but that covered some aspect of design and implementation of computers and programs. This second kind of articles seemed to be valued for exposing some novel idea that might appeal to the readership. A series of algorithms, including Hoare’s Quicksort, published early on is a wonderful example of this (see CACM 4(7), figure on the left). The algorithms were presented as pseudo-code without much text around them other than a comment!

cacmWith 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!). The image on the left is a page from CACM 8(6) 1965 containing 2 short recipes and 1 small observation, the dominant contents of the magazine around that time. There were also longer articles, like McCarthy’s Lisp paper and others, again describing some piece of design or implementation work that seemed novel and interesting, without much of Mathematical or empirical basis for it.

This was the context in which Dijkstra’s “GO TO Statement Considered Harmful” emerged in 1968 and, in this light, it’s clear that his letter to the editor was not an outlier. The computing community was taking the first steps into unknown territory: programs and programming. Never in Human History had these artifacts existed in such scale, and the art of creating them was a whole new endeavor of human intellect! For a long time, it was completely unclear how to argue for or against ideas in this new territory and, to some extent, the methods are still murky today. In the beginning, arguing for or against didn’t even seem to be an issue; the main concern was feasibility — “here’s how we did it” — and that was extremely valuable, because the community was still learning the basics. Opinions also abounded, and taking opinions for fact seemed to be modus operandi. Dijkstra happened to be an extreme case of an opinionated person; his many writings are a testament to the strong beliefs that he was not shy to express, and very amusing too!

Publications in Computer Science grew exponentially since 1960. Starting in the 1970s, special interest groups started to form within the ACM around topic areas, each one with its annual conference. A similar thing happened in other professional societies, such as IFIP. Unlike the conferences in other fields, these conferences featured full-length, highly technical papers selected by committees of peers. The practice of technical publication featuring novel ideas without Mathematical or empirical basis continued throughout the 1970s and way into the 1980s.

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; with so many ideas being thrown around, with so many words being used for similar concepts, and with so many commercial interests at stake, how could we separate the wheat from the chaff? Another reason, I think, was the realization by many that our field had the word “science” in it, but that very few — with the exception of the Mathematically-inclined — were actually doing it, so people scrambled to converge to methods accepted in other scientific communities that could be used in CS.

And so we came to the current state of affairs. Unevenly but steadily, “idea papers” and “opinion papers” have been essentially banned from CS research. Feasibility is usually not considered enough for arguing for the ideas, the work needs to present validation of those ideas — that being via performance numbers, Mathematical proofs, statistics on collections of data, or people-facing empirical methods. Granted, this is uneven; there are still a lot of good old strong opinions and tastes floating around! — e.g. types in PLs.

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.

This entry was posted in academia, research. Bookmark the permalink.

5 Responses to The Evolution of CS Papers

  1. Dirk Riehle says:

    Crista, excellent blog post! I don’t particularly care about the GOTO paper, but the observation of how the need for validation has changed papers, careers, and education. Peer review itself is fine (but has its own critiques). The strong empirical focus these days is important but also limited. We need more rigor, in particular when compared with the old papers, but this has come with increasing exclusion of other forms of equally valid research, in particular more qualitative research.

    I split research into two parts, steps if you will, theory generation and theory validation. Top journals and conferences are clearly focusing overly on theory validation, leaving little room for theory generation, which is valuable research in itself.

    One reason for this is that education of researchers has not kept pace. Many colleges still teach research as it was done 30 years ago. Those that have kept pace with the validation part of research employ appropriate methods statistical analysis and mathematical modeling but frequently that’s where it stops. I rarely see well done experiments or surveys, as two examples of other confirmatory research methods. On the qualitative research side it looks even worse. If you find a software engineering research paper with a proper qualitative data analysis like interview analysis, it was probably done by an information systems researcher!

    Software engineering is increasingly borrowing from the social sciences and their research methods and that is creating quite a strain.

    • Marc LeMarc says:

      Dear Dirk Diggler,

      The problem with purely quantitative statistical methods is that they are often very, very disconnected from the real world. They’re applied to models that are simplified to the point of being inapplicable in practice.

      Software engineering is all about practice. Theory by itself is useless unless something can be done with it. So some flexibility is needed. It makes perfect sense to trade away some ultra-rigid modeling approaches that only serve to generate data that are without practical application.

      Software engineering isn’t, of course, computer science. While a computer scientist may be just fine writing highly theoretical papers of no or limited practical purpose, with the sole purpose of padding his or her resume, those within the field of software engineering need to show real results. Researchers in the field of software engineering need to create papers and knowledge that can actually be used by practitioners, and not just written down and filed away in the annals of some journal.

      Until mathematicians develop suitably rigorous methods that can resolve your worries while still allowing for the practical concerns of the software engineering community, I think we’ll just need to accept that flexibility and practicality will trump statistical rigidity.

      Your honorable friend,
      Marc LeMarc

  2. Mircea Lungu says:

    Great historical perspective Crista!

    Another great classic is Lamport with his short papers that were so influential (e.g. Time, Clocks, and the Ordering of Events…) and with his sense of humour and storytelling (e.g. The Part Time Parliament).

    They could have fun and write short influential papers because there was much that wasn’t discovered… it gets harder nowadays to discover new stuff and be influential, unless we focus on things that they could not have done.

  3. Great post! Those idea papers are mostly still being written (maybe not in conference paper form), they are just skipping academia these days. Just look at the output of Bret Victor, who I think tried CS grad school once, and how it is dominating the programming environment design (and design) field. Beyond that, there also many idea-oriented blog posts crowd-filtered by hackernews, reddit, and others daily, which embody the “interest to readership” aspect in a much more efficient way than conferences with academic peer review ever could.

  4. Paul McJones says:

    Dear Crista,

    Today I came across your post “The Evolution of CS Papers” via a link in Lambda The Ultimate. I want to thank you for a stimulating view of how CS research and its literature has evolved over the last 50 or so years. Also I’d like to make a few comments regarding some specifics of your post — they are not intended to change your overall conclusions, but to provide a little more historical context.

    First, regarding Dijkstra’s “Go To Statement Considered Harmful” paper, I would argue that it was somewhat of an anomaly: Dijkstra by that time had developed such a reputation as a brilliant computer scientist that he was not subjected to the normal “checks and balances” of the reviewing process as it existed at that time, and, rightly or wrongly, he chose to ignore many of the norms, such as providing references for previous work, backing up hypotheses with evidence, etc.

    Second, regarding his earlier paper on “Recursive Programming”, I would like to provide a little historical context. This paper was written to describe the techniques that Dijkstra and his colleague Zonneveld used in the construction of their Algol 60 compiler, which was the first compiler to implement Algol 60 in its entirety. Algol 60 included not only recursive procedures, but also “call by name” as well as nested declarations of procedures. Although Algol 60 was one of the earliest programming languages, it incorporated the “static binding” whose importance took another decade or two to be generally understood. (For example, it wasn’t until the Scheme dialect in the mid 1970s that static binding was incorporated into Lisp.) So I think Dijkstra deserved to be proud of his accomplishment in 1960, and there really was very little prior literature for him to cite, but admittedly he never was particularly scholarly about including such citations in his publications.

    Third, regarding the Algorithms section of CACM: there was perhaps more to this section of the journal than would be obvious on a first reading:

    (1) First, the “pseudo-code” that algorithms such as Hoare’s Quicksort were written in was actually Algol 60, which was the international standard “algorithmic language” designed specifically to “describe computational processes”. And it’s worth noting that authors of this language included four people (John Backus, Peter Naur, John McCarthy, and Alan Perlis) who would later win Turing Awards (as would “chief implementor” Dijkstra). So, while programming did not have the long history of mathematics in building up standard terminology and notation, the academic community definitely considered that this was an important issue.

    (2) The initial publication of an algorithm was often followed by subsequent publications by others providing “certifications” describing issues involved in getting them to run on various computers, issues with accuracy and performance, translations to other languages, etc.

    (3) Sometimes the original author of an algorithm would publish additional information as a paper in CACM or another journal. For example, Hoare wrote a little-known but superb paper about Quicksort in The Computer Journal in 1962. This paper gives a careful analysis of its performance, together with a thorough section on implementation subtleties.

    As a final thought, you note your fascination resulting from the time you spent studying the old computer science literature. I definitely concur with you on this. I hope someday our field takes the time to gather together the best work of the founders, as has been the tradition for centuries in fields like mathematics and physics. In addition to the literature, I hope we also preserve historic source code, since it is ultimately the “proof of the pudding”. With that in mind, I have spent some time over the last decade or so putting together some archives of historical software (source code, documentation, standards, etc.), in collaboration with the Computer History Museum in Mountain View, California. To give one example of relevance to this message, you might be interested in:

    History of ALGOL

Comments are closed.