Monthly Archives: February 2008

Notes on the ensuing year

Uni goes back next week, and after a long, and mostly uninteresting holidays, I’ll be quite glad to go back. Not that my holidays were awful (NCSS and LCA made sure that they weren’t), but it’ll definitely be good to go back to some form of long-term regularity, which has been missing for the past few months. This semester I’ll be studying three maths units (Algebra, Calculus and Operations Research, all at 2nd-year level) and the third year Concurrent Programming unit, which should be interesting (and hopefully difficult, challenging, and all of those other adjectives which acadmically-oriented people like to hear).

One thing that I thought might be worthwhile this year is to set some goals that fall outside the usual inevitabilities of an academic year, mostly because all these years that I don’t, I tend to somehow let the uni/school-related ones take hold (and that normally makes the following December a lot more depressing than it needs to be), and in order to hold myself to this, I’m posting them here for the world to see:

  1. Use LaTeX more. Using LaTeX to write up my Calculus 1B assignments last year seemed to coincide with a marked increase in marks for that subject (in comparison with the previous semester, in which I didn’t) — in fact, the only >90%-achieving subjects I’ve undertaken were the ones where I used LaTeX to write up my asssignments. Coincidence? I think not! Of course, the reasons I’ve just given aren’t probably very sound, and there were probably better reasons for my doing well in those units, but there’s still good reason for me to learn it better. So I will.
  2. Improve my placing in the Programming Competition. Last year, my team achieved 16th (equal 11th according to the official standings). I want my team this year to achieve 12th or better. I’ll figure out how to do this later on.
  3. Better promote Free and Open Source Software at Uni. This one is important: UTas is hosting Linux.conf.au next year, and in my opinion, the cause of Free Software is not very well-known within the student body. Therefore, I’m going to try and hold as many events as possible (probably through the Computing society, whatever it may be called this year), including one just before Software Freedom Day in September (Since this is the big FLOSS advocacy day, it would be silly not to do something then). I’ll also try to promote LCA2009 amongst the staff and students.
  4. Get more involved with TasLUG. I’ve said it once, and I’ll say it again: I was shocked to find out that TasLUG still exists, let alone that they were considering a bid for LCA2009. Now that I know that they do indeed exist, I’ll be doing my best to become an active member of the local FLOSS community.
  5. Organise a Python MiniConf for LCA next year. This one’s really a no-brainer. I like Python, and from what I could gauge at LCA this year, there’s a big Python community within Australia. Therefore, I think it’s worthwhile that we have an organised conference at LCA, so I’ll be trying my hardest to make that happen (if you think you can help here, send a mail to any_name_at_all at this domain).
  6. Make a concerted effort to get involved with a Free Software project. Unfortunately, this goal seems to show up every year. I’m definitely going to make a concerted effort on this one, and I’ll aim to participate in the Australian Summer of Code next summer (since I know that that’s going to happen). Currently Python looks good, but we’ll see how that progresses through the year.
  7. Better promote NCSS within Tasmania. Another obvious one — Attending NCSS as a student was a great opportunity for me, and going back as a tutor was wonderful. I want to make sure that more people get that opportunity.

And there you have it. I’ll make periodic posts this year as I work on achieving these.

Python Ugliness

UPDATED: The code I posted initially had a slight bug in it, this has since been fixed. There is another bug in this code, which is addressed at the end of the post.

This is part two in a continuing (maybe) series about writing Perverse sorting algorithm implementations in Python — part one can be found via this link

After discovering the three-line Quicksort, and showing it to a friend of mine, I was challenged to come up with an implementation of Merge Sort in a similar length of time. I was fairly certain that it couldn’t be done, until I discovered some really nasty features of Python that probably aren’t meant to be exploited in the way that I’ve done so. And so here’s the result (reformatted for line-length issues), followed by a commentary on why this is as damn-awful as I say it is:

 def msort2( L ): a,b = ((len( L ) > 1 and (msort2(L[:len( L )/2]), msort2(L[len( L )/2:]))) or (list( L ), [])) return ([(lambda m,n: ((len( n ) == 0 and m.pop( 0 )) or (len( m ) == 0 and n.pop( 0 )) or (m[0] < n[0] and m.pop(0)) or (n.pop(0))))(a,b) for i in xrange(len( a )+len( b ))]) 

