On August 5, 2016 John Alan Robinson died. In him, a great scientist departed, and I mourn a dear friend. His great discovery was the resolution principle in mathematical logic, a discovery that capped two decades of development. In its turn, it spawned a plethora of new developments in computer programming. It became important enough in Artificial Intelligence to become controversial. Read the rest of this entry »
Since time immemorial cryptography was a common feature of puzzle columns in magazines and newspapers. But up until the 1970s only the military, departments of foreign affairs, and spies with their minders were seriously interested in the technology. This changed when banks and other commercial organizations started using computer networks. They needed industrial-strength cryptography. Not only that, but it needed to be standardized and preferably sanctioned by government. For the bank’s IT chief it was even more important for encryption to be standard than to be secure: if a breach occurred that cost the bank a few million, he wouldn’t lose his job as long as he used the industry-accepted standard. This was the situation that led to the adoption in 1977 by the U.S. National Bureau of Standards of the Data Encryption Standard (DES). Its current successor is the Advanced Encryption Standard (AES), adopted in 2001.
I have gathered such introductory books on the C programming language as I own or could borrow. The result is an eight-storey tower. A quick scan shows that I could easily buy another half dozen, but I doubt whether that would yield any new insights.
For most teachers “an introductory programming book with C” is an oxymoron. The extreme wing in this school of thought consider only designedly friendly languages suitable for an introduction to programming. BASIC is an early example. My current favourite friendly language is Python . But the mainstream of teachers of introductory programming has settled on Java as a compromise between friendliness and attractiveness to prospective employers.
The most authoritative source for an answer to the question in the title would be Dennis Ritchie. Next best is Bjarne Stroustrup:
The semantics of C operators should be simple to the point where each corresponds to a machine instruction on a typical computer. An exponentiation operator doesn’t meet this criterion. , page 247
Stroustrup’s criterion needs to be taken with a grain of salt. For example, the assignment operator does not meet the criterion: a = b takes a LOAD and a STORE. In this case the criterion translates to: “should correspond to no more than a LOAD and a STORE. But Stroustrup was onto something, because we can tweak his answer to:
The semantics of C operators should be simple to the point where they each compile to code that is as fast as what one can write in assembler.
I’ve been reading a paper  written two decades ago, which itself is an account of events two decades before that. It is Alan Kay nominally writing about the history of a programming language called Smalltalk. I say “nominally” because already by Smalltalk 72, Kay was losing interest in language matters and wanted concentrate on what the language, as part of the computer-as-medium, could do for thought. Along with various other sources of inspiration that led to Smalltalk (Sutherland’s Sketchpad, the Burroughs B220, the Burroughs B5000, …) Kay mentions attending in 1968 the conference presentation by Douglas Engelbart  that has since become known as the “Mother of All Demos”.
In 1968, when timesharing by users behind teletype terminals was regarded as avant-garde, Engelbart gave a demo that featured a number of firsts: a screen display for both and text and graphics, interactive text-editing, a mouse. All that was integrated into a fluidly handled medium. Kay gives testimony to the huge impression this made on him: “Engelbart was a prophet of Biblical proportions”.
The first programming language to allow functions to be recursively defined was McCarthy’s LISP in 1959. Its introduction was not controversial: nobody but John McCarthy had any say in what the language was going to be. In addition to his work on LISP, McCarthy was on the committee finalizing the Algol language in 1959 and 1960. In spite of the fact that a majority was opposed to it, the definition of Algol 60 ended up allowing recursively defined procedures. In  I gave an acount of how this happened.
Why was recursion such a big deal? For us this is hard to understand: for decades the programming language C, not exactly a paradigm of avant-garde, has allowed recursion. Still, remnants of unease remain. Still, in some introductory courses, recursion plays the role of a pons asinorum. Have instructors been traumatized by a sarcastic teacher finding, oh horrors, a circular definition in their high-school essay? In this essay I’m going to explore recursion by contrasting it to its opposite, iteration.
How recursion got into programming: a tale of intrigue, betrayal, and advanced programming-language semanticsJune 18, 2014
By now it is difficult to imagine that once there was a time when the utility, and even the possibility, of recursion in programming was in doubt. Yet that was true of the programming community around 1960. Even the committee that was to create Algol 60 was divided on the issue. How recursion got into the language is a story of intrigue and misunderstandings. I came across this story for the first time when reading Gauthier van den Hove’s excellent MSc thesis . It is also the subject of Chapter 3 in .
E.W. Dijkstra is known for several important contributions. It does not seem to be widely known that he played a role in the origin of computer architecture as a concept. In arguing that this is the case I draw attention to the passage in his 1972 Turing lecture where he recounts that the darkest week in his professional life was when he studied the specifications of a newly announced line of computers that he does not further specify than being “of the third generation”.
My first Python sighting was around 1999, in the part of the building where the hackers hang out. Somebody had a poster on the door saying something like If you would have used Python, then you would have been done by now.
Next stop 2005. Since 1986 I had been a fan of “Structure and Interpretation of Computer Programs” by Harold Abelson and Gerald Sussman. At the University of Waterloo it was only in a fourth-year topics course that this book could make a brief appearance. I was envious of MIT, where masses of first-year students took EECS 6.001, where Abelson and Sussman was used from day one. That was class. In 2005 I heard the sad news that, after two glorious decades, EECS 6.001 was closed down, replaced by a course where the text was … a book written for high-school students. Maybe EECS wouldn’t have picked that book if its language would have been BASIC. Perhaps it had to do with the book’s choice of Python. It was from this news item that I learned that Python is a programming language.
When Ludwig Boltzmann (physicist, 1844–1906) was criticized for his ugly brute-force calculations, his defence was: “Elegance should be the concern of shoemakers and tailors”. The criticism was of course not about elegance in the sense of fashion. It was about the fact that an elegant structure would have had the power to convince the reader of whatever the calculations were intended to demonstrate.
I think this episode has something to do with the fact that much of what we do on computers depends on software that, among other weaknesses, is in need of frequent and urgent “security updates”. Those who criticize this state of affairs are dismissed as unrealistic. To be realistic is to understand that any useful piece of software consists of millions of lines of code written by many programmers, mostly no longer traceable and certainly not accountable. No one has a clear view of the system as a whole; there is no description that enables anyone to gain such a view. The realists of today, who accept this state of affairs as inevitable, are of Boltzmann’s brood.