This site is ©2006-2008, Christopher Neugebauer, this page was last updated on January 19 2008
posted: Mon, 25 Feb 2008 13:56 | filed under: / blog/ meta/ | permalink | Comments: 1
Well, it seems as though TasLUG have started their own Planet-like website, so I've submitted my blog to it. Hello, all you TasLUGgers who are now getting my blog. (And to all of you who are reading through other channels, sorry for the disturbance)
posted: Thu, 21 Feb 2008 15:28 | filed under: / blog/ life/ | permalink | Comments: 0
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:
And there you have it. I'll make periodic posts this year as I work on achieving these.
posted: Wed, 13 Feb 2008 23:27 | filed under: / blog/ programming/ | permalink | Comments: 2
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:
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).
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).
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.
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.
posted: Wed, 13 Feb 2008 22:40 | filed under: / blog/ meta/ | permalink | Comments: 2
Hello, World!
This post is to let you know that my blog's feed has been added to Planet.Linux.org.au (PLOA, or Planet Linux Australia), so, welcome to all of you who are now getting my feed syndicated!
posted: Sun, 10 Feb 2008 12:45 | filed under: / blog/ programming/ | permalink | Comments: 0
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.
posted: Fri, 08 Feb 2008 17:10 | filed under: / blog/ programming/ | permalink | Comments: 0
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.
posted: Sun, 03 Feb 2008 21:21 | filed under: / blog/ life/ | permalink | Comments: 0
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:
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.
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!
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.
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.