I remember Donald Michie (1923 – 2007)

On July 7, 2007 Dame Anne McLaren and Donald Michie died in a car accident. Last time I had met Anne was in the 1970s when I had stayed at their house in Edinburgh. Both were launched on scientific careers that were to lead them to positions rivalling each others’ eminence in their respective fields.

The last time I met Donald (henceforth “DM”) was when my wife and I visited him in Oxford in November 2004. He demo’ed the SOPHIE chatbot system, asking us what we thought of his choice of accent for the speech-generating software. He was intrigued by the way his current choice, labeled “Southern California Trash”, blended with the other personality attributes of Sophie. The stereo was playing DM’s current favourite, “Harper Valley PTA” sung by Jeannie C. Riley, another sassy American female.

Although excited by his current project, DM was depressed by the gloomy British weather; he would depart shortly to spend the winter in Gibraltar. “Gibraltar??”. “Yes, Gibraltar. I trust it will be sunny, and it is British.” In the following pages I have noted, roughly in chronological order, some experiences with this extraordinary man, one of the great pioneers in Artificial Intelligence.

Against Structured Programming

In 1968 the Communications of the ACM published a Letter to the Editor from E.W. Dijkstra (volume 11 (1968), pp 147–148). The Editor, perhaps a bit puzzled by the contents, summarized them by supplying as title “Goto Statement Considered Harmful”. The mere thought was sufficiently provocative to ensure that the idea spread like wildfire, initially to be dismissed, but soon to be blessed with universal approval. “Structured Programming” was born.

The most enthusiastic converts were the computer science professors. These people were doing research on esoteric topics like formal languages or graph theory and were gang-pressed into teaching introductory programming. With little programming experience, they welcomed a clear rule (no GOTOs!) and welcomed the casuistry required for forcing non-conforming code into the straight jacket of the officially approved formats.

This essay is a thought experiment: suppose one had never heard of Structured Programming, that one wanted to solve a little programming problem by common sense reasoning; that this solution process not only had to supply the conviction of correctness, but also had to help discover the algorithm. My conclusion will be that these goals, though ambitious, are achievable, but that Structured Programming is at best a handicap.

Remember Software Verification?

Maybe not. It used to be taken for granted that in the more or less remote future it would no longer be necessary to debug software because it had been verified.

That time is long past. What we now take for granted is that, for example, the two pieces of software essential to the health and safety of the internet, MS Windows and MS Internet Explorer, “vulnerabilities” are discovered at such a rate that the repair sessions are saved up to the second Tuesday of each month. Rarely does such a Tuesday pass without an update; sometimes five or six. Another exhibit for the prosecution: many pieces of software that invite being downloaded distinguish between the “latest version” and the “latest stable version”. Forget correctness: “stability” is the goal. Diminished expectations …

Ventilated Prose

In the 1930s Buckminster Fuller (he of the domes, but also of many other things) was doing research for the Phelps Dodge Corporation. His boss could not read Fuller’s reports, but found them perfectly intelligible when read aloud by the author. Fuller thought he remedied the problem by breaking up the text in the same way he read it aloud. Though this made the written text readable, it was not acceptable: it looked like … eh, well, poetry, and the Phelps Dodge Corporation was not into poetry. As a compromise, Fuller called his text format “ventilated prose”. In this article I show examples of Fuller’s writing and report how I use it to get over “writer’s block” in my own practice.

Rewriting a Utility

I can’t leave well enough alone. The most recent manifestation of this problem is the following program from Kernighan and Ritchie (”The C Programming Language”), which is perfectly OK code for converting a number to the equivalent decimal numeral.

No Silver Bullet? Get a Humble Programmer.

Consider this:

1. Software reliability is rapidly becoming more
   important.
2. Software development technology is inadequate and
   is only slowly improving.

The question arises:

Is disaster inevitable?

This has been debated for some time in the computer
science community. Recently it has begun to attract
attention from the general public.
For example a newspaper ran a story entitled: “A Lemon Law for
Software?” Here the author observed:

If Microsoft were liable for product defects the same
way automobile manufacturers are, then it would have
been driven out of business a long time ago.

As we all know, this has not happened. And this is only
because the law exempts the software industry from
product liability.

The question I’m now asking is: Should it be exempted in
this fashion?

Any suggestion that it is time for the software industry
to grow up and accept responsibility for its products is
greeted by an indignant chorus asserting that software is
special and that not recognizing it as such will stifle
innovation.

Clearly Microsoft stands to lose most in a change from
the status quo. But the rest of industry, including those
who love to hate Microsoft, do not dare to contemplate a
world where creators of software are responsible,
seriously responsible, for their products.

While in industry there is agreement on this topic,
academia, in so far as it has an opinion at all, is
divided. Some argue that software is special in such a
way that the current unreliability of software is
inevitable. They argue that there is no prospect of
drastic improvement. I will call this camp “The Real
World”. Their most eloquent, and most widely quoted,
spokesman is Frederick P. Brooks, Jr., in his paper “No
Silver Bullet”.

Others argue that techniques for producing reliable
software are known, that these are practical, and that
some of them have been known for decades. Whenever one
brings these to the attention of industry, one is
dismissed as being sadly out of touch with reality. Hence
I will denote the proponents of the known techniques for
producing reliable software as “The Ivory Tower”.

