All entries for April 2008

April 30, 2008

Weak Typing vs Weak Testing

I haven’t written a blog post on anything vaguely related to Computer Science in a while, so here’s an effort to change that. Bruce Eckel (BE) wrote a noted entry a while back, which seems to have been heavily discussed in what the guardian would refer to as the ‘blogosphere’, I’m thinking the kind of inflamatory and inaccurate articles that get posted on prc (not to say there aren’t good articles, but I find it increasingly difficult to sieve for something new and interesting these days).

I don’t intend to discuss BE’s terrible misconceptions that are perpetuated by this article, for example his reference to C++ as strongly typed, or blame him for not fixing the myriad of problems that the language has, after all standards bodies are mirred in backwards compatibility issues and compromise. I will blame him for the link to his blog not working, but thats another matter entirely.

What I really want to discuss is the limits of testing. Thats not to say that testing software isn’t a crucial part of the development process, and has helped me to find numerous bugs in software that I’ve written over time, but it has its limits. Now I’m not talking about expressiveness here – its plainly apparent to me that a test written in a turing complete programming language can test any property of the program that a decidably complete type checking algorithm can. Thats not really an idiomatic approach to testing unfortunately, since once one writes a test that is harder to reason about than the computer program they are trying to debug they have got a problem trying to test their test harness. I’ve numerous times found that the mistake was in a testcase, or harness that I’d coded up rather than the program itself.

A considerable number of unit tests are of a very simple form, for example testing that the sum of the numbers in the list [1,2,3,4] is 10. This is to be encourage and is all well and good. Unfortunately the problem occurs when one tries to extend these simple test cases to check complex properties. Let us imagine we are trying to write a function that sums up some numbers in a list, and we want to be confident that this function terminates. This is a trivial problem that I find it hard to think of how to test. Let us consider the following implementation, written in ML.

fun sum [] = 0
    | sum (h :: t) = h + sum t;

I can be highly confident that this function terminates because I am using primitive recursion. This is a highly important approach in the development of usable theorem provers, for example the Isabelle theorem prover automatically generates proofs of termination for functions that are defined using primitive recursion. It is also easy to see how one would construct such a proof informally for this function:

1. Base Case: the list is empty so Its sum is 0. Statement holds true vacuously.
2. Inductive case: we have a list of length n. We assume that the sum of a list of length n-1 terminates and we know the addition function takes a finite amount of time to compute. Thus conclude that summing a list of length n terminates.

This is pretty much a trivial case for any primitive recursion function in ML. Our type checker helps us here – case exhaustiveness is checked for the function’s domain, in case we forget any possible cases. This may seem trivial for this function – but its incredibly useful. For example if one is writing an interpreter based on an IR composed from a union type of different datatype constructors for different IR elements.

I find it hard to convince myself that the python (chosen because of Mr. Eckel’s rampant fanboying) equivalent terminates. I have implemented the function like this:

def sum(l):
  total = 0
  for i in l:
    total += i
  return total

I don’t know where to begin in formulating a testcase to check termination. If someone does – then please comment on this blog, I’d really like to know if its possible.

A quick superficial glance would suggest that the foreach loop used here would allow me to conclude termination, but unfortunately it only return iterable items. Here’s an example:

def inf():
  i = 0
  while(True):
    i = (i + 1) % 100
    yield i

print sum(inf())

I can’t use static type checking to ensure that the parameter is a List unfortunately. I could add a decorator with explicit type checking, but unfortunately this can simply be monkey patched away. Similar problems exist if I choose to write this function in Java. For example:

int sum(Iterable<Integer> entries) {
    int sum = 0;
    for (Integer i: entries) {
        sum += i;
    }
    return sum;
}

Since one could implement an iterable that always returns true. This can be resolved in Java (I think) through the following changes:

1. Write your function like:

int sum(ArrayList<Integer> entries) throws Exception {
    if(entries.getClass() == java.util.ArrayList.class) {
        int sum = 0;
        for (Integer i: entries) {
            sum += i;
        }
    return sum;
    } else {
        throw new Exception("Might not terminate since you are using a subclass of ArrayList"); 
    }
}

2. Use a custom security manager in order to ensure that system classes have been replaced.

This has obvious disadvantages – for example if one later decides that you want to use a LinkedList or a Vector. It also assumes that no one has replaced the system classes files (e.g. rt.jar) with miscreant ones. Though obviously that could be checked using the Class Data Sharing parameters. All in all – its a massive bunch of hacks that one doesn’t want to be forced into doing just to be convinced that a damn sum function terminates!

