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

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."""
        ...

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.

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.

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: emacs, editting, abbrev, java, skeleton

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!