Talmudic codes

My knowledge of Talmud is, to be generous, zilch, but consider the format and style of Talmud. This is what you get when each commentator takes the arguments of colleagues and predecessors seriously. In the center a discussion between one group of experts, commented on and amplified by a second group. On the side a detailed line-by-line commentary and then on the other side a series of comments and explanations. This is the direct opposite of what we find in the computer science literature – where a mass of following footnotes is generally there as a required nod of the head or to provide the illusion of scholarship, but there is very little effort to actually wrestle with the existing body of knowledge. As Spolsky shows (this must be my month to comment on Spolsky) applying such detailed analysis to trivia just elucidates the trivial nature of the material. But imagine if we did this for serious scientific work.

Comments

This is really the first “structuring” paper for OS design.

The non-real-time aspect of this is critical- note that for a real-time system the synchronization may not be necessary.

The “shell” is split off from the OS and turned into a user program only in the 1960s in CTSS

Dijkstra writes before such problems as cache locality existed

Dijkstra: THE Processing System 1968.

Therefore we have arranged the whole system as a society of sequential processes, progressing with undefined speed ratios. To each user program accepted by the system corresponds a sequential process, to each input peripheral corresponds a sequential process (buffering input streams in synchronism with the execution of the input commands), to each output peripheral corresponds a sequential process (unbuffering output streams in synchronism with the execution of the output commands); furthermore, we have the “segment controller” associated with the drum and the “message interpreter” associated with the console keyboard. This enabled us to design the whole system in terms of these abstract “sequential processes.” Their harmonious cooperation is regulated by means of explicit mutual synchronization statements. On the one hand, this explicit mutual synchronization is necessary, as we do not make any assumption about speed ratios; on the other hand, this mutual synchronization is possible because “delaying the progress of a process temporarily” can never be harmful to the interior logic of the process delayed. The fundamental consequence of this approach–viz, the explicit mutual synchronization–is that the harmonious cooperation of a set of such sequential processes can be established by discrete reasoning; as a further consequence the whole harmonious society of cooperating sequential processes is independent of the actual number of processors available to carry out these processes, provided the processors available can switch from process to process.

Explication

A process combines program code and state (usually a stack and some memory for process global variables). User programs are applications, the other processes constitute the (operating) system – drivers for input and output devices and segment controller (disk buffer manager) and “message interpreter” (shell).

Mutual synchronization statements are semaphores – this paper introduces their use.

The fundamental property of a time shared system is that the system can schedule at will because “delaying a process temporarily… ” But this also requires that the system is “live” or else we don’t have the “temporarily” property.

Partitioning into processes that are explicitly synchronized simplifies the operation of the system because each process can be independently verified.The design extends to multiple processors

Advertisements

Elegance shmelagance, the Le Corbusier fallacy again (rev3).

Spolsky recently writes

Alain de Botton, writing in The Architecture of Happiness (Pantheon Books, 2006) has a section on elegance that any software designer will find familiar.

And I do find it drearily familiar: it is ignorantly dismissive and embraces the Le Corbusier fallacy and, (oddly) directly contradicts Spolsky’s argument. Le Corbusier was an architect who favored monumental “modern” structures and complexes and functional “clean” “elegant” design that has turned out to be unfriendly to human use. The Le Corbusier fallacy is the mistaken belief that the purpose of engineering works is to impress passersby with a show or spectacle or to exhibit the aesthetic sensibility of the “artist”. In architecture, this fallacy produces high rise slums that look striking from the highway but that are uninhabitable. In programming, the fallacy produces microkernel operating systems, “formal methods”, functional programming languages, and other “simple”, “clean”, “elegant” designs that do nothing interesting. De Botton compares the Salginatobel Bridge in Switzerland to Brunel’s Clifton Suspension Bridge in England and finds the first to be “elegant” and the second to be clunky and “ponderous”. Of course the Brunel bridge is bulkier than the swiss toy: it is far larger, carries much more and much heavier traffic, has been adaptable, and was built 100 years earlier with much less capable materials. But one might as well argue that clipper ships are ponderous compared to jet-skis, or that 727’s are not as lightweight as paper airplanes or that UNIX systems are more “bloated” than some academic proof of concept. The Salginotobel bridge is cute and features a bravura use of what was new technology in the 1930s when it was designed, but the Clifton bridge has been an engineering and aesthetic triumph since it was completed in the 1860s and it is a far more powerful work. If you are going to diss someone like Brunel, you should bring something more to the table than a sneer. Here’s the odd thing: Spolsky’s point is an important one – that users are interested in using the application to do their own work and not in how easy or clean the work is for the programmer. But we are so used to being hectored about “elegance” that he cites De Botton approvingly, while arguing the contrary.