So here’s an open challenge – can anyone convince me that they can write a simple sum function in a weakly typed language (static or dynamic) and be sure that it terminates. If you can do it via testing then its bonus points! Either way you get my respect. Note that this is my definition of weakly typed languages – anything with a type system with more loopholes/problems/lack of expressiveness in than ML is weakly typed.


April 21, 2008

Council Elections 2008

Coventry

It seems a bit unfair of me to have already mentioned the London Mayoral elections, given their massive media coverage, without having talked about our local vote on 1st May. Its council election time!

Practical Points
The election is on May 1st. It is now too late to apply for a postal vote, Your polling card will specify what what ward you live in, and where you need to vote. If you can’t be bothered to move, you can find out here . I live in Whoberley, which has a wikipedia page that really needs improving, and if you live on campus you are likely to be in the Wainbody ward. Each ward has three councillors, for a total of 54 councillors in Coventry City Council. One will be elected this election. You can find out who is running here If you live in whoberley and are confused by the map on the polling card then I’ve created a Google Map .

Background
Historically Coventry has been a Labour stronghold. They held control of the council every year from 1973 to 2002 with the exception of 1978. The conservatives took over in 2006, with a period of no overall control in between. Both Wainbody and Whoberley have currently three conservative councillors. In wainbody in 2007 the conservatives took 56% of the vote, approximately 2.5 times the number of votes that the second place candidate came in. A student (Emma Biermann) stood for election as the Green Party candidate, coming in 4th place with nearly 9% of the vote.

Whats worth noting is that there are approximately 4,000 students living on campus at University of Warwick, the university registers everyone to vote, and the total turnout in wainbody at the last council elections is also about 4,000 people. In other words a highly motivated student populace could not only swing a close vote – they could vote in whomever they wanted. (Assuming of course that not too high a percentage of campus dwellers are ineligible to vote.)

In Whoberley the conservative majority in 2007 was only 127 votes. Furthermore, the incumbent Conservative Councillor (Joan Griffin) has been booted from their ticket due to health scares, but is running as an independant. I suspect this will split the vote, and offer somewhat of a spoiler for the conservative party.

Whoberley
I’d really like to cover the liberal democrats at these elections, but they don’t really seem to be making much of an effort to get my vote. The Labour Party has put out a full, front, page ad in the Coventry Times, whilst the Conservatives have sent out quite good looking flyers. I have received no such information from Brian Rees Lewis (who also ran as the Lib Dem candidate last time). I can’t even find his name listed on their website. Their website is also incredibly uninformative. They have 9 days to shove something under my door if they want me to care.

Joan Griffin seems to be emphasizing school discipline and minimising the number of drinking licenses handed out. Both of these policies put me off. The conservatives and their candidate Roger Bailey have made a series of commitments for the next few years:

“Continue the ‘Contact and Connect’ service for our elderly residents” & “Keeping council tax rises below pensions” – I think is probably a good thing overall, and that policies should be sympathetic to the needs of those on fixed incomes, but its not really a key issue for me.

“Keeping Pool Meadow open” & “Keeping weekly refuse collections” – I don’t believe any party has the balls to close it, so this seems like rabble rousing to me. Also neither of these are new policies, so making pledges on them is a pretty weak campaigning effort.

Expanding recycling – thats a great pledge, but the council also wanted to allow building on Hearsall Common before a residents petition (organised by Lib Dems in the apparently vastly more active neighbouring region) stopped it . There’s more to environmental issues that just recycling and its a very vague pledge – they don’t specify what they will actually do to improve recycling.

The Labour candidate for Whoberley, Bally Singh, seems to be making a strong effort – lots of emphasis on consultation and a blog. He also also emphasises working with other people – quite important since I expect that Coventry will remain a Conservative controlled council even if he is elected, so he will need to force change from a minority position – a hard task to accomplish. He provides 3 policy pledges:

“Protect our local environment” – he specifies problems here well (Hearsall Common, Watchmakers Building, litter) though not solutions. He also a more broad ranged view of environment than the Conservative Pledges.

“Challenge Anti Social behaviour” – I have no sympathy for ‘anti-anti social behaviour policy’. He somewhat redeems himself by discussing how they can work with the local MP to try and get more activities for people to do.

