Showing posts with label donald knuth. Show all posts
Showing posts with label donald knuth. Show all posts

04 June 2009

Knuth: Every Algorithm is Sacred

One of my computer heroes, Donald Knuth, has sent a message to the head of the EPO, hoping to convince her that every algorithm is sacred, and should not be delivered up to become the personal, exclusive, proprietary possession of any one person or company:

Basically I remain convinced that the patent policy most fair and most suitable for the world will regard mathematical ideas (such as algorithms) to be not subject to proprietary patent rights. For example, it would be terrible if somebody were to have a patent on an integer, like say 1009, so that nobody would be able to use that number "with further technical effect" without paying for a license. Although many software patents have unfortunately already been granted in the past, I hope that this practice will not continue in future. If Europe leads the way in this, I expect many Americans would want to emigrate so that they could continue to innovate in peace!

Follow me @glynmoody on Twitter or identi.ca.

13 October 2008

Symbian's Patently Terrible “Triumph”

Although I've written elsewhere about the recent court case of Symbian v Comptroller General of Patents, noting that it was bad news, I hadn't realised quite how bad the news was until I went through the complete judgment. It's plain that the judges in question, who to their credit tried their level best to understand this mysterious stuff called software, failed to grasp the central issue of what software is. As a result, they have passed down a judgment that is so seriously wrong it will cause a huge amount of damage in the future unless it is revoked by a higher court....

On Open Enterprise blog.

27 April 2008

Patron Saint of Computing on Free Software

During the writing of Rebel Code I had the privilege of talking to nearly all of the world's top hackers. Among those, Donald Knuth is pretty much at the apex, certainly in the world of computer science.

His interviews are all-too rare these days, not least because he is racing against time to write as much of his magnum opus, The Art of Computer Programming, as he can. So I was pleased to come across this one, in which St Donald has these wise words to say on the subject of free software:

The success of open source code is perhaps the only thing in the computer field that hasn’t surprised me during the past several decades. But it still hasn’t reached its full potential; I believe that open-source programs will begin to be completely dominant as the economy moves more and more from products towards services, and as more and more volunteers arise to improve the code.

For example, open-source code can produce thousands of binaries, tuned perfectly to the configurations of individual users, whereas commercial software usually will exist in only a few versions. A generic binary executable file must include things like inefficient "sync" instructions that are totally inappropriate for many installations; such wastage goes away when the source code is highly configurable. This should be a huge win for open source.

(Via tuxmachines.org.)

18 October 2007

Of Open Source, Open Access and Donald Knuth

I often witter on about open access, assuming people know what I'm talking about. But if you'd like a little historical background, try this, which explains why people interested in open source should also be interested in open access:


Like all things that has to do with the Internet, the computer scientists are ahead of the curve in the flight from the old model of scientific publishing.

In probably one of the biggest shocks of the scientific publishing world, in 2003, the entire editorial board of the prestigious Journal of Algorithms resigned en masse. They subsequently re-formed as the editorial board of a new journal with the similar-sounding name of ACM Transactions of Algorithms.

In a sharply worded letter, the co-founder of the journal (and legendary computer scientist) Donald Knuth, explained the reasons for the mass defection. The reason being that Elsevier had been gouging the subscribers of the Journal of Algorithms for years. It had reached the point where the only defense was to bail ship.

31 July 2007

Darkness Visible

Yesterday I wrote about Knuth's wise words on software patents. In the course of trying to discover when exactly they were written (anyone know?) I found what seems to be the main source for it - a wonderful page entirely about patents and patent madness.

It only goes up to 2003, but nonetheless has lots of unusual links on the subject that are well worth exploring if, like me, you are a sad individual who finds this stuff both important and fascinating.

30 July 2007

Patron Saint of Computing Against Software Patents

If computing has a patron saint, it is the great and amazing Donald Knuth. Put another way, he is the god of computer algorithms, so I was particularly pleased to come across this definitive statement on their patentability:

