Writing Assembler using Standard ML Functors

Here is an example of something important which is seldom mentioned in Functional Programming circles. One can use Standard ML functors to produce type-checked, efficient assembler code. For example, here is a functor implementing assembler primitives for CAML byte-code machines. The same functor implements code for three different ABI representations of "machine words," which are instances of the Standard ML basis signature Word. The Functor AbstractMachineWord effectively composes the assembler code from JIT instruction-generating routines which are in turn composed by other functors. In this instance, for example, the parameter WordEnc (which is another structure with a defined interface like this one) is something like  that produced by the functor VectorSliceWordEnc.sml which uses other assembler code composed by the code-generating primitives defined in PrimEnc.sml which, you might be pleased to hear, is a first-class structure, also with a defined interface. This structure is fixed in terms of the primitives implemented by the 'foreign function interface' binding to the GNU lightning JIT code-generating library. , and it implements only the  CAML ABI. But VectorSliceWordEnc.sml is just one of the possible representations of machine words in memory, and another is ArraySliceWordEnc.sml. And this uses the same primitives, but results in a different set of assembler functions.

There are also other possible representations of the ABI calling conventions, so we could use the same AbstractMachineWord functor to generate primitives for GNU guile, Python, or Ocaml, just by writing a different version of PrimEnc.sml. Provided this conforms to the interface signature defined in PrimEnc.sig, it will work.

The remarkable thing about these functors is their reliability. It is actually easier to write assembler this way than it is to write it ad-hoc. You don't have to take my word for it, you can try it yourself. The whole repository is available for download and/or forking.

Hindley-Milner Type Inference

A few years ago I lost access to my web site and the Proof-toys people very kindly offered to host this description of Hindley-Milner type inference, including the brilliantly written 1982 paper by Damas and Milner, Principal Type Schemes for Functional Programs, describing the soundness and completeness proofs. There is also a file of the purely functional (but nevertheless buggy! See below.) Standard ML implementation. I am posting this here just to increase the number of links to it.

There are a couple of errors. One is a serious misapprehension I was under. Despite having implemented the algorithm in (apparently working) code, I still thought that resolution happened under universal quantification. That is not so. All quantifiers are stripped before resolving the type-schemes. The mistake is in the last-but-two paragraph on page 12 where I state:

If the assumptions include a type-scheme for x, then the result is simply the generic instantiation of the type-scheme to new variables. Otherwise the algorithm fails.

The other error is in the implementation of capture-avoiding substitution in the function tssubs: it fails when there are free variables in the assumptions Gamma, because an over-enthusiastic optimisation means it doesn't rename below a binder of the variable being alpha-converted. Capture-avoiding substitution is a simple idea, but a bit tricky to implement efficiently, and you probably shouldn't try to implement it in just 22 lines of code!

Thanks for BZIP2

Here's a mail I just sent to the author of the Bzip2 tools.

"If you can be bothered, please email me to say you've got a copy. It's nice to know where this stuff gets to."

Everywhere, I think is the answer, except the default OpenBSD distribution ... which is why I'm fetching source.

Thanks for making bzip2. I have always appreciated it. I used to take tea with David Wheeler every day at Cambridge. I spent a decade at the Computer Laboratory, for some sins I must have committed in a past life, ... but tea with David Wheeler never seemed like punishment. He didn't have a lot to say, but what he did say was always pretty interesting.

He used to use bzip2 as his spam filter. Did you know that? He used it to measure the information content of his incoming messages M as the change in entropy between his "verified as spam" archive S and S+M. The change in entropy was just the difference in the size of the bzip2 compressed files. I was a sys-admin and had to help him once with some technical fiddling to get the mail message processing done automatically.

He used to think about physics in terms of information and entropy too. He had a Machian perspective. He told me once that a better physical theory was one which explained the data more concisely. In a sense he viewed physical theories as programs which reproduced the observed data from a compressed expression of the mechanical cause, i.e. the program. This was essentially Mach's view. I didn't ask David whether he took Mach to Mach's extreme of saying that there was no truth independent of our ability to concisely describe phenomena.

So there, I hope this amuses you, and I hope you feel good about all that effort you put into making bzip2 a supremely reliable workhorse of the Free Software revolution.

And do you know David carried on working right to the end. Despite failing eyesight and heart. He died in the bicycle shed seconds after arriving by bike for work at 8am on a cold winter's day.