“Improve our council services” – He doesn’t actually say what he will do, but he does talk about consulting with the community, so this pledge is somewhat worthless, but not entirely.

Your Vote
Please do vote in your local council elections. I’ve presented what I think is a useful summary of information, so you have no excuse.


April 11, 2008

Tibet

Recently a lot of campaigners have argued the case that China shouldn’t be allowed to hold the olympics due to its ongoing occupation of tibet. It has been proposed that a boycott would reduce the positive publicity that the Chinese would be getting from their hosting activities. Gordon Brown announced the other day that he wouldn’t be present at the opening ceremonies. Media fetishism suddenly turned this into some kind of important stand again Chinese policies on tibet. This was denounced by Downing Street in an effort not to upset diplomatic relations.

But even if he hadn’t turned up – how is that progress? I can’t imagine Wen Jiabao trembling in his boots. Do we think that not having to shake some fat Scottish bloke’s hand is the biggest stand we can make on foreign policy? Is that what being a world power means these days? We fight wars against 3rd world countries actively and via proxy and yet here we are facing the another major country and all we can manage is a minor diplomatic snub? Will the historians of the 22nd Century ever enscribe the sentence “Chinese human rights abuses were cleaned up thanks to a second rate act of gesture politics by an unpopular 1/2 term prime minister?” I sincerely doubt it.

The key issue here is that whilst people have been caught up in the idea of denying China the publicity and support that the Olympics brings – we politcally, legally and by implication morally acquiesce to their acts. We’ve somehow managed to completely the obvious fact that Britain recognises Chinese rule over Tibet. We signed a treaty with the Qing empire in 1904 and ratified it in 1906. We officially considered it part of the Republic of China when dealing with Chiang Kai-shek in the second world war. When the west decided to be less hostile to the PRC the Tibet issue was ignored.

Bottom line: if you really want a stand from Britain on tibet – don’t boycott the olympics. Call for an Act of Parliament changing Britain’s recognise Chinese borders to exclude tibet. Now that really would be a stand on the matter.


April 03, 2008

London Mayoral Election

In respense to several requests I’ve deided to hand an entry over to the London Mayoral election. See here for details of polling figures I refer to.

ICM are normally about 1-3% left of yougov, so I would have expected Johnson to be about 7-8% ahead, not 2% compared to the existing yougov polling. So there’s likely a methodology difference. ICM polling focussed on ensuring their survey had a weight average of ethnic minorities at the same level as their percentage of the London population. This is according to their announcement, and with reference to Livingston’s apparent criticism of the yougov polling.

Judging from the yougov blog they seemed to focus more on socio-economic groupings when trying to make their surveys representative, but this stuff tends to be quite hazy – polling isn’t as scientific as it ought to be. Furthermore historically ethnic minorities have poor turnout rates, so choosing the percentage of population is highly likely to overestimate their impact. So verdict is still out on which poll is more representative. Bear in mind the ipsos/mori polling from about a month and a half ago had Livingston ahead, but that was labour party funded and looking pretty out of date now.

Boris fell by 2% between the last two yougov polls, but this is within the margin of error of the poll, so can’t really be considered a trend without supporting evidence (comparing with ICM would be particularly flawed, since they are using a different methodology for deciding who to survey). Quantitative evidence seems to suggest that Boris is ahead, but by an indeterminate amount. A few points to consider:

1. Boris has a large financial advantage, according to both sides – he claims to be aiming at raising £1 million. This will come into play more as the campaign continues. Since I doubt either side is spending much at the moment (since the campaign is really only just started) it probably isn’t in the numbers already.
2. Large blatantly don’t know how to attack Johnson. First they tried calling him a racist then a right wing clown. The racism charge was never going to stick, and Johnson seems to have made a significant effort to behave in a more serious manner in the run up to this campaign. As incumbent Livingston has the massive advantage that he can do things, where as Johnson merely has to say them, therefore by allowing this to become a personality race Livingston gives away his big advantage and plays into Johnsons. When he first came to office he pushed the congestion charge as a radical policy, that both polarised debate and pushed popular voting his way. In order to make a comback in this race he needs another ‘big idea’. No new bendy buses and increasing congestion charges just won’t do.
3. I imagine given their traditional strength in London that the Labour party would have much more ‘on the ground’ support. This is hard to quantify, however and highly personality dependant. Frequently heavy in your face campaigning turns people off, whilst a personal chat from a respected neighbour might be the best campaigning method.
4. Location of votes – Livingston will dominate central London, whilst Johnson takes the suburbs – this seems to be so strong that even amongst informal conversation with people I know, people living in West London seem to support Johnson, and more central/city centre support Livingston.
5. According to the labour website tag cloud they seem to be really interested in Boris Johnson, he has more tags (41) than Alan Johnson (29), Alistair Darling (7), David Miliband (13), Harriet Harman (24), Hazel Blears (32) and Hilary Benn (37). I bring this up as interesting, rather more than informative and let the readers draw their own conclusions.

