Paul's Pontifications

Enough with the blue LEDs!

2011-11-18T11:45:00.000-08:00

The first blue LED was created by Shuji Nakamura in 1993. It was a technical triumph, and Nakamura eventually managed to win a $9M bonus (after suing his employer). Before then LEDs ranged from red to a slightly yellowish green, and nobody could figure out how to get the wavelengths any shorter. Nakamura's LED was not merely slightly blue; it could go right up into the UV, and was amazingly bright. Today I am typing this in a room illuminated by white LEDs that are made using this technology. Slim, low powered LED-illuminated screens have been created, and blu-ray players use lasers with the same basic semiconductor combination to give us high definition movies on a disk. Science and technology march on, hand in hand.

But that's not what I want to write about.

On Wednesday I plugged in a new cable modem, enabling faster broadband. On the front panel are two LEDs. One is green and shows that the modem has locked on to a signal. The other is blue and flashes. So now I have this bright blue flashing light near me. The coax cable comes into my office near my desk, so I can't move it far. Fortunately I've been able to tuck it into a cubby-hole next to the bookshelf, so its not in my line of sight. Without that I'd probably have had to put it inside a box or something just to hide the LED.

I was not too surprised by the appearance of blue LEDs as an alternative to the old red and green back at the turn of the century; they were novel and eye-catching, which is what manufacturers need if they are to sell stuff. But the trouble is that they are too eye catching; the piercing blue light is actually unpleasant to look at directly, and is far more intrusive than the quiet red and green.

Some manufacturers seem to have got the idea. I have a couple of USB hubs with blue LEDs, but they don't flash and they are sufficiently buried inside that you don't have the piercing gleam. But this cable modem (its a Netgear SuperHub, by the way) doesn't follow that rule. We also bought a moderately expensive audio system a few months ago, and that also has a piercingly bright blue LED on the front. So when we watch TV we have this shining in our eyes just below. We've got some relief by sticking some white tape over the LED, but we shouldn't have to do that.

So could anyone reading this who works for a consumer electronics company please point the design department at this posting. Remember guys; shining bright flashing lights in your customers' eyes may get their attention, but it won't get you repeat business.

I wrote about this before, in 2008. I'm disappointed to have the same problem three years later.

Windows, Linux, ARM and Intel in a Zero Sum Game

2011-05-22T10:03:00.000-07:00

Microsoft is talking about putting Windows 8 on ARM. Intel is trying to play this down, talking about how Linux is already on ARM, and how Intel even supports Linux itself. None of this makes sense unless you understand the position of Microsoft and Intel in the PC market.

People often speak of the "Wintel" duopoly, which of course is a misnomer. A duopoly is when two companies share a single market, at which point there is a risk of anti-competitive behaviour. However Microsoft and Intel are not a duopoly, they are two near-monopolies. Microsoft dominates the desktop operating system market, and Intel dominates the desktop CPU market. Although both OS and CPU are necessary components in a desktop computer, this doesn't make their manufacturers a duopoly because even in the best of worlds they don't compete: increased market share for Microsoft is not at the expense of Intel.

However this doesn't mean that everything can be all cozy between them, because in a broader sense they do compete. Microsoft and Intel are players in the desktop PC "value chain" (actually, its a value network, or even more precisely, a value directed acyclic graph, and if you look closely you find it isn't even really acyclic because chip-makers buy PCs, but term "chain" is more often used so that is what I'll stick to). This describes the way that money flows from PC buyers through vendors to manufacturers to parts makers to raw materials.

If you are a player in a value chain then its pretty much a zero sum game; every time someone buys a PC their money bubbles back up through the value chain and everyone grabs their bit. Your problem as a player is to get as much of this money as you can, which inevitably means that someone else gets less. Value chains are characterised by dysfunctional relationships between people who need each other but nevertheless hate each others guts.

There are two big strategic goals in a value chain. The first is obvious, the second less so:

Make your bit a monopoly, so the rest of the value chain has to come to you to produce the product. That way you can charge monopoly prices and hoover up all the money coming through the value chain.
Make everyone else's bits into generic commodities so that they can only compete by keeping prices low. That way they can't charge monopoly prices, which leaves more money for you. That's the consequence of the zero sum game thing.

Once you understand the second goal you understand everything about Microsoft and Intel.

Microsoft makes very sure that Windows runs well on as wide a variety of hardware as possible in order to keep PC hardware a commodity business.
Intel makes sure that Linux runs nicely on Intel processors in order to create a competitor for Microsoft, so Microsoft will have to reduce its prices, thereby leaving more money for Intel. I suspect Intel were also very supportive of Apple's move to Intel hardware for this reason, as well as the more obvious one of having a new channel.
Microsoft made sure that Windows runs well on AMD. However AMD have never really recovered from Intel's "Intel Inside" marketing coup (where they paid box vendors to make it sound like "Intel Inside" was a big selling point, so lots of customers thought it was). So now Microsoft need to create a new competitor for Intel, and have decided that ARM will fulfil this role nicely. In the past they also did this with the DEC Alpha for the same reason.

ARM already plays nicely with Linux, which is quite a feat because ARM isn't a single processor; its an entire family. If ARM have any sense they will make sure that this continues. Microsoft are likely to try to pay ARM off to get it to remove support for Linux. If ARM have any sense they will resist this because it will enable Microsoft to entrench itself as a mobile monopoly, thereby decreasing the amount of money available for ARM to grab for itself.

Edit: "zero sum gain" -> "zero sum game". That's what happens when you let your fingers do the thinking.

Patent reduction redux

2011-05-02T05:26:00.000-07:00

In my last post I presented a translation of a patent into Haskell. This post went up on Hacker News and Slashdot, and I got over 25,000 page views plus a lot of comments. There are too many comments to respond to individually, and many of them cover similar ground. So here is a more general response to the main issues raised.

Its trivial

Well, yes, in the computer science sense it is. We all know that any algorithm can be written in any turing-complete language, and the Lambda Calculus is turing-complete. QED.

However when I read court judgements related to patentability this never gets mentioned, not because judges are too stupid to understand the point, but because as far as I can tell no lawyer has ever tried to put it in front of a judge. I'm not sure exactly why this is, but I suspect that it is a combination of the general squishiness of the law (see below) and the fact that you want to base your case on a tried-and-tested legal theory rather than building something completely new. From a lawyer's point of view an obscure mathematical theorem (most lawyers have never heard of Turing) looks like a very shaky foundation for a legal argument.

So it seemed to me that if I could convert this abstract theoretical point about turing-complete languages into a practical demonstration that directly addressed a key point of law then it might make a big difference. Sure its a small step for computer science, but it could be a giant leap for legal thinking.

The law is squishier than that

Eben Moglen has said

... the hacker belief that laws are form of code [creates] a particular frame of analysis for legal questions. [...] one thing which lawyers around the world all share is an awareness of the squishiness of law, it is by no means the hard arthropod carapace for internal soft organs that non-lawyers have a tendency to assume it is

Moglen is undoubtedly correct, and when I look at legal judgements I often seem to discern a judge trying to construe the facts and law in a way that will deliver what s/he believes to be justice in the wider human sense as well as in the strict legal sense.

But judges are still constrained by the law; however much they might want to, they cannot look at evidence conclusively showing fact X plus a law saying "if X then Y", and then deliver a judgement of "not Y". The trick is to provide incontrovertible evidence for X. To extend Moglen's metaphor, the law may not have an arthropod carapace, but inside the squishy flesh it still has a rigid skeleton of of laws that judges cannot bend at will.

The law / lawmakers are too corrupt; they'll just legislate around this.

I don't believe the application of the law in the US is anything like corrupt enough for this to be an issue. The worst one can say about the application of American law is that effective legal representation can be bankruptingly expensive for the little guy. But that's not a problem here.

Lawmakers are an issue; the leadership of America is routinely for sale to any sufficiently large campaign contribution. But the limits on patentability are long-standing and fundamental, and until the State Street decision in 1998 it was generally understood that computer software and other information-processing algorithms were not patentable. For the US legislature to change this basic principle of patent law seems unlikely.

Everything in the patent is prior art anyway.

Prior art is one of the most misunderstood things in patent law. Each claim in a patent is an entire invention; there may well be things in the invention that are prior art, but unless you can show that everything in the whole claim existed in a single entity previous to the patent priority date then you don't have prior art.

So the fact that hash tables and linked lists were well known before this patent is irrelevant. Of course if anyone can show actual prior art that includes everything in one of the claims then I imagine that the Red Hat lawyers would like to hear of it.

But all patents can be reduced to a formula / number, so this argument would abolish all patents.

This misunderstands patent law.

USC 35 II 10 defines a patentable invention as

... any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof ...

This definition excludes mathematical formulae and physical facts from patentability. Leaving aside the fact that it is also well known, the quadratic formula is not patentable because it is not a useful process, machine etc.

The patent covers the physical realisation of the idea, not the idea itself. So publication of the patented material in any form is fine in theory; that is the whole point of the patent system. What you can't do is make and sell the patented invention. (An exception has been carved out here for ready-to-run implementations of software patents on the grounds that they contribute to infringement by the users, which is bad law but not part of this argument).

The 120 patent recites a computer running the algorithms to create a useful improvement in performance, so that makes it patentable.

In the State Street case the Court decided that a mathematical formula could form part of an invention, as long as the whole thing was a new and useful process, machine etc. This was a radical departure from previous US decisions, but it matches current European law (I don't know which came first) where mathematical formulae and computer programs cannot be patented "as such", but can be patented as part of an invention that achieves a "technical effect" (which seems to mean the same as "new and useful improvement" in the US).

However Bilski has now blown all that out of the water. The Court in Bilski specifically declined to endorse anything in State Street, and instead decided that patentability should be decided in line with three other cases. For more details see my post on this, but in essence it means that while a mathematical formula or algorithm can form part of a patented invention, it doesn't contribute anything to the novelty of that invention. Even if the formula or algorithm is completely new, for the purposes of the patent it is treated as "well known". Hence in the Diehr case (the rubber curing method) the invention was the use of a calculation to tell the mould when to open rather than a predetermined time interval. The formula to do this was part of the patent, but the invention was its use in a new kind of machine; one that opened based on temperature readings rather than a timer. On the other hand in the Flook and Benson cases the only novelty was in the formula; everything else was held to be already known, so the patents were disallowed.

In Bilski the central component of the invention was a formula for hedging bets in energy markets. All else was well known, so the patent was disallowed. The Supreme Court said:

Claims 1 and 4 explain the basic concept of hedging and reduce that concept to a mathematical formula. This is an unpatentable abstract idea, just like the algorithms at issue in Benson and Flook.

In this case the patent application itself contained the reduction of the concept to a mathematical formula. But clearly if the claims had left the formula unstated and merely listed an equivalent series of steps or assemblage of "means" (e.g. "a multiplication means connected to an addition means") then this would have merely been a change in the drafting, and it is well established that you can't make something patentable just by changing the words in the claims. So this leads to the following conclusion: any element of a patent claim that can be reduced to a mathematical formula is not patentable material, and the subsequent Section 102 analysis (to determine if the invention is new and non-obvious) must ignore it.

So in the case of the 120 Patent, all the claims come down to "a general purpose digital computer running software that implements a bunch of mathematical formulae". Running software on a computer is prior art, so there is no new invention here.

Patent 5,893,120 reduced to mathematical formulae

2011-04-30T02:17:00.000-07:00

I have previously argued that the Bilski ruling renders all software unpatentable in the US because any method of manipulating information (i.e an algorithm) can be translated into a Haskell program, every Haskell function is a formula in the Typed Lambda Calculus, and all the variants of the Lambda Calculus are part of mathematics. Hence any algorithm can be reduced to a mathematical formula, which US patent law states is not patentable subject matter.

The computer science community has tried to explain this to the patent industry, but these explanations have fallen on deaf ears. So I thought I would try a different tack.

Google has just been ordered to pay $5M for infringing patent 5,893,120 (hereafter "Patent 120"). This patent covers a very simple data structure and the algorithms for manipulating it. In fact much of the text of the patent is a pseudo-code implementation in a Pascal-like language. So I thought I would provide a practical demonstration of what has, until now, been a theoretical proposition; the reduction of a software patent to set of mathematical formulae. The result is below, and is also posted here (although I believe that the paste-bin will eventually expire).

I chose this patent partly because it is comparatively simple (there are 95 lines of Haskell source code in the file), but also because it is potentially important; Google's "infringement" consisted of using Linux, which uses this algorithm. Hence anyone using Linux is a potential target.

Red Hat is reportedly seeking a declarative judgement that this patent is invalid, and Google is expected to appeal, so this is not over yet. If anyone knows how I can contact their lawyers to draw these formulae to their attention, I'd be grateful.

Edit 1:A brief overview of the relationship between Haskell and the Lambda Calculus can be found here.

Edit 2:Of course a judge isn't going to know the Lambda Calculus from a lump of rock, but that is what expert witnesses are for. Get a professor of mathematics from an internationally recognised university to testify that these are formulae in the Lambda Calculus, and that the Lambda Calculus is part of mathematics, and you have a sound legal proof. The only thing the patent holders could do is find another professor to testify differently.

Edit 3:Sorry about the broken formatting. If you want to review the code you can either look at this colourised version or copy and paste it into your favourite editor.

Edit 4: This post has been slashdotted. Rather than try to respond to all the various comments individually I have posted a general response to the common themes.

In the meantime, here are the formulae:


{- |

The claims of United States Patent 5,893,120 may be reduced to a set
of mathematical formulae expressed in the Typed Lambda Calculus, also
known as System F.  This file contains these formulae.  The language
used is Haskell, which is a version of System F with extra "syntactic
sugar" to make it useful for practical purposes.

It happens that formulae expressed in Haskell can also be transated by
a Haskell compiler into executable computer programs.  However that
does not make a Haskell function any less of a mathematical formula.
Otherwise the quadratic formula

>    x = (-b +/- sqrt (b^2 - 4ac))/2a

would be rendered patentable subject material by the same argument.

-}


module Patent120 where

import Data.Char (ord)

-- The "ord" function defines a bijection between text characters and
-- numbers.

import Data.Map (Map)
import qualified Data.Map as M

-- The Data.Map module is a standard module defined entirely as a set
-- of Haskell formulae, in the same way as this module.  The "import"
-- means that these formulae are incorporated with the formulae given
-- here.

{-
Claim 1. An information storage and retrieval system, the system
comprising:

  a linked list to store and provide access to records stored in a
  memory of the system, at least some of the records automatically
  expiring,

  a record search means utilizing a search key to access the linked
  list,

  the record search means including a means for identifying and removing
  at least some of the expired ones of the records from the linked list
  when the linked list is accessed, and

  means, utilizing the record search means, for accessing the linked
  list and, at the same time, removing at least some of the expired ones
  of the records in the linked list.
-}

-- | A record with Birth value below some threshold is considered "expired".
type Birth = Integer 


-- | Records in the list have their birth recorded, and also contain
-- a key and a value.
data Record k a = Record Birth k a

-- | True iff the record is older than the threshold argument.
expired t (Record b _ _)  =  b < t   -- | True iff the record matches the key. matches k (Record _ k1 _) = k == k1   -- | The value stored in a record. value (Record _ _ v) = v   -- | Records are stored in a linked list in the system memory. type Storage k a = [Record k a]   -- | The "search1" function includes a threshold age parameter. -- It returns both the items that match the key and the linked list -- with the expired items removed. --  -- The recitation of "means" cannot be used to disguise the formula -- given here.  Otherwise any mathematical formula could be patented -- by reciting e.g. "addition means" and "multiplication means" that are -- mechanically derived from the formula. search1 :: (Eq k) => Birth -> k -> Storage k a -> (Storage k a, [a])
search1 t k records = foldr nextItem ([], []) records
  where
     nextItem r@(Record b k2 v) (retained,found) =
        (if b > t then r:retained else retained,
         if k == k2 then v:found else found)


{-
Claim 2. The information storage and retrieval system according to
claim 1 further including means for dynamically determining maximum
number for the record search means to remove in the accessed linked
list of records.
-}

-- | Similar to "search1", but with an added parameter for the maximum
-- number of records to remove.
search2 :: (Eq k) => Int -> Birth -> k -> Storage k a -> (Storage k a, [a])
search2 n t k = (\(_,x,y) -> (x,y)) . foldr nextItem (n,[],[])
  where
     nextItem r@(Record b k2 v) (n2,retained,found) =
        (n2-1,
         if b > t || n2 == 0 then r:retained else retained,
         if k == k2 then v:found else found)


{-
Claim 3. A method for storing and retrieving information records using
a linked list to store and provide access to the records, at least
some of the records automatically expiring, the method comprising the
steps of:

  accessing the linked list of records,

  identifying at least some of the automatically expired ones of the
  records, and

  removing at least some of the automatically expired records from the
  linked list when the linked list is accessed.

Claim 4. The method according to claim 3 further including the step of
dynamically determining maximum number of expired ones of the records
to remove when the linked list is accessed.
-}


-- | Claim 3 can be reduced to the same formula as Claim 1.  The use of
-- a sequence of steps cannot disguise the fact that this represents
-- a mathematical formula.  Otherwise it would be possible to patent
-- any mathematical formula simply by reciting the steps in evaluating
-- it. e.g. "step 3: the addition of the results of step 1 and step 2"
search3 :: (Eq k) => Birth -> k -> Storage k a -> (Storage k a, [a])
search3 = search1

-- | Likewise Claim 4 can be reduced to the same formula as Claim 2.
search4 :: (Eq k) => Int -> Birth -> k -> Storage k a -> (Storage k a, [a])
search4 = search2

{-
Claim 5. An information storage and retrieval system, the system
comprising:

  a hashing means to provide access to records stored in a memory of the
  system and using an external chaining technique to store the records
  with same hash address, at least some of the records automatically
  expiring,

  a record search means utilizing a search key to access a linked list
  of records having the same hash address,

  the record search means including means for identifying and removing
  at least some expired ones of the records from the linked list of
  records when the linked list is accessed, and

  meals, utilizing the record search means, for inserting, retrieving,
  and deleting records from the system and, at the same time, removing
  at least some expired ones of the records in the accessed linked list
  of records.
-}


-- | Every key has a hash code.  Strings of characters may be used as
-- keys.
class (Eq k) => Hashable k where
  hash :: k -> Int  -- Every key has a hash code.

instance Hashable Char where hash = ord

instance (Hashable a) => Hashable [a]  where
  hash = foldr (\x h -> ((hash x + h) * 53 + 1) `mod` 1733) 0

type HashedStore k a = Map Int [Record k a]


-- | Access a hashed store with a function that returns the modified list of records.
hashAccess5 :: (Hashable k) =>
  (Storage k a -> (Storage k a, [a])) -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])
hashAccess5 f t k store = (M.insert h retained store, result)
  where
     h = hash k
     (retained, result) = case M.lookup h store of
                             Just records -> f $ filter (expired t) records
                             Nothing      -> ([], [])


-- | Search using hashAccess.
search5 :: (Hashable k) => Birth -> k -> HashedStore k a -> (HashedStore k a, [a])
search5 t k = hashAccess5 srch t k
  where srch store = (store, map value $ filter (matches k) store)

-- | Insert using hashAccess.
insert5 :: (Hashable k) => Birth
                             -- ^ Expiry threshold for old entries.
                          -> Birth
                             -- ^ Birth date for new entry.
                          -> k -> a -> HashedStore k a -> HashedStore k a
insert5 t b k v = fst . hashAccess5 (\store -> (Record b k v : store, [])) t k


-- | Delete using hashAccess
delete5 :: (Hashable k) => Birth -> k -> HashedStore k a -> HashedStore k a
delete5 t k = fst . hashAccess5 (\store -> (filter (not . deleted) store, [])) t k
  where deleted (Record _ k1 _) = (k == k1)


{-
Claim 6. The information storage and retrieval system according to
claim 5 further including means for dynamically determining maximum
number for the record search means to remove in the accessed linked
list of records.
-}


-- | Access a hashed store with a function that returns the modified list of records.  The "Int"
-- argument is the maxiumum number of expired records to remove.
hashAccess6 :: (Hashable k) =>
  Int -> (Storage k a -> (Storage k a, [a])) -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])
hashAccess6 n f t k store = (M.insert h retained store, result)
  where
     h = hash k
     (retained, result) = case M.lookup h store of
                             Just records -> f $ filterN n (expired t) records
                             Nothing      -> ([], [])
     filterN _ _ [] = []
     filterN n1 p (x:xs) = if n1 <= 0 || p x then x : filterN n1 p xs else filterN (n1-1) p xs    -- | Search using hashAccess. search6 :: (Hashable k) => Int -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])
search6 n t k = hashAccess6 n srch t k
  where srch store = (store, map value $ filter (matches k) store)

-- | Insert using hashAccess.
insert6 :: (Hashable k) => Int
                          -> Birth
                             -- ^ Expiry threshold for old entries.
                          -> Birth
                             -- ^ Birth date for new entry.
                          -> k -> a -> HashedStore k a -> HashedStore k a
insert6 n t b k v = fst . hashAccess6 n (\store -> (Record b k v : store, [])) t k


-- | Delete using hashAccess
delete6 :: (Hashable k) => Int -> Birth -> k -> HashedStore k a -> HashedStore k a
delete6 n t k = fst . hashAccess6 n (\store -> (filter (not . deleted) store, [])) t k
  where deleted (Record _ k1 _) = (k == k1)


{-
Claim 7. A method for storing and retrieving information records using
a hashing technique to provide access to the records and using an
external chaining technique to store the records with same hash
address, at least some of the records automatically expiring, the
method comprising the steps of:

  accessing a linked list of records having same hash address,

  identifying at least some of the automatically expired ones of the records,

  removing at least some of the automatically expired records from the
  linked list when the linked list is accessed, and

  inserting, retrieving or deleting one of the records from the system
  following the step of removing.

Claim 8. The method according to claim 7 further including the step of
dynamically determining maximum number of expired ones of the records
to remove when the linked list is accessed. 
-}

-- | As with Claim 3 vs Claim 1, the formulae for Claim 7 are the same as for Claim 5
hashAccess7 :: (Hashable k) =>
  (Storage k a -> (Storage k a, [a])) -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])
hashAccess7 = hashAccess5

search7 :: (Hashable k) => Birth -> k -> HashedStore k a -> (HashedStore k a, [a])
search7 = search5

insert7 :: (Hashable k) => Birth
                             -- ^ Expiry threshold for old entries.
                          -> Birth
                             -- ^ Birth date for new entry.
                          -> k -> a -> HashedStore k a -> HashedStore k a
insert7 = insert5

delete7 :: (Hashable k) => Birth -> k -> HashedStore k a -> HashedStore k a
delete7 = delete5


-- | And the formulae for Claim 8 are the same as for Claim 6
hashAccess8 :: (Hashable k) =>
  Int -> (Storage k a -> (Storage k a, [a])) -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])
hashAccess8 = hashAccess6


search8 :: (Hashable k) => Int -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])
search8 = search6

insert8 :: (Hashable k) => Int
                          -> Birth
                             -- ^ Expiry threshold for old entries.
                          -> Birth
                             -- ^ Birth date for new entry.
                          -> k -> a -> HashedStore k a -> HashedStore k a
insert8 = insert6

delete8 :: (Hashable k) => Int -> Birth -> k -> HashedStore k a -> HashedStore k a
delete8 = delete6

Why I am voting Yes to Alternative Vote

2011-04-20T23:52:00.000-07:00

On May 5th the UK votes whether to change its electoral system from "first past the post" (FPTP) to "alternative vote" (AV). In FPTP you put an X next to the name of one candidate, and the candidate with the biggest number of Xs wins. In AV the first preferences are counted as for FPTP, but then the candidate with the lowest number of votes is eliminated and the second preferences of their voters are then counted towards the other candidates. This process carries on until someone has more than 50% of the vote.

When I was at University the Students Union used AV, and one year a man stood for the post of Womens' Officer under the name of "Captain Kirk". Against him were two more conventional candidates standing on the Conservative and Labour platforms.

When the votes were counted Captain Kirk got 49% of the first preference votes, with the Conservative getting 26% and Labour 25%. Under FPTP Kirk would have won, but now the Labour candidate was eliminated and it turned out that all of the people who voted for her first had voted for the other woman as second preference. So now the Conservative candidate had 26%+25%=51% of the vote, and Kirk was defeated.

I'm well aware of the Arrow Impossibility Theorem, which shows that given an election with three or more candidates and three or more voters it is impossible to have a voting system that always delivers the right result, but it seems to me that this is rather like the fact that any programming language is logically equivalent to a Turing Machine; its true, but it doesn't mean that all (voting systems | programming languages) are equally good. FPTP seems particularly prone to perverse outcomes, such as the election of a male Womens' Officer when the majority of the electorate wants a female. Pretty much every election in the UK is a 2-horse-1-pony race, with the Liberal Democrats as the pony, and every election pundits discuss the impact of "tactical voting" as people who would like to elect the Lib Dems instead vote Labour for fear of otherwise "letting the Conservatives in". Under AV they can simply vote Lib Dem first and Labour second.

The anti-AV campaign's arguments seem to come down to:

It will create more hung parliaments. Possibly. I don't see this as a bad thing. The current coalition seems to be doing OK, and a coalition means that more of the electorate's views get represented in government. Having a government elected by 40% of the people get 100% of the power seems to me rather undemocratic.
It will empower the National Front. For those who don't know, the National Front (NF) is an extreme right wing racist party, which occasionally does well in poor inner-city areas where the "immigrants are taking your jobs and houses" line gets a sympathetic hearing. But equally, if most people object to the NF on principle then AV makes it much easier to vote against them; just put the NF at the bottom of your list. That ensures that no matter how other people vote, your vote will count against the NF.
The most popular person doesn't always win. Well yes, if you define "most popular" as "winner under FPTP" then this is true; if AV didn't give a different result sometimes then there wouldn't be any difference. The point about AV is that the candidates with the broadest support tend to win much more often, whereas FPTP is prone to producing winners who most of the electorate actively dislike.

So for these reasons I'm going to be voting YES to AV.

Why I am not buying an ebook reader

2011-04-20T11:11:00.000-07:00

Being the kind of person with a lot of bookshelves and still not enough room to keep all my books, I wondered about moving to ebooks. There is a lot to like in the concept; the idea of being able to take a significant chunk of my library with me when I am away from home is very attractive, as is being able to back up the whole lot somewhere off site. With a waterproof cover for my ebook reader I could take it into the bath or just read when outdoors on a rainy day without worrying about the wet. And of course you don't have to wait for days for a book to be delivered by Amazon.

So I started looking for answers to the following questions:

1: What books are available in ebook format? And for how much?

I picked a selection from the books I have around me now. Terry Pratchett's books are on the Kindle for around £4.50 each, although "I Shall Wear Midnight" is £9.24. Hang on a minute, the paperback of ISWM is only £3.49. So for almost three times the price I get to save the book industry the cost of printing and shipping me a physical product? I don't think so. Even the older Pratchett books still cost more for the Kindle than in paperback.

Looking elsewhere, the first four Google hits are for pirate torrents and Usenet indexers. Then there is "Fictionwise", which seems to be Barnes & Noble in the US selling stuff on it's Nook. Despite getting a hit in the Google search it seems that B&N don't actually sell any Pratchett. Finally the Diesel e-book store has them for around $8 each, with ISWM for $10. At the moment a dollar is about £0.61 although doing it through a credit card company is going to cost more.

OK, what about some other books? Robert Heinlein: there are four Kindle e-books out of the 32 novels and 59 short stories written by Heinlein. Diesel does better, with 8 Heinlein books. Baen also have some more Heinlein books.

"Contact" by Carl Sagan is not available for Kindle. Googling for "contact sagan ebook" turns up pages of pirate copies but nothing legitimate.

Lois McMaster Bujold's Vorkosigan saga I already have in ebook format because Baen included the entire opus on a CD with the latest volume. Not only does it not have DRM, but it is licensed for free redistribution. Kudos to Baen, and I hope the experiment works for them.