Best wishes,
Ian

On Feminist Genealogy

The tradition of women adopting the surname of their husband is a strange one. In Spanish cultures the custom is far more symmetric. I don't exactly know what it is, but it is roughly that a girl takes the surnames of both her father and mother, and takes that of the mother first. And the boys take both too, but the other way around. So for example, El Che was named Ernesto Rafael Guevara de la Serna, Guevara was his father's surname, and de la Serna was from his mother. But it is recorded that his father's mother's name was Lynch. This is because Lynch, was an Irish grandmother of his. But her surname would have been passed down to all her female descendents, which means that in Spanish speaking countries women have the same 'genealogical continuity' as men.

The tradition of women adopting their husband's married name is a pernicious one. It basically means that in these cultures it is practically impossible for a woman to know her ancestry! Humanity is not a tree, going back to Adam and Eve, it is really one whole river, and within it we can trace two streams. There is a feminine stream and a masculine one. And the feminine stream is the more fundamental one. As I've said before, men and women are different: the mechanics of human Biology are such that women are all practically the same living organism, which exists in many different places at any one time. Men are different, they don't have this physical continuity from father to son because there is a fourteen-year discontinuity between the sperm which fertilises the ovum in the mother and the sperm which will fertilise the ovum in the mother of that woman's grand-daughter. Men are like the flowers on a tree, they serve just to equilibrate the genetic stream. So men are like a distributed data storage facility. They each store up a bit of genetic flexibility and can transmit it from one part of the whole Global Plant to another part.

The male genome has a tiny amount of information compared to the mitochondrial genome of the female. The mitochondrial genome is much more stable. It is through mitochondrial DNA that we can trace migration of human populations over centuries, such as those Jews who became black and wound up living in Masvingo and keeping the ark of the covenant in Zimbabwe!

And the male genetic heritage is often doubtful. Men cannot easily know who are their children, but no woman is likely to give birth without knowing about it! If you want to do a little interesting research project, then look up the life of Frederick, Lord North, and George III, and look up Thackeray's Lectures on the Georges which Dodgson mentions in his "Life and Letters," and read about Sir Isaac Brock, and George IIIs support of Charles Stuart in exile in France.

I personally think the probability that George III was really the son of Frederick Prince of Wales is far less than fifty percent. And so I think that the probability that the English Royal Family are in fact bona fide is far less than fifty percent. That doesn't mean I think they shouldn't be the Royal Family, but I wish people had the courage to discuss this openly. You won't find anyone asking this question on any public forum. Goodness knows why though, because if you actually read around any bit of history a bit you find a lot more questions than you find answers. And note how beautifully polished and well-researched is the Wikipedia page on George III. It couldn't have been done better by an equerry to the Prince of Wales!

Now back to the main point of this e-mail: this uncertainty of the male genetic line, coupled with the fact that in English tradition (or is it wider than that?) the more evident feminine genetic stream is rendered practically untraceable in historical records, means that in reality none of us really knows our true cultural heritage. For example, we imagine we know that the Grants mostly originated from Scotland. But we don't really know that. All we know is that the male line can be traced back to Scotland. What do we know about the mothers of all those men though? Absolutely nothing, they aren't 'real Grants'. Some of them could have been Greek, or Finnish, and some very probably were. That all these different women from different parts of the world all happened to marry male descendents of one old man Grant who lived in Scotland is just a long series of accidents. Or could it be the other way around?

If you want to test this, then try to find the statistics. Who in the English speaking world, has a greater interest in Genealogy, men or women? Do a survey amongst your friends. How many women can trace their feminine ancestry? I recall trying to find out about the Clarkson family. I was interested to know if there was any connection with the anti-slavery campaigner who has lent his name to Clarkson Rd in Cambridge, which is the address of the Cambridge Centre for Mathematical Sciences. I found it almost impossible to make connections amongst the publicly available data. Because I was trying to connect the surname of a male stream with the practically non-existent female stream. I realised later that the coincidence of the surnames is totally irrelevant. "Clarkson," being an English surname, is an essentially masculine phenomenon: it is solely the male genetic line, and has nothing whatsoever to do with the women. I am told the Church of Mormon has one of the biggest genealogical databases in the world. I don't suppose that it is run entirely by Mormon women, but go on, someone surprise me!