My guess is that Boris’ lead is reasonably strong, but overturnable, so in summary – he’ll win if he doesn’t stick his foot in his mouth or if Livingston doesn’t pull anything out of the hat.


April 01, 2008

Some thoughts on the Labour Party

I haven’t blogged for a month, and US politics isn’t really worth covering atm (in short, Obama will take the democratic nomination, but it’ll be painful for a few weeks yet, and polling numbers vs McCain aren’t worth analysing for a while yet). So I return to my home ground of British politics.

A short while back a friend of mine felt that the early years of the Blair government (his first term basically) were the best for the British people during his lifetime. This is a sentiment shared by media analysts, people who believed in Blair, his brand of 3rd way politics. (A brand is not a paradigm, perhaps I am too cynical) In my considered opinion this is not the case.

In my opinion for a government to be considered of note or above average they must achieve a victory on a major issue over their political foes. A victory can only be claimed when their opponents are forced to concede the point politically.

An example of this is the formation of the National Health Service by the Attlee government. It was opposed at the time by the conservatives, but it has never been dismembered. One can argue over side issues – like differences in service in different parts of the country or internal market reforms for example, but the principle that it is the obligation of the government to provide for the health of the nation is not under political threat.

Another example is the change in economic policy during the thatchers years: principly privatisation of government services and emphasis of the importance of monetary, rather than fiscal policy. Keeping to these policies has become a fundamental part of the set of policies that the labour party have been elected on over the last few years, even though they have begun to overspend somewhat.

Which leaves the open question: What have the New Labour Government done to justify the praise. As far as I can see there are several key issues, none of which are ‘victories’.

Foreign policy – pre-emptive military aggression, backed by Bush and Clinton. This hasn’t proved to be popular with voters, or been a key issue battle with the Conservative Party.

Constitional Reform – with the growing nationalism in both Scotland and Wales this could be seen as a successful labour policy. Unfortunately its not exactly unilaterally accepted, a lot of English voters are wondering why their taxes are subsidising Scottish and Welsh extravagense, the NHS is no longer national, and I suspect that Britain won’t maintain its integrity throughout my lifetime. Upper house reform has also failed to achieve anything of significance – instead of two democratic houses we have gone down an appointments route.

Fox Hunting – passed through massive majority of labour voters in the house, this issue has been heavily protested by the people it actually affects, nearly no one else thinks its in any way important and the key arguments for and against haven’t been challenged. It also isn’t fully enforced.

Minimum Wage – another possible example of a major victory by Blair, the fact that it was set at the same level as most entry level jobs were paying rendered it null and void. Portillo may have caused a stir by accepting it, but ultimately it was more reflective of the internal divisions the conservatives faced at the time, than a like/dislike of the policy.

Independance of the BoE – this is a Thatcherite policy, and since its passing Hague has commented that he felt he was in opposition, and was obliged to disagree with the government on policy, not that he was fundamentally opposed to its passing.

Now I have reached the end of my post, I remember why I’ve been so much more interested in American politics than British politics. (In a Walter Sobchak-esque voice) Say what you want about the tennents of George Bush, but at least he had an ethos.


April 2008

Mo Tu We Th Fr Sa Su
Mar |  Today  | May
   1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30            

Search this blog

Tags

Galleries

Most recent comments

  • Apart from the plea "can I have your old one?" (the yearning never diminishes) I'd like to leave you… by Sue on this entry
  • Unfortunately I still haven't seen a film for which you have to read up on quantum mechanics as I mi… by Sue on this entry
  • I've never been to watch a film before when it's been recommended that you first read up on quantum … by Sue on this entry
  • Well this is very interesting, i really liked reading this blog, this was very informative and very … by Mio Navman Spirit S300 on this entry
  • I thought it was fascinating. Griffin isn't like any other, media–trained, polished politician, and … by Tim on this entry

Blog archive

Loading…

Hello

Not signed in
Sign in

Powered by BlogBuilder
© MMXXII