The Matthew Shardlake stories by C.J. Sansom are all available for Kindle, for about the same price as the paperbacks. They are also available in other ebook formats from Diesel for $13 each, which seems a bit steep even by ebook standards.

"Next Stop Execution" by Oleg Gordievsky is not available on the Kindle or on Diesel.

Some of Matt Ridley's books, including "The Red Queen", "Genome", and his latest "The Rational Optimist" are available on the Kindle, but "The Origin of Virtue" is not, which seems odd. Diesel only has "The Rational Optimist".

So my conclusion is that I can buy most of my existing library in ebook format, but not all. Even then its going to be an expensive business to do it legally; we probably have around 1,000 books in our house (never actually counted), and the cost of getting just half of them in ebook format is going to be in the thousands of pounds. Ouch!

2: What about Digital Restrictions Management

The attitude of most publishers here is best summed up by Barnes & Noble. Its "LendMe(TM) technology" lets you lend a book to someone else for a maximum of two weeks exactly once. Amazingly this is sold as a feature! What planet are these people living on? My wife and I both enjoyed C.J. Sansom's series of historical novels. If we used ebook readers then we would both have to buy our own copies. And our son is now starting to read my Terry Pratchett books, so make that three copies in some instances.

And then there is the limit on transfers to new devices. It seems from reports on the Web that ebooks can only be transferred to new devices a finite number of times. After that, your books are stuck on your old devices. So as I upgrade and replace my ebook readers over the years, as I am sure I will, eventually I will start having to keep my old readers around or else purchase their content yet again. Also these transfers have to be mediated by the website you bought the ebook from; if they go out of business then your content is stuck.

Of course I could resort to the pirate copies around the Net. It seems like pretty much anything that is available in a DRM version is available unlocked for free. As a test I downloaded a copy of "The Moon is a Harsh Mistress" from one such site, and sure enough I got an unencrypted PDF (which I could read on my Linux box as an added bonus). I don't feel morally obligated to buy a whole new book just to shift formats: I've already paid the author for the words when I bought the dead-tree version. (Or have I? Some of my books were purchased second-hand. Interesting conundrum there.) But such "solutions" are inherently unreliable. I also worry that I will be sucked into a life of copyright infringement; a little demon on my shoulder is asking me, if I'm going to the trouble of locating and downloading a pirate copy to escape the DRM, why bother buying a legitimate copy that I'm never actually going to look at?

The list of things I can't do with a DRM'd ebook grows the more I think about it. As our son grows out of books we have donated the old ones to his school library. I've lent technical books to colleagues. I've bought out-of-print books second hand. I've borrowed books from libraries. My parents read some of our books when they visit. None of these things are possible with ebooks.

So despite all the advantages, I think I'll pass for now. Maybe in a few years the publishing industry will learn the same lessons that the music industry is learning about the futility of DRM and how to price electronic material, and more old books will be digitised. Then I'll get an ebook reader. But not now.

Is this an Arrow II: The Type System Strikes Back!

2010-10-30T02:45:00.000-07:00

In my last post I asked about my EventStream and RTSP types, and asked if RTSP could be an arrow and what the behaviour of "&&&" should be. You can see the first post with the type definitions here. Jason Hart Priestley replied suggesting that "&&&" should be thought of as a join of two computations, which made a lot of sense. So I went with that.

Returning now to the definition of "first", consider:

first ((*2) >>> dup 5)

where "dup 5" emits two copies of every input event, the second one delayed by 5 seconds. So if the input event was [Event t (3, 3)] you would want the output to be [Event t (6, 3), Event (t+5) (6, 3)]".

But suppose that the input had two events like this: [Event t (3,3), Event (t+1) (4,4)]. What should the output be now?

It seems to me that the output of the argument to "first" should be paired with the second value of the events that "caused" those outputs. So the result should be:

[Event t (3,6),
 Event (t+1) (4,8),
 Event (t+5) (3,6),
 Event (t+6) (4,8)]

However to get this you need to have every arrow track the "cause" of every output and tag the event with that information. So you get

type TagEvent t a = (t, Event a)

data EventStream t b c =
   Emit {esEmit :: TagEvent t c, esFuture :: EventStream t b c, esHandle :: RTSP t b c}
   | Wait {esHandle :: RTSP t b c} deriving Show

newtype RTSP t b c = RTSP {runRTSP :: TagEvent t b →  EventStream t b c}

The type "t" indicates the type of the tag for this kind of event. Whenever an arrow emits an event in response to an input then it puts the tag from the input on the output. In the case of "dup" the EventStream it returns from handling a new event will contain both the pending outputs (with the tags from previous input events) and the two new events with tags from the latest input.

So now I can define two functions:

esFirst :: EventStream (d, t) b c → EventStream t (b, d) (c, d)
esFirst (Emit (Event t va, (vb, tag)) es k) =
      Emit (Event t (va, vb), tag) (esFirst es) (rtspFirst k)
esFirst (Wait k) = Wait $ rtspFirst k 

rtspFirst :: RTSP (d, t) b c →  RTSP t (b, d) (c, d)
rtspFirst (RTSP r) = RTSP $ λ(Event t (va,vb), tag) ->
      esFirst $ r (Event t va, (vb, tag))

The second item in the pair (of type "d") gets tacked on to the tag for the whole arrow and re-appended at the end. Problem solved? No.

instance Arrow (RTSP t) where
   arr f = RTSP $ λ(e, tag) →  Emit (fmap f e, tag) (Wait $ arr f) (arr f)
   first = rtspFirst

GHC complains about the infinite type "t = (d, t)". The problem is that the argument to rtspFirst has the type "RTSP (d, t) b c" but it needs to have the type "RTSP t b c". So this version of RTSP isn't an arrow. I have get rid of the type tag "t", but still have some way of having an arrow match causes with effects. Is there some kind of type hackery that will do this?

Is this an Arrow?

2010-10-26T12:42:00.000-07:00

I've been thinking about what a native Haskell middleware would look like for a while. One thing seemed obvious: it was going to have to be event-based. So I started thinking about event
streams.


 data Event a = Event  {
    eventTime :: UTCTime
    eventValue :: a
 } deriving (Show, Eq)

 instance Functor Event where
 fmap f (Event t v) = Event t (f v)

 -- | True if the first event occurs strictly before the second.
 isBefore :: Event a →  Event b →  Bool
 isBefore ev1 ev2 = eventTime ev1

The simplest representation of a stream of events is just an infinite list, so you can define an event processor as a function from one stream to another:


 type EventProcessor a = [Event a] -> [Event a]

Unfortunately this won't work. Suppose that your program is going to emit an event e1 at time t1, but an incoming event before t1 would make your program do something else. In order to decide whether the next item in the output list is e1 you need to look at the time of the next input event. But since that event hasn't happened yet you have to wait for it. If it arrives after t1 then you have missed the deadline.

What is needed is a way to reify the two possibilities here: either the next input event is before t1 or it is after it. This leads to the following data structures:

   data EventStream b c =
    Emit {esEmit :: Event c, esFuture :: EventStream b c, esHandle :: RTSP b c}
    | Wait {esHandle :: RTSP b c} deriving Show
  
 newtype RTSP b c = RTSP {runRTSP :: Event b →  EventStream b c}

The "Emit" case embodies these two possibilities. An interpreter function will process this as follows:

If no input event intervenes then it will emit the event esEmit and call
itself on esFuture.

On the other hand if an input event arrives before esEmit then the function
in esHandle gets called instead, generating a replacement EventStream
representing a different future.

Finally the Wait case allows the event stream to do nothing until an event
arrives.

The RTSP stands for "Real Time Stream Processor". It also handles the problem of what an event stream is supposed to do before the first event arrives.

Interestingly, both EventStream and RTSP are Categories. The composition operator for EventStream is simple in principle, although in
practice all the different combinations of value and timings make it rather fiddly. Here it is,along with a block comment that explains the logic if you are really interested.


  {-
  The (.) operator for EventStream has to deal with several scenarios:
  
  1: (Wait k2)∘(Wait k1).  This is simple because the only possible event
     is an input that is piped through the two RTSPs.
  
  2: (Wait k2)∘es1@(Emit e1 es1a k1).  In this case there are three timelines:
     a) e1   : (k2 e1)∘es1a      -- Event e1 is passed to k2 and the result composed with es1a.
     b) ev e1: (Wait k2)∘(k1 ev) -- e1 never happens.  Instead the input is passed to k1, which
        generates a new event stream to be composed with k2.
  
     The code for case b is the "k" value in the "let" clause.
  
  3: es2@(Emit e2 es2a k2) es1@(Emit e1 es1a k1).  The logic here is similar to scenario
     2, except that the timing of e2 has to be taken into account as well.  There are five basic
     timelines. Let ev = the next input event and es2b = runRTSP k2 e1
  
     a) e2 e1    : Emit e2 (es2a∘es1a) (k2∘k1)
     b) e1 e2    : k2 e1 ∘ es1a    -- e2 never happens because it is overridden by e1
     c) ev ...   : es2∘(k1 ev)    -- ev overrides e1, and the new output is fed to es2.
     d) e1 ev e2 : esProcess (es2b∘es1a) ev  -- e1 overrides e2, giving es1a and es2b to process ev.
     e) e2 ev e1 : Emit e2 (es2a∘(k1 ev)) -- e2 is emitted, then ev overrides e1.
  -}
  instance Category EventStream where
     -- id :: EventStream b c
     id = Wait $ RTSP $ λe →  Emit e id id
  
     -- (.) :: EventStream  c d →  EventStream b c →  EventStream b d
     (Wait k2)∘(Wait k1) =
        Wait $ k2∘k1
     es2@(Wait k2)∘es1@(Emit e1 es1a k1) =
        let es = (runRTSP k2 e1)∘es1a
            k = RTSP $ λev ->
               if ev `isBefore` e1
                  then es2 ∘ runRTSP k1 ev        -- Timeline 2b
                  else runRTSP (esProcess es) ev  -- Timeline 2a
        in case es of
           Emit e2 es2b _ →  Emit e2 es2b k
           Wait _         →  Wait k
     es2@(Emit e2 es2a k2)∘es1@(Wait k1) =
        Emit e2 (es2a∘es1) (RTSP $ λev →  es2∘runRTSP k1 ev)
     es2@(Emit e2 es2a k2)∘es1@(Emit e1 es1a k1) =
        let k = RTSP $ λev ->
               if ev `isBefore` e1
                  then es2∘runRTSP k1 ev          -- Timeline 3c
                  else runRTSP (esProcess es) ev  -- Timeline 3d
            es = (runRTSP k2 e1)∘es1a
        in if e1 `isBefore` e2
           then   -- Timelines 3b, 3c and 3d.  e2 never happens.
              case es of
                 Emit e3 es3 _ →  Emit e3 es3 k
                 Wait _ →  Wait k
           else   -- Timelines 3a, 3c and 3e.
              Emit e2 (es2a∘es1) (esProcess es2∘k1)
            
  -- | Given a new input event to an existing event stream, this returns the
  -- modified event stream.
  esProcess :: EventStream b c →  RTSP b c
  esProcess (Wait k) = k
  esProcess (Emit eOut rest k) = RTSP $ λeIn ->
     if eIn `isBefore` eOut
        then runRTSP k eIn
        else Emit eOut (runRTSP (esProcess rest) eIn) k

And here is the matching RTSP instance:

  {-
  The (.) operator for RTSP has to deal with a similar range of scenarios to that of EventStream.
  The event that fires off the composed stream is e0.  This is passed to r1, giving es1, and the
  first event from es1 is passed to r2, giving es2.  Hence these events must occur in order.  However
  ev is a second input event that can arrive at any time after e0.
  
  The possible timelines are therefore:
  
     1: e0 e1 e2 ev: Emit e2 (es2a∘es1a) _  -- The basic case.  ev is passed to (es2a∘es1a)
     2: e0 e1 ev e2: es2∘es1a               -- e1 has happened, but ev occurs before e2 is emitted.
     3: e0 ev e1 e2: r2∘esProcess es1       -- e1 is overriden by ev.
  -}
  instance Category RTSP where
     -- id :: RTSP b c
     id = RTSP $ λev →  Emit ev id id
     -- (.) :: RTSP c d →  RTSP b c →  RTSP b d
     r2∘r1 = RTSP $ λe0 ->
        let es1 = runRTSP r1 e0
        in case es1 of
           Emit e1 es1a k1a ->
              let es2 = runRTSP r2 e1
                  k = RTSP $ λev ->
                     runRTSP (if ev `isBefore` e1 then r2∘k1a else r2∘esProcess es1) ev
              in case es2 of
                    Emit e2 es2a k2a ->
                       Emit e2 (es2a∘es1a) k
                    Wait k2a ->
                       Wait k
           Wait k1a ->
              Wait (r2∘k1a)

So now we have shown that these two things are both Categories, can we make them Arrows? The Arrow class requires a definition of first with the following types:

  first :: EventStream b c -> EventStream (b, d) (c, d)  
  first :: RTSP b c →  RTSP (b, d) (c, d)

This is where I run into problems. EventStream can't be an Arrow because the first argument might emit a value before any input is received. At this point first is supposed to pair up the output with some other value of type d, but no such value exists. So EventStream can't be an Arrow.

RTSP doesn't have this problem because some value of type d must have been passed in at the start, so this lets us define first. However from a semantic point of view it is not clear how this should deal with delays and subsequent events.

Its easy to write a delay arrow: it simply echoes every incoming event with a fixed delay added to the event time. Other variations on the theme are possible, such as a dup arrow that echoes every input immediately and then again after a fixed delay, or an arrow that echoes every input as a Right value, but also emits a Left timeout value if no input is received after a defined delay. There is clearly a whole family of combinators waiting to be written here. But first things first.

What should first do if its argument is delay 1? Intuitively, first puts the first item of the pair through its argument, but the second argument bypasses this processing. However this would mean emitting one part of the result before the
second. What should it do with dup 1? And what do the answers imply for this
expression?

  delay 4 &&& delay 5

I don't have any good answers. Maybe RTSP isn't an arrow, but that is a real nuisance. Any ideas?

Bilski says software is not patentable

2010-07-08T11:54:00.000-07:00

The US Supreme Court's decision In re Bilski doesn't say much, but I think it says more than perhaps Justice Kennedy intended. In particular I think it is possible to argue that software is not a patentable subject matter.

The Court rejected the "machine or transformation" test as being too narrow; it would seem to exclude things, including business methods, that are "processes" or "methods" under the usual English meanings of those words. But the Court also refers to precedents in Benson, Flook and Diehr (three previous cases), and states that these were used to decide Bilski. It follows that the principles in those precedents are the ones that should generally be applied. Crucially the Court also declined to endorse anything in the State Street decision that originally opened the floodgates to software patents.

The Benson case involved a patent for converting BCD into pure binary. It was held to be an unpatentable abstract idea because the method in the patent was derived from a formula, and so a patent on the method was in effect a patent on the formula.

The Flook case was for a patent on setting alarm thresholds based on a "mathematical algorithm". Again the patent was overturned. In this case a key principle made in the decision was that any mathematical algorithm must be assumed to be "well known". This is a crucial point; a patent can include things that were already known, provided it combines them in a novel way, or with some novel element. The invention has to be considered as a whole, but adding a "trivial post-solution activity" such as setting an alarm wasn't considered to be inventive enough if the formula used was considered to be part of prior art. This means that any "mathematical algorithm" you might come up with is considered as "well known" even if you are the first person to invent it. It can go into a patent, but it doesn't add to the novelty.

Diehr was concerned with a patent for curing rubber. The patent described a machine that measured the mould temperature continuously, pushed the temperature readings through a "mathematical formula" (which was in fact very well known in practice as well as in the narrow legal sense), and opened the mould when the output reached a certain value. The patent was upheld because the novelty lay in the use of continuous measurements to control mould opening, rather than a precomputed delay as had previously been the practice. The fact that a formula was embedded in a computer program as part of the invention did not change this.

So where does this leave software patents? The Court followed the reasoning in the precedents to conclude that since the concept of "hedging" in the Bilski patent was reduced to a mathematical formula in Claim 4, that formula could not be considered a novel contribution. Nothing else in the patent was novel, so they rejected it.

Following this reasoning, it would seem that anything that can be reduced to a "mathematical formula" or "mathematical algorithm" is not patentable. It is possible that Justice Kennedy made a layman's error in his thinking here by assuming that all "mathematical formulae" are concerned with real numbers, as were all the formulae considered in Bilski and the precedents listed.

But of course any computer scientist or mathematician will tell you that this is not true. The whole of discrete mathematics is concerned with mathematical formulae and algorithms that are not related to real numbers.

So it would seem that formulae and algorithms related to discrete mathematics would fall under this rule as well. The Court uses the term "algorithm" and "formula" as synonyms, as indeed they are. To see this, consider the QuickSort algorithm:

If there are only 0 or 1 items in the list to be sorted then stop.
Take the first item from the list of things to be sorted. Call this the "pivot".
Divide the rest of the items into two sublists; (a) those less than the pivot, and (b) the rest.
Apply this whole algorithm to each of the two sublists from step 3, thereby sorting the sublists.
Assemble the sorted list by taking the sorted sublist (a), appending the pivot, and then appending the sorted sublist (b).

This is clearly a method or process. It is also an algorithm. It can also be represented as a formula:

sort [] = []
sort [x] = [x]
sort (pivot:rest) = sort sublistA ++ [pivot] ++ sort sublistB
where (sublistA, sublistB) = partition (< pivot) rest

This is QuickSort written in Haskell. Every Haskell program has a well-defined translation to a formula in the Lambda Calculus, and the Lambda Calculus is part of mathematics. Haskell is turing-complete, which means that any process that can be written as a sequence of steps for manipulating information of any sort can also be written as a Haskell program. Therefore any such process can be reduced to a "mathematical formula". Since mathematical formulae are not patentable subject matter it follows that no process for manipulating information is patentable subject matter.

It might be argued that the use of the modifier "mathematical" by the Court is an attempt to distinguish mathematical formulae and algorithms from non-mathematical ones. But in reality there is no such distinction.

Merriam-Webster defines mathematics as:

the science of numbers and their operations, interrelations, combinations, generalizations, and abstractions and of space configurations and their structure, measurement, transformations, and generalizations

This is a poor definition, since it seems to ignore many topics that are conventionally considered part of mathematics even though they have no apparent relationship to numbers, such as graph theory and topology.
The Britannica is rather more useful, defining mathematics as:

[The] science of structure, order, and relation that has evolved from counting, measuring, and describing the shapes of objects.

It deals with logical reasoning and quantitative calculation. [...]

So is there a class of algorithms or formulae that is not "mathematical" in nature? Clearly not. If any algorithm can be recast as a formula. If such a formula is a product of logical reasoning then it falls under the ambit of mathematics. Even if we take the more limited definition of Merriam-Webster, Godel showed how any logical statement can be recast as a statement of number theory.

Another possible objection to my argument is that mathematics is "abstract" while a process is "concrete". But this is a distinction without a difference. It suggests that the algorithm for QuickSort, expressed as a series of steps, is somehow more concrete than the equivalent formulation in Lambda Calculus. Of course any formulation of QuickSort is going to be longer than the typical single line that non-mathematicians think of when presented with the phrase "mathematical formula", but this would imply that patentability is determined by length, which is clearly nonsense. A mathematical formula that takes a dozen pages to write down is still a mathematical formula.

So I have to conclude that anything capable of being expressed as a computer program is not patentable subject matter under US law.

This probably extends to business method patents as well. Since any business method is the manipulation of information, it follows that it can be written as a computer program (and in fact many Internet businesses have been built by doing exactly that). Even if the business method requires human judgement at some point, that judgement can be treated simply as another input to the program.

To return to where I started, the Supreme Court says that business methods are not a-priori unpatentable, since they are processes and methods. Bilski may not have had sufficient novelty once the formula was stripped out, but the Court wanted to allow for the possibility of a set of business methods that were sufficiently novel. However by following the court's own reasoning it is clear that this set is empty.

How many copies is Jammie Thomas-Rasset responsible for?

2009-07-12T06:31:00.000-07:00

So Jammie Thomas-Rasset did indeed download and share music using P2P. Others have commented on the disproportionate nature of the penalty damages imposed in this case. Here I want to address a narrower question: how many copies should she be charged for?

The RIAA argues that Thomas-Rasset was sharing 1,700 audio files, and that 2.3 million P2P users had access to those files. This is "the equivalent of standing on a street corner with approximately 150 CDs and giving away free copies to anyone who asks".

But clearly Thomas-Rasset didn't actually create 2.3 million copies of those 1,700 files. Even if she had, the people who downloaded the files must share some responsibility, since they actively chose to make copies (unlike Thomas-Rasset, who merely chose to make them available). The RIAA seems to believe that because we don't know how many people actually downloaded these tracks from Thomas-Rasset's computer rather than someone else, that statutory damages are justified.

But this begs an important question: if a million people decide to share and copy some music track over P2P, how many copies do they make? The answer is quite obvious: one million users, one million copies. Nobody is going to fill their disks with thousands of copies of the same song, and even if they did it wouldn't make any difference.

(Actually quite a few users will have also made temporary copies on MP3 players and the like, but since doing that with a CD you own is fair use, that seems pretty irrelevant)

So at most Thomas-Rasset is guilty of having made 1,700 illegal copies of 1,700 songs. The fact that these songs were also available for others to download is irrelevant to the damages argument. Maybe 1,000 people made copies of these songs, maybe none. Civil law (which this is) is based on the balance of probabilities, and on the balance of probabilities the total responsibility of Thomas-Rasset for the copies made by the network of which she was a part is one copy of each song. These songs are sold for download for a dollar each, which suggests that, absent punitive damages, Thomas-Rasset's true liability should be $1,700. Even with triple damages for deliberate actions, that would still only be $5,100.

But of course, this isn't about justice for artists, this is about the business model of the RIAA members.

Vote Windows, for No Tax On Sheep!

2009-06-16T13:06:00.000-07:00

Once upon a time, so I have heard, there was an Australian politician who ran on a platform of "No Tax On Sheep". None of the other candidates would have dreamed of trying to tax sheep. Nevertheless, our hero won by a landslide.

Its a nice trick; claim a common virtue, not because it differentiates you, but because it casts a subtle doubt on whether your competition has the same virtue. It involves no actual lies, and you don't even need to name the competitors; they are all equally suspected, and must either ignore you or issue hasty and unconvincing claims to be just as good.

Advertisers love this one. In advertising "knocking copy" is the term for pointing out the defects in your competition. But blatant knocking copy is usually counter-productive: potential customers see it as mean, and it also carries an implicit message that the product you are knocking is a significant competitor (otherwise why spend money knocking it). But the "no tax on sheep" strategy neatly sidesteps this; you don't name your competitors and you don't say anything bad about them. You merely imply that they are not as good as you.

So its no surprise to see Microsoft using this strategy against Linux. The Microsoft page on Netbooks has this to say on why you want Windows on your Netbook:

For starters, you already know how to use it. Windows also works with more devices and applications, and offers security features to help keep your PC and personal information safe. Here's a whole list of other Windows benefits:
Windows makes your life simpler. Windows is easy to set up and use. You already know your way around, which means you can get started right away and easily find everything you need.
Windows just works with your stuff. With Windows, it's "plug and play"—meaning it works out-of-the-box with your PC applications and peripherals such as printers, digital still and video cameras, music players, and webcams.
Windows gives you peace of mind. Windows comes with features and tools that help keep your family and personal information safe. When you install Internet Explorer 8 as your Internet browser, you get additional built-in security features that help protect against deceptive and malicious websites.
Windows comes with more goodies. With Windows running on your netbook PC, you get access to additional software and services provided for free, like Windows Live services, which help with photo editing and organization, instant messaging, and family computing safety—all of which are just a download away.

I've highlighted the items which (in my opinion) apply to Linux as well. About the only thing I can't honestly claim is the "Windows is familiar" line. I can't deny that if you have only ever used Windows then Linux is going to be a bit different. Its not huge, but there is no point pretending its zero either.

So, I wonder, how could we turn this trick around? What can we say about Linux that casts doubt on Windows? To work, the implication has to be something that is truthy, regardless of how true it actually is. How about:

Won't send your files to the US government. Linux has no stealth functionality, and it wasn't written by people with big Government contracts.
No Blue Screen of Death! Linux was designed to be reliable.
Puts you in charge. You decide what software to install, and if you don't like it you can always remove it.
No extra fees just to get a feature you thought you had already bought.

But of course none of this will work in reality. Deceit of any kind and open source are fundamentally incompatible.

An Optimistic View of Net Neutrality

2009-06-13T09:10:00.001-07:00

The Net Neutrality argument has been puttering along for a few years in the US, and is now starting to get going over here in the UK as well.

On one side are the ISPs, most of whom are telephone and TV cable companies. They are used to being a choke point between the consumer and the rest of the telecoms world, and their managers all have MBAs. The latter point is important because analysing your position in the value chain is a big part of the MBA curriculum, and everyone knows that being a commodity provider is a bad place to be. So the ISPs are desperate to re-establish their choke-hold, which means doing something that forces the other players to treat with them rather than the competition. Hence they want the right to cut deals with, for instance, streaming video providers. If you want to see good quality TV over the Internet from the Foo Video Company, you have to go with an ISP that has a deal with Foo Video, which restricts your choice as a consumer and therefore allows the ISP to charge more. The ISPs also want to charge Foo Video on the grounds that Foo must want its end users to get good quality video and will therefore pay for the privilege.

Everyone else in the value chain (including the domestic Internet users) is up in arms at this prospect for the excellent reason that if the ISPs can capture some of the money flowing around this part of the economy then there will be less for everyone else. They want the ISPs to be required to stay neutral on the grounds that anything else will increase prices (which, from the point of the ISPs, is the point) and restrict new developments because start-up companies won't have the financial and market muscle to cut the necessary deals.

Unlike many commentators I believe that in the long run this argument will be irrelevant, and that whatever various governments do on the subject will make little or no difference, and I believe this because of Metcalf's Law.

Bob Metcalf's original formulation of his law said that the value of a network is proportional to the square of the number of users. In fact that is only true if everyone on the network is equally interested in communicating with everyone else. In reality that isn't true, but whatever the pattern of communication the value of a network still rises more than linearly with its size, which is what matters.

The History of Metcalf's Law 1: Peering versus Transit

Back in the late 1990s there was a big argument over network peering. There were big ISPs and little ISPs. Big ISPs had all the same costs as little ISPs in running points of presence for modem users to phone into, but they also had to run long-haul bandwidth terminated by big routers. A small ISP could hook into this infrastructure just by connecting to a big ISP, which gave the small ISPs a competitive advantage and left the big ISPs without a business case for running that vital long haul infrastructure.

At the time the only kind of connection between two ISPs was "peering", which means that two ISPs share a connection point where they exchange traffic. So the big ISPs implemented a new policy:

Henceforth peering connections would only be made between ISPs the same size, and would only carry traffic bound for customers of the other ISP.
Small ISPs could pay for "transit" connections to big ISPs. A transit connection would carry traffic bound for anywhere.

There was a big argument over this change. Small ISPs complained that this would lead to the "balkanisation of the Internet", by which they meant that customers of ISP X might not be able to communicate with customers of ISP Y. But in practice that didn't happen. The peering/transit distinction continues to be the mechanism by which the Internet is organised commercially, but the Internet was never balkanised because Metcalf's Law meant it was never in anyone's interest.

To see why this is, consider what happens to the value of a network cut in half. If the value of a network is purely proportional to the size then you now have two networks worth half as much each; the total value hasn't changed. But Metcalf's Law says that the position is worse: the total value of two networks is less than the value of one big one.

So the only way to make money from splitting a network in two is by capturing value faster than you destroy it. But there just isn't that much loose value floating around the Internet, and all the companies involved found that they made more money by keeping everyone connected. So they did.

The History of Metcalf's Law 2: Walled Gardens

Another bright idea floating around in the early days of the commercial Internet was the Walled Garden. This was pioneered by Compuserve in the days before dial-up Internet access, but MSN and AOL were created with similar concepts. The basic idea was to provide a premium branded information service that would be exclusively available to dial-up subscribers. Internet access was added by these providers later because their customers demanded it, but the business model was based on selling a value-added subscription information service that would be better than the free Internet.