In this introduction I have sketched the problem,
which is:

1. Software reliability is rapidly becoming more
   important.
2. Software development technology is inadequate and
   is only slowly improving.

I have also sketched the main points of view, and called
them “The Real World” and “The Ivory Tower”. In this
lecture I will elaborate further on these two opposing
positions, starting with the real-world people, and
continuing with those who inhabit the Ivory Tower.
Although I will avoid technical matters, few such
concepts need a brief review, which I will do next.

Cargo-cult Engineering

There is an old song about software engineering. I thought it had died until the other day I came across a post by Jack Ganssle (Embedded.com; 05/12/08). Under the title “Programmer or Engineer?” he argues that the word “programmer” should be banned and that embedded applications should by built by electrical or computer engineers.

It may well be that engineers are satisfactory for the “embedded applications” that Mr Ganssle has in mind. But another category of people is needed to meet the greater challenges posed by computers. Neither of the existing categories: “engineer” nor “computer scientist” can be relied on to fit the bill.

A Possible Future History of Logic Programming

(from “The ALP Newsletter”, vol. 17, no. 1, Feb. 2004)

While it is well-known that it is hard to know anything about the future, it is less widely realized that it is also difficult to understand the present. It is therefore paradoxical that it sometimes helps to understand the present by means of a fictitious future history. In this essay I am going to exploit this paradox.

I place the viewpoint well away into the future. Again this may seem paradoxical, because in computing everything is supposed to happen fast. Not everybody thinks so. Paul Graham has embarked on a project that he calls “The Hundred Year Language” , pointing out that it is only hardware that changes fast. Programming languages change slowly. This is because they are part of culture; they reflect how human minds tackle problems. Hence Graham’s “Hundred Year Language”.

It so happens that Graham is concerned with Lisp. This is not the only paradigm in need of the long-term perspective. Accordingly, I imagine a history of logic programming as it may be written in the 2020s.

As I’m already exercising your indulgence with speculation, I will not attempt the fictitious future history itself, but instead bring out the salient points in an equally fictitious review of this nonexistent
history.

Digital Gold

The true nature of money has, through the centuries, been an inexhaustible source of puzzlement. This has abated somewhat in the Greenspan era when currency management sort of limped along by being conducted according to business as usual. Post Greenspan, the avalanche of crises triggered by the subprime debacle should have come as a wake-up call that business as usual is a recipe for disaster. But you wouldn’t guess so from The Economist’s Special Report on International Banking (May 17, 2008), which foresees return to “normal” after a “salutary dose of reality”. This underlines what many readers have noticed, namely that The Economist is not what its title suggests, but rather is The Voice of the Industry.

One of the ways in which The Economist affirms its orthodoxy is to state or suggest that only cranks entertain ideas like the gold standard or social credit. The Web is more rewarding in this respect. For example, the Wikipedia article (version of 080530) on the gold standard tells that Alan Greenspan, this pillar of orthodoxy, was once a proponent of its return.

Though the gold standard is a lousy system, it has the advantage of being a fruitful starting point in the search for something better. Business as usual does not have this property. The problem with the gold standard is that the money supply is rigidly equated to the amount of gold that circulates as coins or serves as back-up to paper certificates. In the 16th century, when the gold of the New World was imported into Europe, this gave rise to a large amount of inflation. In the 1930s the US economy required a larger supply of money than was available under the then reigning gold standard, thus aggravating the depression.

These problems suggested a monetary system in which economists determine the money supply needed by the state of the economy and in which governments have various means at their disposal to ensure that the actual money supply closely approximates this ideal. Both economists and governments like this idea: they are flattered by the power it ascribes to them.

This may have worked for a while, but since asset-backed securities, credit derivatives, and hedge funds neither governments, nor anybody else, has any idea what the money supply is. So there we are: equating the money supply to a gold reserve at a fixed price doesn’t work. Alternative ways of controlling the money supply, such as the M1 and M2 of yore don’t work. Isn’t there anything else?

There is a lot one can do nowadays with digital authentication techniques. It is time to investigate whether it is possible to implement digitally a collection of monetary certificates that is the equivalent of the Federal Reserve’s gold supply in the days of the gold standard. These digital techniques have been used for message authentication and digital signatures. It is worth investigating whether they can be used to create a digital one million dollar version of the hundred-dollar bill signed by the Secretary of the Treasury.

Specifications: the Good, the Bad, and the Ugly

One can define a prime number as an integer greater than 1 that has no divisors other than 1 and itself. This is a declarative definition: it says what a prime number is rather than how to get one. One can also appeal to the Sieve of Eratosthenes. This would be a procedural definition. It is the opposite of declarative and it only tells how to get prime numbers.

In Software Engineering it is considered bad form to specify a function by pseudocode or by a reference implementation; a proper specification is supposed to be declarative. This blanket preference for the declarative assumes that such specifications are always better: easier to understand and to write. This is indeed the case with prime numbers, but not always. In the case of the Reef Knot, the Bowline, or any other kind of knot, a declarative definition, though perhaps possible, is likely to be less useful than being shown how to make one, which is procedural. Here I consider an example where it is easy to compare the merits of the Good (declarative), the Bad (procedural), and an even less respectable third approach.