Now, by using the Internet, we could reconnect this one river. But it will only work if we all share all our family heritage data. And I mean everyone in the world. This is why no-one should use these proprietary genealogy databases. There is technically no necessity for that: we just need a well designed meta-data catalogue describing the different concrete representations of genealogical data. The basis for this is all laid out in the single most impressive example of systems engineering I have ever come across, which is the OSI's standard called ASN.1 which stands for Abstract Syntax Notation. This is just one example of one application of ASN.1, but there are many, many others covering all types of communication and computation. And the work I have been doing recently is towards a generic system for editing abstract syntax notation.

This cannot be done by any one private company for profit, because it is something that will never be profitable for any particular organization: it will only be profitable for the whole of humanity. That is the unfortunate situational logic we constantly have to fight against: what is good for the whole Earth is never going to be financially profitable for any particular person or group of people. So while capitalism is the fundamental basis of the Global Economy, the future of the Earth, and the whole of humanity, is more than a little doubtful.

Of course, if everyone in the world did share their genealogical data then we would all know with near certainty, who really was the father of George III, and no doubt there would be some other potentially embarrassing paternity conclusions. So I don't think it is entirely an accident that the word Genealogical has ancient Greek roots of Genus and a-logical, which is a privative alpha: it means illogical or incomprehensible, or without reason.

Google, Going, Gone to Pot?

Well, I heard that in the USA it is a domestic industry worth almost as much as Microsoft. Pot, I mean. All that money must be coming from somewhere, ... ad clicks, or the CIA, funding projects to discourage Americans from thinking about anything at all.

I wanted to upload my Red October patch for Moscow ML, but Google project hosting has moved the downloads function to Google Drive, and the latter doesn't work for me. I suppose because my ancient FireFox has bit-rotted. The more fancy Google's web user interfaces get, the less well they work. I suppose I am expected to get a Windows licence and download Google Chrome to read e-mail.

But how hard is it to implement an HTTP file-upload page, ... I am sure I did it, about ten times, ... It's half an hour's work, at the most. But that wouldn't work for the cloud, ...

Maybe it's because they are pissed-off at my insinuating that they, together with Microsoft, Skype and FaceBook are wide-open to the biggest class-action lawsuit in legal history, for abusing public resources.  What keywords do I need to put in here to get a greedy lawyer interested? Is "greedy lawyer" and "biggest class-action lawsuit in legal history" appearing twice enough? Where are the ambulance-chasers when you need one ...

What is a user interface supposed to do?

Let us assume, initially at least, that the only thing a computer can do properly is deconstruct one recursive data structure (including any iterative data structures such as lists and arrays,) whilst constructing another.  What is the user interface of a general purpose computer going to look like, then?

As we use the machine, we necessarily interact with it, which means that we adjust the machine state according to our intentions. We are typically choosing from lists of available options in the given input state: in other words, through our conscious intentions, we are choosing or determining the actual state transitions from amongst the possible state transitions. So the user interface must allow us to know what is the machine state, and to alter it according to our wishes. The machine state has three parts: the structure being deconstructed, which is the input; the program that is doing the deconstruction; which is the control, and the structure it is constructing in the process, which is the output. Therefore the requirements of a user interface are that we need to see, or at least be aware of, what are the possible state transitions at any given instant. Then we need to be able to choose a new state from amongst those possible, and we then need to see, or at least to be aware of, the subsequent actual state, because this will be the start of the next interaction with the machine. This is the principle of a feedback loop, and it is fundamental to any cybernetic system.

Of course it is not only the user who is interacting with the machine; the environment does too, through various connections such as internal thermal sensors, when the ambient temperature changes; rapid changes in air pressure interact with it via a microphone; and visible electromagnetic radiation interacts with it via a camera. Other machines interact with it too.  For example, a phone interacts with it via a short-range radio connection such as WiFi or BlueTooth, another computer interacts with it via a network connection, and a satellite interacts with it via a GPS radio receiver connected to a USB interface. These interactions are all composed of synchronous events, so-called because they are represented simultaneously on both sides of the interface. There are also asynchronous events, when the machine state changes spontaneously, marking the passage of internal time according to some cyclical frequency standard: in these cases, the new actual state is one from which a transition to the subsequent state in the cycle is possible. Asynchronous events are are not interactions, they are just actions. There are other types of asynchronous event such as the generation of hardware random numbers, which is typically done by counting the number of synchronous events that occur between consecutive events in an asynchronous cycle.