The whole idea flopped. Not enough subscribers were prepared to pay the premium. The basic problem was, and is, that as soon as you put up a paywall between your content and non-subscribers you split the network in two: there is the bit you own, and the rest of the network. Your bit is very small, and Metcalf's Law says that it therefore has a much lower value. So nobody wants it.

Metcalf's Law and Network Neutrality

So what about the network neutrality debate? If you googled for "balkanise Internet" a few years ago you got lots of articles from the 1990s arguing about ISP peering and transit fees. Today the same search yields just as many arguments about network neutrality.

The ISPs want to create a new version of the Walled Garden: information providers will pay to get better links to their end users, and certain protocols will get higher bandwidth than others. And I believe that this will suffer the same fate as all the other attempts to fight Metcalf's Law. An ISP that places artificial boundaries between Internet users (wherever they fit in the Internet's various value chains) is lessening the value of the Internet as a whole to those users. If they make a significant difference to the user's experience then they are offering less value, and will lose market share as a result. If they don't make a difference then nobody will care. Either way its not a paying proposition.

Therefore network neutrality will dominate because anything else is less valuable, and therefore will drive away customers.

There is one application where non network-neutral services may survive for a while, which is TV over the Internet. A DVD-quality video stream is around 5Mbits/sec, or about 2GBytes/hour, which is a bit too high to just transport over the Internet to a home internet connection. Never mind what happens when two people in the same household want to watch different things. So for a while it makes economic sense for ISPs to cut special deals with TV providers. But that's nothing new: the economic model is identical to cable TV. Existing cable TV companies would probably like to keep it that way, but their power to do so is very limited. Sooner or later some combination of improved ADSL, fibre to the curb/home/street and wireless connections will provide commodity bandwidth high enough to carry decent video, and cable TV companies will cease to exist.

UK to store more "communications data"

2009-05-02T07:38:00.000-07:00

The UK has a rather odd regime for intercepting on-line communications. The law distinguishes between the content of communications and "communications data" (such as a list of the telephone calls you have made). Content cannot be used in criminal investigations, although it is widely believed that the security services intercept a lot of it as part of their general signals intelligence activity. However "communications data" is available to pretty much any part of Government provided that a sufficiently senior person signs off on the request. No warrant is needed.

The UK Government is consulting on proposals to require ISPs to gather and store a lot more "communications data". At present they basically have to take the IP header data: origin, destination, port number and protocol (TCP/UDP). Volumes and times are likely to be recorded, and of course your DHCP lease so that they can tie a physical machine to the IP address. So with this they can see that you browsed http://www.bbc.co.uk, but not what you actually read. But the Government argues that this is increasingly insufficient. If its investigating suspicious activity, such as a big purchase of fertilizer, then it needs to find out who the suspect is communicating with. If the suspect uses an off-shore email service such as Gmail then the existing communications data regime can't get at this.

So the Government's proposed solution is to require ISPs to capture and store more data, including "third party data", which seems to mean anything inside the packets that helps to identify the people you are communicating with.

The problem with this is that its an impossible job. Most stuff that is even vaguely sensitive (like Gmail) is sent using HTTPS as a matter of course. Even if this could be got over, communication data is simply too slippery a concept once you get away from IP headers. For instance, MMORPGs like Runescape and World of Warcraft (and for that matter Second Life) have "chat" facilities that use game location to determine who can "hear" you. Suppose a conspiracy decides to meet at the edge of a forest in Runescape: their location is exactly the sort of communications data that the Government wants to capture. Doing so requires someone to reverse engineer the existing Runescape protocol and then write software to extract just that part of the data. This software would then have to be run by every ISP in the UK, and the whole exercise repeated for every other multi-player game and interactive website.

This would be a huge effort, but it would still fail to capture data about any criminal who had a modicum of technical knowledge, because there are too many options for setting up channels that the Government cannot intercept. For instance encrypted messages could be left as Usenet posts. Freenet exists specifically for avoiding surveillance. And SSH tunnel services can let you use any Internet service without being tracked.

So in effect the Government is proposing a huge technical boondoggle to do the impossible. Not for the first time, and I'm sure it won't be for the last.

My full response is available here in PDF format.

Bruce Sterling accused of sham marriage

2009-04-05T13:10:00.000-07:00

I've just read on Bruce Sterling's blog that he and his Serbian wife have been accused of a "green card" marriage by the US immigration authorities. They basically have a couple of weeks to prove to the authorities satisfaction that their marriage is not a sham. If they cannot do so then Jasmina Sterling (nee Tesanovic) will be deported.

This is wrong on many levels. I've never met them, so I can't comment myself on the reality of their marriage, except to note that Bruce Sterling is a good looking wealthy intelligent over-achieving man, so I can't see that he needs to hire himself out as a husband-of-convenience, nor does it seem likely that he needed to offer a green card just to get a woman into his bed.

(Aside: I also think it truly ironic that an organisation that takes 6 months to decide on a 3-month visitor's visa allows only a couple of weeks for them to put together evidence that their marriage is real).

But US Immigration don't think like that. It seems from what Sterling wrote that they check up on marriages between Americans and non-citizens, and look for the paper trail that would be generated by people living together: joint ownership of homes, bank accounts and the like. And because of their somewhat nomadic existence it seems that Bruce and Jasmina don't have that paper trail.

Students of organisational behaviour will recognise an anti-pattern here, although I don't know if its ever been written down. It looks like this:

Name: Chasing Reality

Context: Enforcement of rules that mandate an ill-defined threshold of performance.

Forces: People attempt to meet the performance threshold with minimum effort. The enforcing authority becomes concerned that their effectiveness is being eroded.

Supposed solution: The enforcing authority requires increasingly stringent evidence of performance. The rules about what is "sufficient" may also be kept secret or poorly defined to prevent people from engineering their evidence to follow the requirements.

Resulting context: the enforcing authority becomes increasingly unable to judge real performance, and instead becomes obsessed with the production of evidence. Success depends more on finding out what the real criteria are and meeting them than on actually performing the original task.

I have seen this pattern before, although never with such horrendous consequences. Some years ago a senior manager told me that he had a set of criteria for any application to spend money, but he would not tell anyone what they were for fear that all the applications would then meet those criteria. When I visited the US many years ago, before the visa waiver programme, I had to provide evidence of solvency to get a visa, but was not told what "evidence of solvency" looked like (I photocopied a year of bank statements; it did the trick).

Mr & Mrs Sterling are apparently required to meet a secret (or at least highly under-advertised) set of criteria for a "real" marriage. When the US first controlled immigration I expect it only had to be a legal marriage, but sham marriages were an obvious problem. So the Immigration people wanted to see wedding photos. So sham couples hired photographers. Then Immigration wanted to see you living together, so sham couples rented apartments. And so it goes on. The Immigration people are on an endless treadmill: whatever evidence they require will be produced, whether by sham couples or real ones. Now its got to the point where the sham couples will actually have better evidence of their reality than real couples, because they are more aware of the need to generate it. Or as Granny Weatherwax once put it, "Things that try to look like things often look more like things than things."

Its also ironic that a writer with a great talent for spotting trends and capturing the zeitgeist should be caught up in exactly the kind of insane socio-political trend that he writes about so entertainingly.

Bad banking drives out good

2009-01-31T01:58:00.000-08:00

I heard this quote from the CEO of Standard Chartered Bank on Radio 4's Today programme this morning, and it summarises the problem very well. (Its also a reference to Gresham's Law.)

Its become a commonplace to simply blame the credit crunch on "stupid, greedy bankers". The trouble is, suppose you were a smart, frugal banker five years ago. Your exceptional brains let you see that subprime self-certified mortgages were a bad idea, and therefore anything built on them was clearly going to collapse. Therefore you weren't going to invest in that part of the market.

The trouble is, you would have had years of below-average results. Your clients and employers would be looking at your competitors and pointing out how bad your results were. Even if your clients were prepared to listen to your explanations, many are under a legal obligation to maximise their investment returns, and their customers will be less sophisticated and correspondingly less willing to listen to complicated explanations about why their pension is so much less than their neighbours.

So you get removed from your job, and someone else is put in who is willing to do what it takes to deliver market returns.

Looked at from an abstract point of view the game resembles a "Tragedy of the Commons". A banker who gets good returns while taking hidden risks is like the commoner who puts an extra cow on the common pasture. He gets richer while all his neigbours get a little poorer. So everyone else is forced to do likewise, even though everyone can see that collectively this is going to lead to ruin. And so the game goes.

The traditional solutions to the Tragedy of the Commons are:

Property rights. Divide up the commons into individual plots and allocate them to the commoners. Failing that, give each commoner a tradeable right to put exactly one cow on the commons.
Regulation. Make a law that each person can only put one cow on the commons.

The question is, how to apply this to the finance industry. In this case cows are equivalent to risk. Banks have had "risk management" departments for years, but risk turns out to be very difficult to measure. Its as if our commoners have invisible cows: verifying the numbers is impossible, although I've previously posted a suggestion for making the cows more visible.

So without this, what can we do to prevent the next big bust? It doesn't look like there is anything. As memories of this bust fade and the people who experienced it retire, a new generation of bankers will come along with a new ingenious method for hiding risk, and once again bad banking will drive out the good until the whole thing collapses once more.

Wikipedia and Britannica are Converging

2009-01-26T11:23:00.001-08:00

Is there a network equivalent of market forces? The crowdsource equivalent (or perhaps generalisation) of Adam Smith's "Invisible Hand"?

When I was in my early teens my school got the new edition of the Encyclopaedia Britannica in over 30 volumes costing around £1,000. It was a huge wealth of authoritative information on just about everything. I spent quite a few lunch hours just reading about stuff.

In the 90s Microsoft bought out Encarta on CD-ROM. It was a lot less information, but it cost a lot less than £1,000. Britannica has been in trouble ever since. Now there is Wikipedia, which is free, a bit less authoritative than Britannica, but has even more information and a great deal more mindshare.

So Britannica has responded by taking a page out of Jimbo Wales's book; its going to start accepting user-generated content, albeit with a stiff editorial barrier to acceptance into the core Encyclopaedia.

Meanwhile the latest controversy on Wikipedia is about whether user-generated content needs more controls. I say "more" because Wikipedia has always had some limits; locked pages, banned editors, and in extreme cases even the deletion of changes (as opposed to reversion, which preserves them in the page history). Increasingly sophisticated editorial policies have been put in place, such as "No Original Research" (originally put in to stop crank science, but now an important guiding principle).

When you look at Wikipedia's history there is a clear trend; every so often Wikipedia reaches a threshold of size and importance where its current level of openness doesn't work. At this point Jimbo Wales adds a minimal level of editorial control. Locked pages, for instance, were added because certain pages attracted unmanageably high levels of vandalism.

It seems that Wikipedia and Britannica are actually converging on the same model from different ends of the spectrum: Wikipedia started out completely open and is having to impose controls to manage quality. Meanwhile the Britannica started out completely closed and is having to allow in user-generated content because comissioning experts to write it is too expensive. Somewhere in the middle is a happy medium that gets good quality content without having to charge subscribers.

Not charging is important. In these days of the hyperlink, an encyclopedia is not just a source of knowledge, it is a medium of communication. If I want to tell people that they should read about the history of the Britannica then I refer to the Wikipedia page because very few people who read this are going to be able to follow a link to a Britannica article (even if I were a subscriber, which I am not).

Wikipedia is often said to have been inspired by the "open source" model in that anyone can edit Wikipedia just as anyone can edit the Linux source code. In fact the cases are not parallel. The GPL allows me to download a copy of the Linux source code, hack it to my heart's content, and give copies of my new version to anyone who wants them. What it does not do is authorise me to upload my version to kernel.org and pass it off as the work of Linus Torvalds. Getting my changes into the official kernel means passing through a strict quality assurance process including peer review and extensive testing on multiple architectures.

So I think that this proposal to create "flagged revisions" for editorial review moves Wikipedia towards the open source model rather than away from it. Anyone will always be able to fork Wikipedia if they wish: the license guarantees it. But the offical version at wikipedia.org will earn increasing trust as the quality assurance improves, just as the official version of the Linux kernel is trusted because of its quality assurance.

The next challenge for Linux

2009-01-21T11:23:00.000-08:00

I was in the local branch of "Currys" (UK electrical and electronic goods chain) recently and had a look at the line-up of computers. They had some little netbooks, and taped next to each one was a little note saying something to the effect of "This runs Linux, so it won't run Windows software". It was a local version of a wider story about Linux:

People buy netbooks and then discover that Windows isn't part of the bundle, and they don't like it.

A teacher found a student handing out Linux CDs and accused him of pirating software.

A student accidentally bought a Dell laptop with Ubuntu instead of Windows, and complained that she couldn't submit the Word documents required by her college (they say they are happy to accept OpenOffice.org documents) and the installation CD for her broadband service wouldn't install so she couldn't get the Internet (Ubuntu connects to the Internet just fine without it). The local TV station picked up the story as a "consumer rights" case and was amazed to find a virtual lynch mob chasing them for being less than enthusiastic about Ubuntu. They quoted an expert saying that Ubuntu "isn't for everyone" and is more suited to tinkerers than people who just want to get stuff done.

Behind all this is what "everyone knows" about computers (everyone who isn't interested in computers for their own sake, that is):

There are two sorts of computers: Apple Macs, and PCs.
Apple Macs run Apple software. PCs run Windows software.
Windows is bundled with PCs. On expensive PCs the bundle might include Office as well.
If you want extra software, you buy it at a store, take it home and stick the CD in the drive.

This is how its been for almost 20 years (25 if you count the MSDOS era). An entire generation has grown up knowing that if its a PC, it runs Windows. They know it in the same way they know the sky is blue: its always been blue.

Of course those of us who use Linux know different. But for most people, Linux is something they might have heard about once or twice, but they didn't pay any attention and couldn't tell you anything about it. Outside its current user base and their immediate circle of friends and family, Linux has zero mindshare.

This is not another lament about Joe Sixpack being too stupid to understand Linux. The problem is not that Linux is too complicated, its that Linux and Windows do things differently. Imagine someone who was raised on Linux; how would they react to Windows? Software installation would seem complicated and geeky, the single desktop would feel claustrophobic, and as for the idea of paying for software...

So I think we need to sort out a message to broadcast to the world and then focus on it. I suggest the following:

Linux is an alternative to Windows and Apple. It comes in several flavours.
Linux isn't easier or harder than Windows, but it is different, and it takes a while to get used to those differences.
Linux is bundled with a huge range of downloadable free software, including office, graphics and photographic packages.

So next time you see a story that misrepresents Linux please send a correction with these three points.

Where did all the money go?

2008-12-14T12:48:00.000-08:00

I've got a simple question about the Credit Crunch? Where did all the money go?

I've always thought of money as something that is "conserved" in the physics sense, like energy. Money in = money out + money stored. So when someone "loses" money it implies that someone else got it. If I run a company that loses money, what it means is that I'm getting less money in than I'm spending on staff and supplies. But the money hasn't disappeared, its just moved from my pockets to my suppliers (and their suppliers, and so on).

But the financial institutions seem to have had billions of dollars disappear into thin air. They got poorer, sometimes so poor that they went bust, but nobody seems to have become correspondingly richer.

I guess this has something to do with fractional reserve banking, which I know doesn't conserve money. Suppose I start with £1000 and put it in a bank. The bank shows a balance of £1000, but it doesn't just hang on to my money, it loans £500 of it to Joe Bloggs, who spends it on a new TV, and the person who sold the TV also puts the money in the bank. So now the bank has $1,500 on deposit even though our imaginary economy just started with £1,000. So what happens if Joe can't pay the money back?

Can someone enlighten me?

Fundamentalist terrorist assassination plot defeated

2008-11-05T13:18:00.000-08:00

Tonight the British people celebrate the defeat of a terrorist assassination plot. A group of disaffected men, followers of a foreign religion and egged on by propaganda from overseas and a radical cleric, planned a spectacular atrocity: they would blow up the entire government in one huge explosion. The plot was foiled by the security services, who, responding to a tip-off, mounted a surveillance operation and arrested one of the plotters red handed as he prepared to detonate the explosives. The rest of the gang were tracked down and shot or arrested when soldiers stormed their hideout. In accordance with an executive order from the head of state the survivors were subsequently imprisoned, tortured, and executed after a show-trial.

This happened over 400 years ago, on November 5th 1605. The plotters were Catholics rather than Muslims, but apart from that the story sounds disconcertingly modern, although we tend not to go in for show trials these days: they went out of fashion with Stalin.

Today the Gunpowder Plot is celebrated as Bonfire Night: Guy Fawkes (the one caught with the explosives) is still burned in effigy, and in some places the Pope gets the same treatment as well. However, over the past 400 years the anti-Catholic content has almost entirely leached away: now its just an excuse to let off some fireworks. A Catholic can join in the celebrations just as I (a Briton) joined in the 4th of July celebrations when I was living in the US.

Maybe one day we will look back on 9/11 the same way. I certainly hope so.

Petition on Broadband Advertising

2008-10-28T13:47:00.001-07:00

I've become rather depressed about broadband advertising. I found it very difficult to discover the web page describing my own ISPs traffic policy. Furthermore if you compare it to this version from January on the Wayback Machine you can see that the headline speed on the "Large" package has gone up from 4Mbit/sec to 10Mbit/sec, but the evening download limit has merely increased from 800MB to 1,200MB, while extra restrictions have been added starting at 10am as well. Somehow that 10MBit/sec upgrade doesn't feel so generous now: when I want to install Fedora 10 I'd better make sure I schedule the download to start after 9pm.

Virgin Media, in common with most other ISPs, says that the few people who make heavy use of their broadband link reduce capacity for everyone else, and that providing truly "unlimited" service for these few would mean higher bills for everyone. They do indeed have a point. If I want truly unlimited service then I'm sure I can get it, for a price. And the fact is that I probably don't want to pay the price. The occasions when I do want a multi-gigabyte download are sufficiently rare that I can put up with scheduling around Virgin's traffic limits.

So why am I depressed about it? Its because my problem with finding Virgin Media's traffic management policy is not unusual. A sample taken from Google found:

TalkTalk have a 40GB monthly limit right up there on the front page, although I'm not sure if you can find out how much of your limit you have used this month. What happens when you use it all? Presumably you are cut off until next month.

O2 claims "unlimited" usage, but if you search the site for the word "unlimited" you find that excessive use at peak times will lead to warnings and then account termination. They don't define "excessive" or "peak time". I couldn't find a link to this information from their list of broadband features; it certainly wasn't obvious.

Tiscali have a similar policy, except that after three warnings they limit your peak time speed. They also don't define what "excessive" and "peak time" mean, and they don't say how long this will last or what the speed limit will be. This page was two not-very-prominent links away from the package features list.

Fast actually sells a range of monthly capacity limits. They warn you by email when you hit 90%, and when you go over 100% they throttle you down to 100kBit/sec. Full marks!

So out of 5 providers (including Virgin) we have only one that makes all the limits and policies clear up-front while three try to hide behind weasel words and hard-to-find web pages. This makes it difficult for consumers to figure out what they are buying. Is Tiscali's unstated policy better or worse value for money that one of the Fast packages? Even if its better at the moment, will it still be so next month? As a consumer I have no way of knowing. Worse yet, if I were a technically naive consumer I might not even realise that the question needed asking. "Unlimited" sounds much better than "40Gb monthly limit".

I think that something needs doing about this. However the Advertising Standards Authority have wimped out: they have declared that "unlimited" actually means "95% of users don't hit the limit in any given month". So its hardly surprising that people are confused.

Therefore I have started an on-line petition at the Number 10 web site. If you are a British citizen or resident then I urge you to sign it. The petition calls on the Government to require ISPs to make all caps and limits on their services a prominent part of their advertising. Only when they do so will consumers have a clear choice between different packages.

SSDs and the return of the root partition

2008-10-26T14:07:00.000-07:00

Back in the days when Unix was new to the world computers came with two sorts of mass storage: fast-small-expensive, and slow-big-cheap. A minicomputer typically had one of each, so that frequently-used files could be kept in the fast unit while everything else was kept on the slow one.

Unix was designed with this in mind, which is why to this day most programs on Unix and Linux are found in one of two directories: /bin holds the frequently used ones, and /usr/bin holds the less frequently used ones. A similar arrangement applies to libraries, which are held in /lib and /usr/lib. The idea was that the "root" partition was put on the fast small device, and the "user" partition went on the big one. This led to some other restrictions as well; /bin and /lib together have to have all the software needed for a minimally functioning system, because until all that stuff is going the system can't mount /usr to get at the rest of it.

All that became irrelevant in the age of the Linux PC because the entire system hung off one physical disk. But maybe that is about to change. Solid State Disks (SSDs) are entering the disk world. They have zero mechanical latency and their read speed is blisteringly fast. Write speed is more variable, but the new Intel product is reported to be very fast. It is also small (80GB) and expensive ($600).

So it looks like the time has once again arrived for keeping the commonly used programs and libraries on a small fast disk and everything else on something big and slow. The original root versus /usr division doesn't work for this of course: people want the system to fire up X windows, KDE or Gnome and a bunch of apps, not just a shell prompt. But all of those things will fit very nicely onto one of these SSDs. Better yet, the user files have now been shifted out from /usr (from which it got its name) and put in /home. So this needs zero surgery to the standard Linux layout.

For the average user $600 is a bit steep though. What is actually needed here is something smaller and cheaper. I run a well-populated version of Fedora, and my root partition with all the Fedora packages is under 10GB. So I while I can't imagine blowing $600 (or whatever that is in £s these days) on 80GB of SSD, I could certainly imagine putting a 10GB version in for $100. That would hold the Linux kernel, X Windows and all the apps, with enough room left over for /etc. That would increase the speed of booting up, logging in and starting applications without greatly increasing the cost of the system, especially since that often involves reading lots of different files scattered around the disk. Even better, most of this stuff is only written rarely, and then mostly in the background by system updates. So the current poor write performance of most SSDs doesn't matter.

(Update: I have of course forgotten that by default Unix and Linux keep track of the access time (atime) of files, which means that every time you read something a little metadata write happens. So write performance does matter here).

Looking around, the nearest product to this specification seems to be the OCZ 32GB unit, which retails for a bit over £100 (say, around $170). Thats bigger and more expensive than what I want, but hey, Moore's Law seems to be working so I'll just wait a bit. I also note that all these products seem to be targetted at the laptop market, which makes sense given SSDs other advantages of low power consumption and physical robustness. Maybe they should start thinking about the market for hybrid desktop systems as well.

Why the banks collapsed, and how a paper on Haskell programming can help stop it happening next time

2008-09-23T12:12:00.000-07:00

Trading Risk

The financial system exists to trade three kinds of thing: money, commodities and risk. Money and commodities are the easy bit. Either I have £1,000 or I don't. Similarly with commodities: either I have a barrel of oil or I don't. But risk is a very different matter. In theory risk is easy to quantify: just multiply the probability of something by the cost, and you have the expected loss. But in practice its not so simple because the probability and cost may be difficult to quantify, especially for rare events (like, say, a global credit crunch). Many of the factors that go into a risk model are subjective, so honest people can have genuine disagreements about exactly what the risk is.

The Slippery Slope

Unfortunately risk assessment is not value-neutral. Risk has negative value: you have to pay people to take it off you. The higher the risk, the more you have to pay. And because the amount of risk is always debatable this is a very slippery slope; the people paying others to take the risk away have every incentive to present a lower estimate. Everyone can see that everyone else is doing the same, and so methods of hiding or downplaying risk migrate from dodgy dealing to open secret to standard practice.

Specific examples abound throughout the recent history of the finance industry;

The retail mortgage houses that originally lent to "sub-prime" clients would hire valuers who were known to be on the generous side with their valuations. So any valuer who wasn't so generous found their income drying up. Background checks on clients were cut back, then eliminated. Eventually borrowers were simply told what income to claim on the forms, regardless of what they actually earned.
These loans were then bundled up and sold. The idea was that the buyers would each get a share of the incoming loan repayments. Rights to this stream of money were divided into "tranches", the idea being that, for instance, Tranche 1 would get the first 34% of whatever money was due, Tranche 2 would get the next 33%, and Tranche 3 would get the last 33%. When some borrowers defaulted (as some always do), Tranche 3 would lose out first, then Tranche 2. Tranche 1 would only fail to get all their money if the overall repayment rate fell below 34%, which had never happened. The game here was to persuade a credit rating agency that Tranche 1 was so safe that it was worthy of a "Triple A" rating, because that meant that banks, insurance companies and similar big financial institutions could legally buy this debt without having to put cash aside to cover potential losses. The rating agencies earned fees for evaluating securities, so just like the house valuers they found it paid to be on the generous side.
All these institutions had risk management departments who were supposed to watch out for excessively risky behaviour. But in practice they found it very difficult to blow the whistle. Risk managers tell stories of being given two days to review a deal that took ten people a month to negotiate, and of accusations of "not being a team player" when they questioned over-optimistic claims. This story from the New York Times has some details. Look through the comments after the story as well; many of them are by people with their own tales of risk.

None of this is new; similar behaviour has contributed to past financial crises. In theory more regulation can prevent this, and everyone is now planning or demanding lots more regulation (even the banks). But in practice regulation has failed repeatedly because the regulators always concentrate on the way it went wrong last time. Regulations have to be written carefully, and the companies being regulated have to be given time to understand changes and put their compliance mechanisms in place. This prevents regulators from moving as fast as the institutions they regulate.

The regulators also don't have visibility of the information they need to assess systemic risk. Systemic risk arises because financial companies are exposed to each other; if one institution fails, others have to write off any money it owed them, possibly pushing them into bankruptcy as well. Regulators try to make companies insulate themselves by avoiding excessive risk and keeping some cash on hand, but without a clear picture of the risks being run by each company they have no way to tell if this is enough.

The basic problem, I believe, is the food chain of risk management within each institution. At the top are the negotiators and fund managers who design and package the securities. Then the lawyers are bought in to specify the precise terms of the deal. Somewhere along the way the "quants" will be asked to develop mathematical models, and at the bottom coders will be given the job of turning the models into executable code that will actually determine the real price and risks. It is this food chain that needs to be rethought, because its hiding important information.

This 2000 paper by Simon Peyton Jones, Jean-Marc Eber and Julian Seward shows a way forwards. It describes a Domain Specific Language embedded in Haskell for describing the rights and obligations imposed by a contract. Arbitrarily complicated contracts can be built up using a small collection of primitives. Aggregations of these contracts can also be created, as can risks of default and bankruptcy. This created quite a stir in the quantitative analysis world when it was presented, as it was the first time anyone had proposed a formal language for describing contracts. Today the list of commercial Haskell users includes a number of financial institutions using this kind of technique to model their market positions.

But on its own this is just a faster and more efficient way of getting the same wrong answer. It doesn't solve the underlying problem of concealed systemic risk. The solution has to be for big financial companies to reveal their positions to the regulators as formal models of the contracts they have written. At the moment they don't even have to reveal all their contracts, but merely knowing the legal terms of a contract is only the first step. Those terms have to be converted into a mathematical model. That model probably already exists, but only as an internal artefact of the parties to the contract. What ought to be happening is that the contract is specified in a well-defined mathematical language that can be converted into a model automatically. If the regulators have this information about all the contracts entered into by all the finance companies then they can model the impact of, say, a downturn in the housing market or a jump in the price of oil, and if they see systemic risk looming then they can order the companies involved to take corrective action. Unlike the various Risk Management departments they will be able to see the whole picture, and they don't have to worry about being "team players".

ISPs and Bandwidth

2008-09-07T05:26:00.000-07:00

This Slate article reminded me of some stuff about how the Internet works that isn't widely appreciated. For a few years now ISPs have been complaining about "bandwidth hogs" while at the same time advertising high bandwidths for fixed prices. Comcast has had its knuckles rapped for discriminating against particular traffic. But this hides the real issues, which are to do with the structure of the market for long-haul infrastructure.

Your ISP has to pay for connection to the Internet in exactly the same way that you do: it pays a big telecom company like AT&T or Qwest. The only exception is if your ISP is one of those companies, but even then the retail ISP business will be a separate division that has to "buy" bandwidth from its parent. These "tier 1 ISPs" don't publish price lists, but the general pricing structure looks a lot like the ones described in the Slate article, and for the same fundamental reason: capacity is limited. So your local ISP may buy, say, 1 terabyte per day upstream and 2 terabytes downstream, with any traffic over those thresholds being charged per megabyte.

Aside: Actually the whole thing is much more complicated: a retail ISP will generally buy connections to more than one upstream ISP, which may be either tier 1 or "tier 2" (with long-haul bandwidth but not global presence). Often it will have multiple connections to each of these ISPs, each of which may have different price plans. Any ISP may also have "peering" agreements with other ISPs of the same size. These are free, but are not allowed to carry "transit" traffic destined for anywhere else. Everyone always tries to offload traffic onto someone else as fast as possible, even if the resulting routes are not ideal. Managing this mess to keep the customers happy at minimum cost is a key skill in the ISP business

The retail ISPs are therefore caught between a rock and a hard place. They are in a commodity business, but the traditional retail price plan of "all you can eat at a given bandwidth" doesn't match their cost structure. Its a general rule that if you are in such a market and have a competitor who's price plan does match their cost structure then you are bound to make a loss, because the customers who find you cheaper are going to be the ones who cost you more than they pay, while the ones who would balance this by paying more than they cost find your competitor cheaper, so they go there instead.

Thus ISPs will gradually converge on pricing plans that are simplified versions of the cost structure of their industry. This will probably be based on a combination of peak-time limitations and traffic caps that give people an incentive to shift their heavy usage off-peak. The winners will be the ones who can innovate. The challenges are:

At any given point in time the network has a fixed bandwidth. Hence the challenge is not to reduce the total amount of data moved but to even out usage. Similarly heavy users are only a problem when they start pushing out other customers who might collectively pay more.
You can't force users to track their usage in detail. Price plans that suddenly cut a customer off until tomorrow (or next month) are scary and unfriendly. Plans that charge extra for heavy usage are even worse, especially for families with teenagers. Throttling is more user-friendly.
Negotiate with your upstream ISPs to bring your costs into line with your pricing structure. They, too, need to shift usage off-peak and will be prepared to offer pricing plans accordingly. However their idea of "off-peak" may not be the same as a retail ISP with lots of home users.
Transparency will happen whether you want it to or not. At least some end users are smart enough to detect traffic shaping and other tricks, and their results will be picked up by price-comparison sites for everyone else to read.

Application-specific traffic shaping (as tried by Comcast) won't work. Customers and regulators both hate it, but more importantly it gets you into an arms race between stealth P2P protocols and your packet inspection software that you can't win. However there is another option: offer your customers the opportunity to do their own traffic shaping. For instance you could have a metered high-priority service for everyday browsing combined with an unmetered low priority service for bulk downloads. The challenge is to give the customer a simple easy-to-use system that distinguishes between the two and (automatically as far as possible) uses the right one.

In many ways the situation reminds me of 1997, when large ISPs first started to deny peering agreements to smaller competitors and made them pay for transit agreements instead. There were many calls to ban the practice, and grave predictions of the "balkanisation of the Internet". But in practice the economics of Metcalf's Law guaranteed that a well-connected network would have more value than a disconnected network, and after that it was just a matter of how that extra value was distributed. I believe that much the same thing will happen with bandwidth. The Internet has most value when its pipes are full of traffic, and if there is demand for more bandwidth then there will be money to be made by providing it. After that, its just a matter of working out who pays how much for what. As long as the market remains competitive it will converge on the optimum solution, probably quite rapidly.

The Netwise Kids of Today

2008-08-03T07:45:00.000-07:00

My son is keen on Habbo (a virtual world ostensibly aimed at teenagers, but probably attracting a lot of pre-teen kids), and spends quite a bit of his pocket money on it. We regard Habbo as a cynical method of separating kids from their money. Lack of credit cards isn't a problem as you can buy Habbo credits using a mobile phone. However we also regard that "I've just blown all my money on this junk" moment as a valuable learning experience, so we've let him take his pocket money in the form of Habbo credits bought with my Visa card.

This being the Internet, a wide range of scams have appeared trying to separate kids from their virtual "furni" bought with Habbo credits. I'm not going to link to any directly because I suspect that they will be too short-lived, but a search for "Habbo cheat" turns up a good selection. Warning: turn your browser up to maximum paranoia before visiting any of these sites.

My son told me enthusiastically about one of these sites that promised lots of free stuff. He just had to fill in his Habbo username and password on a form, and come back in 24 hours. I was horrified. But no, my son reassured me, he had created a new empty Habbo account just for this experiment, so if it was a scam he wouldn't lose anything. (Sure enough, he didn't gain anything either).

