Thursday, 28 December 2006

How to learn a new (programming) language

Pretty much every programmer that I've ever met learns new languages by writing a number of small programs in the new language, that should show up the major features of the language and enable the transference of skills from known languages to new ones. Here's a list of my favourite small problems:

The basics: choice, iteration, recursion

Factorial function
Factorials are easy, but the trick here is to deal with all the various boundary conditions, preferably using exceptions.

Fibonacci sequence
Generating the next Fibonnaci number has a simple recursive solution and a slightly more complex iterative solution which can show up features such as simultaneous assignment.

The first n primes
Print the first n primes using the
Sieve of Eratosthenes. This is an interesting one -- it has nice solutions both iteratively and recursively. Also, you can do neet things with exceptions to give a solution.

Files and other I/O


Caesar cipher
Read in an ASCII sentence and encipher it with the Caesar cipher (add a key to each letter) and print out the enciphered text. Write the converse function to decipher.

Count the occurances of letter 'a' in a file
Read a file name in on the console, open the file for reading and count the occurances of 'a' in the file. Print the result (and close the file!).

Linear data structures: arrays and so on


Binary search
Look for a value in a sorted structure -- iterative or recursive solutions are both interesting to try out.

Bubble sort
The simplist sorting algorithm, but it should give a reasonable idea of how to manipulate mutable structures, or deal with immutable ones if that's all the language has available.

Modularity: modules, classes, objects, etc.

Sets data structure
Sets are a simple data structure to implement, they're easy to test and a good instroduction to polymorphism. Union, difference, intersection, etc. all make useful methods and you can play about with mutable or immutable sets and see the difference.

Wednesday, 11 October 2006

Why Linux is such a great choice for multimedia computing

All about Linux has a great post on the use of Linux in the film industry. Check it out!

Sunday, 1 October 2006

GUI programming basics 1/3

This is the first of three posts on the basics of GUI programming. This post covers the most fundamental of GUI concepts with some example code to illustrate them. The next post will cover some more complex issues (in particular, layout managers) and the final post in this series will contain an extended example -- a simple text editor.



