Explosive Knowledge: Cryptology in the 20th Century

March 28, 2017

In August 1960 the Pentagon announced that William Martin and Bernon Mitchell had not returned from vacation and said “there is a likelihood that they have gone behind the Iron Curtain”. On September 6 they appeared at a joint news conference at the House of Journalists in Moscow and announced they had requested asylum and Soviet citizenship. They revealed that they had worked for the National Security Agency (NSA). In this way the mission and activities of the NSA were made public for the first time [1]. Although these activities are much more wide-ranging than cryptology, this post will only be concerned with that small part.

All branches of knowledge had vigorously developed in the first half of the 20th century. All of it had been sustained by what I like to call a conversation: an open exchange of knowledge in books and journals. Before World War I this was also true for cryptology; afterwards, traffic on that channel fell silent. By the end of the 20th century the cryptology conversation was intense, wide-ranging, and immensely productive of innovations, of which bitcoin technology is but one example. In this post I trace the chain of events that led cryptology from its dark age, which lasted from 1918 to 1967, to its renaissance. My material is obtained, unless otherwise noted, from Crypto, a book by Steven Levy, published in 2001 [2].

Read the rest of this entry »

Children of the Miracle: from Algol to Prolog

March 18, 2017

The appearance of Fortran inaugurated a fruitful period in programming languages that was to last until the early 1970s. When, in 1999, E.W. Dijkstra gave the keynote address at the ACM Symposium on Applied Computing in San Antonio, Texas, he gave an overview of what he saw as the large-scale trends in the preceding half century. I quote:

And then the 60s started with an absolute miracle, viz. ALGOL 60. This was a miracle because on the one hand this programming language had been designed by a committee, while on the other hand its qualities were so outstanding that in retrospect it has been characterized as “a major improvement on most of its successors” (C.A.R. Hoare).

Several friends of mine, when asked to suggest a date of birth for Computing Science, came up with January 1960, precisely because it was ALGOL 60 that showed the first ways in which automatic computing could and should and did become a topic of academic concern. [1]).

Algol was a miracle as a language. It was short-lived, but it left a momentous legacy that acted in two ways: in the way the Revised Report on Algol 60 describes the language and in the way subsequent language designers were influenced by being shown what a programming language could be. In celebration of Algol 60 I refer to these designers as “Children of the Miracle”.

Read the rest of this entry »

The Essence of Algol

November 12, 2016

Elsewhere [10] I considered ways in which programming languages could be different. One of these ways is expressed by asking the question Does the language have an essence? The possibility of an affirmative answer is suggested by the title of John Reynolds’s paper: “The essence of Algol” [7]. Reynolds used what he perceived to be the essence of Algol to make distinctions among members of what is usually considered to be a single family. Thus he argues that Algol 60 is a carrier of the essence, whereas this is not the case for other members of that family: Algol W, Euler, Algol 68, and Pascal.

What is judged to be essence is in the eye of the beholder. I am more interested in what the members of the Algol family have in common and perhaps even with languages not usually considered as members. For example, Prolog. Soon after completion of this language in Marseille, Robert Kowalski wrote a paper (published as [6]) that established a procedural interpretation of a form of first-order predicate logic. Let us examine this interpretation to see whether this gives a hint concerning the essence of Algol as a procedural language.

Read the rest of this entry »

Kinds of Programming Languages

October 21, 2016

I find the number of programming languages mind-boggling. For example, Jean Sammet in her “Roster of programming languages for 1976-1977” [12] lists 156 programming languages in 24 categories. This includes only languages in active use within the USA. The opposite extreme on the spectrum of permissiveness is represented by the “Online historical encyclopedia of programming languages” [7], which claims 8945 “programming languages since the 18th century”.

Read the rest of this entry »

Alan Robinson

September 16, 2016

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 »

Wildcat Crypto

May 13, 2016

With his “Pretty Good Privacy” (PGP), Phil Zimmermann launched the era of what I call Wildcat Crypto. Up to that point discussions on cryptology had focussed on whether DES, the US government standard, was secure and whether government involvement in its development might have jeopardized its security. To avoid government involvement, PGP used IDEA as alternative to DES for its bulk encryption. Yet IDEA is a close relative of DES and shares its weakness: small, constant-size blocks. True Wildcat Crypto calls for a radical departure in the form of blocks that are much larger, and moreover, vary in length under control of the key. In this article I trace the relevant history and outline my implementation of such a radical alternative.

Read the rest of this entry »

Some Books on C

March 26, 2016

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 [1]. But the mainstream of teachers of introductory programming has settled on Java as a compromise between friendliness and attractiveness to prospective employers.

Read the rest of this entry »

Why does C not have an exponentiation operator?

March 15, 2016

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. [1], 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.

Read the rest of this entry »

IA or AI?

October 9, 2015

I’ve been reading a paper [1] 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 [2] 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”.

Read the rest of this entry »

Recursion versus iteration

July 30, 2014

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 [1] 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.

Read the rest of this entry »