In the period 1945-1980, it was generally believed that patent law did not pertain to software. However, it now a ppears that some people have received patents for algorithms of practical importance--e.g., Lempel-Ziv compression and RSA public key encryption--and are now legally preventing other programmers from using these algorithms.

This is a serious change from the previous policy under which the computer revolution became possible, and I fear this change will be harmful for society. It certainly would have had a profoundly negative effect on my own work: For example, I developed software called TeX that is now used to produce more than 90% of all books and journals in mathematics and physics and to produce hundreds of thousands of technical reports in all scientific disciplines. If software patents had been commonplace in 1980, I would not have been able to create such a system, nor would I probably have ever thought of doing it, nor can I imagine anyone else doing so.

I am told that the courts are trying to make a distinction between mathematical algorithms and nonmathematical algorithms. To a computer scientist, this makes no sense, because every algorithm is as mathematical as anything could be. An algorithm is an abstract concept unrelated to physical laws of the universe.

Nor is it possible to distinguish between "numerical" and "nonnumerical" algorithms, as if numbers were somehow different from other kinds of precise information. All data are numbers, and all numbers are data. Mathematicians work much more with symbolic entities than with numbers.

Therefore the idea of passing laws that say some kinds of algorithms belong to mathematics and some do not strikes me as absurd as the 19thcentury attempts of the Indiana legislature to pass a law that the ratio of a circle's circumference to its diameter is exactly 3, not approximately 3.1416. It's like the medieval church ruling that the sun revolves about the earth. Man-made laws can be significantly helpful but not when they contradict fundamental truths.

Congress wisely decided long ago that mathematical things cannot be patented. Surely nobody could apply mathematics if it were necessary to pay a license fee whenever the theorem of Pythagoras is employed. The basic algorithmic ideas that people are now rushing to patent are so fundamental, the result threatens to be like what would happen if we allowed authors to have patents on individual words and concepts. Novelists or journalists would be unable to write stories unless their publishers had permission from the owners of the words. Algorithms are exactly as basic to software as words are to writers, because they are the fundamental building blocks needed to make interesting products.

Amen to that. (Via Coding Horror.)

27 January 2006

Wolfgang Amadeus Mozart, Hacker

Today is the 250th anniversary of the birth of Wolfgang Amadeus Mozart. Most people know him as one of the world's greatest composers: a child prodigy, creator of over 600 works, and – if you believe some of the wilder rumours - fatally poisoned at the age of 35 by a rival composer. Few, though, are aware that Mozart was also a hacker.

Computers may not have existed in the eighteenth century, but the musical machines called orchestras and choirs are conceptually identical to synthesisers, which are themselves specialised music computers. Just as programming code specifies how a computer should act (and a MIDI file controls a synthesiser), so musical code – in the form of a score – directs what instruments and voices should do and when.