I had never told him about throw-away accounts. I had told him that the Internet is not always a friendly place, but I had not expected him to personally be the target of an attempted fraud. Still less did I expect him to identify the fraud and devise a work-around. There are adults who are dumber than this. However I'm not posting this to boast about my clever son, because I've since found out that this is actually fairly typical. The kids round here generally have Net access, either in their own homes or via a friend. They play in a wide variety of virtual worlds. They have learned, sometimes the hard way, about password security, how and where to write down account details so you don't forget them, not letting people "shoulder surf", and how to recognised various forms of fraud. They talk about this stuff, exchanging war stories and security tips.

Internet crime is still enjoying its boom years at the moment. The archetypal victim is too computer-clueless to even understand what malware is, never mind defending against keylogging viruses or spotting phishing websites. There are still many such people, but the next generation is growing up too Internet-savvy to be easily scammed. They can list different categories of malware and describe their uses and how to defend against them. They have grown up surrounded by the Internet, so taking measures to protect themselves from its hostile elements strikes them as entirely normal. As they grow up they will take this attitude, and the associated knowledge, for granted. My generation taught its parents how to program their video recorders. The next generation is going to teach its parents how to secure their computers.

Rate Cap Revisited

2008-07-12T02:24:00.000-07:00

In my last post I complained that I was being rate capped by Virgin Media. I said I didn't mind them having a capping policy, but it ought to be public. I also complained I wasn't getting the full bandwidth I was paying for.

Turns out I was wrong on both counts. Their rate capping policy is here. I did look for it before posting, and it could be easier to find. But its there, its public, and it says everything I would expect it to.

As for bandwidth, the "Large" package I am signed up for was originally for 4 Mbits, which is what I am getting. Virgin are currently upgrading their network to give everyone 10Mbits, and my region is due to be upgraded this month. However new customers get the full 10Mbits wherever they are. I just looked at their headline offer and assumed it applied to me as well.

So, I no longer have any issues with Virgin Multimedia.

Rate Capped

2008-07-05T05:37:00.000-07:00

This is a screenshot from KDE System Guard showing my download speed for the Fedora Core 9 distribution DVD, around mid-day on Saturday. After downloading 1.8GB I was suddenly slapped down to 100 kBytes/sec, which translates to around 1 Mbit/sec with all the packet overhead. This happens consistently with various download sites, so I'm confident its my ISP.

I'm paying Virgin Media for their "Unlimited" 10Mbit service (although I haven't seen anything over 500 kBytes/sec, which would mean around 5Mbit in reality). I was never told that my download rate would be capped, although the fine print in the sign-up page points to their AUP, which says in Section 7 that they reserve the right to restrict Internet services in any way at any time.

However this post is not actually a complaint about rate capping. ISPs are there to make money by providing a service, and as a rule you get what you pay for. In theory if I want a better service all I have to do is switch ISPs, and possibly pay more money. Our email address is routed through a domain I personally own, so we don't even have to tell anyone else that our household has switched ISPs.

But how do I know that I'll get a better deal if I go elsewhere? All retail ISPs offer basically the same terms, which consist of a big headline rate accompanied by a fine-print disclaimer pointing out that you might never get it. If they have a rate-capping policy they certainly don't advertise it.

I don't actually want a faster headline speed (although I'd be very happy to get the one I'm currently promised). I don't even want a promise of "no rate caps": the ISP argument that heavy downloaders hurt responsiveness for all users is valid. All I want is to be able to look at ISP adverts and figure out where the best value for money is. That means the following information:

Ratio of customers to actual incoming bandwidth.
The rate-capping policy: e.g. capped rate and criteria for applying it.

Anybody know a UK ISP that actually provides this?

Is Functional Programming the new Python?

2008-05-09T09:52:00.000-07:00

Back in 2004 Paul Graham wrote an essay on the Python Paradox:

if a company chooses to write its software in a comparatively esoteric language, they'll be able to hire better programmers, because they'll attract only those who cared enough to learn it. And for programmers the paradox is even more pronounced: the language to learn, if you want to get a good job, is a language that people don't learn merely to get a job.

Some tentative support for this theory comes from a study of programming languages done in 2000. The same task was given to over 80 programmers. The chart shows how long they took. Obviously the average for some languages was a lot less than for others, but the interesting thing for the Python Paradox is the variability. Java had huge variability: one developer took over 60 hours to complete the task. Meanwhile the Python developers were the most consistent, with the lowest variance as a percentage of the mean. I suspect (but can't prove) that this was because of the kind of programmers who wrote in Java and Python back in 2000. Java was the language of the Web start-up and the dot-com millionaire, but Python was an obscure open source scripting language. The Pythonistas in this study didn't learn it to get a job, but many of the Java programmers did.

But if this study was repeated today I bet the spread for Python would be a lot larger. Maybe still not as big as Java, but more like C++ or Perl. Because today you can get a good job writing Python. A quick check of jobs on dice.com found 1450 Python jobs against 7732 C++ jobs and 15640 jobs for Java. Python hasn't taken over the world, but the jobs are there.

So the smart employers and developers need something new to distinguish themselves from the crowd, and it looks like functional programming might be it. Programming Reddit carries lots of cool stuff about Haskell, and job adverts are starting to list a grab-bag of functional languages in the "would also be an advantage" list. For instance:

- Programming experience with more esoteric and powerful languages for data manipulation (Ruby, Python, Haskell, Lisp, Erlang)

So it looks like the with-it job-seekers and recruiters may be starting to use functional programming to identify each other, just as they used Python up to 2004.

Update: Oops. I just remembered this post which started me thinking along these lines.

An Under-Appreciated Fact: We Don't Know How We Program

2008-05-04T23:50:00.000-07:00

I was talking to a colleague from another part of the company a couple of weeks ago, and I mentioned the famous ten-to-one productivity variation between the best and worst programmers. He was surprised, so I sketched some graphs and added a few anecdotes. He then proposed a simple solution: "Obviously the programmers at the bottom end are using the wrong process, so send them on a course to teach them the right process."

My immediate response, I freely admit, was to open and shut my mouth a couple of times while trying to think of response more diplomatic than "How could anyone be so dumb as to suggest that?". But I have been mulling over that conversation, and I have come to the conclusion that the suggestion was not dumb at all. The problem lies not with my colleague's intelligence but in a simple fact. It is so basic that nobody in the software industry notices it, but nobody outside the industry knows it. The fact is this: there is no process for programming.

Software development abounds with processes of course: we have processes for requirements engineering, requirements management, configuration management, design review, code review, test design, test review, and on and on. Massive process documents are written. Huge diagrams are drawn with dozens of boxes to try to encompass the complexity of the process, and still they are gross oversimplifications of what needs to happen. And yet in every one of these processes and diagrams there is a box which basically says "write the code", and ought to be subtitled "(and here a miracle occurs)". Because the process underneath that box is very simple: read the problem, think hard until a solution occurs to you, and then write down the solution. That is all we really know about it.

To anyone who has written a significant piece of software this fact is so obvious that it seems to go without saying. We were taught to program by having small examples of code explained to us, and then we practiced producing similar examples. Over time the examples got larger and the concepts behind them more esoteric. Loops and arrays were introduced, then pointers, lists, trees, recursion, all the things you have to know to be a competent programmer. Like many developers I took a 3 year degree course in this stuff. But at no point during those three years did any lecturer actually tell me how to program. Like everyone else, I absorbed it through osmosis.

But to anyone outside the software world this seems very strange. Think about other important areas of human endeavor: driving a car, flying a plane, running a company, designing a house, teaching a child, curing a disease, selling insurance, fighting a lawsuit. In every case the core of the activity is well understood: it is written down, taught and learned. The process of learning the activity is repeatable: if you apply yourself sufficiently then you will get it. Aptitude consists mostly of having sufficient memory capacity and mental speed to learn the material and then execute it efficiently and reliably. Of course in all these fields there are differences in ability that transcend the mere application of process. But basic competence is generally within reach of anyone with a good memory and average mental agility. It is also true that motor skills such as swimming or steering a car take practice rather than book learning, but programming does not require any of those.

People outside the software industry assume, quite reasonably, that software is just like all the other professional skills; that we take a body of knowledge and apply it systematically to particular circumstances. It follows that variation in productivity and quality is a solvable problem, and that the solution lies in imposing uniformity. If a project is behind schedule then people need to be encouraged to crank through the process longer and faster. If quality is poor then either the process is defective or people are not following it properly. All of this is part of the job of process improvement, which is itself a professional skill that consists of systematically applying a body of knowledge to particular circumstances.

But if there is no process then you can't improve it. The whole machinery of process improvement loses traction and flails at thin air, like Wiley Coyote running off a cliff. So the next time someone in your organisation says something seemingly dumb about software process improvement, try explaining that software engineering has processes for everything except actually writing software.

Update: Some of the discussion here, and on Reddit and Hacker News is arguing that many other important activities are creative, such as architecture and graphic design. Note that I didn't actually mention "architecture" as a profession, I said "designing a house" (i.e. the next McMansion on the subdivision, not one of Frank Lloyd Wright's creations). People give architects and graphic designers room to be creative because social convention declares that their work needs it. The problem for software is that non-software-developers don't see anything creative about it.

The point of this post is not that software "ought" to be more creative or that architecture "ought" to be less. The point is that we need to change our rhetoric when explaining the problem. Declaring software to be creative looks to the rest of the world like a sort of "art envy", or else special pleading to be let off the hook for project overruns and unreliable software. Emphasising the lack of a foundational process helps demonstrate that software really does have something in common with the "creative" activities.

Things I'd Put in Room 101

2008-03-29T13:15:00.000-07:00

Room 101 was a BBC TV series named after George Orwell's torture chamber in the book 1984. In it a guest would explain to a regular presenter why s/he wanted to consign half a dozen pet hates into oblivion. Since the series has now ended I no longer have any hope of explaining to the British Public my pet hates, so I thought I'd do it here instead.

One and Two Pence Pieces ("Coppers")

When the UK switched to decimal currency from pounds, shillings and pence (12 old pennies to a shilling, 20 shillings to a pound) the smallest of the new coins was the half penny piece, which was finally withdrawn in 1984 as inflation had made it unnecessary (the UK saw inflation pass 20% during the 1970s). Since then inflation has been lower, but its still there. The copper-coloured 1p and 2p coins have lost about half their value since 1984. Today their only use is as change for something costing £1.99. Since many things cost a penny under a round amount to prevent staff theft and make prices look lower, my wallet fills up with these big, unwieldy, almost worthless bits of metal. Eventually you accumulate enough of them to give £2.09 to a shop assistant and get 10p change instead of 1p. You often get a grateful smile as well: shops keep running out of these coins for the same reason we keep accumulating them.

My wife is a teacher. She tells me that secondary school children use these coins as missiles. You can't ban children from carrying them, they are big enough to hurt if thrown hard, and only cost a penny or two each.

The time has come to abolish these coins. To be sure shops would sell stuff for £1.95 instead of £1.99, but this is an improvement in two ways: the 5p coin is smaller even than the 1p, and a half dozen 5p pieces can actually buy a bag of crisps.

I imagine that having the smallest unit of cash bigger than the smallest unit of accounting is going to cause some headaches: how do you close an account containing £561.34? But there must be ways around this. When I visited Italy in about 1988 the smallest coin was 10 lira, then worth about 0.5p. So they obviously coped with this question.

Having to Listen to the Guy in the Next Toilet Cubicle

Its not him I hate, its the experience of having to listen to all the little noises. I imagine he feels the same about me. In fact I'm sure that the vast majority of you are cringing as you read this, because you know exactly what I'm talking about and hate it just as much. So, if this is such an unpopular experience, why are toilets still being built with no audio privacy?

I suspect that current toilet architecture dates back to the days when masturbation and homosexuality were seen as terrible evils. You couldn't deny people privacy at home, but you could at least make sure they weren't doing anything unnatural in the public loo. Today we are a bit more enlightened, and the justifications for denying us a bit of privacy no longer make any sense. But somehow the architectural profession hasn't caught up. I suspect that amongst architects everyone knows how to build a public or workplace toilet, and everyone assumes there must be some good reason why its that way, even if they don't know what it is themselves. Or is there some British Standard specifying the minimum gap between floor and cubicle partition?

When I worked for Marconi I visited their swank HQ in London a few times. Their toilets had separate soundproofed cubicles. What luxury! Presumably the architects who designed the building back in the 1920s thought that the superior specimens of manhood who would inhabit it would be safe from unnatural vices, and only the lower classes needed to be monitored.

Blue Indicator LEDs

The invention of the blue LED was a technological triumph. It paved the way for higher densities of optical storage and also made efficient LED lighting a feasible proposition. So I don't want to get rid of the blue LED altogether. What I do want to get rid of is the use of blue LEDs as indicator lights in computer equipment because they are so much brighter than the older red and green ones. Red and green LEDs light up enough to show you that they are on, but blue ones are positively dazzling. Having one of these in your field of view is annoying; you have to avoid looking at it because the after image will make it difficult to look at anything else for several seconds. I bought a couple of USB disk drive enclosures a while ago, and not only had the designers included perspex sides with blue LEDs in them, but they had also slaved these LEDs to disk activity so that they flashed and flickered. They shipped these horrible things with leads that had even more flickering blue LEDs. Aaarghh!

The plague of blue LEDs seems to have abated somewhat, but its not gone. My new laptop has almost all green indicator lights, except the Bluetooth indicator is blue. It doesn't flicker with activity, but I've still stuck some masking tape over it. This looks ugly, but it does diffuse the blue enough to be tolerable.

Cellphones that play music through a tiny speaker

Why someone thought this was a good idea I don't know. Its probably not down to one person, more a combination of marketing-driven design and engineering compromise leading to something totally horrible, like deciding your house needs repainting before you sell it, but the only paint you can find is sickly pink. Yes, you've repainted the room as per the requirements from Marketing, but you'd have done better not to bother.

In the case of the cell phone, I imagine the conversation went something like this:

Marketing: We want our phone to be the next ghetto blaster.

Engineering: Ye canna break the laws of physics Jim. Phones are too small to reproduce low frequencies at high volume. Thats why nobody has done it.

Marketing: OK, so its not going to be the greatest sound reproduction. But you're a great engineering team. We have faith that you can rise to this challenge. Besides, we've already paid for the advertising, so its too late for you to back out.

Engineering: Well, I suppose if you shifted all the frequencies up an octave or two you could at least hear the music, but its going to sound...

Marketing: Great. Just great. "Make it so!" .

So last weekend one of my son's friends came over with his new cell phone playing what sounded like Bohemian Rhapsody sung by Pinky and Perky, except that it wasn't meant as a joke. It was probably the most nauseating musical experience of my life.

Distorted Muzak

Another musical one. I don't mind muzak most of the time: shopping is boring, and sometimes they play something I like. But every so often I find myself in a shop that gets its muzak from some kind of satellite radio muzak channel (I gather chain stores often do this because the supplier takes care of copyright licensing). But the signal is weak or the antenna has drifted or something, and the sound is heavily distorted. Muzak is supposed to put you in a relaxed mood in order to make parting with money less stressful, and good muzak does this. Badly distorted muzak just makes me want to get out as fast as possible. But its no good trying to complain. "Its company policy to have music" says the spotty youth at the customer service desk.

Candles on Restaurant Tables

This is another visual distraction, worse even than blue LEDs. Candles are brighter, and they flicker more. Restaurant owners don't even have the excuse that candles are the latest cool technology; they are thousands of years old. So why is it still considered a good idea to put one in between two people who want to look at each other?

Because it draws my eye, I feel compelled to fiddle with it. I wave my fingers through the flame and toy with the softening wax around the edge. Then I remind myself that this behaviour probably drives other people up the wall and put my hands away, for a couple of minutes until I find myself doing it again.

Why Voting Machines Can't Add Up

2008-03-19T14:05:00.000-07:00

Ed Felten is continuing his excellent work exposing the broken state of electronic voting machines. Many people are wondering how such software can have been allowed out by its developers. The discrepancies don't (at the moment) seem to be a result of fraud, just very buggy software.

Voting machines are obviously important, so their development is regulated. I've never worked in the voting machine industry, but I have worked in another kind of federally regulated software: medical devices. So I know how regulated software projects work, and how they don't.

The fundamental problem underlying this is that nobody in the world actually knows how to write software that reliably does what you want. There are quite a lot of people who can write such software, but if you ask them how its done they basically waffle. Most of them agree on a list of steps to take, starting with writing down exactly what the software is supposed to do. Various attempts have been made to codify this list, and they all look pretty similar. The voting machine standards are just another variation on this theme.

However this is all cargo-cult engineering. We know that the people who can summon up the magic cargo planes do it by putting things over their ears and saying magic words, but it doesn't follow that if we put things on our ears and say the same magic words the cargo will appear. So it is with software engineering. You can write Requirements Documents and Class Diagrams and Test Scenario Documents and Test Execution Reports until you run out of paper, but it won't make any difference if you don't have the Quality Without a Name.

Imagine you are managing a development project to build a voting machine. Your mission is to get the thing on the market. You have been given a bunch of programmers, half a human factors person and a quarter of an industrial designer. The time available isn't long enough, but you know its no use complaining about that because its not your boss's fault, or even the CEO's fault. Its the fault of the people at Big Competitor who are planning to release their product just in time to tie up the whole market, so if you don't deliver the product at the same time then its not going to matter who's fault it was, the whole division is going to get laid off anyway. You could get some more people if really wanted, but you know that more people aren't actually going to speed things up.

The Quality Department have downloaded the voting machine regulations and someone has been going through them and writing down a list of the things they say you have to do and the order they have to be done in. This is very good. In fact you send the Head of QA a little note saying how helpful his minion has been to your project, because now you have something to aim at. Project Management is mostly a matter of getting your hoops lined up so that you and your minions can jump through them as quickly as possible, and the QA minion has done the regulatory hoops for you. The regulations boil down to a list of documents that have to be shown to the inspectors (who you are going to hire, but thats another story). Each document has a list of things it must contain, and some of those things have to be traceable to other things. All you need to do now is start allocating people to things on the list and getting them ticked off. The list is long, but you have one big advantage: there is nothing to say how good any of these documents have to be. They don't have to be good, they just have to exist.

One of these documents is called "source code". Of course that one does have some quality requirements on it: its got to pass a bunch of tests. But the tests themselves don't have any quality requirements; like everything else they just have to exist. And passing the tests is the only quality requirement on the code. Once the independent laboratory you hired has run the tests and said "pass" you are over the finishing line and you can start selling these things.

This means that you have a very strong motivation to keep the testing to the minimum you can get away with. The regulations say you have to have a test for each item in the original requirements document, and this test has to be run once. If your software fails a test then you get to fix it, and if the fix was small enough you can get away without repeating all the other tests as well. During this whole time your eyes are fixed on the finishing line: the objective is to get this thing over the line. What happens to it after that is someone else's problem.

When you look at these machines from a project manager's point of view you start to see how they got to be so unreliable. "Quality Assurance" is primarily a matter of making sure you get all the items in the regulations ticked off; it has nothing at all to do with the original meaning of the word "quality". Ironically the regulations may actually do more harm than good because they divert energy from real quality onto generating the required inches of documentation.

Over the years I've spent a lot of time trying to figure out how to fix this problem, and I still don't have an answer. Abolishing private companies is a cure worse than the disease, and it won't cure the disease anyway because it won't abolish projects and the need to manage them. Software Engineering has a bad case of Quality Without A Name, and there is no prospect of it getting better soon.

However in the limited domain of voting machines I believe the best cure is sunlight: we may not be able to define quality in software, but we know it when we see it. The source code for voting machines must be published. The manufacturers will scream and shout about their precious IPR and trade secrets. This is nonsense. Any voting machine must have a well defined version of someone's software running, so any illegal copying will generate a cast-iron audit trail back to the perpetrator. And there are no real trade secrets in voting machines: counting votes is not, when it comes down to it, a particularly complicated problem. The voting machine manufacturers will make just as much money as they do now. In fact they'd probably make more because if the machines were trustworthy then people would learn to trust them. However the first vendor to start publishing their source code will be at a disadvantage because everyone else can pinch bits of it with very little risk of detection (and if they get caught they can just blame a rogue programmer). So the regulations on voting machines should be changed to require the publication of the code (and other design documentation too, while we are about it). That will create a real requirement for quality source code. Until then we are stuck with the current mess.

Why Haskell is Good for Embedded Domain Specific Languages

2008-01-10T10:42:00.000-08:00

Domain Specific Languages (DSLs) are attracting some attention these days. They have always been around, of course: Emacs Lisp is a DSL, as are the various dialects of Visual Basic embedded in MS Office applications. And of course Unix hands know YACC (now Bison) and Lex (now Flex).

However creating a full-blown language is a lot of work: you have to write a parser, code generator / interpreter and possibly a debugger, not to mention all the routine stuff that every language needs like variables, control structures and arithmetic types. An embedded DSL (eDSL) is basically a short cut if you can't afford to do that. Instead you write the domain-specific bits as a library in some more general purpose "host" language. The uncharitable might say that "eDSL" is just another name for "library module", and its true there is no formal dividing line. But in a well designed eDSL anything you might say in domain terms can be directly translated into code, and a domain expert (i.e. a non-programmer) can read the code and understand what it means in domain terms. With a bit of practice they can even write some code in it.

This paper describes an eDSL for financial contracts built in Eiffel which worked exactly that way. It doesn't talk about "domain specific language" because the term hadn't been invented back then, but the software engineers defined classes for different types of contracts that the financial analysts could plug together to create pricing models. Its interesting to compare it with this paper about doing the same thing in Haskell.

But eDSLs have problems. The resulting programs are often hard to debug because a bug in the application logic has to be debugged at the level of the host language; the debugger exposes all the private data structures, making it hard for application programmers to connect what they see on the screen with the program logic. The structure of the host language also shows through, requiring application programmers to avoid using the eDSL functions with certain constructs in the host language.

This is where Haskell comes in. Haskell has three closely related advantages over other languages:

