Category: Uncategorized

There is the classic by Vahalia on UNIX implementation (new edition supposedly coming out ) which, is in my always humble opinion the only worthwhile modern OS textbook although the original edition of Shaw’s book is good too. It’s depressing to see that my list has not changed in 10 years – either I’m fossilized or nobody is writing good OS books (or both).

Any other suggestions?

The BSD books are nice, but more tours of BSD implementation than anything illuminating on OS design. Tannenbaum’s book on MINIX is at the same level – these books are valuable, no doubt. But most OS textbooks are vague treatises on threaded programming. Just wait until I get a free weekend and write my magnum opus: “Rob Pike was right, OS development is so over, why didn’t I go work for Google?”

From Outlaws of the Marsh, translated by Sidney Shapiro

The second [bandit] was Jiang Jing, from Tanzhou in Hunan. Originally he had studied for the imperial examinations. But when he failed to pass, he abandoned the pen and took up the sword. A clever fellow, he was a skilled mathematician. In ten thousand calculations, he was never off an iota. He was also good with a lance and staff, and a skilled tactician in battle. And so he was known as the Magic Calculator.

This inspired me to google Kenneth Krohn, the co-developer of the Krohn-Rhodes theorem which discovers an unanticipated group structure in finite state machines. I’d heard rumors that Krohn had troubles and find

The petitioner testified before the board that a Mexican national (victim) had swindled him out of a large sum of money in the early 1970’s, at a time when the petitioner was living in Mexico under the alias Henry Blackwell. The petitioner was charged with kidnapping but pleaded guilty to the lesser offenses. At his plea hearing, he admitted that he and another individual used a false identity to lure the victim to Dulles International Airport for purposes of extorting the money.(4) The petitioner admitted that his coconspirator met the victim at the airport and took him to a car “rented by [the petitioner], using [a] . . . credit card” under another false name. The victim was taken to an apartment in Maryland that had been rented and “coerced to write approximately seven letters to member of [the victim’s] family.” The letters were in the victim’s handwriting and had the petitioner’s fingerprints on them. The letters instructed various persons to dismiss a lawsuit the victim had instituted against the petitioner, and to transfer assets to the petitioner (i.e., Henry Blackwell). As part of the plea, the government agreed not to prosecute the petitioner for any other crimes related to the case and the petitioner expected to serve approximately three and one-half years in prison. The petitioner was sentenced to ten years’ imprisonment and he served approximately three years of his sentence.(5)

These felonies are very serious and were, one may fairly conclude, committed as retribution for a wrong perpetrated on the petitioner by the victim. At the time the petitioner committed the crimes, in 1973, he was thirty-five years old, and held a master’s degree and a doctorate from Harvard University, which he earned in the 1960’s. His doctorate is in mathematics. He was accomplished in his field. He coauthored a computer science theory that was published in a textbook. He had owned, and sold at a profit, his own computer business making him financially secure. He also owned property in Washington, D.C. See Matter of Prager, 422 Mass. 86, 96 (1996) (admission to bar denied despite board recommendation for admission; at time applicant committed felonies, he was mature, well educated, and possessed adequate financial resources).

A correspondent back from a war somewhere writes:

More to the point, we had a large amount of Civvy laptops, and military systems together. There were major problems with dust, heat etc.

From what I read of the Tilt bits on the DRM in Vista, one malfunctioning peripheral could shut down the whole network.

In addition, there would be no way to reinstall the machine, as you cannot just put the disks in, you have to re-contact microsoft. This could be rather difficult in a war zone without communication. Trying to canibalise machines would have the same effect, disabling the operating system.

What I find most remarkable about DRM evolution is the lack of any discussion about liability – and since, I’m not a lawyer I mean here “moral liability”. If I can’t get to my bank records, or call the cops on skype when an armed intruder is in my home, or send an email on a military radio, or do any number of expected and perfectly legal operations because a DRM system has triggered who is to blame? Suppose XYZ Bank of NY is processing transactions on their rack of standard motherboards, and capacitor fails on an unused peripheral, triggering a chain of DRM actions that causes the hypervisor to decide that the underlying OS is not trustworthy or that the file containing some order is not permitted to be read. Who does the investor contact when his order to sell 1000000 Euros gets delayed until the rates have made it a terribly money losing trade? DRM operations are, in effect, denial-of-service attacks and the excuse is “I can deny service to prevent unauthorized use of some property”. But I’d hate to trying to justify the death of a hiker who couldn’t get to a GPS database because a DRM system was triggered.

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”.

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

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?

One of my correspondents has said my comments on formal method (here and here) were too terse. There are a couple of things that annoy me about formal methods, but the lack of results is the foremost annoyance. After multiple decades of “research”, there should be at least one theorem that tells us something non-obvious about programs. The absence of such a theorem tells us something about the analytical capability of formal methods. About 10 years ago, I asked a formal methods list for an example of such a theorem and got nothing convincing. Remember “non-obvious” is a requirement so a complex re-statement of “a n element queue can be emptied in n steps” does not qualify.

Ambrose Bierce (photo above) defined cynic by: “A blackguard whose faulty vision sees things as they are, not as they ought to be.”

I’ll finish it someday, but here is a variant.

I’m off to give a talk in Bangalore and then visit Chennai and Mumbai. In his delightful book called The Argumentative Indian Amrtya Sen writes

A good example is the transformation of Âryabhat’s Sanskrit term jya … [which] was translated, through proximity of sound, into Arabic jiba (a meaningless word in Arabic) and later transformed into jaib (a bay or a cove in Arabic), and ultimately into the Latin word sinus (meaning a bay or cove) , from which the modern term sine is derived. Âryabhat’s jya was translated in Chinese as ming and was used in such tables as yue jianlian ming, literally “sine of lunar intervals”.

Is that amazing or what?

March 26 is Paul Erdös birthday. The book about Erdös by Paul Hoffman is a nice read and thought provoking. Erdös’ concept of the BOOK recording the most elegant proofs is one that is natural for both mathematicians and engineers even though he might have disagreed. The relationship between mathematics and engineering is peculiar: Erdös like many other “pure” mathematicians didn’t care about applications although his compatriot von Neumann thought otherwise. The famous number theorist GH Hardy, in his very unapologetic Apology, boasted about the inapplicability of his work – although 20 years later some of it became standard tools for cryptography.