The phase space of a system is the set of all its possible internal states, and the system state at any moment is one single point in that space. Now in order to use a machine, we need to determine what it is supposed to be doing. So we need to be able to interpret the information we have representing the internal state. The act of interpretation of that information is what we call the meaning or significance of the computation or communication. The term significance shares a common root with words like sign, and in an automatic system, it is the significance of the state, combined with our intentions, which determine the subsequent state. This whole process of interpreting information and intentionally determining the subsequent state transitions is called operational semantics.

The amount of information we need to interpret to determine the meaning of a single point in the system phase space is effectively infinite, because that state includes not only the internal state of the machine's memory and storage, but also the state of the environment with which the system interacts. This interaction could be via waste heat and temperature sensors, via network interfaces, via stray electromagnetic emissions and radio transmitters and receivers, via loudspeakers and microphones, or via video displays and cameras, etc., etc.

Therefore, to do useful work with a computer, we need to partition the phase space into finitely many classes, such that any of the system states within any one class have the same significance. But how we choose to make these partitions depends crucially on our intentions: i.e. what we are expecting the system to do. In yet other words, it depends on what the system is supposed to do. One way to make such a partition is to conceptually divide the whole into subsystems. A subsystem is a projection of the phase space of the whole system onto a lower-dimensional space. Then we can choose to make a measurement of the state of a subsystem by determining a point of this lower-dimensional space.  Each single point of the subspace then corresponds to a region (a multi-dimensional volume consisting in many points) of the phase space of the whole system.

Some subsystem divisions are called orthogonal, because they affect a partition of the phase space of the whole system into disjoint equivalence classes, which are independent in the sense that a change of sub-state in one subspace does not effect the sub-state in any other subspace. In such a partitioning of a system, learning about the substate of one part tells you nothing about that of another part. For example, one typically does not expect to be able to learn anything about the keys pressed on the keyboard, from observations of the state of the computer's audio input. In this sense, then, the two subsystems could be said to be orthogonal. But this is an abstraction we make, and it's not always the case, because if there is a microphone connected to the audio input then these two particular subsystems are coupled through the environment, thermally as well as electromagnetically. It is the entanglement of the discrete, finite, internal states of the system with the whole (non-determinable) environmental state that makes the actual phase space of the whole infinite.

This is not a problem, however, because it is only the infinite information in the environment which makes the observable behaviour of computers interesting: we can use them to measure things. And the environment, don't forget, includes the mind of the user of the machine who can influence the state transitions of the system according to what they actually know. So for example, the system state can tell us things that are consequences of our knowledge, but ones of which we were not previously aware. For example, it may formally prove a new mathematical theorem.

In any act of measurement, which includes any computation or communication, we interpret the information input from the environment, and that tells us about temperature, intesity of laser light, stock market prices, news headlines, mathematical theorems and so on and so forth. The act of interpretation is crucial to the whole enterprise, but, presumably because it is so natural and instinctive, it is all too often forgotten by theorists. Quantum physicists seem particularly prone to this omission. It is very rare to see the question of interpretation of physical measurements mentioned in introductory texts on quantum mechanics: almost without exception they seem to take it for granted.  But without this possibilty of interpreting the environmental entanglement of the system state, computers and clocks would be deterministic and, like Turing's a-machines, utterly incapable of telling us anything we didn't already know.

The process of measurement is always a restriction to a finite amount of information representing some part of the whole environmental state of the system. For example, a microphone input measures the differences in air pressure at 48kHz intervals, within some particular range, and interprets them as tiny voltage fluctuations which an ADC measures and interprets as binary values on a 16 bit digital input port register. Note that the finite fidelity of the input information is important: without this, we would not be able to assign any significance to a measurement, because, continuing this example, we wouldn't know whether we were measuring the aging of the microphone diaphragm, the barometric pressure change caused by an incoming weather-front, an audible sound, or an asteroid impact.

Therefore the user interface must allow us to determine the programmed responses of the system to the limited information representing the subsystems we have abstracted from its environment, because it is only by changing these programmed responses that we can determine the subsystems that we are measuring, and by which we attach significance to the information we receive.