Monads. The biggest way that a host language messes up an eDSL is by imposing a flow of control model. For example, a top-down parser library is effectively an eDSL for parsing. Such a library can be written in just about any language. But if you want to implement backtracking then its up to the application programmer to make sure that any side effects in the abandoned parse are undone, because most host languages do not have backtracking built in (and even Prolog doesn't undo "assert" or "retract" when it backtracks). But the Parsec library in Haskell limits side effects to a single user-defined state type, and can therefore guarantee to unwind all side effects. More generally, a monad defines a model for flow of control and the propagation of side effects from one step to the next. Because Haskell lets you define your own monad, this frees the eDSL developer from the model that all impure languages have built in. The ultimate expression of this power is the Continuation monad, which allows you to define any control structure you can imagine.
Laziness. Haskell programmers can define infinite (or merely very large) data structures because at at any given point in the execution only the fragment being processed will actually be held in memory. This also frees up the eDSL developer from having to worry about the space required by the evaluation model. (update: this isn't actually true. As several people have pointed out, while laziness can turn O(n) space into O(1), it can also turn O(1) into O(n). So the developers do have to worry about memory, but lazy evaluation does give them more options for dealing with it.)
The type system allows very sophisticated constraints to be placed on the use of eDSL components and their relationships with other parts of the language. The Parsec library mentioned above is a simple example. All the library functions return something of type "Parser foo", so an action from any other monad (like an IO action that prints something out) is prohibited by the type system. Hence when the parser backtracks it only has to unwind its internal state, and not the rest of the universe.

There are other programming languages that are good for writing eDSLs, of course. Lisp and Scheme have callCC and macros, which together can cover a lot of the same ground. Paul Graham's famous "Beating the Averages" paper talks about using lots of macros, and together with his patent for continuation-based web serving it is pretty clear that what he and Robert Morris actually created was an eDSL for web applications, hosted in Lisp.

But I still think that Haskell has the edge. I'm aware of the Holy War between static and dynamic type systems, but if I you put a Haskell eDSL in front of a domain expert then you only have to explain a compiler type mismatch message that points to the offending line. This is much easier to grasp than some strange behaviour at run time, especially if you have to explain how the evaluation model of your eDSL is mapped down to the host language. Non-programmers are not used to inferring dynamic behaviour from a static description, so anything that helps them out at compile time has to be a Good Thing. And its pretty useful for experienced coders too.

(Update: I should point out that monads can be done in any language with lambdas and closures, and this is pretty cool. But only in Haskell are they really a native idiom)

Is Comcast's Packet Spoofing a Federal Crime?

2007-11-29T13:26:00.000-08:00

The EFF has gathered evidence showing that Comcast is deliberately disrupting P2P traffic by spoofing RST packets to appear to come from the other end of the connection. See the EFF report for the technical details.

The US Criminal Code Title 18 Part 1 Title 47 Section 1030 covers "Fraud and Related Activity In Connection With Computers". I'm not a lawyer, but here is my understanding of the relevant bits of the statute (quotes from the statute are in italics):

Jursidiction: a "Protected Computer" is defined, amongst other things, as any computer "which is used in interstate or foreign commerce or communication, including a computer located outside the United States that is used in a manner that affects interstate or foreign commerce or communication of the United States". In other words if your computer is on the Internet, even if its outside the US, then its a Protected Computer. That includes anything connected via Comcast, and anything that talks to any computer connected via Comcast.

Offence: there are two things to prove here:

That someone employed by Comcast "knowingly causes the transmission of a program, information, code, or command, and as a result of such conduct, intentionally causes damage without authorization, to a protected computer". Damage is defined as "any impairment to the integrity or availability of data, a program, a system, or information". A spoof RST packet instructs the receiving computer to drop a TCP connection, so it is a command that impairs the availability of data. I have no direct evidence that these packets were sent knowingly, but I find it difficult to imagine a scenario in which they were sent by accident.
That this action caused "loss to 1 or more persons during any 1-year period [...] aggregating at least $5,000 in value". "Loss" is defined as "any reasonable cost to any victim, including the cost of responding to an offense, conducting a damage assessment, and restoring the data, program, system, or information to its condition prior to the offense, and any revenue lost, cost incurred, or other consequential damages incurred because of interruption of service". This is a bit tricky, but people do value their time. $10 per hour is a pretty low wage, and many professionals charge many times that. If failed P2P connections have cost 500 Comcast users 1 hour each in wasted time then this threshold has been reached. You might also be able to make a case purely on the cost of running a computer and keeping it connected via Comcast. The professional IT people who have taken the time to run tests with packet sniffers could certainly count their time at a professional rate as "responding to an offence" and "conducting a damage assessment". There is also some evidence that Comcast inadvertently disrupted other protocols, including Lotus Notes and Windows Remote Desktop. These are used commercially and their disruption would have real financial impact. So while a detailed accounting remains to be done, it certainly looks likely that the $5,000 threshold has been reached.

Penalty: "a fine under this title or imprisonment for not more than 5 years, or both, [if] the offense was committed for purposes of commercial advantage or private financial gain". Comcast's attempts to block P2P protocols are prompted by their desire to keep costs down while seeming to offer an unrestricted service. That counts as "commercial advantage".

So it certainly looks like a Section 1030 offense has been committed that could see someone put in the pen for five years. Any Comcast customers want to call the FBI?

Disruptive Innovation and the Walmart Linux PC

2007-11-27T12:00:00.000-08:00

The Everex TC2502 is being sold by Walmart for $200 (no monitor included), assuming it hasn't sold out a second time. Part of the reason its so cheap is that it runs Linux and OpenOffice.org instead of Windows and MS Office. The first run sold out within days, which is a strong clue that it was a lot more popular than expected. This doesn't mean popular in an absolute sense, just more than Walmart and Everex expected when they decided how many to get in stock. But its the relative popularity that counts: Walmart and Everex produced this box because they calculated they would turn a profit on whatever number they expected to sell. So the fact that they sold out fast means two things:

A bigger profit than expected, which is nice for Walmart and Everex.
Cheap Linux-based PCs have a market niche big enough to make them worth-while. Other manufacturers will have taken note. Expect imitators.

Anyone who has read The Innovator's Dilemma will recognise this pattern: a market incumbent listens to its best (i.e. richest and most profitable) customers, and in consequence makes its products bigger, better and progressively more expensive. The incumbent also finds it unprofitable to compete with narrow niche offerings at the bottom, because they are low quality and aimed at poor customers that can't afford the market leader. So it forgoes the bottom end of the market and concentrates on its nice profitable high-end models. However over time the bottom-end offerings improve, and so become a cost-effective choice for more and more customers. Eventually this starts to make serious inroads into the sales of the incumbent. But by then its too late. The incumbent must choose between cutting prices to compete with the newcomer or else continue to see its market share erode. Neither option will bring back the glory days, and historically many such companies went out of business surprisingly fast.

I'm quite sure that Bill Gates and Steve Ballmer have read The Innovator's Dilemma and seen this coming. There is a bit of MBA strategy theory that sums up their position nicely. Plot their product lines on a chart with two axes; market share and growth potential. The high-share-low-growth lines are "cash cows": they should be milked, and the profits put into high-growth lines. Eventually all cash-cows turn into dogs (low-share-low-growth) and these should be killed off. You just have to hope that by then you have some new cash cows to replace them.

Microsoft has two cash-cows (Windows and Office), and Microsoft has indeed been milking them for all they are worth. The money has been ploughed into a bunch of ventures over the years, but none of them look like becoming future cash cows.

Now we may be entering the final act. People have talked about Linux as a disruptive technology for the last decade, and for server operating systems it definitely has been. Its effectively killed off proprietary Unix, and put a serious dent in Windows. Microsoft continues to fight a rearguard action in this market, but its reliance on big corporate customers is becoming more and more obvious as it tries to separate its premium products (which rich big companies will still reliably pay for) from its lower end offerings. But on the desktop Windows and Office have continued to reign supreme.

Now for the first time in a decade a competing office suite is starting to nibble at the toes of the incumbent. Its not going to make a dent in Microsoft's quarterly numbers just yet, but the future can only go one way. Microsoft sells Windows and Office to PC builders for less than the retail prices, but it cannot let Windows and Office go onto a PC that sells for $200 because they would be giving it away: it would actually be cheaper to buy the PC with the software than to buy the software alone at retail prices. But as more people find that bottom-end hardware with Linux and OpenOffice.org makes a perfectly useful home PC at a fraction of the cost of the Microsoft alternative, so the market will grow. Microsoft may try to segment the market by offering a cut-down version of MS Office (maybe Word with a 20 page limit), but they are competing with a fully featured product. No matter what they do to Windows and Office, Linux and OpenOffice.org are going to look like better value to anyone who is on a tight budget.

Initially it will just be cash-strapped consumers who buy these boxes (students in particular are going to love them). But this is a one-way street. Every consumer who buys one of these boxes is a consumer who is never going to buy a Microsoft box again, even when they get rich. Why pay more to learn a different set of software? And they'll tell their friends about how well it works too. The flow of money into multiple vendors coffers will stimulate investment and competition. All the vendors will want a slicker, more fully featured Linux offering with a bigger repository of instantly downloadable free (in both senses) software. The resulting competition will be downright Darwinian, and the offerings are going to get very good very fast. Everybody is going to race up-market as fast as possible because thats where the real money is. At the moment that money is being taken by Microsoft, but not for long.

Add to this the famous network effects. Part of the reason MS Office dominates is that you need it to exchange documents with everyone else. But if that stops being true then another good reason to pay for MS Office disappears as well.

So I predict that Microsoft is going to be in serious trouble, probably within the next few years. Their existing cost base is tuned to making and selling ever bigger and better versions of their cash cows, and there is no way that they can cut this back to compete with Linux and OpenOffice.org on a cost basis. But if they can't compete then their cash cows are going to turn into dogs before they can be replaced. So Microsoft will be left with two dogs, a bunch of ventures that require investment, and no cash flow. Sure they have big cash reserves they can burn through, but thats not going to be enough even if their investors let them do it.

Its the disks that are the problem, not losing them

2007-11-23T10:26:00.000-08:00

The UK news this week has been full of stories about the loss of 2 disks (presumably CDs or DVDs) containing all 25 million Child Benefit records. For those outside the UK, Child Benefit is several pounds a week paid to the mother of every child (i.e. under 16) in the UK. In most cases it gets paid directly into a nominated bank account.

This is one of the biggest data losses ever, if not the biggest. The government has been at pains to point out that the disks are probably just mislaid, and they don't contain enough data for criminals to actually use. Meanwhile the Opposition has been alleging government incompetence and calling for them to "get a grip". People are being advised to keep an eye on their bank accounts and not use their childrens' names as passwords.

All this misses the point. The problem was not that a couple of disks got lost, it is that a comparatively junior person could burn the entire database to a couple of disks, apparently on his/her own initiative, and without further controls. There was a time when copying 25 million records would have required substantial resources, such as an overnight run on the mainframe and a boxful of tapes. The sheer volume of data made it physically difficult to copy, or to lose. However Moore's Law has turned that big, slow, expensive job into a few minutes with a CD burner. If those two disks were CDs then the whole lot would also fit on a £10 thumb drive, or even a cell phone. The story referenced above suggests that in the past the National Audit Office (the place where the disks in question never arrived) have made their own copies and sent them to outside auditors. None of the commentators seem to have realised that the most probably route for the data to get into the hands of criminals is not the loss of an authorised copy but the creation and distribution of unauthorised copies.

There are supposed to be procedures in place, but its no surprise that they are not being followed; when was the last time you reached for the Company Procedure Manual to check on the detailed procedure for some simple action? Its also too easy to blame the middle manager who decided that a written procedure was better than implementing a software access control system. Given a choice between implementing costly access controls and writing a procedure for making copies, which would you chose? Now try it again, but imagine that your annual evaluation is going to suffer if you "waste" money doing something that has no positive benefit on your departmental targets.

I would like to think that this incident will be a wake-up call for the civil service to revamp its data control procedures. However I doubt it. A scapegoat has already fallen on his sword (to mix the commonest metaphors). The government is keen to show it is doing something, but mostly to counter the opposition claims of incompetence. And the opposition is more interested in a ministerial scalp than in actually pushing for effective action. What is really needed is an audit of all databases containing UK citizen personal information, followed by a study into the necessary forms of access and the implementation of software-based authorization and logging mechanisms. But nobody in authority seems to be thinking along those lines.

The sad thing is that the Ministry of Defence has had hundreds of years experience in dealing with sensitive and secret data, and they have become quite good at it. Perhaps they should give the rest of the government some lessons.

The Rise of Modern Morality

2007-09-20T11:38:00.000-07:00

Every so often I read a letter in a newspaper or some other forum about "the decline of modern morality", in which the writer laments the failing moral standards of private and public life. I'm old enough to have been reading these articles for two or three decades now, and I've seen some samples of the same genre from past times. Elvis Presley caused a moral panic in 1956 by gyrating his hips on stage, and this was cited by commentators at the time as corrupting the morals of young people. Much has been written about the sociology of moral panics and I don't propose to repeat it here. Instead I want to argue that, far from declining, modern morality is actually superior to moralities of the past (and I use the plural deliberately).

In 1970 in the UK it was not only legal but widely accepted practice to pay a woman less than a man for doing the same job. Women who wanted a life outside of home making and child rearing were seen as aberrant, and often regarded with scorn.
In 1960 in America many parts of the country segregated public facilities by race, with black people consistently and blatantly short-changed. This invidious system was widely supported by prominent politicians and churchmen.
Even into the 1970s in Australia aborigine children were forcibly removed from their parents and placed in institutions where they were denied proper education and were terribly vulnerable to physical and sexual abuse. Again, this programme was considered perfectly proper and moral by the standards of the time.
There was a standing assumption for many years that unmarried mothers should immediately give up their children for adoption. In Ireland they were also incarcerated in the "Magdalene Laundries". Other countries had similar systems. Strangely, the fathers were left to go free.
For most of the 20th century, when it became necessary to remove children from their parents because of neglect or abuse little thought was given to keeping siblings together: they would be split up to suit the convenience of potential adopters or fosterers.
Until recent years in most Western countries, homosexuals were persecuted and discriminated against, both by the law and by society at large.
Until the 90s in the UK drink-driving was considered a minor peccadillo. Drivers convicted of the offence were more likely to encounter sympathy at the unfair attitude of the legal system than censure at their reckless disregard for the safety of others.

Not all of these evils are completely gone, but in all cases there has been a substantial moral shift. I know that some readers will look at some of this list, especially the tolerance of homosexuality, and regard this as evidence of moral decay rather than ascent. But this brings up another issue I have with the Cassandras of moral decay: their belief in moral absolutism; that right and wrong are entirely self-evident, and that any deviation stems from lack of morality rather than a genuine disagreement over what the moral course is.

The problem with moral absolutism is that (in its commonest form) it asserts that the perfect moral code has already been revealed and the only possible improvement is in closer adherence to that code. However I describe myself as a Liberal Utilitarian (although I confess I haven't actually read any of Mill's work). Hence I see "the greatest good of the greatest number" as a basic moral principle, while at the same time acknowledging that there may be a lot of disagreement about exactly what that means and how to bring that about. Liberal utilitarianism recognizes no absolute moral imperative apart from the general principle that life, liberty and the pursuit of happiness are good things. However by retaining that anchor it avoids the charge often leveled by the Absolutists that those who question their moral code are "relativists" who believe that any moral code is as good as any other. Liberal utilitarianism examines the impact of moral rules on the real people affected by them. If different rules would have a better outcome then those rules are automatically better. I see the arguments (both past and ongoing) about freedom, equal opportunities and tolerance to be a part of this process, and I see a steady improvement through history. Those who object to the current crop of improvements in morality because they contradict their particular absolutist code would do well to read their history books.

Windows Disaster Recovery with Bacula

2007-09-07T13:07:00.000-07:00

A few days ago my wife asked me to look at her computer. Programs were taking ages to respond even to a simple mouse click, or just crashed. And the system box kept making odd clicking noises.

I confirmed her diagnosis of a failing hard drive and shut the computer down. The following lunchtime I drove to the nearest PC World and bought a replacement hard drive. I normally buy mail-order, but we wanted the computer back up as soon as possible. That evening I removed the faulty drive and installed the new one, and I also stuck in some extra RAM while I had the case open. Then it was time to find out if my rather sketchy disaster recovery plan was going to work.

I run Fedora on my own box, and both computers are backed up using Bacula. This is designed for backing up lots of computers to tape drives, but it also supports backup to disk drives. I have two USB drives, keep one plugged in, and swap them every month or so. I use the default Bacula backup schedule of a weekly full dump on both machines and nightly incremental dumps. Most of the Bacula components only run on Unix, but there is also a Windows client installed on my wife's computer (which runs Windows XP SP2). Bacula configuration is rather hairy, but if you have more than one computer its well worth the effort.

The big headache for restoring Windows is the Registry. After previous bad experiences with this horrible blob of data I had made sure the registry was backed up by using regedit to dump the registry contents to a file before each Windows backup, so I hoped it would be OK. There are also problems with other files in C:\Windows that are constantly in use and therefore unwritable during system restore.

The Bacula manual pointed me at Bart PE Builder, which generates a Live CD version of Windows XP. It suggested that you might be able to run Bacula in this environment to get around these problems. Bacula ran fine, but I couldn't get the drivers for the network card to install, so that wouldn't work.

Instead I re-installed Windows XP SP1 from the original CD and ran Bacula there. The restore duly dumped copies of C: and D: in C:/temp/restore/c and /d. (The computer has two partitions because it used to have two drives. My wife got used to having C: and D: drives and various programs had been configured to look for data on D:, so I kept the layout even when it went back to a single drive.). Then I booted under the Bart PE disk, deleted the existing contents of C: (except for /temp) and copied the restored contents into the root directories. Then for the big test: would it reboot?

Well, sort of. The login screen came up, but when I tried to log in the computer hung. I tried rebooting in safe mode, and then in "safe mode with console", which seemed to be the bare minimum. That at least got me a command line, so I ran regedit and imported the registry copy that had been created by the last backup. This warned me that some registry keys could not be modified and claimed that the changes had failed. I rebooted again, and this time found that I could log in, but pretty much all the settings had been forgotten. Office wanted to re-install itself, and every time I started Word it asked for my name and initials twice. This suggested that important parts of the registry were not only still not recovered, but also unwritable.

Windows also decided that it was running on new hardware, and badgered me to activate it. So I did. I then tried logging in as a different user and restoring the registry again in the hope that being a different user would lock different bits of registry. This merely overwrote the new activation data and Windows now point blank refused to let me log in at all until I activated it again. So I tried. This time it told me that I had exceeded my activation limit and would have to phone up for activation. So I did. Windows gave me a 36 digit number and a robot on the other end of the phone line told me to type in the number. Then a polite gentleman named "Fred" with an Indian accent asked me how many computers I had Windows installed on and why I needed to activate it. Then he gave me another 36 digit number to type into Windows to activate it. This worked. But when I logged in Windows wasn't behaving any better.

A bit of Googling reminded me of something I should have remembered much earlier: Windows occasionally checkpoints its critical state, including the Registry, and you can wind it back to a previous known good state using the System Restore function. So I located a checkpoint from before all the trouble started, restored Windows to that state and rebooted.

When I tried to log in I got immediate joy: the desktop background had been restored. This suggested that the registry was now intact. But this restore had also overwritten the registration data, and Windows once again demanded to be activated before I could log in. Back to the phone, this time to a polite woman named June with a much stronger Indian accent who asked me the same questions and gave me yet another 36 digit number to type in. This time everything worked. Disaster recovery was completed.

I'd like to thank the authors of Bacula for their excellent backup program. It saved both of us a lot of heartache. In the past I've found it too easy to neglect backups, and sometimes our computers have gone for months without being backed up. When I got it properly configured (not a trivial task) Bacula made backups automatically with minimal intervention by me (basically, swapping USB drives occasionally). That meant I had a good recent backup to work from.

I'd also like to thank Bart Lagerweij, author of Bart PE. I could probably have managed by booting Knoppix and using its NTFS driver capture facility, but having a native Windows environment made life much easier.

Composability and Productivity

2007-09-01T05:10:00.000-07:00

This was posted to my original blog on January 7th 2007. It was also discussed on Reddit, so please do not repost it.

----------------------------------------------------

My earlier post about increased productivity through functional programming stirred up a good deal of comment. A number of people replied that the libraries are more important than the language. More recently a similar point has been made by Karsten Wagner, who argues that code reuse is what makes languages productive.

I remember the early days of OO, when it was argued by many people (me amongst them) that OO languages would finally let us write reusable software. There was optimistic talk of “software factories”, and Brad Cox gave lots of talks about how software could now finally move from craft to engineering discipline, built on the back of libraries of reusable code. So the entire industry went for C++, but the easy creation of reusable software remained elusive. That is not to say you can’t ever produce reusable software in the language, but it is not significantly easier than in C.

Karsten accurately pins the reason why C++ failed to deliver: memory management. Back in those old days I was trying to explain to people why Eiffel would be so much more productive than C++, and garbage collection was a big part of it.

The reason why GC is so important lies in a more general principle called composability. Composability means that you can put two bits of code together and important correctness properties will be preserved automatically. This does not mean, of course, that the composition is automatically correct in a wider sense, but it does mean that you don’t introduce new bugs merely by sticking two things together.

Imagine two modules of code in a non-GC language like C or C++. Module X creates an object and hands a reference to that object over to Module Y. At some point in the future X will delete that object. However it is only safe to do so once Y has finished with it. So if X and Y were written independently then it is quite possible that Y will hang on to the reference longer than X expects. In short, manual memory management is not composable, because the composition of X and Y can introduce stale pointer bugs that were not present in either X or Y.

In a language with GC this is a non-problem: the collector will reap the object once it sees that both X and Y have finished with it. X can therefore forget about the object in its own time without having to know anything about Y. But programmers in non-GC lanuages have to resort to a number of workarounds. Either objects have to be copied unecessarily (which leads to stale data bugs instead of stale pointer bugs), or else some kind of reference counting or similar scheme must be employed. Reference counting is of course merely an ad hoc, informally-specified, bug-ridden, slow implementation of GC, and therefore stands as a classic example of Greenspun’s Tenth Rule.

But programming languages contain other examples of non-composable constructs. The current biggest offender is shared memory concurrency using locking. If X takes locks Foo and Bar, and Y takes locks Bar and Foo (in those orders), then sooner or later they are going to deadlock with X holding Foo and Y holding Bar. Ironically Java has the biggest problems here.

Surprisingly, program state generally is a source of non-composability. Mutable state is actually another form of manual memory management: every time you over-write a value you are making a decision that the old value is now garbage, regardless of what other part of the program might have been using it. So suppose that X stores some data in Y, and then Z also stores some other data in Y, overwriting what X did. If X assumes that its old data is still there then it is going to be in trouble. Either X needs to defensively check for new data, or Y needs to tell X about the change (the Observer pattern). Whichever way, the addition of Z to the system can introduce bugs that stem from the composition of modules rather than the modules themselves.

Another example is the Command pattern, which includes a method to “undo” a previous command. Why undo it? Because the global state has been changed. Get rid of the concept of a single unique state for the entire application and you get rid of the problem.

On a more prosaic level, many library modules have some internal state, and so require an initialisation call to “set things up”. Who exactly is responsible for this initialisation? If you compose two modules together then they may both imagine themselves soley responsible for making this initialisation call, and hence it will be done twice.

It is a truism of programming that “integration” is the most difficult and risky (from a scheduling point of view) part of developing a large system. Integration basically means composing together all the units to try to get a working system. And the biggest integration problems are due to the non-composability of the units. A defect within a unit is fairly easy to identify, but composition bugs are down to the interaction of two separate units in some unforseen way, which makes it correspondingly more difficult to pin them down.

So what would a language look like if it got rid of all of these non-composable constructs? The answer, basically, is Haskell. The underlying goal of functional language designers is to make everything completely composable. Haskell is the language that has advanced furthest towards this goal.

Erlang is pretty good as well. It doesn’t eliminate state, but it does keep it confined to individual processes: there are no shared memory locks. Processes have to communicate according to shared protocols, but this is a manageable dependency on a common abstraction. Even within a process the shared state can be reduced by careful use of functional programming rather than imperative.

Tax as Percentage of GDP

2007-08-27T11:59:00.000-07:00

In the 17th century French economist Jean Baptiste Colbert said "The art of taxation consists in so plucking the goose as to obtain the largest possible amount of feathers with the smallest possible amount of hissing”. His observation is as true today as it was then.

Whenever the government in the UK decides to charge for something, especially if it was previously free, it is in turn charged with "stealth taxation". I don't know about other countries, but I imagine that the politics are similar. There is often a good reason why the government wants to levy a charge, which often has nothing to do with its overall level of income. An example is the recent proposal to charge by the kilo for domestic refuse collection: the "polluter pays" principle is generally recognised as sound and "free" rubbish collection is increasingly expensive. But not everyone agrees:

Mother-of-five Mandy Price, who has just begun to recycle but still produces an average of nine bin liners of rubbish a week, said the assembly could not justify introducing such a policy in the wake of council tax rises.
She said: "You pay your council tax for the local authority to come and collect your rubbish, so why should we pay more?"

In other words, the charge is perceived primarily as just another source of revenue rather than an attempt to shift the costs onto the people who actually use the service the most. The government response is always to say that this is going to be offset by lower taxes elsewhere (in this case, council tax), but this makes a very unconvincing soundbite.

Gross Domestic Product is a standard way of measuring the overall economic activity in a nation or economic area, and the usual way of measuring the tax burden on an economy is the ratio of taxation to GDP. For instance, Reform points out that the US takes 26.4% of GDP as tax, whereas the UK takes 35.8%. Of course, these figures are almost useless for international comparison because they don't say what the tax pays for. In the UK most health care is paid for by the government out of general taxation whereas in the US it is mostly paid for privately by employer-funded health schemes that get a tax break. The NHS is funded out of taxation, and so is charged to the government's account, but a scheme partly funded by a tax reduction (as in the US) is not. If the US were to eliminate the tax break and subsidise these schemes directly instead then the basic nature of the system would not change one whit, but the proportion of US GDP taken in tax would increase. The US spends around 16% of GDP on health care (compared to about 8% in the UK). From an employer's point of view taxation and healthcare are both just costs of doing business, and the overall burden of general taxation and healthcare in the US is actually higher than in the UK. As always you get what you pay for, but a worrying amount of political debate seems to revolve around which ledger the payment is recorded in.

However one place where such figures would be useful (but never seem to be used) is in domestic political arguments. The Liberal Democrats used to have a policy of adding 1% to the rate of income tax in order to fund improved education. Meanwhile the Tories are struggling with a reputation for aggressive cost-cutting in public services in order to fund tax cuts, and the Labour government has been increasing taxes in order to spend more on public services (with notable lack of effect, but thats another issue).

What I would like to see is for each party to declare a target level of taxation as a percentage of GDP. That gets their macro-economic policy on taxation out in the open, without confusing it with a lot of micro-economic questions over how it is collected. Thats not to say that those micro-economic questions are unimportant, but they need to be separated from the macro-economic debate about the overall level of taxation.

Microsoft versus FOSS Configuration Management

2007-08-22T10:57:00.000-07:00

This was originally posted to my old blog on December 3rd 2006. It was also discussed on Reddit at the time, so please do not repost it.

--------------------------------------

Joel Spolsky writes about the Vista shutdown menu and its excess of confusing options (what exactly is the difference between Hibernate and Sleep?). Moishe Lettvin, who happened to have worked on that menu, chimed in with an explanation of why it came out that way, which included a fascinating insight into how Microsoft handles configuration management.

For the uninitiated, configuration management is a lot more than just version control. It includes managing all the libraries and tools used in a build, and if multiple components are being incorporated into the final product then it also involves keeping track of those. The goal is to be able to go back to some build that happened last year, repeat the build, and come out with the same MD5 checksum at the end. Stop and think about what that involves for a minute. Its highly non-trivial. (And some compilers happen to make it impossible by using multiple threads, so that two consecutive builds generate the same code, but with functions in a different order. Under some high integrity quality regimes this actually matters).

The Microsoft problem is that they have thousands of people working on Vista, and a simple repository with everyone checking stuff in and out simply won’t scale. So they have a tree of repositories about 4 deep. Each developer checks stuff in to their local repository, and at intervals groups of repositories are integrated into their local branch. Hence the changes propogate up the tree to the root repository, from where they then propogate back down the other branches.

The trouble is, propgation from one side of the tree to the other can take a month or three. So if developer A and developer B need to collaborate closely but are on distant branches of the build tree then their code takes ages to propogate between them.

Now consider the case of open source software. The Linux kernel and Windows are actually organised in very similar ways: Linus owns the master repository, people like Alan Cox own sub-repositories, and handle integration up to Linus. Sub-repository owners are responsible for QA on the stuff they merge in, just like in Windows.

So why is Windows Vista in trouble, but free / open source software is not? After all, GNU/Linux overall has tens of thousands of people developing for it, and thousands of packages of which the kernel is just one. Worse yet, these tens of thousands of people are not properly organised and have very little communication. Microsoft can at least order all its programmers to work in certain ways and conform to certain standards.

Actually this disconnection is a strength, not a weakness. Conway’s Law says the structure of any piece of software will duplicate the structure of the organisation that created it. So in Microsoft there are lots of programmers who all talk to one another, and this leads to software where all the bits are inter-dependent in arbitrary ways. Open source developers, on the other hand, are spread around and have very narrow interfaces between each other. This leads to software with narrow well defined interfaces and dependencies.

Dependencies are the crucial thing here: if I am writing a new application that uses, lets say, the Foobar library, then I will want to depend on a stable version. If I write to the API in the daily snapshot then my code could suddenly break because someone submits a patch that changes something. So I write to the last stable release. If I really need some feature that is still being developed by the Foobar team then I can use it, but that is an exceptional case and I won’t be releasing my application until the Foobar feature stabilises.

Dependency management is probably the most important contribution of open source to software engineering. The requirement first became obvious under Windows, with “DLL hell”: different applications installed and required different dynamic libraries, and conflicts were inevitable. Then Red Hat users encountered a similar problem in “RPM hell”, in which they had to manually track the dependencies of any package they wanted and download and install them.

As far as I know Debian was the first distribution to really solve the dependency problem with apt-get. These days Fedora has yum and pirut, which do essentially the same job. Its not a simple job either. A program may have a dependency not just on Foobar, but on Foobar version 1.3.*, or anything from 1.3 onwards but not 2.*. Meanwhile some other package may depend on Foobar 1.6 onwards, including 2.*, and yet a third package requires Foobar 2.1 onwards. It is the job of apt-get and its relatives to manage this horrendous complexity.

(Side note: I remember when OO software was young in the nineties, people thought that the biggest challenge for resuable software was searching repositories. They were wrong: it is dependency management).

Open source also has a clear boundary to every package and a very precise process for releasing new versions. So when the new version of Foobar comes out anyone interested finds out about it. Any changes to interfaces are particularly carefully controlled, so I can easily tell if the Foobar people have done anything to break my application. If they have I can carry on depending on the previous version until I can resolve the problem. Then before my application finds its way into, say, Fedora, it has to be integrated into an explicit dependency graph and checked for conflicts with anything else.

Microsoft doesn’t do this. Vista is effectively a big blob of code with lots of hidden dependencies and no effective management of what depends on what. No wonder they are in trouble.

Anatomy of a new monad

2007-08-19T02:33:00.000-07:00

The monad described here was originally written in response to a posting by Chad Scherrer on Haskell-Cafe:

I need to build a function
buildSample :: [A] -> State StdGen [(A,B,C)]

given lookup functions
f :: A -> [B]
g :: A -> [C]

The idea is to first draw randomly form the [A], then apply each
lookup function and draw randomly from the result of each.

I suggested Chad try using ListT for the non-determinism, but this didn't work, so I decided to try solving it myself. I discovered that actually ListT doesn't work here: you need a completely custom monad. So here it is. Hopefully this will help other people who find they need a custom monad. This isn't meant to be yet another ab-initio monad tutorial: try reading the Wikibook or All About Monads if you need one.

The basic idea of the MonteCarlo monad is that each action in the monad returns a list of possible results, just like the list monad. However the list monad then takes all of these possible results forwards into the next step, potentially leading to combinatorial explosion if you can't prune the tree somehow. It was this explosion that was giving Chad problems when he scaled up his original solution. So instead the MonteCarlo monad picks one of the results at random and goes forwards with that.

Picking a random element means we need to thread a random number generator StdGen as a form of monadic state. So the monad type looks like this:

newtype MonteCarlo a = MonteCarlo {runMC :: StdGen -> (StdGen, [a])}

This is based on the state monad, except that the type parameter "s" is replaced by StdGen. I could have used the state monad here, but it would have meant working its "bind" and "return" into MonteCarlo, which would have been more trouble than it was worth.

Picking a random item from a list is going to be necessary, and as seen below it is actually needed more than once. So:

-- Internal function to pick a random element from a list
pickOne :: [a] -> StdGen -> (StdGen, a)
pickOne xs g1 = let (n, g2) = randomR (0, length xs - 1) g1 in (g2, xs !! n)

Monad instance
Now for the Monad instance declaration. In this we have to declare the bind function (>>=) and the return function.

instance Monad MonteCarlo where
 MonteCarlo m >>= f  = MonteCarlo $ \g1 ->
    let
       (g2, xs)  = m g1
       (g3, x)   = pickOne xs g2
       (g4, f')  = case xs of
                      []   -> (g2, mzero)
                      [x1] -> (g2, f x1)
                      _    -> (g3, f x)
    in runMC f' g4

 return x = MonteCarlo $ \g -> (g, [x])

The return function shows the minimal structure for a Monte-Carlo action: wrapped up in the MonteCarlo type is a function that takes a StdGen state and returns the state (in this case unmodified) along with the potential results. If the action had used the generator then the result pair would have had the new generator state instead of the old one.

The bind (>>=) is a bit more complicated. The type for monadic bind is:

(>>=) :: m a -> (a -> m b) -> m b

In the MonteCarlo instance of Monad this becomes:

(>>=) :: MonteCarlo a -> (a -> MonteCarlo b) -> MonteCarlo b

The job of bind is to take its two arguments, both of which are functions under the covers, and compose them into a new function. Then it wraps that function up in the MonteCarlo type.

We unwrap the first argument using pattern matching to get the function inside "m". The second parameter "f" is a function that takes the result of the first and turns it into a new action.

The result of the bind operation has to be wrapped up in MonteCarlo. This is done by the line

MonteCarlo $ \g1 ->

The "g1" lambda parameter is the input generator state for this action when it is run, and the rest of the definition is the way we compose up the functions. We need to call the first function "m" to get a result and a new generator state "g2", and then feed the result into the second argument "f".

The "let" expression threads the random generator manually through the first two random things we need to do:

Get the possible results of the first argument as a list.
Pick one of these at random.

However there is a twist because the result set could be empty. This is interpreted as failure, and the "MonadPlus" instance below will explain more about failing. In addition the result set could also be a single item, in which case there is no need to generate a random number to pick it. So the f-prime value is the result of applying "f" to whatever item was picked, or an empty list if the "m" action returned an empty list. We also avoid getting a new generator state if the random pick was not needed.

Finally we use "runMC" to strip the MonteCarlo type wrapper off the second result, because the whole thing is being wrapped by the MonteCarlo type constructor at the top level of bind.

And there you have it. In summary, when defining an instance of "bind" you have to construct a new function out of the two arguments by extracting the result of the first argument and passing it to the second. This then has to be wrapped up as whatever kind of function is sitting inside your monadic action type. The arguments to this hidden function are the monadic "state" and therefore have to be threaded through bind in whatever way suits the semantics of your monad.

MonadPlus instance
MonadPlus is used for monads that can fail or be added together in some way. If your underlying type is a Monoid then its a good bet that you can come up with a MonadPlus instance from the "mempty" and "mappend" functions of the Monoid. In this case the underlying type is a list, so the "mempty" is an empty list and the "mappend" is concatenation.

instance MonadPlus MonteCarlo where
  mzero = MonteCarlo $ \g -> (g, [])
  mplus (MonteCarlo m1) (MonteCarlo m2) = MonteCarlo $ \g ->
     let
       (g1, xs1) = m1 g
       (g2, xs2) = m2 g1
     in (g2, xs1 ++ xs2)

Here the "mzero" returns an empty list. The bind operation interprets an empty list as failure, and so indicates this to its caller by returning an empty list. Thus a single failure aborts the entire computation.

"mplus" meanwhile threads the random number state "g" through the two arguments, and then returns the results concatenated. The bind operation will then pick one of these results, so "mplus" has become a kind of "or" operation. However note that the alternation is done over the results, not the original arguments. If you say "a `mplus` b" and "a" returns ten times as many results as "b" then the odds are 10:1 that you will be getting one of the results of "a".

One important combinator introduces a list of items to pick one from.

-- | Convert a list of items into a Monte-Carlo action.
returnList :: [a] -> MonteCarlo a
returnList xs = MonteCarlo $ \g -> (g, xs)

Finally we need to be able to run a MonteCarlo computation. You could do this using runMC, but that gives you the full list of results for whatever the last action was, which is not what you want. Instead you want to pick one of them at random. So there is a runMonteCarlo function that looks an awful lot like the bind operation, and for similar reasons. This returns a Maybe type with "Just" for success and "Nothing" for failure.

-- | Run a Monte-Carlo simulation to generate a zero or one results.
runMonteCarlo :: MonteCarlo a -> StdGen -> Maybe a
runMonteCarlo (MonteCarlo m) g1 =
  let
     (g2, xs) = m g1
     (_,  x)  = pickOne xs g2
  in case xs of
     []   -> Nothing
     [x1] -> Just x1
     _    -> Just x

Exercises for the reader:

Add a new combinator allowing access to the random number generator.
Each computation returns only a single result, but Monte Carlo methods depend on statistical analysis of many results. How should this be done?
Can we introduce a "try" combinator to limit the scope of failure?

New Software Technology: Blockage On Line

2007-08-19T01:40:00.000-07:00

This was originally posted to my old blog on December 14th 2006. It was discussed on Reddit so please don't repost it there. Since it was posted even stronger evidence has emerged showing the productivity increase from functional languages.
-----------------------------------------------------

This is the promised posting about why new software technology finds it so difficult to gain acceptance even when major improvements are likely.

To give you some idea of the scale of the problem, in 1997 Ulf Wiger wrote a paper entitled Four-fold Increase in Productivity and Quality. It described a practical experience with a mature technology (the Erlang language) on a significant new system by a large company.

Now Ulf Wiger is a well known proponent of Erlang, so the uncharitable might suspect some degree of bias and selective reporting. But however skeptical one might be of Ulf Wiger’s claims it would be a big stretch to think that he had invented or imagined the whole thing. The most likely explanation is that the reported results are broadly accurate.

So how come we are not all now programming in Erlang? I believe the answer lies in the “hill climbing” approach that most companies take to optimising their behaviour.

If you are lost on a foggy mountain then one way to reach the top is to simply head up hill. You don’t need a map or compass to tell which way that is, and eventually you will reach a point where every way is downhill. That is the top. Businesses are very much in this situation. There are lots of things a business could do that might work to increase profits. Some are big steps, others are small. The likely result, especially of big steps, is shrouded in fog. So the best thing is to move up the hill of profitability in small steps. Eventually you get to the top, and then you can rest for a while.

The trouble with this algorithm is that you are likely to have climbed a foothill, and when the fog clears you see that the real mountain is somewhere else.

Here the analogy breaks down because unlike real mountains the business environment keeps changing. Mountains go up and down over millions of years. In business the equivalent happens much faster. In fact many businesses have to run as fast as they can just to keep up with the foothills.

So now what happens when someone claims to have discovered a huge mountain in the distance? Three questions will immediately occur to the managers:

Is it real?
Will we survive long enough in the Lowlands of Unprofitability to get there?
Will it still be there when we arrive?

All three are extremely good questions, and I’ll analyse them in detail below. For brevity I’ll talk about new programming languages but the same arguments apply to many new software technologies, especially the ones that affect the way that you program.

Is it real?

Managers in the software business are bombarded by sales pitches for things that will make their software faster, cheaper and better. 90 out of 100 of these pitches are for pure snake oil. A further 9 are stuff that will work, but nowhere near as well as advertised. The last 1 will change the world, and possibly make you a fortune if you time it right. The trouble is, how do you find that diamond in all the dross? Each new sales pitch requires a lot of time and effort to evaluate, most of which will give no return on the investment. And in the meantime there are those foothills to keep up with. So managers learn to listen to the sales pitch, nod sagely, and then carry on as before.

I say “managers” because they are usually the ones who make the decisions, and are therefore the target of the sales pitches. Sometimes they can be evaded. The early days of Linux adoption were punctuated by anecdotes of IT managers declaring that Linux was verboten in their shop, only to be gently told that it was already running some piece of key infrastructure.

Will we survive long enough to get there?

At first sight a new programming language looks simple to deploy: just start using it. Unfortunately things are not that simple.

Any significant project is going to require a team of developers, and then on-going maintenance and development of new versions. This means putting a team of people together who all know the language, and then keeping them on the staff. Do you train them? If so how long is it going to take them to get productive? In the days of the great OO paradigm shift it was generally agreed to take months. On the other hand you could hire them, but how many people out there know the language? Probably not very many. Either way, if somebody leaves then replacing them will be problematic.

A software house that has been earning money for a while will have been doing so on the back of some body of software (the exception being pure “body shops” who just write code for customers). This software is the major strategic asset of the company, and in practice most of the development effort in the company is devoted to maintaining and extending existing packages. The only way that you can apply a new programming language to an existing software package is to throw away and rewrite the whole thing. At the very least this is a huge and risky enterprise: revenue from the old legacy will drop off fast if you stop developing it, and in the meantime you just have to hope that the new system gets delivered on time and on budget, because if it doesn’t you will go bust. Of course a rewrite of this sort will eventually be necessary, but the sad thing is that by then the company is not in good enough financial shape to take the project on.

Most software companies have diversified and do not depend on one monolithic software asset, so in theory you could do the rewrites one system at a time. This is still expensive and risky, but at least you don’t have to bet the company. But typically each major asset has a division looking after it, and from within the division the sums look just the same as for a smaller company with one big asset. So the only people who can make such a decision are the board of directors. I’ll come back to this point later.

The last option for a new programming language is a completely new product line. Here you are starting with a clean sheet. You still have training and recruitment issues, not to mention long term support, and you have to put together a whole new toolchain for the developers, but the proposition does at least look sensible.

Will it still be there when we arrive?

New technologies often don’t hit the big time. If the suppliers go out of business, or the open source community loses interest, then anyone who adopted the technology early is going to be left high and dry. A previous employer of mine opted for Transputers in a big digital signal processing project. The Transputer was technically ideal, but then INMOS went out of business.

Geoffrey Moore has described a “chasm” between the Innovator market (who will buy anything just because it is new) and the Early Adopters (who make a rational decision to invest in new things). I’m not convinced that there is really a chasm: people seem to have continuous variations rather than discrete types. But either way there is a real obstacle here. In effect everyone is waiting for everyone else to jump first.

So those were the rational reasons why companies tend to avoid new technology. Now for the, err, less rational reasons.

Most of these come down to the fact that companies are not like Hobbe’s Leviathan. As described in The Tipping Point, once you get past about 150 people in an organisation the people in it cannot keep track of everyone else. Hence you find lots of people at all levels working hard to optimise their bit, but inadvertently messing up the stuff done by someone else. Bear with me while I take you on a short tour of the theory and practice of management motivation.

Companies try hard to reward people who do the Right Thing (at least, the Right Thing for the company). This generally means short term evaluation on how they are doing at their main task. Sales people, for instance, get paid partly by commission, which is a very direct linkage of short term performance to pay. Other people get annual bonuses if their bosses recommend them for it, and of course promotion happens from time to time. And its backed up by social pressure as well: these people are being rewarded for doing the Right Things, and everyone else takes note.

All of this is absolutely vital for a company to survive: you have to keep your eye on the ball, nose to the grindstone and ear to the ground. However, as Clayton Christensen describes in The Innovator’s Dilemma, it also leads to a problem when a “disruptive technology” arrives.

An example of what goes wrong was Xerox PARC. As is well known, the researchers at PARC pretty much invented the modern Office software suite, along with graphical user interfaces, laser printers and ethernet. The usual myth has it that Xerox executives were too dumb to realise what they had, but the real story is more interesting. Xerox did actually go to market with a serious office machine, called Xerox Star. You or I could sit down at one of those things and feel right at home. But when it was launched in 1981 it only sold 25,000 units, which was far too few to make a profit.

The reason (I believe, although I haven’t seen this anywhere else) is that Xerox salesmen (and they were almost all men at that time) were experts at selling big photocopiers to big companies. That was the bread-and-butter of Xerox business, and the quarterly bonuses of those salesmen depended on doing that as much as possible. Anything else was a distraction. So when this funny computer thing appeared in their catalog they basically ignored it. If someone specifically asked for some I’m sure that any salesman would be happy to fill the order, but they weren’t going to waste valuable face time with corporate buyers trying to explain why a whizzy and very expensive piece of equipment was going to revolutionise everything. So Xerox concluded that there was no market for networked desktop computers and sold the whole concept off to Steve Jobs in exchange for some Apple stock.

Christensen has a number of other examples of this phenomenon, all of which are market based. This is probably because you can observe the market behaviour and success of a company, whereas just about everything else they do tends to be visible only on the inside, and often not even then. But the same logic applies.

Suppose you are a project manager, entrusted with Project X to develop some new software. You have had your plans and associated budget approved by the Committee That Spends Money (every company has one, but the name varies). And then some engineer walks into your office and starts talking about a programming language, ending with “… so if you used this on Project X you could do it for a quarter of the cost”.

Now, strange to relate, a project manager will not actually be rewarded for coming in 75% under budget. Instead he (even today it is usually “he”) will be told off for not submitting a better estimate. Senior managers do not like padded estimates because it prevents the money being invested more profitably elsewhere. Coming in a bit under your original estimate is OK: it shows you are a good manager. But coming in way under shows you are either bad at estimation or just plain dishonest (managers watch Star Trek too). Besides, you already have approval for your original plan, so why bother changing course now?

But you have also been around a bit longer than this engineer, and have seen some technology changes. So you ask some pertinant questions, like who else has used it, how long it will take the programmers to learn it, and where the support is going to come from. At the end of this you conclude that, even if this technology is as good as claimed, if you use it on Project X you stand a very good chance of blowing your entire budget just teaching your programmers to use it. This will not get you promoted, and might even get you fired for incompetence. So you thank the engineer for bringing this matter to your attention, promise to look into it carefully, and show him the door.

So now the engineer tries going up the ladder. Next stop is the Product Manager, who looks after the product line that Project X will fit into. He can see that there just might be a case for making the investment, but he has already committed to a programme of improvements and updates to the existing product line to keep it competitive. His annual bonus depends on delivering that plan, and this new language will obviously disrupt the important work he has been entrusted with. So he too thanks the engineer and points him out of the door.

Next stop is the Chief Technology Officer. He is vaguely aware of programming languages, but being a wise man he seeks advice from those who understand these issues (most geeks will find this surprising, but very few senior managers got there by being stupid). Meaning, of course, the project and product managers mentioned earlier, possibly with a trusted engineer or two as well.

These engineers know about programming. In fact they owe their position to knowing more about it than anyone else. This new language will make that valuable knowledge obsolete, so they are not well disposed to it. On top of that they find the technical arguments in favour of the new language highly unconvincing. Paul Graham has christened this phenomenon The Blub Paradox. If you haven’t already read his essay please do so: it explains this far better than I ever could.

In short, everyone in the company with any interest in the selection of a new programming languge can see a lot of very good reasons why it would be a bad idea. The only people who disagree are the ones who have taken the trouble to learn a new language and understand its power. But they are generally in a minority of one.

And this is true in every company. Every company has a few eccentric engineers who try to explain why this or that new technology would be a great investment. Sometimes they are even right. But they are almost never taken seriously. And so great technologies that could actually save the world a great deal of money on software development (not to mention improve quality a lot as well) languish on the shelf.

Why Making Software Companies Liable Will Not Improve Security

2007-08-13T09:44:00.000-07:00

(((This was originally posted to my old blog on January 28th 2007. However my host Blogthing went down almost immediately thereafter, so as far as I know almost nobody saw it. I'm now reposting it in response to the recent House of Lords report on e-crime. Bruce Schneier has commented approvingly on the report, including its recommendations for liability for security defects in software. So I think that now is a good time to repost this, including to Reddit.)))

----------------------------------

Bruce Schneier has written that the way to improve the current lamentable state of computer security is to impose mandatory liability on vendors for security breaches. I disagree: I think that this would have little positive impact on security, but a lot of negative impacts on the software industry generally, including higher prices, increased barriers to entry, and general reduced competition.

This is a bit worrying: Schneier is a remarkably clever guy who understands software, security and (at least a bit of) economics. His understanding may well exceed mine in all three areas . I’m used to nodding in agreement whenever I read his words, so to find myself shaking my head was a strange experience. Hence this blog post: whether I turn out to be right or wrong, I will at least have scratched the itch.

So, to the argument:

On the face of it, Schneier’s argument is impecable economics. Security is an “externality”, meaning that all of us pay the price for bad security, but only the software vendor pays the price for good security. In theory we should demand secure software and pay higher prices to get it, but in practice most people cannot accurately evaluate the security of a software system or make an intelligent trade-off about it. So system vendors (including, but not limited to, Microsoft) find it is more cost effective to trumpet their wonderful security systems while actually doing as little as possible. Security is more of a PR issue than a technical issue.

So the Economists Solution is to push the costs of bad security back on to the vendor, where they rightfully belong. Therefore you and I should be able to sue someone who sells us software with security defects. That way if we suffer from virus infections, spambots or phishing because some software somewhere was defective, we should be able to sue the manufacturer, just as I could sue a car manufacturer if I am hurt in a crash due to defective brakes.

So far, so fine. But now imagine you are a small software company, such as the one run by Joel Spolsky. You sell a product, and you are making a reasonable living. Then one day a process server hands you a writ alledging that a cracker or crackers unknown found a defect in your software, and used it to cause series of security breaches for many of your customers, followed by downtime, loss of business, theft from bank accounts, and a total of a million dollars of damages. It could easily put you out of business. Even if the claim is slim and the damages inflated, you could still have a big legal bill.

Obviously this is not useful: the point is to encourage the vendors to do better, and while hanging the worst one occasionally may encourage the others, doing so by a lottery won’t.

Part of the problem is that the economic logic calls for unlimited liability. So it doesn’t matter whether you sold the software for $5 or $5,000, you are still on the hook for all damages due to security defects. Of course the law could move to a limited liability model, capping it at, say, the price of the software, but that is still too big for most companies to pay out. Even if it was 10% of the price of the software, Microsoft is probably the only company with a big enough cash pile to survive an incident that hit 50% of its users. But 10% of the price of a piece of software is going to be only a very tiny fraction of the real cost of a security incident. It looks a lot more like a fine than real liability.

So if you are a software vendor then how do you protect yourself from such an incident? Of course you can tighten up your act, which is the whole point. But no amount of checking and careful architecture is going to protect you from the occasional defect that blows everything wide open.

You could buy insurance. Lots of professions have to carry liability insurance: its just a cost of doing business. Insurers will want to see you take proper steps to avoid claims, but will then cover you for the ones that do happen. Or, more or less equivalently, there could be a “safe harbour” clause in the liability law. If you can show that you have taken all proper steps to ensure the security of your system then its just bad luck for the customer and you are not liable.

The trouble with both of these solutions is that we do not have any way of deciding what the “proper steps” to either maintain your insurance cover or stay in the safe harbour are. There are lots of good practices which are generally thought to improve security, but they actually depend more on motivated people than anything else. From the developers point of view, the need to develop secure software is replaced by the need to reach the safe harbour. If the approved practices say you do X then you do it, and ensure that a written record exists to prove that you did it. Whether doing X actually improves the security of your product is irrelevant.

I’ve seen this effect personally. For a while I worked in an industry where software defects *do* give rise to unlimited liability, and where the government inspectors check that you are following the approved process. The industry was medical devices, and the government department was the FDA. The entire focus was on the paper trail, and I mean paper: signed and dated pieces of paper were all that counted unless you could prove that your CM system was secure according to yet another complicated and onerous set of rules (which we couldn’t). Worse yet, the inspectors wanted to see that you worked from the same records they were auditing, so you couldn’t even keep the training records on a database to find out who still needed what training: it was the signature sheet or nothing. In theory we weren’t even allowed to do software development on a computer, although in practice the inspectors merely noted that we were not in compliance on that point.

The impact of these rules on everyday work was huge and often counterproductive. For instance, it might have been a good idea to run lint or a similar tool on our C code. But this could never become part of the official process because if it was then the inspectors would ask to see the output (i.e. the dated, signed printout from a particular run), annotated with the written results of the review of each warning showing how it had either been resolved or why it could be ignored. Even if this could have been done on the computer, the overhead would have been huge. So it was cheaper not to put lint in the official process, and the resulting loss in real quality didn’t cost us anything.

(Actually individual programmers did compile with gcc -Wall at least some of the time, which is the modern equivalent. But because this wasn’t part of the official process I don’t know how many did so, and there was certainly no independent review of their decisions to fix or ignore warnings).

And despite our best efforts it was simply impossible to comply with 100% of the rules 100% of the time. The FDA knows this of course, so its inspectors just hang someone from time to time to encourage the others. Most of the QA people in the industry are ex-FDA people, so they know how the system works.

(Side note: in 1997 the FDA justified their regulation of medical device design on the grounds that over 50% of device recalls were due to design defects. I never saw any figures for the design defect recall rate *after* they imposed these regulations).

In short, I believe that any attempt to impose quality on software by inspection and rule books is doomed to failure. This approach works in manufacturing and civil engineering because there a good safe product *is* the result of following the rules. But software engineering is nowhere near that mature, and may never be because software is always invented rather than manufactured: as soon as we reduce the production of some category of software to a set of rules that guarantees a good result we automate it and those rules become redundant.

So, back to security. Much as I dislike the current state of computer security, I don’t see liability or regulation as answers. I’ve seen regulation, and I don’t think liability would look any different because it always comes down to somebody outside the company trying to impose good practice by writing a rule book for software development that the company must follow (and prove it has followed) on pain of bankruptcy.

It might be argued that an insurance market would seek the least onerous and most effective rulebook. I disagree. All forms of insurance have the fundamental problems of “moral hazard” and “asymmetrical information”, both of which come down to the fact that the development company knows a lot more about its risk than the insurer. From the outside it is very difficult to tell exactly what a software company is doing and how well it is doing it. As long as security improvement requires time and thought I cannot see any effective way to tell whether the right amount of thought has been dedicated to the subject.

At the top I said that enforcing liability would increase costs and barriers to entry, and thereby reduce competition.
Obviously risk brings cost, either in the money that has to be set aside to cover it or to pay insurance. The extra work required to preserve evidence of good practice will also increase costs. Finally, these costs will fall hardest on the start-up companies:

They are always short of money anyway
Setting up the process requires up-front work, and having your process inspected by possible insurers to get a quote is going to be expensive too
Maintaining the evidentiary chains is particularly hard when you are trying to modify your product in response to early feedback
Insurers will prefer companies with an established track record of good practice and secure software, so start-ups will have to pay higher prices

Put all of these together, and it really does add to the costs for small companies.

But suppose despite all the obstacles listed above we have our software, and its more secure. Not totally secure, of course, because there ain’t no such thing. Lets say its a web framework, along the lines of Rails or Twisted. It gets incorporated into a banking system, along with a web server, a database, an open source token-based security system and a set of front-end web pages written by a bunch of contractors being bossed about by some project manager employed by the bank. And despite everyone’s best efforts, next month a few thousand people have their accounts cleaned out. It seems they fell for a targetted trojan that performed a man-in-the-middle attack and then used a defect in the web pages to inject SQL commands that, due to another defect in the database, were able to disable the bank’s monitoring of suspicious transactions. Lawyers representing the customers, the bank, all the contractors various liability insurance companies, the database vendor and the web framework vendor are suing or threatening to sue. Industry observers think it will be a good year or two before some kind of settlement is arrived at. And what about the open source developers of the security system? It seems that the ones in the UK will be fine, but the ones in the US have already received writs. The law says that developers are only liable if they received payment for the development, so they thought they were safe. But their project web server was partly funded by a donation from the bank, and according to the database vendor’s lawyers that is enough to establish liability.

Responses to 'Silver Bullets Incoming!'

2007-08-12T04:06:00.000-07:00

(((
These are the responses originally posted to "Silver Bullets Incoming". Many of these responses are worth reading in their own right, and I'd like to thank the respondants for taking the time for such thoughtful posts.

Please do not post this to reddit, as it has already been discussed there under the original URL.
)))

Stephen Says:
December 9th, 2006 at 4:38 pm e
Paul:

I enjoyed your first article quite a bit - it got me thinking about technical language issues again (always fun).

I’d like to comment on your update to the original article. Specifically, I have some comments regarding C++

C++ is not an “old” language, incorporating many language features of more “modern” languages, including exceptions, automatic memory management (via garbage collection libraries and RIIA techniques), and templates, a language feature that is only available in C++, and that provides support for generic programming and template metaprogramming, two relatively new programming paradigms. Yes, C++ has been around a while, but until I see programmers constantly exhausting the design and implementation possibilities of C++, I won’t call the language “old.”

C++ was not designed to support just OO programming: From “Why C++ Isn’t Just An Object-Oriented Programming Language” (http://www.research.att.com/~bs/oopsla.pdf):

“If I must apply a descriptive label, I use the phrase ‘multiparadigm language’ to describe C++.”

Stroustrup identifies functional, object-oriented, and generic programming as the three paradigms supported by C++, and I would also include metaprogramming (via C++ templates or Lisp macros) as another paradigm, though it is not often used by most developers.

Of course, we should also keep in mind Stroustrup’s statement regarding language comparisons (”The Design and Evolution of C++”, Bjarne Stroustrup, 1994, p.5): “Language comparisons are rarely meaningful and even less often fair.”

Take care, and have a good weekend!

Stephen
pongba Says:
December 12th, 2006 at 11:26 am e
I found it so weird that, on the one hand you argue that haskell is fast( to the extend that it might be even faster than some compiling language such as C++), while on the other hand you said “where correctness matters more than execution speed its fine today”.
Does that sound paradoxical?
Another Paul Says:
December 12th, 2006 at 3:59 pm e
Paul:

“I think that Dijkstra had it right: a line of code is a cost, not an asset. It costs money to write, and then it costs money to maintain. The more lines you have, the more overhead you have when you come to maintain or extend the application”

By that measure, there’s no such thing as an asset. Think about that a moment - someone buys a general ledger or CAD/CAM system and modifies it as companies do. Either system reduces staff, provides more accurate information much more quickly, and renders the company more competitive. Take it away and what happens?

It’s been my experience that while these systems require maintenance (and sometimes a lot) they usually result in a net reduction in staff and the cost of doing business. And some types of systems provide a clear competitive edge as well. I think that makes many systems just as much an asset as a house, factory building, or a lathe.

Interesting article. Thanks.

Another Paul
BobP Says:
December 12th, 2006 at 6:07 pm e
>> An order of magnitude is a factor of 10, no less

> Well, the Wikipedia entry does say about 10. All this stuff is so approximate that anything consistently in excess of 5 is close enough.

0.5 orders of magnitude = power(10.0,0.5) = sqrt(10.0) = 3.1623 (approx)
1.5 orders of magnitude = power(10.0,1.5) = sqrt(1000.0) = 31.623 (approx)

If we are rounding off, a factor of 4 is about one order of magnitude; also, a factor of 30 is about one order of magnitude.
Jeremy Bowers Says:
December 12th, 2006 at 6:36 pm e
You missed my point with Python, or at least failed to address it.

My point wasn’t that Python is also good. My point was that you lept from “10x improvement” to “it must the chewy functional goodness!” But your logic falls down in the face of the fact that Python, Perl, Ruby, and a number of non-functional languages that also have a 10x improvement over C++, therefore it clearly is not a sound argument to just leap to the conclusion that “it must be the chewy functional goodness!” when there are clearly other factors in play.

I’m not criticizing Haskell or functional programming, I’m criticizing your logic, and you’ve still got nothing to back it up.

(This is par for the course for a claim of a silver bullet, though.)
Sam Carter Says:
December 12th, 2006 at 8:14 pm e
“Libraries and languages are complicit: they affect each other in important ways. In the long run the language that makes libraries easier to write will accumulate more of them, and hence become more powerful.”

This argument has a large flaw in it, namely the current state of libraries doesn’t reflect this claim. The largest and most powerful collection of libraries seem to be .NET, CPAN, and the Java libs, certainly not Lisp libraries.

But the advocates of Lisp would argue that it’s the most powerful language, and it’s clearly been around for a long time, yet the Lisp community has not accumulated the most powerful collection of libraries. So unless the next 40 years are going to be different from the previous 40 years, you can’t really assert that language power is going to automatically lead to a rich set of libraries.

I stand by my original comment to the previous article that programming is more about APIs and libraries than about writing their own code, and that if you are focused on measuring code-writing performance, you are just measuring the wrong thing.

I also disagree with the claim that this is unmeasurable because doing a real-world test is too expensive. As long as the project is solvable in a few programmer-weeks, you can test it out with different languages. I took a computer science class (Comp314 at Rice) where we were expected to write a web browser in 2 weeks. It wouldn’t be that hard to have a programming test which incorporated a database, a web or GUI front end, and some kind of client/server architecture, e.g. implementing a small version of Nagios, or an IM client, or some other toy application.

I’m sorry but writing a command line application that parses a CSV file and does some fancy algorithm to simulate monkeys writing Shakespeare is about as relevant to modern software engineering as voodoo is to modern medicine.
Paul Johnson Says:
December 12th, 2006 at 8:27 pm e
pongba:

I’m arguing that Haskell programs are faster to *write*. Execution speed is a much more complicated issue. FP tends to lose in simple benchmarks, but big systems seem to do better in higher level languages because the higher abstraction allows more optimisation.
Paul Johnson Says:
December 12th, 2006 at 10:54 pm e
Another Paul:

The functionality that a package provides is an asset, but the production and maintenance of each line in that package is a cost. If you can provide the same asset with fewer lines of code then you have reduced your liabilities.

Paul.
Paul Johnson Says:
December 12th, 2006 at 11:12 pm e
Jeremy Bowers:

Teasing apart what it is about Haskell and Erlang that gives them such a low line count is tricky, because it is more than the sum of its parts. One part of it is the high level data manipulation and garbage collection that Python shares with functional languages. Another part of it is the chewy functional gooodness. Another part, for Haskell at least, is the purity. OTOH for Erlang it is the clean and simple semantics for concurrency.

What I see in the results from the Prechelt paper is that Python was, on average, about 3 times better than C++ while the average Haskell program (from a sample of 2) was about 4 times better. Actually the longer Haskell program was mine, and I was really embarassed when someone else showed me how much simpler it could have been.

In terms of pure line count I have to conceed that Python and Haskell don’t have a lot to choose between them. A 25% improvement isn’t that much. Its a pity we can’t do a controlled test on a larger problem: I think that Haskell’s type system and monads are major contributors to code that is both reliable and short. Unfortunately I can’t prove it, any more than I could prove that garbage collection was a win back in the days when I was advocating Eiffel over C++.

Paul.
Paul Prescod Says:
December 12th, 2006 at 11:59 pm e
If you cannot “tease apart” what it is about Haskell and Erlang that makes them so productive then you cannot say that any one improvement is a silver bullet. It just feels truthy to you. Furthermore, if you are presented with counter-examples in the form of Python and Ruby then surely you must discard your thesis entirely. The best you can say is that there exist non-functional languages that are 10 times less productive than some functional languages for some projects.

Duh.
Paul Johnson Says:
December 13th, 2006 at 12:26 am e
Sam Carter:

On languages with expressive power gathering libraries; point mostly conceeded, although Perl certainly is a very expressive language, so I don’t think it supports your point, and .NET has Microsoft paying its mongolian hordes, so its not a fair comparison.

There are two sorts of libraries: general purpose ones (e.g. data structures, string manipulation, file management) that get used in many applications, and vertical libraries (HTTP protocol, HTML parsing, SMTP protocol) that are only useful in specific applications. There is no hard dividing line of course, but the usefulness of a language for general purpose programming depends on the language and its general purpose libraries. The vertical libraries have a big impact for applications that use them, but not elsewhere. So I would generally judge a language along with the general purpose libraries that are shipped with it. The special purpose libraries are useful as well, but its a secondary consideration.

Paul.
Paul Johnson Says:
December 13th, 2006 at 12:33 am e
Sam Carter (again):

Sorry, just looked back at your post and realised I’d forgotten the second point.

A worthwhile test is going to take about 10 versions to average out the impact of different developers. So thats 2 weeks times 10 coders is 20 developer-weeks, or almost half a man-year. Say a coder is on $30K per year and total cost of employment is three times that (which is typical). Round numbers $40-50 per language. Ten languages will cost the best part of half a million dollars to evaluate. Not small beer.

Of course you could use students, but on average they will know Java or Javascript better than Python or Haskell, so how do you correct for that?

Paul.
pongba Says:
December 13th, 2006 at 7:10 am e
I’m arguing that Haskell programs are faster to *write*. Execution speed is a much more complicated issue. FP tends to lose in simple benchmarks, but big systems seem to do better in higher level languages because the higher abstraction allows more optimisation.

I always hear people saying that, but I really don’t get it.
I know that *theoretically* abstraction( or non-side-effect, etc) gives more opportunity for optimization, but I have never seen people show some real data that can *really* prove it.
One question constantly annoys me - If higher-level of abstraction allows more optimization, then why .NET put the burden of discriminating value-types and reference-types on us programmers. Shouldn’t the referential-transparency-ness be better at this?
Jonathon Duerig Says:
December 13th, 2006 at 10:58 am e
I have two specific (and one general) criticisms to make about your line of argumentation:

First, I think you do not adequately address the criticisms about lines of code as a metric. The cost of a line of code is the sum of five factors: (a) Difficulty of formulating the operation involved (original coder*1), (b) Difficulty of translating that operation into the target programming language (original coder*1), � Difficulty of parsing the code involved to understand what the line does (maintainer*n), (d) Difficulty of later understanding the purpose of that operation (maintainer*n), and (e) Difficulty of modifying that line while keeping it consistent with the rest of the program (maintainer*n).

(a) and (b) are done only once, but �, (d), and (e) are done many times whenever the program needs to be fixed or modified. Brooks’ argument was specifically that in the general case the time for (a) is more than 1/9 the time for (b), and the time for (d) is more than 1/9 the time for � and (e). This is important because (a) and (d) are both language and tool independent.

When comparing the lines of code from different languages, it is important to realize that the formulation of the operations and the understanding of purpose are spread across those lines. And the verbosity of the language usually doesn’t impede either of these problems (unless it is extreme).

For instance, take the creation of an iterator or enumeration in C++ or Java respectively and compare that to creating a fold function in Scheme. These are roughly equivalent tasks. In C++, an iterator is defined first by defining a class with various access operators like * and -> and ++ and — and then implementing them. This adds a lot of baggage because there are half a dozen or so functions that must be defined and there is a separate class specification. In constrast, a scheme fold function is much simpler from the language perspective. A single function is defined rather than half a dozen. It will almost certainly have fewer lines, possibly by 4 or 5 times.

But let us look at what the creation of the iterator or fold function means from the perspective of items (a) and (d). Both of these are common idioms in their respective languages, so all of the code specifically dealing with iteration/folding is trivial to conceptualize and trivial to understand the purpose of. The difficulty in writing either a custom iterator or a custom fold function lies within the subtleties of the iteration. If it is a tree, what information needs to be maintained and copied to successive iterations (whether that be in the form of state, or in the form of argument passing)? Are there multiple kinds of iterations? How would they be supported? (For example, sometimes a user wants to traverse a tree in pre-order, sometimes in post-order, sometimes in-order, and sometimes level by level in a breadth-first order.) These are the questions which the original coder and the later maintainers will have to contend with. And these are really orthogonal to lines of code counts.

But there is another factor at work here which makes lines of code a faulty cross-language measurement. Every language has a grain to it. If you program with the grain, then any difficulty will be easily solved by the tools in the language. If you program against the grain, then you will run into difficulty after difficulty. This applies to fundamental language properties. You can bypass the type system in C++ and avoid all the type checks, but it is cumbersome and unpredictable if you do it wrong. Ruby allows you to be much more flexible with types and provides a safety net. If you try to enforce a more strict typing in Ruby, then you will have to fight the language every step.

But the grain of the language also includes the question of scale. Some languages provide a lot of flexibility. They allow compact and loose representations of programs which can be customized to the problem domain easily. These languages include Scheme and Ruby and Haskell. These flexible languages are very useful for small projects with one or a few developers because they can be metaphorically molded to fit the hand of the person who wields them. But there is a trade-off because they tend to be more difficult to use in large groups because it is harder for others to undestand what it going on. This is a fundamental trade-off that programming languages must make. And it means that a language which is great at one end of the spectrum will likely be lousy at the other end. And this is reflected in the lines of code required for a particular scale of problem.

My second criticism is in regard to your discussion of state. You point out that Brooks considered managing of state to be a major essential difficulty of programming and you then claim that functional languages obviate this difficulty and hypothesize this as the reason that they can be a silver bullet.

I believe that you have misunderstood the kind of state the Brooks was referring to. He was not talking about run-time state but compile-time state. He was not talking about what variables are changed at run-time. He was talking about the interactions between components of the program. These interactions are still there and just as complex in functional languages as in imperative languages.

Second, even when considering just the run-time state, the referential transparency of functional languages simplifies only the theoretical analysis of a program. As far as a normal programmer who is informally reasoning about what a program does, the programmer must consider how state is transformed in the same way whether or not a modified copy is made or a destructive write is made. This is the same kind of reasoning.

Finally, I have seen many people talk about getting an order of magnitude improvement by finding some incredible programming tool. Functional programming is not unique in that respect. But in my experience this is more likely to be about finding a methodology that suits the persons mindset than about finding the one true language or system. Somebody who thinks about programming in terms of a conceptual universe that changes over time will be an order of magnitude less effective in a functional environment. And somebody who thinks about programming in terms of a conceptual description of the result which is broken up into first class functions will be an order of magnitude less effective in an imperative environment.

I have programmed in both imperative and functional languages. I know and understand the functional idioms and have used them. My mindset tends to the empirical. I am a less effective programmer in such languages. But I have seen programmers who can pull a metaphorical rabbit out of a hat while tapdancing in them. This says to me that evangelism about functional languages or empirical languages is fundamentally misguided regardless of the side.
Paul Johnson Says:
December 13th, 2006 at 7:20 pm e
Jonathon Duerig:

I had decided not to respond to any further comments and instead get on with my next article. But yours is long and carefully argued, so it merits a response regardless. Its also nice to be arguing the point with someone who knows what a fold is.

You make the point that during maintenance the difficulty of later understanding the purpose of an operation is language independent. I’m not so sure. A maintainer may suspect that a C++ iterator is truly orthogonal, but it can’t be taken for granted. There may be a bug hiding in those methods, or perhaps someone fixed a bug or worked around a problem by tweaking the semantics in an irregular way. Also a lot of the understanding of a piece of code comes from context, and it helps a lot to be able to see all the context at once (why else would 3 big monitors be a selling point for coding jobs?). So terse code makes it a lot easier to deduce context because you can see more at once.

(Aside: I remember in my final year project at Uni going into the lab at night because then I could get two VT100s to myself).

You say that Scheme, Ruby and Haskell can be moulded to fit the hand of the user, making them more productive for single person tasks, but less productive for groups because of mutual comprehension difficulties.

This is hard to test because of the lack of statistics, but Haskell is strongly typed and the community has already developed conventions and tools for documentation and testing (Haddock and QuickCheck). I can see that Scheme macros can be used to construct an ideosyncratic personal language, but I really don’t see how this could happen in Haskell. Things that get done with macros in Scheme are usually done with monads in Haskell, but whereas Scheme macros are procedural monads are declaritive and must conform to mathematical laws, making them tractable. My experience with Haskell monads is that you generally build a monadic sub-language in a single module and provide libraries for it in some other modules (e.g. Parsec), and that the end result is intuitive and simple to use. But maybe I’ve only been exposed to well-designed monads.

On the subject of state and informal reasoning: personally I use whatever reasoning forms that will work. In debugging a particularly complex monad I once resorted to writing out the algebraic substitutions long-hand in order to understand how the bind and return operators were interacting. It worked, and I got the monad to do what I wanted. I routinely use informal algebraic reasoning of this sort in simpler cases in order to understand what my program is doing. Any informal reasoning must be a hasty short-hand version of what a full formal proof would do, and it follows that language features that make full formal proof easier will make the informal short-hand mental reasoning easier too.

Pure functions are particularly valuable when trying to understand a large program because you don’t have to worry about the context and history of the system for each call; you just look at what the function does to its arguments. In a real sense this is as big a step forwards as garbage collection, and for the same reason: any time you overwrite a value you are effectively declaring the old value to be garbage. Functional programs (at least notionally) never require you to make this decision, leaving it up to the GC and compiler to figure it out for you based on the global system context. Thus complex design patterns like Memento and Command are rendered trivial or completely obsolete.

Finally you talk about the many over-hyped technologies in this industry. Yes, hype is a common problem. Those of you who think you have a silver bullet are very annoying for those of us who actually do.

Paul.
Paul Johnson Says:
December 13th, 2006 at 7:34 pm e
Jonathon Duerig:

I had decided not to respond to any further comments and instead get on with my next article. But yours is long and carefully argued, so it merits a response regardless. Its also nice to be arguing the point with someone who knows what a fold is.

You make the point that during maintenance the difficulty of later understanding the purpose of an operation is language independent. I’m not so sure. A maintainer may suspect that a C++ iterator is truly orthogonal, but it can’t be taken for granted. There may be a bug hiding in those methods, or perhaps someone fixed a bug or worked around a problem by tweaking the semantics in an irregular way. Also a lot of the understanding of a piece of code comes from context, and it helps a lot to be able to see all the context at once (why else would 3 big monitors be a selling point for coding jobs?). So terse code makes it a lot easier to deduce context because you can see more at once.

(Aside: I remember in my final year project at Uni going into the lab at night because then I could get two VT100s to myself).

You say that Scheme, Ruby and Haskell can be moulded to fit the hand of the user, making them more productive for single person tasks, but less productive for groups because of mutual comprehension difficulties.

This is hard to test because of the lack of statistics, but Haskell is strongly typed and the community has already developed conventions and tools for documentation and testing (Haddock and QuickCheck). I can see that Scheme macros can be used to construct an ideosyncratic personal language, but I really don’t see how this could happen in Haskell. Things that get done with macros in Scheme are usually done with monads in Haskell, but whereas Scheme macros are procedural monads are declaritive and must conform to mathematical laws, making them tractable. My experience with Haskell monads is that you generally build a monadic sub-language in a single module and provide libraries for it in some other modules (e.g. Parsec), and that the end result is intuitive and simple to use. But maybe I’ve only been exposed to well-designed monads.

On the subject of state and informal reasoning: personally I use whatever reasoning forms that will work. In debugging a particularly complex monad I once resorted to writing out the algebraic substitutions long-hand in order to understand how the bind and return operators were interacting. It worked, and I got the monad to do what I wanted. I routinely use informal algebraic reasoning of this sort in simpler cases in order to understand what my program is doing. Any informal reasoning must be a hasty short-hand version of what a full formal proof would do, and it follows that language features that make full formal proof easier will make the informal short-hand mental reasoning easier too.

Pure functions are particularly valuable when trying to understand a large program because you don’t have to worry about the context and history of the system for each call; you just look at what the function does to its arguments. In a real sense this is as big a step forwards as garbage collection, and for the same reason: any time you overwrite a value you are effectively declaring the old value to be garbage. Functional programs (at least notionally) never require you to make this decision, leaving it up to the GC and compiler to figure it out for you based on the global system context. Thus complex design patterns like Memento and Command are rendered trivial or completely obsolete.

Finally you talk about the many over-hyped technologies in this industry. Yes, hype is a common problem. Those of you who think you have a silver bullet are very annoying for those of us who actually do.

Paul.
Toby Says:
December 15th, 2006 at 7:36 am e
Since I happened to stumble upon an actual Dijsktra cite just now, I thought I’d add it here (having read and appreciated your original post a few days ago).

In EWD513, “Trip Report E.W. Dijsktra, Newcastle, 8-12 September 1975,” he writes,

“The willingness to accept what is known to be wrong as if it were right was displayed very explicitly by NN4, who, as said, seems to have made up his mind many years ago. Like so many others, he expressed programmer productivity in terms of ‘number of lines of code produced’. During the discussion I pointed out that a programmer should produce solutions, and that, therefore, we should not talk about the number of lines of code produced, but the number of lines used, and that this number ought to be booked on the other side of the ledger. His answer was ‘Well, I know that it is inadequate, but it is the only thing we can measure.’. As if this undeniable fact also determines the side of the ledger….”

That is the edited version as printed in “Selected Writings on Computing: A Personal Perspective”. The original text can be found in the EWD Archive, at http://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD513.html

Original responses to '"No Silver Bullet" and Functional Programming'

2007-08-12T04:01:00.000-07:00

(((
These are the comments originally appended to the article. Many of them are thoughtful and worth reading in their own right.

As with the article, please do not submit this to reddit.
)))

Chris Morris Says:
December 7th, 2006 at 6:51 am e
” experts in several different languages were given a simplified spec taken from a real problem and asked to implement it.”

So, was the use of Haskell an integral part of simplifying the original spec given to the experts in the first place? To me, the essential difficulties of programming are in figuring out what the hell to really build in the first place. None of the programming languages in that study helped them do that. They skipped the bulk of the essential difficulties and went right into studying the effects on the accidental portion.
Craig Says:
December 7th, 2006 at 7:41 am e
I really enjoyed that, looking forward to your next blog.
Functional Lover Says:
December 7th, 2006 at 8:21 am e
You know why? Because all the colleges have been brainwashed by Java. Damned be they.
Paul Johnson Says:
December 7th, 2006 at 8:26 am e
There has been some discussion of this at http://discuss.joelonsoftware.com/default.asp?joel.3.424533.12

Paul.
Jonathan Allen Says:
December 7th, 2006 at 9:04 am e
From the study referenced:

> 1. The NSWC experiment was conducted in a very short time-frame with very little direct funding. Thus many corners had to be cut, including significant simplification of the problem itself; the largest of the prototypes was only 1200 lines of code.

> 2. The geo-server specification was by nature ambiguous and imprecise, thus leading to some variation in the functionalities of the developed prototypes. (On the other hand, the specification is probably typical of that found in practice, especially during requirements acquisition.)

> 3. The participants were trusted entirely to report their own development metrics. In addition, not all of the participants attended the first meeting at NSWC; those who did attend were advantaged.

> 4. No guidelines were given as to what exactly should be reported. For example, development times usually included documentation time, but there were major variations in the code-size/documentation-size ratios. In addition, different methods were used to count lines of code for each language, and it is not clear how one line of code for one language relates to that of another.

> 5. The review panel had very little time to conduct a really thorough review. For example, none of the code was actually run by the panel; they relied on the written reports and oral presentations.

The problem was grossly simplified, the code was rushed, the line count and time spent numbers questionable, and the final application never run.

This is your proof?

We don’t even know what those 85 lines of Haskel actually work with good inputs, let alone if they correctly responded to bad data.
Mike Griffiths Says:
December 7th, 2006 at 10:50 am e
I think you re missing the point with regard to the whole process of software development. Even orders of magnitude improvements in the process of writing code have no impact upon the problem of writing the right code - defining right as “fit for the required purpose” once the problem domain exceeds a remarkably small limit.
v Says:
December 7th, 2006 at 1:22 pm e
While the arguments you present in the bulk of your post are convincing, the hard data presented hardly seems so. How does low LOC = high productivity except in the wierd world where CMM makes sense?

What gets put down as code is but the distill of all the knowledge stored in a programmer’s head, and functional languages do demand a higher overhead of that storage space than imperative ones (more for historical reasons, i admit, but there it is).

Moreover, code building tools reduce the effort to actually input those high LOCs with automation that is improving by the day.

Can you present a better quantitative metric than LOC counts for functional languages being an order of magnitude better?
thomas lackner Says:
December 7th, 2006 at 3:07 pm e
You should link to information about the STM implementation in Haskell.. sounds very interesting.

I refuse to comment on the constant debate about programmer efficency, as I’m sure the same program would be 72 characters in K/Q!
hxa7241 Says:
December 7th, 2006 at 3:27 pm e
I have recently translated a minimal global illumination renderer from C++ to OCaml. It is about half the size — similar to the Ruby translation. The difference is in having class interfaces defined separately, and other small things.

The implication that functional is so much more compact and simple than imperative is wrong. Look at the granularity of abstractions: they are practically the same. If you still code with the same sized building blocks it will demand similar effort.

Also, well-made imperative code has many restrictions on state interaction. It is not so far away from functional code.

The only forseeable way to greatly improved productivity is with reuse: more, better libraries/frameworks and ways of using them. (As Brooks says.)
Achilleas Margaritis Says:
December 7th, 2006 at 3:48 pm e
As always, benchmarks are biased.

Getopt is a parser.

You can write a command line parser in a few lines of code in C++ using a library like boost::Spirit. For example (code not tested, just an illustration):

rule letter = range(’a', ‘z’) | range(’A', ‘Z’);
rule digit = range(’0′, ‘9′);
rule alphanumeric = digit | letter;
rule id = *letter << *alphanumeric;
rule num = +digit;
rule cmdLine = *('-' << (id | num));

There are many tasks in which functional programs are shorter and more concise, but these advantages are not due to the functional nature of a program, but due to design choices (better syntax, no semicolons, lambda functions etc). These advantages can happily exist in imperative languages too. The only difference is referential transparency, but, for me, it gets in the way.

Can we please see a MVC application with Haskell where the model is cleanly separated from the view?
Achilleas Margaritis Says:
December 7th, 2006 at 3:59 pm e
As always, results are biased.

The command line parser could be written in C++ with a Spirit-like framework like this:

rule id = letter << *alphanumeric;
rule num = +digit;
rule cmdline = *('-' << (id | num));

The advantages of FP come from concepts that can also be used in imperative languages: lambda functions and closures (Smalltalk/Ruby), simplified syntax (Ruby), etc. On the other hand, in pure FPs many things are unnecessarily complex.
anonymous Says:
December 7th, 2006 at 5:22 pm e
Your argument about the lack of states in functional programs is fundamentally flawed. FP-s appear to have no states simply because they describe what would happen (sort of.) However, in order for a FP to, well, run, someone, somewhere, must pull a lever so that the wheels start turning according to the spec of the FP, and what ticks under the FP ultimately does have state. I am not suggesting that there are no gains from functional programming, but the notion you offer is bogus as it stands.
Edward Ocampo-Gooding Says:
December 7th, 2006 at 5:23 pm e
A popular excuse for why programming folks all don’t immediately jump into functional programming is because it’s not as intuitive a paradigm as the procedural style.

I’d like to see a psychology study that measures programming proficiency vs. time trained with “fresh” students unaware of either paradigm and have two separate groups be trained.
I
You wish Says:
December 7th, 2006 at 5:34 pm e
And yet Lisp, which is considered a functional language, has been around since 1962 (it was spec’ed in 1958), and Brooks doesn’t point to it in his paper. Functional programming isn’t new, and it is certainly not a silver bullet.
Sam Carter Says:
December 7th, 2006 at 8:04 pm e
The reason why the whole world isn’t using functional languages is very simple: shitty library support. The real silver bullet for most programmers is access to large, high quality libraries, with the primary examples being the .NET runtime, or Java’s libraries. Programming tests that require writing 100% of the code from scratch are just flat out inaccurate, because you are measuring the wrong thing. The bulk of modern development time isn’t writing code from scratch. It’s writing code that interfaces with libraries for networking, or XML parsing, or database handling, or whatever (see http://www.joelonsoftware.com/articles/LordPalmerston.html for a fuller treatment of this topic). The functional programming language community is more interested in marginalizing their access to external systems rather than making it easier (research into monads being a great example of that).
Larry O'Brien Says:
December 7th, 2006 at 8:50 pm e
I intended to post the URL of some thoughts on your post, but your comment engine diagnoses dashes in URLs as indicative of spam. (Not so, I think.) Anyhow, http://www.knowing.net/PermaLink,guid,659c9535-6674-48f9-a4f9-8bc34fe724b5.aspx
Paul Says:
December 7th, 2006 at 9:39 pm e
Comparing Haskell to C compares a variety of design parameters at once: strong versus weak-ish typing, garbage collection versus hand collection, high level data types versus low-level ones, different libraries etc.

Based on my experience with functional languages and other high-level languages like Python, Ruby, Smalltalk, Javascript, Perl, C#, REXX etc,, I would guess that those other factors are MUCH MORE likely to be relevant than just the functional programming paradigm.

In addition, comparing lines of code for PROTOTYPING is pretty uninteresting. I’d like to compare lines of code for a functional application used by customers. What if the design decisions in a particular language are focused on robustness and maintainability?
Larry O'Brien Says:
December 7th, 2006 at 10:19 pm e
I’ve posted a reply at my blog. Unfortunately, I can’t paste the exact permalink, which your comment engine wrongly insists are spam.
Indeed You Wish Says:
December 7th, 2006 at 10:19 pm e
Certain problems are more easily solved with certain tools — let’s not fool ourselves, and believe FP solves all problems better.
Jeff Says:
December 7th, 2006 at 10:37 pm e
You can make any language look good by comparing it to C++. If being functional is the magic bullet, then why do stateful languages like Python, Perl, Ruby, Lua, Lisp, etc. always do just as well as Haskell in this sort of omparison?
Stuart Dootson Says:
December 7th, 2006 at 11:29 pm e
Unlike the rest of your commenters (as far as I can tell), I *have* used Haskell for real-world problems, and can confirm that (for the problems I’ve used it for), it is significantly more productive than imperative languages like Java, C++ or Ada.

I don’t think it’s quite ready for the maistream, but it’s definitely got promise.
Not Silver But Still Very Good Says:
December 8th, 2006 at 12:54 am e
I’m very sceptical about LOC as a measure. However, here’s a very recent informal data point, which I’m mentioning partly because it’s notable for the relatively controlled nature of the comparison: Lucian Wischik at Microsoft recently had to rewrite a 6,000 line F# program in C# (C# was required for unrelated reasons). It became 30,000 lines (references to comments by Lucian below). Now, this comparison is with essentially the same .NET libraries (F# adds a few minor libraries), the same (talented) programmer, the same .NET runtime, the same performance profile, the same problem specification, and the C# code has the advantage of being a reimplementation.

See Lucian’s comments on the Google group at microsoft.public.dotnet.languages.csharp at http://groups.google.com/group/microsoft.public.dotnet.languages.csharp/tree/browse_frm/thread/38a144ceaf101030/fb4664a7e4c27cf6?rnum=11&q=F%23&_done=%2Fgroup%2Fmicrosoft.public.dotnet.languages.csharp%2Fbrowse_frm%2Fthread%2F38a144ceaf101030%2F38d9aa4dbda50892%3Flnk%3Dgst%26q%3DF%23%26rnum%3D1%26#doc_814fd26871c2c6b7

More extensive analysis of the differences by Lucian at http://groups.google.com/group/microsoft.public.dotnet.languages.csharp/browse_frm/thread/38a144ceaf101030/38d9aa4dbda50892?lnk=gst&q=f%23&rnum=1#38d9aa4dbda50892
Josh S Says:
December 8th, 2006 at 1:53 am e
“However, in order for a FP to, well, run, someone, somewhere, must pull a lever so that the wheels start turning according to the spec of the FP, and what ticks under the FP ultimately does have state.”

That’s not the point. The point is that an FP utilizes a framework that *safely* translates from an abstract language without a concept of state to a concrete language that is basically nothing but state.

Likewise, object oriented languages do not actually have objects — whether they are detected at compile time or run time, they ultimately map to swaths of memory and functions.

It’s all smoke and mirrors. But it’s the magic of the smoke and mirrors that enhance our productivity. By building the funnel from a “safe”, “imaginary” language to the “dangerous”, “unproductive” one, we eliminate the problems inherent at the lower level.
Joel Says:
December 8th, 2006 at 2:41 am e
Functional programming is not usually adopted because so many real-world systems are almost entirely side-effects. Look at all the things a shell script does; it’s changing system state. What’s that JDBC app doing? Changing database state.

In the world of web applications, you’re always doing I/O. It’s almost all I/O. And that is state (of your I/O streams).

I’ve been looking at Erlang a lot recently. I have a serious jones for its concurrency constructs. They are as awesome as advertised. But man, you can’t do a decent thing with strings in that language. Seriously, it’s not much better than C. Python, Perl, even Lisp can do a lot of manipulation of the strings - things you have to do in parsing protocols and HTML and so on. But Erlang here is almost a non-starter. Ugh!

Then there is the subject of libraries. Some major languages provide many things you don’t have to reimplement. But do the functional languages? Lisp has been around the longest, but try getting a gui library that works on all of (SBCL,CMUCL,CLisp). Or a decent GUI on Erlang at all. Even Paul Graham, champion of Lisp as Solution To Everything, admits that you need massive libraries to be useful - it’s a goal he has for Arc.

At least Haskell has GTK+ bindings. I haven’t explored Haskell enough to comment on it. I just wonder why folks haven’t used it to do Yahoo! Store. If it’s that good, it will make someone money.
fez Says:
December 8th, 2006 at 5:07 am e
I would love to see a shootout between the various web frameworks (including any based on functional languages).

Something like the following:
- well-defined spec
- basic CRUD functionality for the most part
- some integration(s) with a third-party API (thus existing off the shelf libraries will be of use)

Let the best coders from each language duke it out. Record time spent for each segment of app development & log all commits to a Subversion repository.

Have a panel of neutral judges look at not just the time spent but also feature completeness and any other niceties the teams added in the time alotted, and give a score to each team.
Ulf Wiger Says:
December 8th, 2006 at 1:20 pm e
More references were asked for. Here’s one:

“Comparing C++ and Erlang for Motorola Telecoms Software”
carried out by Heriot-Watt University together with Motorola.

http://www.erlang.se/euc/06/proceedings/1600Nystrom.ppt

Two applications were re-written from C++ to Erlang, and one of the applications was benchmarked. The pure Erlang version was 2-3x faster, much more robust, and had 1/3rd to 1/18th the number of lines of code, depending on how you compare the libraries. Detailed analysis suggested:

“- Code for successful case – saves 27%
- Automatic memory management – saves 11%
- High-level communications – saves 23%” (slide 31)

Like all other studies, this one can certainly be debated. Does anyone have a reference to a study concluding that functional programming does NOT lead to a productivity increase?
tndal Says:
December 8th, 2006 at 3:04 pm e
You omitted that ISI Relation Lisp scored the most rapid development time by far: less than half the time required by Haskell.

Although the line count was greater, this version of Lisp cleaned the floor with Haskell as a productivity tool. And Relational Lisp is a mirror of Prolog.
Jason Says:
December 8th, 2006 at 6:42 pm e
Some points:

- LOC does not imply that less effort was involved in crafting the Haskell solution. Just less effort in typing it in.

- Some problems have greater susceptibility to different approaches. One small “real world” problem is completely inadequate.

- Double-blind experiments in this regard are, in fact, impossible, so this will remain a bench-race forever.

—
Jason
Joel Reymont Says:
December 8th, 2006 at 7:51 pm e
Paul, you may be interested in the latest article in my blog. See “Re-birth of a trading platform”. http://wagerlabs.com/2006/12/8/re-birth-of-a-trading-platform

Thanks, Joel
Larry O'Brien Says:
December 8th, 2006 at 7:51 pm e
Jason: “LOC does not imply that less effort was involved in crafting the Haskell solution. Just less effort in typing it in.”

Not so. In industrial systems, lines of code produced per month is essentially constant, regardless of language. Also, defect rates per KLOC is essentially constant, regardless of language. (ref. Capers Jones works on “language levels”) (In small programs, you definitely see greater variation.)

I agree with your other points.
Larry O'Brien Says:
December 8th, 2006 at 7:57 pm e
“Not Silver But Very Good” ref’s Lucian’s claims. The threads have little substance. I’ve been following Lucian’s Website and I feel that a grain of salt is called for. For instance, he wrote an F# program that displays a teapot in Direct3D; fair enough, but he makes it sound like the lighting and manipulation in 3D comes from a few lines of F# when, in fact, the “teapot in a viewport” is canned functionality that can be done in a few lines of _any_ language.
Ben Moseley Says:
December 8th, 2006 at 9:24 pm e
The thrust of your article is very close to the thrust of our “Out of the Tar Pit” paper which investigates FP (along with the relational model) as being very relevant to the Silver Bullet question - http://web.mac.com/ben_moseley/frp/paper-v1_01.pdf .
Not Silver But Still Very Good Says:
December 9th, 2006 at 3:26 am e
Re the teapot - you’ve got the wrong guy: Lucian works at Microsoft, and has never touched a DirectX teapot. I think you’re thinking of Flying Frog consultancy.
Ulf Wiger Says:
December 9th, 2006 at 12:50 pm e
I totally disagree with the idea that LOC wouldn’t matter. It’s not just a matter of the effort of typing in the code. Much of that extra code often represents “unnecessary” detail that distracts the reader, hides the core logic, and which also needs to be maintained. I’ve seen projects that have problems with keeping “boilerplate” code consistent when the system gets complex enough. Some projects resort to using modeling languages that generate the boilerplate. When judged as programming languages, these tools are usually quite crappy, but their supporters defend them based on the opinion that it’s still a lot better than having to code the stuff by hand. But there are good programming langugages that work at the same abstraction level as those modeling tools. We’ve also found that the learning curve for e.g. Erlang is much shorter than for e.g. UML or C++, contrary to the statement that FPLs would be more difficult to learn, or less intuitive.

My own conclusions are based on 10 years of working in and around very large software projects, with code volumes in the order of hundreds of thousand lines, or even millions. I’ve had the opportunity to review several projects using C++, UML, Java and Erlang. I get the feeling that many of the comments above come from very limited comparisons. That’s ok - you have to start somewhere. For me, it took 2-3 months to properly un-learn C++ and OO when I first started with Erlang.
anonymous Says:
December 14th, 2006 at 12:57 pm e
Josh S:

“That’s not the point. The point is that an FP utilizes a framework that *safely* translates from an abstract language without a concept of state to a concrete language that is basically nothing but state.”

Brooks was talking about the complexity arising out of the sheer multitude of possible states (or combinations thereof). In FP, you retain (at least in part) this very complexity in order to be able to produce any useful behavior, and whether this complexity is state-based or not, is totally irrelevant.

What’s left to argue about is whether complexity is significantly reduced by imposing the stateless view, and I for one am still a bit sceptical about any radical claims on that account, especially if well-designed programs/systems from both domains are compared.

Another point that comes to mind is that, paradoxically, FP actually inhibits stateful programming when you need it (and you almost always do when designing and implementing systems,) by making the complexity of combining states explicit. Inherently stateful models, on the other hand, will let you hide some of this complexity, be it at the still-present risk of coming up with something inconsistent.

It pays to note that, compared to the current state of the art in PP/OOP, the FP way of combining state is clunky even with the help of monads and monad transformers, in case you wanted to bring those into the argument.

Silver Bullets Incoming!

2007-08-12T03:50:00.000-07:00

((( This was originally posted on December 8th 2006 on Blogthing. It is reposted here because Blogthing seems to be permanently down. The original was posted to Programming Reddit and extensively discussed at the time, so please do not resubmit this version.)))

-----

First, an apology to those who have tuned in to read about the obstacles to technology adoption. I will get to it, but first I wanted to respond to the staggering set of comments to my post about functional programming. In addition to the ones here there is the thread I started at Joel On Software and over 100 posts at programming.reddit.com. Wow!

Some people tried to post here first, but postings are held for moderation even if you don’t get flagged as a spammer. Blogthing is apparently configured to reject URLs with hyphens, even though Blogthing puts hyphens in its own URLs. Anyway, one bit of pond scum posted a bit of JavaScript which automatically redirected a browser to some other site, so be glad you didn’t have to deal with that.

Also I’m sorry I couldn’t moderate more often, but I’m afraid that work and family take priority.

Anyway, on to some responses. I’m going to tackle the more common themes in no particular order:

Lines of code is a lousy metric

I think that Dijkstra had it right: a line of code is a cost, not an asset. It costs money to write, and then it costs money to maintain. The more lines you have, the more overhead you have when you come to maintain or extend the application.

Many people asked about development time, or pointed out that the Relational Lisp version in the US Navy study took even less time than the Haskell. However development time is often not available, when reported it is highly dependent on the programmer in question, and may not always be reported accurately (how do you count the time you spent thinking about the problem when driving to work?).

One study, which I am annoyed with myself for not remembering earlier, did collect coding time and found it highly variable, but on average the terser languages took proportionately less time. Implementations for the specimen problem in that study also exist in Haskell and Lisp. The average Haskell program was 57 lines, the average Lisp program was 119 lines, and the average Python program was about 80 (from the graphs in the article). C, C++ and Java all had averages around 240. The shortest program was in Haskell, with a mere 27 lines. The next shortest appears to be a Python program at about 40 lines.

It was just a toy problem, so not representative

True, but non-toy problems are too expensive to run statistical tests on. The Erlang ATM switch was a non-toy problem, but it was also not a controlled study with a statistically valid number of independent implementations. You can’t have both (unless you are an eccentric millionaire).

As several people pointed out, the Annual ICFP Programming Contest provides a non-toy problem and a tight deadline every year. Its a level playing field: the problems are hard and open ended, and any language may be used. Functional languages always dominate the top ten, and for the last 3 years the winners have used Haskell (although last year it was one of several languages used by the winners).

This kind of problem is obviously suited to functional languages, so they look artificially good

I hope I have cited a sufficiently wide range of problem domains, from text processing to geometry to telecoms, to be able to argue otherwise.

There is nothing in the way that functional programming languages work that necessarily fits them to a niche domain, although they do tend to shine particularly in applications requiring complex algorithms and symbolic rather than numeric computation.

Libraries matter more than languages

Libraries and languages are complicit: they affect each other in important ways. In the long run the language that makes libraries easier to write will accumulate more of them, and hence become more powerful.

There is no sharp dividing line between language and library. For example, Haskell has no loop construct built in to the language. Instead there are functions in the standard library to do the job of loops. Conversely Perl has regular expressions as a built-in type, whereas most languages treat them as a library. Therefore the programming environment as a whole should be judged, with language and libraries combined. I don’t know how well the studies above did this. I do know that the US Navy study did not have STL for C++ because it hadn’t been invented then.

C++ is an old language: you should compare it with modern languages like Python

Fair enough. Haskell is an order of magnitude better than C++, and maybe Java. Against Python it is merely significantly better.

An order of magnitude is a factor of 10, no less

Well, the Wikipedia entry does say about 10. All this stuff is so approximate that anything consistently in excess of 5 is close enough.

You can do functional programming in C++ with Boost

Yes I know. This argument reminds me of the early days of OO, when people argued that OO languages were not necessary because you could do the same thing in C with structures of function pointers. Yes you could, but it was a masochistic exercise. I haven’t played around with Boost, but I suspect the same applies. Trying to retrofit ideas from one paradigm into a language designed for another is generally a bad idea.

Python has functional programming stuff, so why do I need Haskell or Erlang? Anyway, purity just gets in the way.

You want Erlang for big, distributed, highly concurrent systems. There is simply nothing comparable.

If you aren’t persuaded by the scalability argument for purity then try this: the purity of Haskell lets the compiler do lots more optimisations. You could write code in either language to apply a series of maps and folds to a list, but Python would (AFAIK) generate all the intermediate lists, while the Haskell compiler would apply a deforestation transform to eliminate all the intermediate lists and therefore be lots faster. The Haskell compiler can do this because the intermediate functions are guaranteed not to have side effects, and therefore the order of execution can be rearranged at will.

Haskell isn’t ready for prime time yet

True, but its pretty close. The wxHaskell and Hs2GTK GUI libraries are currently being updated, database access works fine, GHCi is getting a debugger, and people are already using it for real work.

I wouldn’t recommend using Haskell on a 50-programmer-year bet-the-company project just yet, but for a small agile project where correctness matters more than execution speed its fine today.

“No Silver Bullet” and Functional Programming

2007-08-06T14:28:00.000-07:00

(((This was originally posted on December 6th 2006 on Blogthing. It is reposted here because Blogthing seems to be permanently down. The original was posted to Programming Reddit and extensively discussed at the time, so please do not resubmit this version.)))

-----

This post is about No Silver Bullet by Fred Brooks. If you haven’t already read this paper then trust me, you really should. It says a lot, and it says it far better than I ever could.

In this post I’m going to look at this paper in the context of functional programming. Brooks thesis is that there will be no technology that brings an order-of-magnitude improvement in software productivity “in the next ten years” (i.e. in the years 1987 - 97). This is because most of what makes software difficult to write is “essential” complexity (i.e. inherent to the problem) rather than “accidental” complexity (i.e. bought in by the implementation technology).

Brooks’ career had in fact spanned the adoption of a silver bullet. High level languages had replaced assembler, and led to an order of magnitude improvement in productivity. Brooks argued that assembler has a very high accidental complexity, but high level languages like C and Ada had already disposed of most of this, leaving only the essential complexity. Therefore the big wins had all been achieved, and only small incremental improvements were left.

In fact Brooks has already been proved right. It is now almost 20 years after he wrote, and no order-of-magnitude step has occured in mainstream software. Things have certainly gotten better, and some application domains have improved by an order of magnitude thanks to application frameworks. Ruby On Rails is certainly that much better for writing web apps than raw C on top of sockets. But outside of these niches software is still not much easier to write than in 1987. OO helped, but not by an order of magnitude. Garbage collection also helped, but again not by an order of magnitude.

Brooks argument that only essential complexity was left is founded in the size of the
state space of software. As the data and necessary processing increases, so the number of possible states grows. The data and processing are inherent to the problem, and so are therefore essential
rather than accidental: any technology must grapple with the same complexity.

But now lets look at this argument in the context of functional programming. Back in 1993 the US Navy ran a little test of prototyping languages: experts in several different languages were given a simplified spec
taken from a real problem and asked to implement it. Some results:

Ada 83: 767 lines

Ada 95: 800 lines

C++: 1195 lines

Haskell: 85 lines

So on that particular problem Haskell really was an order of magnitude better than conventional languages. Other studies have confirmed this result, although usually with somewhat lower degrees of improvement. Ulf Wiger wrote a paper called Four-fold Increase in Productivity and Quality about the use of Erlang in an ATM switch, although in the paper Wiger claimed to have seen as much as a 10-fold reduction in line count when C++ code was rewritten in Erlang. The Haskell implementation of getOpt took a mere 13% of the line count of the GNU C version. However you slice it, it looks like functional programming can deliver between 4 and 10-fold reduction in line count.

But is this truly a reduction in complexity, or is it just packing that the same into fewer lines? I believe the former, for two reasons.

First, Wiger reports that defect count fell in proportion to line count (i.e. defects per thousand lines of code was constant, but with fewer lines the Erlang code had proportionately fewer bugs). This strongly suggests
that Erlang was indeed hiding accidental complexity from the developers.

Second, “pure” functional code has no side effects and stores no state. Thus it completely evades two kinds of accidental complexity that are inherent to any conventional “imperative” code:

If the program lacks state, then there is no way that the number of states can become a problem.

The order in which statements are executed, and hence the execution trace of the program, is completely irrelevant. Thus execution order is revealed as a major source of accidental complexity which Brooks mistook for essential complexity, but which is eliminated in pure functional programs.

Of course not everything can be pure functional. Erlang has functions with side effects, and so the order of execution matters for those. But they are only used when necessary e.g. for I/O). If the bulk of the code employs only pure functions then it gains these benefits in proportion.

Haskell goes even further than Erlang. Stateful code is fenced off by the type system using a mathematical construct called a monad, and fragments of monadic code can be passed around and stitched together without the side effects escaping to mess up the pure code. Within a monad most of the usual vices of imperative programming are possible (although an uninitialised variable takes real effort). But like Erlang the bulk of Haskell code does not in fact have side effects, and the resulting lack of state makes Haskell programs easy to understand and safe to modify.

There is one more source of complexity that Brooks did not in fact tackle in his paper: concurrency. In 1987 concurrency was not a major problem in most systems. But today it is becoming a serious headache. Today applications are increasingly distributed and concurrent, and the urrent trend towards multi-core CPUs will make concurrent programming a real imperative for high performance applications. But concurrency is very hard to get right first time, and very hard to debug when you get it wrong. In other words it is a huge source of accidental complexity.

Both Erlang and Haskell tackle concurrency. Erlang was designed for telecom applications, which require both concurrency and reliability in large amounts. Erlang implements a simple message passing model of
concurrency with light weight threads based on Hoare’s CSP formalism. This represented the state of the art when it was designed in the late 1980s and is still far more robust than the Java model of object-as-monitor.

Haskell, on the other hand, has recently introduced “software transactional memory” (STM), which provides transactional semantics for ordinary variables. This was originally tried during the 1990s, but the overhead of tracking every access to every variable made it too slow for practical use. But the Haskell
implementation cleverly exploits both the rarity of state in Haskell programs and the way the type system fences it in. Side effects can occur within a transaction, but only to special STM variables. The type checker guarantees that these side effects cannot escape from the transaction until it is committed. Thus a transaction can be tried, rolled back, and retried as often as necessary without any change in
the behaviour of the program.

Both of these systems are very effective at removing the accidental complexity of concurrency. Erlang
programmers think in terms of concurrent servers and clients exchanging information, where each individual server acts as a transactional machine and no client can ever see the server state half way through a transaction. Haskell provides much more direct transactional semantics, but the overall result is the same: the programmer can ignore the concurrency on their own bit of program without having to worry about the rest of the system.

So: is functional programming an actual bona-fide silver bullet as defined by Brooks? I believe it is.
Functional programming is based on a sound theory of scalable software engineering, and the empirical evidence clearly and consistently supports the theory.

So if its so good, why isn’t the whole world using it? That will be the subject of my next blog.

Planning to port my old posts

2007-08-05T04:40:00.000-07:00

I used to have my blog on Blogthing. However that seems to be more or less permanently down now, so I've retrieved my old posts from the Wayback Machine and will be reposting them here in the next couple of days. I'll also post the comments as separate pages.

Homo Economicus and Other Straw Men

2007-08-05T02:22:00.000-07:00

Quite a lot of political arguments seem to depend on whether the economists have got it right. Broadly speaking (and yes, this is a horribly broad generalization with lots of counterexamples) the economists tend to favour more "conservative" policies such as trade liberalisation, low taxation and deregulation, which presents a problem for people who disagree with these policies.

Economics tries to be an academic discipline that is above politics. Whilst it doesn't always succeed, it does favour arguments with intellectual rigour over soundbites and statistical evidence over anecdotes. So if you are a politician or pundit who disagrees with the majority of economists then you have some explaining to do.

The most common starting point for such an attack is the "rational actor" assumption that lies at the foundation of most economic models. This makes a number of assumptions about people:

People only care about money. Actually this is an extra simplifying assumption. The basic rational actor theory supposes that people seek to maximise "utility" (i.e. whatever it is that makes them happy). In practice economists usually have to equate this with money on the assumption that money buys happiness.
They are universally greedy and amoral, and so if someone sees a way to get money then they will automatically go for it regardless of the consequence for others.
They see no difference between options that have the same "expected value". In other words they would see no difference between $10,000 in their pocket and a 10% chance of $100,000.
They are stunningly intelligent and informed, able at the drop of a hat to calculate which of half a dozen cell phone plans (each with its own combination of peak, off-peak, weekend, roaming, subscription charges, bundled handsets and monthly minutes) is going to minimise their phone bill for the next year.

This is not a pretty picture of human beings. It also has some obvious gaps. Why do people give to charity? In some cases they might be buying prestige and status, but thats not a universal explanation. More generally, why do some highly talented people prefer to work as teachers (notoriously underpaid) or go and work helping extremely poor people (some of whom are poor because they are mentally unstable, violent, drunk, or just have very bad personal hygiene). Whatever made Linus Torvalds write Linux it wasn't an expectation of monetary gain. Yes, he's got a job out of it, but there are are less risky and more lucrative ways of exploiting a talent like that than giving something away. For that matter I've written a bit of open source software myself. According to classical economic theory I should have spent that time beavering away at work earning myself a promotion.

The mythical human being who behaves like this is often termed "homo economicus"; economic man. He is such a gross approximation to real human beings that I often think of h. economicus as a stick figure portrait. For those who disagree with the "economic conservative" consensus this is a clear point of attack: demonstrate that economics rests on such shaky foundations and you can cast doubt on the conclusions. However this is very much a straw man attack. Economists use homo economicus because it makes economic questions analytically tractable, not because it leads them to pre-defined answers. In this they closely resemble scientists from other disciplines who will use linear approximations rather than precise models because they are analytically tractable. The key question is whether the analysis is sensitive to the difference between the simplified model and reality.

And the economic models based on h. economicus do seem to match with reality reasonably well. Countries with high levels of taxation, protectionist policies and generous social benefits really do seem to wind up with a lot more slums and shanty towns than countries with low taxation, open trade and limited social support. If protectionist policies were good for people as a whole then an economic embargo ought to be welcomed as an opportunity to build up national industries, when in fact its real impact can be economic destruction.

So I generally take a dim view of political platforms that dismiss economics. Economists are not always right (an old joke says that if you laid all the economists in the world end to end they still wouldn't reach a conclusion). But before I will vote for a politician who disagrees with the mainstream economic consensus I'd want to see a detailed rebuttal explaining exactly why the economists are wrong in this case. And complaining about h. economicus isn't going to cut it.

2007-02-12T09:56:00.001-08:00

I've decided to relocate my blog. Blogthing has been unreliable, so I'll try here instead.

Haskell for Alphas and Betas

2007-02-12T09:56:00.000-08:00

A few times now I've seen or heard an argument that goes like this:

Haskell is fine for people with the Hacker Nature, but there is no way that the average Code Monkey is ever going to grok recursion, let alone monads. Therefore Haskell is doomed for use in the Real World, and will forever remain a plaything of academics and over-enthusiastic start-up companies.

Lets call the people who can define new monads "Alphas" and the rest of the developers "Betas". First of all, its worth noting that most, if not all the people who make this assertion are in fact Alphas, and they might be surprised at how much some other people can understand. But I can accept that there are people out there who generate software, but for whom software is not a primary skill. For example a physicist who writes a numerical simulation of particle interaction in Fortran, or a financial trader who's understanding of how to price a swaption is embedded in Excel. And of course the favourite example: people who's primary job is the design of dynamic web applications and who know just enough to query a SQL database and convert the results into HTML. Some of these people are capable of groking the monad laws, but they are not interested in theoretical computer science. So how will they do in Haskell?

I think a clue comes from an experience report on Eiffel. The application was for financial derivatives back in the 90s. The developers used Eiffel to create a library of classes (which would now be called an embedded domain specific language) for derivative construction. It sounds not unlike the one proposed by Simon Peyton Jones in Haskell. Once the developers had generated a library of Eiffel classes, the people who understood derivatives could use the existing library to describe esoteric financial contracts and define the pricing algorithms associated with them.

This is the way that Haskell should go in the future. The Alphas can formalise the problem domain in a way that saves the Betas from having to understand any advanced stuff like GUIs, database access, and all the other stuff that makes our lives so interesting.

Excel is very much a case in point here. It has been called "the most popular functional programming language in the world", although of course it is not Turing Complete. But it shows that many people can get their heads around a system of linked equations, and even simple recursion where necessary.

But the real beauty of Haskell is that it doesn't have any built-in concept of flow of control. This may sound like an odd advantage, but it allows an embedded DSL to have a monad embodying its own domain-specific notion of control flow in which the cause-and-effect model follows the model of the domain experts rather than the rest of the language. Parsec (the recursive descent parser library for Haskell) is a good example: a parsing action can have side effects, but anything that happened in a failed parse is guaranteed to be invisible. Coming up with Parsec took some Alpha brains, but now any Beta can write a parser in Haskell without worrying about the interaction of side effects and backtracking.

Environments such as Vital may help to push this even further by providing an intuitive spreadsheet-like front end, but many of the Betas don't actually need it: they are happy with expressing their knowledge in source code; they just want a language that thinks the same way they do.

So I really don't think that Haskell has to be a closed world to the Betas. The Alphas will interpret the domain as a library of monad combinators, and the Betas can just use the library without worrying about details like the exact flow of control. Over time some of the Betas will come to understand and be promoted to Alphas, and the rest will continue to code unabated.