Friday, November 28, 2014

Babbage's Language of Thought

This is a guest post by Adrian Johnstone, Professor of Computing at Royal Holloway, University of London.

Babbage has been called the 'great-uncle' of modern computing, a claim that rests simultaneously on his demonstrable understanding of most of the architectural principles underlying the modern computer, and the almost universal ignorance of Babbage's work before 1970.

There has been an explosion of interest both in Babbage's devices and the impact they might have had in some parallel history, as well as in Babbage himself as a man of great originality who had essentially no influence at all on subsequent technological development.

In all this, one fundamental question has been largely ignored: how is it that one individual working alone could have synthesised a workable computer design over quite a short period, designing an object whose complexity of behaviour so far exceeded that of contemporary machines that it would not be matched for over one hundred years?

I believe that the answer lies in the techniques Babbage developed to reason about complex systems. The Leverhulme Trust have recently made a major award to myself and my collaborator Prof Elizabeth Scott which we will use to document, formalise and implement simulators for Babbage's Notation. The team also includes Plan 28’s Dr Doron Swade, who is the foremost authority on Babbage, and Dr Piers Plummer who has an extensive background in chip design, computer architecture, mechanical CAD and programming language compiler design. The work will be based in Royal Holloway's Centre for Software Language Engineering.

Flow diagram using Babbage's Notation of the output apparatus (printer) of the Analytical Engine and Difference Engine No.2
The notation, or more correctly Babbage's parallel notations showing the geometry, the timing, the causal chains and the abstract components of his machines, have a direct parallel in the Hardware Description Languages developed to aid the design of modern large scale integrated circuits. These languages typically have a geometry facet in which the arrangement of components in space is specified; a register transfer facet which emphasises the interconnection of functional units via registers and memory buses; and a behavioural facet which describes sequences as state machines or in software-like notations. In modern digital electronics, these techniques are now ubiquitous although they met with some resistance when first introduced.

Output apparatus of the Difference Engine No. 2 and Analytical Engine
There is a 150 year delay between Babbage's first attempts at an engineering notation and the application of hardware description languages to electronic computer design yet Babbage's notations also include a geometry facet (corresponding to the fabrication drawings used to specify the individual parts and their position in space), an enumeration of functional parts, a functional transfer facet in which large flow diagrams show the cause-and-effect relationships between those parts, and most strikingly of all a behavioural facet in which the timing relationships and state machine transitions are directly displayed. For those with a background in modern digital hardware design techniques, the similarities are striking.

The artefacts that Babbage designed are wondrous, but the system of thought he developed in which those artefacts' complex state spaces could be designed and checked before any metal was cut is a much more significant achievement. Every modern engineer knows the value of speculative design backed up by simulation and prototyping. The integrated circuit industry led the way with design notations simply because the cost of prototyping, and the financial loss for an erroneous design, was economically unsustainable. By the same token, Babbage was forced to develop paper methods to exercise his designs because the cost of implementation, and the length of time needed to manufacture his designs rendered physical prototyping and experimentation largely infeasible.
Babbage himself was very aware of the relative importance of the objects and the meta-object; the design and the design discipline: he wrote
By the aid of the Mechanical Notation, the Analytical Engine became a reality: for it became susceptible of demonstration
and he believed that the notation would become the standard design method taught in the engineering schools. In that he was quite wrong. Nearly all mechanical systems, from steam engines to internal combustion engines, pumps and jet engines are sufficiently simple that their state space may be deduced by inspection of the engineering drawings which show their geometry. This is because they do not have memory: an engine rotates, and each rotation is as the last. Understanding one cycle is sufficient to understand all cycles. It is only the introduction of memory that generates complex time-dependent behaviour, and that is exactly the point at which the geometry diagrams become inadequate to the task of capturing the function of the machine.

We all know that the workings of a computer programme will not easily be gleaned from an examination of its transistors and their interconnections: that is the wrong level of abstraction. Babbage was the first individual to work with systems where the function transcends the components, and our Notions and Notations project aims to elucidate, formalise and test the techniques he developed.

We are going to do this by treating his system of notations as a formal language, adopting techniques from software language engineering. The team will develop abstract simulators which make specification written in the notation executable (and as a byproduct generate graphical visualisations of the system described by a specification) and use these simulations to verify our understanding against Babbages's descriptions and actual artefacts.

In this we are greatly aided by the existence of a complete draft and finished notations for Difference Engine 2, along with instances of the physical machine built by the Science Museum in London which were built according only to the drawings, but largely without reference to the notations.
Our goals then, are to research the development of the notations over time; to formalise the notation in a way that can be parsed and processed by modern computers; to implement a simulator for the notation; to test the simulator by reference to Difference Engine 2 and to provide simulations that will help understand the operation of the Analytical Engine.