I’ll continue this later, but want to recommend Richard Gabriel’s Patterns of Software and Jan Michl’s essay on design.

I’m thinking of a related essay about the superiority of Fortran over Haskell – the first was designed by working mathematicians and the second by computer science “logicians”.

Free software economics

Here are four quotes. Quotes 1, 3, and 4 all make sense together, if you are sufficiently cynical, but quote #2 is remarkably odd when taken with the others.

1For ten years now, free software developers have tried various methods of finding funds, with some success. There’s no need to make anyone rich; the median US family income, around $35k, proves to be enough incentive for many jobs that are less satisfying than programming. – Richard Stallman

and

2We, the creators of the free information society, mean to wrest from the bourgeoisie, by degrees, the shared patrimony of humankind. We intend the resumption of the cultural inheritance stolen from us under the guise of “intellectual property,” as well as the medium of electromagnetic transportation. We are committed to the struggle for free speech, free knowledge, and free technology. The measures by which we advance that struggle will of course be different in different countries, but the following will be pretty generally applicable:

1. Abolition of all forms of private property in ideas.

2. Withdrawal of all exclusive licenses, privileges and rights to use of electromagnetic spectrum. Nullification of all conveyances of permanent title to electromagnetic frequencies.

[…]

By these and other means, we commit ourselves to the revolution that liberates the human mind. In overthrowing the system of private property in ideas, we bring into existence a truly just society, in which the free development of each is the condition for the free development of all. – Eben Moglen

and

3We all do it together, the software’s a public utility; “Write once, run everywhere”; we’re done. This is a noticeable proposition, not just to us-though we understand why it is socially and politically desirable that the world work this way. It is a noticeable proposition for the International Business Machines Corporation, too. You now have, after a mere twenty years of work on our part, the largest, best-funded technology company on earth fundamentally on our side with respect to how the information technology system will work in the twenty-first century. San Palmisano, Irving Wladawski-Berger, you read them all the time, there’s a simple proposition: software’s a public utility, computing is an on-demand service provided by service providers who handle the internalized cost of making computing possible, and so on – Eben Moglen

and

4State-of-the art patent portfolio

For each of the past 13 years (1993-2005), IBM has been granted more U.S. patents than any other company. During that period IBM has received 31,995 US patents. In 2005, IBM received 2,974 U.S. patents.

Since 1996, IBM has invested approximately $5 billion per year in research, development and engineering. IBM’s current active portfolio of about 26,000 patents in the United States and over 40,000 patents worldwide for inventions in areas of primary technology focus for all IBM customers, is a direct result of that investment.For each of the past 13 years (1993-2005), IBM has been granted more U.S. patents than any other company. During that period IBM has received 31,995 US patents. In 2005, IBM received 2,974 U.S. patents.

Since 1996, IBM has invested approximately $5 billion per year in research, development and engineering. IBM’s current active portfolio of about 26,000 patents in the United States and over 40,000 patents worldwide for inventions in areas of primary technology focus for all IBM customers, is a direct result of that investment. IBM

Bitkeeper and tossing crates of money out the windows (vistas)

wish I was like Mr. Gates, all my money in big crates – Bruce Springstein