Conductors are largely superfluous in all this (at least for Mozart's music): they do not create the output, which is specified by the score. All they do is interact with the score “loaded” on the orchestral or choral machine, in the same sense that someone might interact with a video game loaded on a console. The incidental nature of humans in the performance of classical music is shown by some pieces that Mozart wrote at the end of his life for a clock with built-in mechanical organ. Here the scores completely determined the audio output: there was no human intervention once the music had been converted to a kind of piano roll – a forerunner of the punch cards employed a century and a half later by the early commercial mainframe computers.

More generally, though, hacking is a state of mind, a way of understanding and exploring the world, independent of a particular technology (and not to be confused with “cracking”, which is the correct name for the kind of digital smash and grab too often in today's headlines). Richard Stallman, perhaps the greatest hacker of modern times, has defined the essence of hacking as “playful cleverness” - as good an encapsulation of Mozart's genius as any.

The cleverness showed itself early. Mozart started learning the piano when he was three, began composing when he was five, and wrote his first symphony and opera at the age of eight and 11 respectively. Like many top coders, he frequently worked out everything in his head before consigning it to paper at a single sitting (often just hours before a deadline – again, just like some programmers), and usually without the need for revisions (that is, bug-free). He could also multi-task: he is supposed to have written one of his finest works during a game of skittles.

Like any red-blooded hacker, Mozart adored mathematics as a child (and gambling as an adult), found word-play irresistible (email would have been perfect for him) and loved setting himself puzzles. His Musical dice game uses dice throws and pre-composed short fragments of music to form compositions created by random numbers; the challenge was writing fragments that would fit together whatever the throws. At one point in his opera Don Giovanni, in addition to the main orchestra accompanying the singers, there are three more orchestras on stage, each playing completely different music. It all fits together so perfectly that most opera lovers are unaware of the compositional tour-de-force they are witnessing.

Mozart's playfulness was a key facet of his character. The musical form he seems to have enjoyed writing most – opera buffa – is simply Italian for “funny opera”. In several concertos composed for a horn-playing friend, Mozart added jocular comments to the music - “Slowly, Mr Donkey”; “Breathe!”; “Go on!”; “Oh, filthy swine!” - an early example of commented code. He sometimes employed different coloured inks in a score, rather as modern programming tools do to differentiate various elements. Another piece, called A musical joke, includes notes that are blatantly wrong. If the musicians play them as written, they sound incompetent; if they play the “right” notes, they have failed to perform the piece as the composer intended, and so are indeed incompetent.

Significantly, Mozart was a big fan of a key hacking concept known as recursion, whereby something refers to itself to create a kind of infinite loop. For example, a core hacking project started and led by Stallman is called “GNU”, an acronym for “GNU's Not Unix”, which uses itself in its own explanation. (Recursion is another example of playful cleverness).

Recursive music is created by employing a delayed version of a tune as its own accompaniment. Formally, this is known as a “canon” (simpler versions, like the song “London's burning”, are called “rounds”), and Mozart wrote dozens of them, mostly for himself and his friends to sing at purely private performances. They are notable not only for their fine music, but also for the texts Mozart chose to set: “Lick my bum” is one memorable line that crops up more than once. Today's hackers, too, enjoy dubious lyrics, and have an earthy turn of phrase: the injunction “RTFM” - often thrown at hapless newbies - does not stand for “Read The Flipping Manual”.

Another notable characteristic of hackers is their fondness for science fiction. Overt references to Star Wars may be thin on the ground in Mozart's works, but many of his operas written in the older, “serious” style are based on the same eternal themes of good versus evil and love versus duty that lie at the heart of George Lucas's epic.

The science-fiction writer Arthur C. Clarke once suggested that any sufficiently-advanced technology is indistinguishable from magic; the corollary is that magic is indistinguishable from sufficiently-advanced technology. So Mozart's last opera, The Magic Flute - full of other magical objects, too - is, from this viewpoint, a work of science fiction. It is also a Masonic opera, steeped in mysterious symbols and rituals that will be nonetheless be familiar to the hackers who participate in MMORPGs (Massively Multiplayer Online Role-Playing Games), where characters join guilds, complete quests and seek to gain experience points - just like the hero in The Magic Flute.

The close links between music and hacking run both ways, and many of today's top coders are highly musical. Richard Stallman – whose dedication to the cause of freedom is positively Beethovenian - carries with him a soprano recorder wherever he travels. The profoundly-religious and frighteningly-cerebral Donald Knuth – a kind of hacker J.S.Bach - was moved by his love of music to have an 812-pipe baroque organ built in a specially-designed room in his house. Appropriately enough, Knuth's life-work is called The Art of Computer Programming (Bach called his The Art of Fugue). Representing a different musical tradition, Brian Behlendorf, the prime mover behind the Apache Web server program that runs two-thirds of the Internet, DJs ambient and dub music. And it is well known that for most hackers the crucial first step when they start working is to fire up some particularly loud and inspirational music on their computer. Mozart would have approved.