GUI programming is a bit of a black art. It sits on the interface of prgramming and HCI and usually requires careful planning (for usability) and relatively, but not very, sophisiticated programming techniques (meaning we don't teach it in the first year). Generally, GUI toolkits make good use of objects and to learn a new toolkit you need to understand a whole bunch of GUI jargon. Conceptually, there's not a lot new to learn when it comes to writing GUIs. If you already know about objects, OOP and event loops then you've learned most of what you need, the rest is just jargon and libraries. So, first to the jargon, then we'll look at some code. The following is a brief glossary of GUI concepts, in alphabetical order:




Binding:

Binding is the process of associating an event (such as a key press or mouse movement) with a callback or event handler. For example, we might bind the key accelerator Ctrl-S with the callback onSave.


Callbacks (or Event Handlers):

A callback or event handler is a piece of code (usually a function or method) which is executed when an event occurs. For example, an callback called 'onQuit' may be run when the key accelerator Alt-F4 is pressed by the user. Note that callbacks are written by the GUI programmer but scheduled to run by the toolkit -- i.e. you don't usually have to write your own event loop!


Containers:

A container widget may have other widgets embedded within it. For example, a top-level container for an application may contain a menu, statusbar, toolbar and so on.


Events:

An event is usually some form of input or interaction that occurs externally to a GUI but can be detected by the GUI toolkit. Examples include keyboard key presses, mouse movements and button presses, drag'n'drop, and so on. Most events will be uninteresting (e.g. mouse movements) but some require a response from the GUI (such as button presses and key accelerators).


Event Loop:

A loop which is used to dispatch callbacks in response to events. Usually the event loop for a GUI is provided by the toolkit and doesn't need to be written from scratch.


Widgets:

A widget is a single element in a GUI and in OOP languages is usually an object. Example widget types are: label, button, text entry field, canvas (to display graphics), list box, scroll bar, radio button, etc.



Simple GUIs with Tkinter and Python



Tkinter is the cross-platform GUI toolkit which ships with Python. It's based on the Tcl/Tk system and it's popular because of it's simplicity. Other toolkits are a bit more sophisitcated (like, wxPython, based on the C++ toolkit wxWidgets) but are also more complex. So, Tkinter is a good place to start if you haven't writen GUIs before, but you might want to look around at other libraries when you're a bit more confident of the basics.



What follows is a very simple series of 'Hello World!' scripts which introduce the very basic concepts of GUI programming by producing minimal GUIs. The next post on GUI programming will introduce some more complex practical concerns -- various widget types, layout (geometry managers), and so on.



Hello World! (1)



This script is absolutely minimal. It simply creates an empty application window (called root) and instructs Tkinter to start it's event loop.




#!/bin/env python2.4

"""
Hello World! with Python's Tkinter GUI toolkit.
"""

from Tkinter import *

__author__ = 'Sarah Mount'
__date__ = 'October 2006'

root = Tk()
root.mainloop()



Hello World! (2)



An empty application window isn't much use! The next script creates a single widget, a label. Labels are holders for text. They generally don't do anything (unlike, say, buttons) so they are really the simplest widget around. In our case, we just want to create a label, pack it (meaning, arrange it on the main application window) and start the Tkinter event loop.




#!/bin/env python2.4

"""
Hello World! with Python's Tkinter GUI toolkit.
"""

from Tkinter import Label

__author__ = 'Sarah Mount'
__date__ = 'October 2006'

# Create a widget
widget = Label(None, text='Hello World!')
# Arrange widget in application window
widget.pack()
# Start GUI event loop
widget.mainloop()


Hello World! (3)



Our third version of Hello World! introduces callbacks. Here, we use a button widget rather than a label. When we create the button, we need to give Tkinter a reference to a function which can be called to handle mouse click events.




#!/bin/env python2.4

"""
Hello World! with Python's Tkinter GUI toolkit.
"""

from Tkinter import *
import sys

__author__ = 'Sarah Mount'
__date__ = 'October 2006'

def quit():
print 'Quitting...'
sys.exit()

widget = Button(None, text='Quit Hello World!', command=quit)
widget.pack()
widget.mainloop()


Hello World! (4)



This last script is essentially the same as the last, but makes use of a lambda expression in the callback. This is a common technique and although it's rather pointless in such a simple script, lambdas are a great way to cut down the size of your code whenever you need a simple function call in an event handler.




#!/bin/env python2.4

"""
Hello World! with Python's Tkinter GUI toolkit.
"""

from Tkinter import *
import sys

__author__ = 'Sarah Mount'
__date__ = 'October 2006'

def quit(msg):
print msg
sys.exit()

widget = Button(None, text='Quit Hello World!', command=lambda: quit('Quitting...'))
widget.pack()
widget.mainloop()


Further reading



Sunday, 10 September 2006

Cheat4Success! How to cheat a Computer Science degree

Every time lecturers mark work, there is inevitably an amount of time spent dealing with plagiarism -- detecting it, checking sources, dealing with the resulting paperwork, and so on. With cut'n'paste making cheating ever easier, it seems that plagiarism will never completely disappear.

Cheating, in this sense, means taking credit for someone else's work. It does not mean discussing ideas with friends, making use of someone else's (abstract) ideas or choosing to do the same homework as someone else. It does mean downloading someone else's work and passing it off as your own. In work, this is professional (or gross) misconduct and would get someone sacked. At University (and Schools, presumably) it's treated seriously, but expulsion is not usually the first line of punishment.

Of course, this is totally unfair, right? Most students don't cheat, most students want to get a degree and take some pride in their work. However, more and more time is spent with the few percent who cause trouble, which wastes time, (public) money, energy, devalues good degree courses, causes apathy in both students and staff and is generally a complete pain. That time and money could be much more usefully spent helping students who are engaged in their work to do a bit better, rather than in policing a small number of students who cheat. So, in light of that, this is my guide to cheating and cheating well (4success!) on a Computer Science degree. If only students cheated better, no one would catch them out and any effort put towards dealing with plagiarism could be so much better spent.

1. No one else can use Google except for you.
You've probably figured out that many programs exist on the Internet and can be downloaded. Also, many people put their homework online and you can get hold of that too. There are only so many ways to teach any particular topic, so probably the questions you're set have been set elsewhere already, so the answers are out there for you to see, copy, paste, and claim as your own. Fortunately, students are the ONLY people able to use Google for this purpose. Your instructor cannot possibly google for the work s/he has set, certainly won't find the same links as you and (thanks to the genius of those guys at Google) is physically prevented from finding out how you cheated.

2. Mix your sources.
Some things in life are better mixed. Drinks, for example. And the same is true for sources. If you have an instructor who is particularly persistent in tracking down cheats, it's better to cut'n'paste code (or text) from as many different sources as possible. This way, even if you're caught, you've wasted as much time and public money as humanly possible. Also, as your number of sources tends to infinity, your false claims of ownership cease to be cheating and become research and everyone knows that lecturers love research. For top marks, you should find at least 20 different sources to copy from.

3. Change variable names
One of the nice things about programming (rather than wussy subjects like history) is that two programs are distinct and different if they differ by only the names of their variables. It doesn't matter if every single part of the two programs is identical, including the comments and whitespace. If you really want to cheat4success, you need to take someone else's code, change the variable names and Ta-Da! it's a whole different program. Then when your instructor challenges you, you can just say "Ha! Those programs are different, they have different variable names!". And your instructor will be dumb-founded. The posh word for this is "alpha-conversion". Which is to do with lambda calculus. Which is clever. So, now you can not only cheat well, but justify what you've done with Big Words. Even better!

4. Hand in code which doesn't work.
One good trick is to download someone else's code and break it. Now you can play a particularly clever ruse. Your code is broken, it can't possibly be someone else's code -- after all, why would anyone put broken code up on the web? So, it's just a coincidence that (apart from the small changes you've made) your program is identical to a published one. For best results, change filenames and libraries.

5. Copy from your lecture notes.
That's not plagiarism, it's flattery. Your lecturer won't be able to resist.

6. Deny the laws of probability.
If the worst happens, and despite following this guide your lecturer still suspects you've cheated, then the worst mistake you can possibly make is to appear rational. So, refuse to see reason, don't engage in meaningful dialog and certainly don't be honest (after all, that rather defeats the object). Your lecturer might want to engage you in strange thought experiments like "What's the likelihood of your submission being identical to that one. Oh, it's 1/10^googol. And 10^googol is more than the number of atoms in the Universe". Everyone knows that statistics lie. Don't be drawn into the discussion.

7. It weren't me 'guv.
no one can resist your charming smile. Just grin widely, tell your lecturer that you wouldn't dream of doing such a terrible thing and you'll be fine. If that doesn't work threaten formal complaints, litigation or the breaking of limbs. Works every time!

Thursday, 27 July 2006

Testing programmer aptitude


In January, Richard Bornat and Saeed Dehnadi discussed their work on testing programmer competence at the PPIG WIP workshop at Coventry, and now it's featured in the Grauniad. Woo!

Blogged with Flock

Programming idioms #2: Design by contract

This is the second in my "Programming idioms" series, the first (on mixin classes) can be found here.

Design by contract (DBC) is a practical implementation of Floyd-Hoare logic which is intended to eliminate certain classes of bugs from imperative (i.e. procedural and OO) languages. One of the nice things about DBC is that although it's firmly rooted in the theoretical world, for the "working" programmer it's really very practical. So, no need to learn all about tedious categories and arrows and other such weirdness.

In DBC (and Floyd-Hoare logic) each block of code can have associated with it pre- and post-conditions. Pre-conditions are predicates (relations) which must hold true directly before the block is executed at run-time and post-conditions must hold true directly after. In DBC the runtime system running your program will barf if a pre-condition or post-condition is not met. You may also have invariants, which must always be true. For example:


// Pre: True

x = 43

// Post: x == 43


or:


class BankAccount:

    # Inv: balance > -overdraft_limit

    self.balance = ...

    ...

    # Pre: w > 0

    # Post: balance == balance' - w

    def withdraw(w):

        self.balance = self.balance - w


DBC gotchas

As I'll comment on in the next section, DBC conditions and invariants are often annotations in comments. Many systems exist to implement assertion checking for DBC in languages that were designed without it. However, it's worth watching out for a few idioms which suck and you'll want to avoid.

Firstly, DBC should really be used to document and check for semantic conditions which are *not* documented and caught elsewhere. I've seen the following idiom in student code and (shockingly) in lecture notes:


/* Pre: a is a String (VERY bad) */

/* Pre: a isinstanceof String (Better but still dumb) */

public void foobar(String a) { ... }


The problem with this code is that the declaration "String a" already documents that a is a String and provides run time checking of that assertion. Notating the same thing in a comment is just asking the programmer to read the same thing twice and introduces an opportunity for error (what if you change the type declaration and forget to change the comment?). The second comment is better than the first because it's more precise (think: what does 'is a' mean?) and could be automatically checked if a suitable system were available.

Pedagogically this anti-pattern is very damaging. Whenever I've seen students taught this they end up commenting every since ****ing type declaration and never manage to use DBC for any other sort of semantic condition.


Practical implementations

Bertrand Meyer designed the language Eiffel which has DBC built in, although many other languages have pre-processor and similar systems which add DBC onto non-DBC languages.

Since Eiffel never really took-off in the way that Java and Python have, most of the time the only place you'll see DBC is in comments (as above) and assert statements.  It's a shame, because DBC enforces a useful discipline about state management, it provides extremely precise documentation and it adds a relatively small runtime cost (of condition and invariant checking).

However, some of the power of DBC can be added to languages in other ways, and it's worth considering how this might work itself out in production languages of the future. Tim Sheard has a nice concept he calls Generalized Algebraic Data Structures, which are basically type definitions with extra semantic information. So, while in DBC you might declare an invariant that says "an 'age' must be an integer over zero" in GADS you would just create a new int type which only ranges over positive integers and let the type checker (rather than an assertion checker) barf if you try to store a zero or negative as an age.

Blogged with Flock

Monday, 10 July 2006

Programming idioms #1: Mixin classes

I've decided to devote a few blog posts to programming idioms. These aren't as fancy as design patterns but they are useful and often skipped over by text books. At the very least, you rarely see a whole bunch of them collected together. So... in the next few weeks expect to see posts on point-free-programming and all sorts of other goodness.

Firstly, though: Mixin classes. This is an idiom object-oriented programming. A mixin class is one which implements a bunch of different behaviours but doesn't hold any state. The idea is that you use the mixin class as a superclass so that it's methods are "mixed in" with the methods of the sub class.

An obvious use for mixin classes is GUI programming. There's a variety of behaviours which are useful in most applications written with any given widget set, such as setting text in a status bar, popping up a modal dialog, and so on. Each of these tasks requires some logic and resource handling and because the operations are common to many different applications they can usefully be factored out. Here's an example stub from a GUI I recently wrote (in Python):



class GUIMixin:
def about(self):
"""About dialog."""
...
def error(self, str):
"""Modal dialog box to display error messages."""
...
def onQuit(self, event=None):
"""Handle resources and close GUI."""
...
def help(self, title, helpfile):
"""Display a help file."""
...

Tuesday, 18 April 2006

Student Java gotchas

We've been doing a lot of marking lately, it being the holidays, which is always a revealing experience. The results have been pleasing, but having to go through Java code caused me to remember how many small idioms students wrongly replicate. OOP so often ends up being all about style and detail and much of that can elude a beginner, because there's so much to learn about programming when you start.

My two favourite annoyances are unnecessary setters and getters and the following use of boolean expressions:

while / if(x == true) { ... }

The latter just says that the student doesn't really understand how expressions are evaluated, which is pretty fundamental, although I've seen the same "mistake" in production code too.

The first thing about setters and getters is slightly more subtle. A field should be declared private if either it is or should never be used by another object or if it has some class or object invariant associated with it. A field with no associated invariants can be declared public. In fact, this is probably preferable, as declaring a field to be public tells anyone using your API that that particular field definately has no invariants associated with it that they need to think about.

Sunday, 9 April 2006

Pygame

This year, with our intro programming class, James and I used Pygame as an example API in our weeks on using-external-libraries. There was some debate amongst the class as to whether Pygame is such a good choice (as oppose to, say, using a full-blown games engine from a popular game). I think our approach is very defensible: Pygame is a fast API to write with (in terms of development time) it's powerful enough to enable very creative games to be written, and so on. However, Jay Barnson, of Rampant Games has written about his week-long game hack which -- not surprisingly -- used Pygame. He puts the case very eloquently:


Lesson 4: Python rules!

I can't believe how quickly many features came together using Python as opposed to, say, C++ or even Java. Things like typeless variables, dictionaries, and extremely easy-to-declare lists (allowing a mixing and matching of object types) made it very easy to implement content lists, attribute handling, spell effects, and so forth. I was already a fan of the language, but now the prospect of using Python, tied into a high-level 3D engine, has become extremely appealing to me.

Friday, 24 March 2006

Emacs-fu

Emacs just rules. Lately, I've been trying to figure out how abbrev mode can be used nicely with skeletons. The following is a skeleton to produce a Java "main" method and is due toJorgen Shaefer:

(add-hook 'java-mode-hook 'fc-java-setup)


(defun fc-java-setup ()
(c-set-style "k&r")
(setq c-basic-offset 4)
(c-set-offset 'case-label '+)
(define-abbrev java-mode-abbrev-table "main" "" 'java-main-skeleton)
(define-skeleton java-main-skeleton
"Insert a Java main function."
> "public static void main (String[] args) {\n"
_ "\n"
"}" >)
)

technorati tags: , , , ,

Tuesday, 28 February 2006

Tail Call Optimization as a Python Decorator

Until today the coolest uses I've seen for Python decorators were implementing design by contract and currying. However, Crutcher Dunnavant has implemented a decorator which performs tail call optimization by messing with the runtime stack. Even cooler, it's only 14LOC. Go check it out!

Monday, 30 January 2006

Colour transforms

I found this *really* useful comment in the Python source for the Python Image Library. Guess I should have remembered this from Uni, but never mind!

When translating a colour image to black and white (mode "L"), the library uses the ITU-R 601-2 luma transform:

L = R * 299/1000 + G * 587/1000 + B * 114/1000

technorati tags: , , , , , , ,

Wednesday, 25 January 2006

Pong for the Symbian60


I've spent an evening and a bit writng Pong in Python for my Nokia 7610. Seems weird to have a hobby after all the time we've spent working for the ARC launch, but Pong was fun and it was nice to see how incredibly simple the PySymbian stuff really is. Yay.

technorati tags: , , , , , , , ,

Monday, 23 January 2006

Camera modes for Symbian60 camera phones

I've been messing about with the Python SDKs for Symbian60 phones. If you want to write anything using the camera, it helps to know what modes are available on your phone. So, here's a short Python script to do that and print the relevant information to the interpreter window:




"""
Prints all available information about available cameras:

* Number of cameras
* Maximum zoom
* Available image modes
* Available white balance modes
* Available image sizes
* Available flash modes
* Available exposure modes
"""

from camera import *

__author__ = 'Sarah Mount '

print 'This phone has', cameras_available(), 'camera(s).'
print 'Max zoom is', max_zoom(), '.'

for mode in image_modes():
print 'img_mode:', mode
for mode in white_balance_modes():
print 'wb_mode:', mode
for size in image_sizes():
print 'img_size:', size
for mode in flash_modes():
print 'flash_mode:', mode
for mode in exposure_modes():
print 'exp_mode:', mode

Tuesday, 17 January 2006

PPIG workshop

I've been meaning to blog about the PPIG Unroll Your Ideas workshop that Andree organised at Coventry last week. The meeting was fantastic and the level of debate was probably the best I've seen almost anywhere, perhaps with the exception of some OOPSLA sessions. Definately the highlight was Richard and Saeed's paper on predicting whether or not students will pass a programming course, before they have started learning anything about software at all. Interesting stuff and if the data bears out in longditudinal studies this could be a really big result. There's a little more on Richard's site and no doubt the full paper will be available soon. You heard it here first! (Or maybe second.)

technorati tags: , , , , ,

Sunday, 8 January 2006

Python on my Nokia 7610


This absolutely rules ;-) Go get it here.


technorati tags: ,