There you have it -- merge sort in three lines of Python. Though, in my opinion, it looks a lot more like something a chronic Perl obfuscator would be proud of. So let's investigate the language "features" that I've employed in order to get the code so compact:

The boolean operators

Python's boolean operators are weird. Instead of returning boolean literals, and and or return one of their operands, in the following way:

A B A and B
True ANYTHING B
False ANYTHING A
A B A or B
True ANYTHING A
False ANYTHING B

It's easy to convince yourself that this behaviour is correct, if esoteric. Making use of this feature, a and b or c behaves very similarly to C/C++/Java's ternary operator (enough for our purposes). The fact that these operators are shortcircuited allows us our next abuse (although it prevents the sort from being general -- the code can't quite handle lists with zeroes in them).

list.pop() returns the value it removes

Due to Python not allowing arbitrary assignments as expressions, we need a convenient method of both incrementing a list, and getting the front of that same list at the same time. Happily, pop will return the list element that you pop from the list, which provides us with a value to insert into our comprehended list. C++'s queue template from the STL has both a front() method, as well as a pop() method, probably just to avoid travesties like this (pop does not return a value).

List comprehensions are sequential

For this code to work, it absolutely depends on the list comprehension getting evaluated like a for loop -- and thankfully that is the case. If it weren't, then all of the pop() side-effects would fall apart quite terribly.

lambda

Need I say more?

And there you have it -- a strictly non-Pythonic implementation of Merge Sort. Hate mail to the usual address, or if you think you can better it, feel free to comment. Everyone else, take this as an educational exercise in writing readable code.

Small disclaimer: This version is not quite general -- it can't handle lists with zeroes in them: I do have a version which makes use of Python 2.5's ternary operator, but the code was a lot more readable.

Python Prettiness

Whilst in Melbourne, and on the recommendation of Anthony Baxter (current Python release manager) I picked up a copy of O’Reilly’s Python Cookbook, it’s certainly a worthwhile read. In it, I found the most beautiful piece of Python code I’ve seen in a long time:

def qsort( L ): if len( L ) <= 1: return L return qsort( [i for i in L[1:] if i <= L[0]] ) + [L[0]] + \ qsort( [i for i in L[1:] if i > L[0]] ) 

For those of you who don’t recognise it, it’s an implementation of Quicksort, and a particularly inefficient one, at that. What is nice about it is how it shows off the expressive power of Python’s list comprehensions. The example in the Cookbook credits the Haskell Web Site for the inspiration for the code (Haskell, incidentally is where the idea of list comprehensions came from in the first place)

It’s worth noting that it’s not a piece of code that I’d use in real life, but as an example, it’s certainly interesting.

If you’re interested in the original recipe from the cookbook, you can find it at the Online Python Cookbook.

Why I hate Java (part 1)

People have often asked for my opinion on Java (the programming language, not the Runtime engine, or the Coffee), and my response is normally a very unreserved expression of hatred. I have condensed all of my evidence from the past year, and the result is the following piece of code:

 public class Dodgy{ public static void main (String[] args) { boolean a = true; boolean b; if (a == false) { b = true; } if (a == true) { b = false; } System.out.println(b); } } 

Whilst this code looks harmless, let’s see what Java does when I try to compile it:

chris@blackboard:~/src$ javac Dodgy.java Dodgy.java:14: error: The local variable b may not have been initialized System.out.println(b); ^ 1 problem (1 error) 

It is obvious, from such a trivial example, that b will be initialised when line 14 is reached, however, Java prevents my code from even compiling. This demonstrates one differentiation between Java and C (or C++): Java does not trust your judgement. With appropriate syntax changes, that code would have been valid C code, but in Java it is illegal.

Whilst I would approve of such a case being a compiler Warning (I could then flag a -Wall or similar, and have my compiler abort when it finds such an issue), but causing such a thing to be an error is irrational.

Of course, all cases of whether a variable is initialised or not cannot be verified: a general purpose algorithm to do such a thing can be proven to not exist via reduction to the halting problem; so why should Java even attempt to do it in the first place?

So there you have it: Java has a distinct lack of trust in the programmer who uses it, and this is why I dislike it.

Linux.conf.au — Wrapup

LCA officially finished yesterday with the Open Day being a massive success. Here’s my attempt to wrap up everything that I’ve done since Tuesday:

Wednesday

Keynote was Bruce Schneier, he gave a speech which was not terribly revelatory, but was entertaining nonetheless. This was probably to be expected — keynoters are notorious for regurgitating talks, but the talk was well-presented, and thinking about the psychology of security was a particularly interesting process.

Other highlights of the day included The Kernel Report, and a talk on the OLPC by Jim Gettys.

Thursday

There was one standout talk from Thursday, and that was Andrew Tridgell‘s talk on Clustered Samba (not just a hack any more). The level of thought that’s gone into the system is incredible, one particular standout from that talk was the concept of a “Tickle ACK”, which in my opinion, was the most beautiful piece of TCP Hackery I’ve ever seen. The audience’s reaction is well-justified — make sure you watch the talk.

Leslie Hawthorn’s talk on the Summer of Code and other Google Open Source stuff was worth going to; whilst the topics covered were for the most part repeats of stuff that’s already been revealed, one small soundbite was dropped, and that is that Summer of Code is almost certainly going to happen in the Southern Hemisphere. This is great news for Australian coders, since the Northern Summer of Code really doesn’t work for committed students (a clash with exams and 7 weeks of second semester is particularly discouraging). I’m seriously considering doing it this year. Thanks Leslie!

The Google Student Party was also really cool — an evening in a dingy pub in the middle of Melbourne, chatting with students and hobbyists, and planning projects for the rest of the year — I already have one, and thanks to Leslie, a contact to pitch it to. I’m looking forward to that!

Friday

The day started out with Anthony Baxter‘s talk on Python’s latest developments, with a really stupid title. Fortunately, the talk itself wasn’t stupid: it was definitely the standout keynote talk for the conference, and probably the best talk on Python, which is cool. He talked about all of the things that are going to break in version 3.0, future developments on the 2.x line, and also mentioned NCSS (in particular, he namedropped me, which is nice — I’ll be posting a post about NCSS in the near future for those of you LCAers who are interested in it)

Another cool thing done for the last day was a “Geek Junk Giveaway”, where people would give out their old computer junk to people who wanted it: I hope this becomes an LCA tradition.

The lightning talks (can’t find the video yet, sorry!), which went for the last hour of the conference were many, varied, and generally excellent. Standout talks included Jeff Waugh on Getting Laid (or rather, “Couple-oriented Software”, or the lack of software services that don’t recognise couples), and Paul Fenwick on Fixing the Web (using greasemonkey to remove content from Myspace).

Finally, the best part of Friday was finding out that LCA2009 will be in Hobart! And I’ve already started inviting people to pop by for it.

Saturday

Open Day == Schwag (Red Hats, DVDs, and a Google T-Shirt), Schmooze (I spent 20 minutes exploring the Clustered Samba codebase with Tridge — and a generalised version of the Tickle Ack (the Socket Killer — it’s cool!), dicussing developments in Kate with Aaron Seigo, and playing Infra-red Pong with Rusty Russell), and Schpeech (that was dreadful, but the lightning talks were good)

So, that’s it for LCA proceedings, onto my general thoughts: LCA was fantastic. To Donna, Peter, and the rest of the mel8ourne crew, you did a fantastic job, it’s going to be interesting to see if Hobart can top it.

To the People of LCA, thanks for making it worthwhile — people who work on cool stuff actually giving me the time of day (thanks Tridge and Aaron and Anthony for all of that), the community really makes LCA special. I will be going back every year that I can, as it’s really a special event.