For example, in order to receive a written message by e-mail, we typically restrict our attention to a limited part of a screen, in which the strings of character glyphs representing the written words of the message are represented by, say, black pixels on a white background. In determining the significance of the message, we ignore the rest of the screen, and all the rest of environment with which the system state is entangled. So, for example, the intended significance of the message is not typically affected by the sound that happens to be playing through the speaker at the time, nor by the contents of messages subsequently received, but as yet unread. Of course the significance of the message may be affected by these things, but we say not typically to emphasise the importance of the intention of the user in choosing the representation of the channel this way. She could have chosen to have some of her e-mail messages read out aloud by speech synthesis, then the audio output would typically affect the significance of the messages.

Now let us give an extended example of computer use. Imagine Alice is supposed to produce a series of satellite images, overlaid with graphics representing a road network developing over a period of fifteen years or so. In her home directory, she has an ASCII text data file, giving sectors of roads of different types and different construction dates, represented as sequences of points represented as eastings and northings from a certain false origin on a transverse Mercator grid with a datum on the Airey spheroid. The grid coordinates are units of kilometers, given to 3 decimal places. The road types are just numbers 1, 2 and 3, and the dates are numeric, in the form DD/MM/YY. She also has a URL giving access to a USGS database of satellite images via a Java applet which allows her to select the mission, the image sensor, one square of the 30 arc-second mosaic defined in the WGS 84 coordinate system, the year, the month, and the minimum percentage cloud cover. The applet allows her to view thumbnail GIF images, and to request the full resolution images, which are JPEG data embedded in GEOTIFF files, and sent by e-mail within a few hours.

What she needs to do is parse the data file defining the roads, order the sectors of roads by increasing construction date, then find matching satellite images around the same time for the different tiles of the region of interest. Then she needs to find those images with the least cloud cover, request the files from the server, and when the e-mails arrive, extract the data files from the mail message.  She must then tile these images together using a spherical projection, according to the geographical coordinate metadata in the TIFF headers.

Now she needs to find all the sectors of roads that were constructed before the date of the most recent tile in that composite image. Then she needs to convert the grid points of the roads to WGS 84 coordinates using the same spherical projection, to give page coordinates which are used to overlay SVG paths representing the roads, according to a line-style and width determined by road type, and a colour key indicating the approximate age of the sectors. Then she needs to project the UTM grid, draw the border of the WGS84 graticule, and overlay a title and a key showing the construction dates of the roads. And she needs to do this at approximately two year intervals, covering a period of fifteen years. These images will form part of a written presentation containing other text and images, some part of which will be presented on a television programme via a Quantel video graphics system which will broadcast directly from digital representations of the images in a proprietary format, reading them from an ISO-9660 format CD-ROM and inserting them into a video stream according to synchronous cues provided by the presenter pressing a button.

While she's doing this, her phone rings. She turns down the volume of the music to answer the call. Afterwards she sends an e-mail to someone else, after looking up their e-mail address on a web page. Finally she makes a note of a scheduled meeting in her diary. That done, she turns up the volume of the music a little, and carries on with her work.

It turns out, then, that the user interface is primarily concerned with switching information channels from one source to another.  Now by assumption, a channel is some kind of recursive data structure, and a source is a process which deconstructs one such recursive structure, the input, and constructs another, which is the output.  This general form of process is called interpretation.

Now we can't yet answer our original question, but we can say this much:

   A user-interface is a means to create new information channels by plugging sources into existing channels.

So that's what a user interface actually does. It remains to say what it is supposed to do. And the answer is in that word supposed because what it is supposed to do is what we intend it to do. This means that an effective user interface must be intensional: it must allow us to express the operation of the system intensionally. This is because it is only intensional representations which can be effectively interpreted. An intensional representation is one that is essential in so far as it is free of any and all accidents of representation, such as superfluous parentheses, white space, and arbitrary variable names. So the ideal user interface should allow one to express the intended operation of the system using abstract rather than the concrete syntax one typically works with using a text editor.

Let us make this very clear: the notion of using text representation to express semantics is fundamentally wrong. Anyone who doesn't believe this need only take a brief look at the two examples on lists given on page 91 of Girard, Lafont and Taylor's Proofs and Types to see just what kind of a mess one inevitably gets into if one tries to deal with the semantics of concrete syntax, such as operator precedence and associativity. It is not a simple kind of mess! If you like clearing up that sort of problem, then you're welcome, but you will only ever be clearing up one particular instance, and you will never be bored again, because there will always be plenty more such problems for you to solve. The only general solution is to avoid concrete syntax altogether.