One of the many peculiar features of the software industry is the stubborn manner in which important innovations are ignored. If you read this account of Microsoft’s source code managment methods and this more believable response, and you know about BitKeeper, you can’t help but be struck by how much money Microsoft was throwing away in order to keep using obsolete technology.

A source management system is essentially a data base recording changes to a program. When a problem is found in running a program under development, the source management system allows developers to peel back changes to find the culprit. Without such a system, developers are reduced to the kind of painstaking line by line comparison of differences that should be reserved for obsessive James Joyce scholars and many projects have sunk because of poor record keeping. A complex program can be almost impossible to debug during the development process, but source management allows us to think of the program a collection of more manageble components – the changes that have been added over time.

Things become more complicated when the program is so complex that several developers need to work on it concurrently. If groups A, B, and C are all adding changes at the same time, these changes can clash and tracing which change caused which problem is harder. The traditional way to manage such problems is to create development “branches” – copies of the program that can be worked on independently. The primary copy is called the “root”. Each group starts out by with a “check out” of a copy of the root, works on it until they have something that meets some quality criteria (hopefully) and then “commits” their changes back to the root. Unfortunately, while one group is programming away, other groups will “commit” so that the root is no longer identical to what it was, and a combination of smart commit software in the source management program and effort by the programmers is needed to resolve incompatibilities.

When a development effort is so big that branches have sub-branches and sub-branches have sub-sub-branches and so on, ad infinitum the process can become daunting. If group A uses a module developed by group B and finds a bug, then A needs to wait for B to fix the bug and commit it and then for the fix to percolate up the sub branches and so on until it gets to the root – at which point A may find the fix breaks something else and so on.

In 1733, Johnathan Swift, in his On Poetry: A Rhapsody, wrote:
So Nat’ralists observe, a Flea/Hath smaller Fleas that on him prey,
And these have smaller Fleas to bite’ em
And so proceed ad infinitum.

In the 19th century, an unknown author, possibly Oliver Wendell Holmes, parodying Swift, wrote
Big bugs have little bugs
Upon their backs to bite them.
And little bugs have littler bugs,
And ad infinitum
.

Well you can see the problem. Or if you can’t, go back and read the more believable account of Vista’s problems.

This problem of branching source management is not new, but it was solved a couple of years back in BitKeeper. One of the brilliant insights behind Bitkeeper was that if you kept track of information in the right way you could throw out the tree structure. So instead of waiting for group A to merge back into main, group B can just “pull” from A to get its changes directly. Then if group C needs fixes from A and B it will pull from B getting both the B and A fixes which can then be merged back into the main. Thanks to some smart software and a number of “obvious in retrospect” ideas about how to record change data, Bitkeeper can turn a tree into a network. Instead of waiting for changes to wend their way up and down tree branches, groups can pull in what they need and let the source code management software take care of keeping it all straight. The effects on software productivity are remarkable – one of the 3 or 4 reasons why FSMLabs has been able to blow away software organizations 20 times our size is our fanatical use of Bitkeeper.

In a rational market, the kind that economists like to fantasize about, the immediate response would be to give the Bitkeeper engineers a lot of money and incorporate the technology into most software projects. But the market is not rational. Engineers and engineering management resist change that makes them learn something new or admit that someone else was smart. “That’s obvious, I did something like that at my old company” and “we could reimpliment that easily” are standard refrains of this business. (Isn’t it about time that “something like that” was regarded skeptically and the difference between “obvious” and “obvious in retrospect” was commonly understood in software engineering?). Company managers resist change that makes them take a risk on something new – “but X is the standard solution”. And accounting procedures in many companies make spending money on buying software less acceptable than spending much more money on working around the absence of that software. We run into the same phenomena with RTCore and it complicates life. For example, we see that our customers projects succeed at a much higher rate than industry norm, but is how much of this is due to the quality of our products and how much of it is due to the self selected nature of a customer group smart enough to make sensible purchases of innovation?