This would have the not insignificant side-benefit of avoiding so-called 'religious wars' such as that between some adherents of OCaml and Standard ML. This is a problem only because programmers insist on using linear text representations of program source code. If they switched to using abstract syntax representation then programs in either of the two languages could be translated immediately, one into the other (notwithstanding semantic insanities such as the typing of OCaml's optional arguments, which not even the OCaml compiler can interpret.)

Using abstract syntax would have other advantages too, because editors could easily rename variables, merge change sets, and even translate program keywords into other languages. For example, someone in Pakistan could use Standard ML with Urdu syntax, written right to left, and with meaningful Urdu names for keywords and program variables, and these could be automatically translated, via a dictionary, into Chinese OCaml, written from top to bottom, and with variable names that mean the same things in Chinese. Then someone in China could edit the same source code in Chinese OCaml and send change sets to Pakistan, where they would appear to have been made in the Urdu dialect of Standard ML. This would be an example of religion, which means joining back together.

Our provisional answer has evolved a little:

We need user interfaces to allow us to express the intensional semantics of plugging information sources into channels.

It is the presence of that word intensional that is most crucial. The problem Alice has to solve in the extended example of a user interface we gave above would be trivial if systems were specified using only abstract syntax. But as it is now, well, just try and do what she has to do, and tell us how long it takes you. You can use any languages, libraries and tools you like. And then tell us how long you think it would take you to solve the same problem, with the same data, but after we've changed the concrete representation: i.e. the character sets, the file formats, the transmission medium, the communications protocols, the programming languages and tools, the measurement units and the coordinate systems?  The answer would be "about the same time, or rather longer," I expect. But these two instances are essentially the same problem. If only we had an intensional abstract syntax representation of the algorithms, the application, the programming languages, the file formats and the protocols, we could change any of these things with half a dozen key-strokes. Then either problem could be solved in ten minutes, even allowing for the time she has take out to deal with the phone call and to schedule the subsequent meeting. And once given the solution to one problem, she could solve the other effortlessly in ten seconds, because it would be just a matter of a few trivial identifier substitutions.

The answer to the question "What is a user interface supposed to do?" is:

A user interface is supposed to allow us to compose abstract syntax representations of intensional descriptions of operational semantics of arbitrary languages.

Or, if we put it in less abstract terms:

A user interface is supposed to allow us to compose abstract syntax representations of the semantics of arbitrary languages.

And because it is supposed to do this, and because arbitrary languages are just arbitrary abstract syntax:

A user interface uses abstract syntax to specify abstract syntax representing the semantics of arbitrary abstract syntaxes.

So a user interface allows one to create and edit abstract syntax according to arbitrary grammars. Now if one of those grammars were the grammar of a language for expressing context-free grammars, and if that were itself a context-free grammar, then it could be expressed in its own language, and it would be the only language one would need because all others could be defined in that language.

What is wrong with Unix?

The problem with Unix is that "everything is a text file." Unix systems typically use linear text to represent structured data. This is a mistake, because there are many different linear sequences of characters that represent any particular piece of structured data, so the interpretation of data files is complex and therefore slow.

A parser is a program which takes a linear sequence of lexical tokens, which is a concrete representation, and produces a data structure, which is an abstract representation. Because there are many different concrete representations of any given abstract representation, the parser effectively quotients or partitions the space of possible concrete representations into equivalence classes each identified by the abstract representation of all the equivalent concrete representations in that class.

The problem is noise: a parser converting a text file into abstract syntax is in fact doing the same thing as an error correcting decoder on a communications channel. We can think of the parser as a decoder, receiving a message on the input, and interpreting it to produce an abstract representation of the semantics of the message. Just as in the case of a hamming code, in which there are many redundant forms of transmission which lead to the same message, the parser translates each of the many different possible concrete representations of the abstract syntax into the same message.

The translation process involves thermodynamic work, because the parser must reduce the information in the machine state: there is always more information in the input textual representation of the source code than there is in the output abstract syntax representation, so the system, in parsing the input, reduces the information of the machine's state, and therefore it must produce entropy in the machine's environment. And any mechanical process which produces entropy is a process which takes time and consumes energy.

In the C programming language, for example, the term 'white space' denotes any sequence consisting entirely of space, tab or newline characters. As far as the parser of the C compiler is concerned, all sequences of white space are equivalent. Therefore white space makes the character sequence representation of programs redundant: we can replace any white space sequence of a program file with a different white space sequence, without changing the abstract syntax that program represents. Another source of redundancy in C language source code are the operator precedence and associativity rules which mean that in certain circumstances parentheses may be redundant. So for example any program text contained by well-balanced parentheses can be replaced by the same text with one extra pair of parentheses. The following four files all define the same abstract syntax:

#include <stdio.h>
void main(int argc, char **argv)
 {
   printf ("Hello, World.\n");
 }

#include <stdio.h>
void main(int argc,
          char **argv)
   {printf ("Hello, World.\n");}

#include <stdio.h>
void main(int argc, char **argv)

{printf (("Hello, World.\n"));}

#include <stdio.h>
#define S "Hello, World.\n"
void main(int argc, char **argv) {
   printf (S);
}

Textual representation seems like a good idea, because it offers a  very simple and elegant solution to the problem of concrete representation, which is in some sense the essence of the problem which the idea of an operating system is an attempt to solve.

For example, a C compiler may represent the number 365 as a sixteen bit binary integer 0000000101101101. On an Intel i386 system, this number would be stored in two consecutive bytes, with the least significant byte first: 01101101 00000001. But on a Motorola 68000 system, the same number would be stored with the most significant byte first: 00000001 01101101. So, if these systems were to exchange the blocks of memory representing the number 365, over a network connection for example, then each would receive the number 28,032 from the other. If instead, numbers were represented as null-terminated ASCII strings then the number 365 would be represented as four consecutive bytes 00110011 00110110 00110101 00000000 on both systems.

Unix systems have a command line editor, ed, which can be used to edit text files. For example, the following shows the creation of a text file hello, containing just one line, which is the text Hello, world.:

$ ed
a
Hello, world.
.
w hello
14
q

The first line invokes the editor program ed from the shell command prompt '$'. The editor is invoked with an empty text buffer. The second line is the command 'a' to append lines at the current point. The third line is the line to append, and the fourth line, a single full stop, signals the end of the append operation. The next line 'w hello' writes the buffer to the file hello, and outputs 14, which is the number of characters written. Finally the 'q' command terminates the editor and returns the shell command prompt.

On any Unix system, the C compiler, cc, takes as an argument, the name of a text file representing a C program, and compiles it to machine code, writing the output to another file. For example, the following program parses a list of numbers from the command line adds them, and then prints the result. We can use ed to create a text file add.c containing the lines:

#include <stdio.h>

int stoi (char *s) {
    int r=0;
    char c;
    while (c = *s++) {
       if (c >= '0' && c <= '9') {
          r = r * 10 + (c - '0');
       }
    }
    return r;
}

void main (int argc, char **argv) {
    int r=0;
    while (--argc) {
        r += stoi (*++argv);
    }
    printf ("%d\n", r);
}

We can compile this program by typing the following command at the '$' shell prompt:

$ cc add.c

The resulting executable machine code program in the file add, can then be run from a shell script, which is a text file containing a sequence of shell commands. For example, we could use ed to create the shell script file test.sh containing just one line:

./add 300 65

And the we could run the shell script test.sh from the shell prompt, thus:

$ . ./test.sh
365

Now everything here was done by using text file representations of data and programs and so this sequence of representations will work on any Unix machine, regardless of the convention for storing binary integers in memory, and regardless of the encoding used to represent characters. And this shows the underlying machine representations of the data are arbitrary.

In Unix systems, the kernel, the shell sh, the editor ed, the C compiler, cc, and all the other system commands and applications are each just C programs, represented by some text files. So 'the Unix philosophy' of representing all data as text files and using system programming languages which interpret these text files, achieves independence from the underlying machine representation of data in memory. That is how Ken Thompson and Dennis Ritchie, the designers of Unix, abstracted the operating system from the particular accidents of the physical hardware, and it is a clever idea.

But as Thompson himself points out in his famous ACM Turing Award lecture "Reflections on Trusting Trust," this very fact means that the correspondence between the textual representation of a program's source code, and the actual operations carried out by the Unix system as it executes that program, is entirely arbitrary. In other words, the actions performed by the machine are completely independent of the concrete syntactic representation of the system. In yet other words, in case you still don't get it: the sequences of characters one sees in the source code text files are in fact utterly meaningless, and Unix is therefore, in principle, an insecure Operating System. And this was presumably the substance of the United States Air Force report on the security of an early implementation of the Multics operating system, to which Thompson attributes this idea.

As Thompson says in the lecture, the problem is a profound one, and it stems from the fact that the source code of any particular Unix system has a unique abstract syntax representation. It is essentially the uniqueness of the abstract syntax that enables the parser of the C compiler to identify the source of any system command, and thereby choose an arbirtary abstract syntax representation, which could be of any operation whatsoever: Trojan semantics.

The solution turns the problem up-side-down: if we use an abstract syntax representation of the program source, we don't need the parser, and therefore there is no opportunity for the parser to choose an arbitrary operational semantics for the source code. Then the process of compilation need not involve thermodynamic work: in converting the abstract syntax into machine code, there is not neccesarily any reduction in information, because it is possible that the particular abstract syntax representation is the smallest information (i.e. the shortest message) which could produce the intended operational semantics. So the system source code is not the source code of any particular implementation, it is the source code of the general implementation.

Why is this turning the problem up-side-down? It is because by doing this, we can choose an arbitrary abstract syntax representation for any given operational semantics. So the tables are turned: the bad guys can no longer choose an arbitrary operational semantics for a given abstract syntax representation, because the good guys can choose an arbitrary abstract syntax representation of a given operational semantics. Rather than reflecting on trusting trust, we are reflecting on reflecting on trusting trust, which is the same as simply trusting trust.

But how can this be done in practice? We can use metaprogramming. As Thompson points out, the problem with Unix is that you cannot trust any program that you did not write yourself. But using metaprogramming, we don't write the programs we use, we write programs that write the programs we use. So all we need to do is to make sure that we wrote the top level program. But the top-level program is just the program which interprets an arbitrary abstract syntax representation according an arbitrary abstract representation of the semantics. Then when that abstract syntax represents arbitrary abstract syntax, and that semantics is also arbitrary abstract semantics, this top-level program will produce itself, or a program which, when fed the same abstract syntax and semantics, will produce itself. This will then be the greatest fixed point and we will know the system is sound and complete.

Having produced one such system in some specific target language, sheme, say, it would be easier to define a system for another language, such as Standard ML, because we could use the first system to compile the second. We could then construct the greatest fixedpoint again, by crossing over the abstract syntax compilation steps, so that each system compiled the input of the other. We would then have a pair of fixed points which we knew were as reliable as each other.

We could then add semantics for another language, JavaScript, say, and construct a third fixedpoint, which would be each of the three systems crossed with each of the other two. Even though the encodings of the same abstract syntax in the three cases may be entirely different, these three systems could share abstract syntax representations, and we could be certain that all three representations, though different as representations, would have identical operational semantics.

The crucial step is the use of abstract syntax using an arbitrary encoding. Because of this, there is no possibility whatsoever of a Trojan recognising which program is being compiled, so there is no possibility of it reproducing itself in the encoded representation.

This is the foundation from which one could proceed to define abstract types representing the full set of instructions for each and every processor, and the associated encoding specifications which would encode those instructions with the given arguments. From this abstract specification, one could produce tools such as Intel's XED, automatically, for all processors, and in any language. And using that, one could specify an assembler. The next stage would be to specify a code generator for a generic bytecode language, and from there one could formally specify other languages such as C.

The purpose of this higher level development is not to generate a better C compiler: it is unlikely that a C compiler specified this way would be as good as, say, GCC. The purpose of adding metaprogrammed higher-level languages would be to enable more fixedpoints to be established. If the encoding representations can be produced in C, then the C compiler would be included in the fixedpoint, and the foundation for generating GCC binaries that would be certain not to have any Trojan semantics. This would then extend to the entire GCC toolchain, and any operating systems built with GNU tools.

The aim, however, is not to secure operating systems: that is only a temporary measure. The aim is to metaprogram all applications and algorithms, so that we don't need any operating systems at all; just the one global commons, the Mother of all programs: the Foundation.