On not avoiding null pointer exceptions

A common piece of Java advice that floats around encourages programmers to use “Yoda conditions” - that is, to structure comparisons so that the subject of comparison is on the right hand side of the expression, while the thing it is being compared against is on the left. Instead of

name.equals("Yoda");

we are advised to write:

"Yoda".equals(name);

This is bad advice; but I think the reason why it is bad advice illustrates some interesting features of how (and how not) to write reliable software.

Typesafe builders

I’ve been writing a lot of Java for work recently (after an extended sojourn in Scala for my master’s project), and it’s got me thinking about language ergonomics: the ways in which we adapt programming languages to make them easier to write (I actually think many common Java idioms which are supposed to make it easier to write code, don’t; there may be more posts soon-ish on some of these).

One common pattern in Java is the simple builder. I call it a simple builder to distinguish from the full-blown Builder pattern presented by the Gang of Four. The full Builder pattern is used when you have a complex construction process which is shared between a number of different representations. The example the GoF give is a function that reads a rich-text document and can be used to build a document model in a number of different formats (TeX, HTML, GUI widgets).

The simple builders commonly encountered in Java are much simpler: they usually only construct one type, and the construction process is usually straightforward, just involving setting a few parameters.

Rough guide to Intel's Spark CRF library

Spark includes a machine-learning library implementing a number of useful statistical techniques, but one it does not include is Conditional Random Fields, which are a popular choice for classifying tokens in a sequence (I think they’re probably best known as a technique for part-of-speech tagging, but I’m interested in using them to classify paragraphs in documents based on their semantic role). There is a Spark-based CRF library, though, which is part of Intel’s IMLLIB. Unfortunately, it’s not very well documented, so I’ve spent the past couple of days figuring out how to use it, which I thought I’d document here in case it’s of any use to anyone else (even if that other person is just me in a few weeks time).

Bridging patterns and programming

It’s hard to escape the feeling, reading the Gang of Four Design Patterns book, that there are slightly too many design patterns. Many of the patterns seem to have similarities and homologies, leading to the suspicion that with just a little more abstraction some of the patterns could be combined. After thinking about this for a while, though, I’m not sure this objection is right; at any rate, considering why it might not be helpful to abstract away differences between patterns has clarified some stuff for me about the point of design patterns.

What leads to the suspicion of there being a few too many patterns are the many often-remarked on similarities between different patterns (including some that are remarked on in the GOF book itself). What got me thinking was a similarity that hadn’t occurred to me before (and which Google suggests isn’t commonly discussed), that between the bridge and builder patters.

Bridge

The bridge pattern is used, according to the GOF, to

decouple an abstraction from its implementation so that the two can vary independently.

That is, you have a hierarchy of classes which can be implemented in terms of some set of operations, and that set of operations can itself have multiple implementations. The example they use is a hierarchy of widgets in a GUI, each of which could itself be implemented by many different window systems. Something like

trait Window {
    def setPosition(x: Int, y: Int): Unit
    def draw(): Unit
    def onClick(handler: Int => Unit): Unit    
}

trait Button extends Window {
    def setCaption(caption: String): Unit
}

trait List extends Window {
    def setEntries(entries: List[String])
}

Rather than having a separate implementation of each interface for each window system, you provide an interface for basic window system operations, and you implement the widgets in terms of this interface, e.g.

trait WindowOperations {
    def drawRect(left: Int, top: Int, right: Int, bottom: Int): Unit
    def drawText(x: Int, y: Int, text: String): Unit
    def registerHandler[T](event: Event, handler: T => Unit): Unit
}

class WindowImpl(ops: WindowOperations) extends Window {
    var x: Int
    var y: Int

    override def setPosition(x: Int, y: Int): Unit = {
        this.x = x
        this.y = y
    }

    override def draw(): Unit {
        ops.drawRect(x, y, x + width, y + height)
    }

    override def onClick(handler: Int => Unit): Unit {
        ops.registerHandler(Click, handler)
    }
}

Then you could provide as many implementations as you need of the WindowOperations interface: MSWindowOperations for Windows, XWindowOperations for X, etc.

Builder

The builder pattern, again according to the GOF, is used to

separate the construction of a complex object from its representation so that the same construction process can create different representations.

You use this pattern where you have a complex construction process that can be built up from simpler parts, and you have multiple implementations of those parts. The example the GOF use is creating different representations of text from an RTF. The class that controls the construction process (in this case, parsing the RTF) is called the ‘director’; the classes that implement the elements of this construction process are called ‘builders’.

trait TextBuilder {
    def addParagraph(): Unit
    def addCharacter(char: Char): Unit
    def changeFont(newFont: Font): Unit
}

class RTFReader {
    def parseRTF(rtf: String, builder: TextBuilder): Unit = {
        // Imagine this parses the rtf string and calls
        // methods on the builder for each relevant part
        // of the RTF.
    }

}

class PlainTextBuilder extends TextBuilder {
    private sb: StringBuilder = new StringBuilder

    override def addParagraph(): Unit = sb.append("\n\n")
    override def addCharacter(char: Char): Unit = sb.append(char)
    override def changeFont(newFont: Font): Unit = ()

    def getString: String = sb.toString
}

class TextWidgetBuilder extends TextBuilder {
    // Using some imaginary windowing system's text widget
    private widget: WindowSystemTextWidget = new WindowSystemTextWidget

    override def addParagraph(): Unit = widget.newParagraph()
    override def addCharacter(char: Char): Unit = widget.append(char)
    override def changeFont(newFont: Font): Unit = widget.setFont(font)

    def getWidget: WindowSystemTextWidget = widget
}

Bridge and builder: similarities and differences

So in the builder pattern, you have some functionality (complex construction), implemented in terms of an API which itself may have a number of implementations. Described that way, the builder pattern sounds a lot like the bridge pattern. There are differences, though, in the exposed functionality. The bridge pattern suggests that the functionality is fairly rich - in the example, the functionality exposed abstractly by Window and the other traits is sufficient to build a whole GUI. In the builder pattern, the functionality is much simpler - the director class, RTFReader only has one method. What’s more important, though, is what’s missing from this abstracted functionality: the method to get the constructed object only exists in the concrete builder implementations, not in the director class or the abstract TextBuilder class.

This is intentional. The GOF write:

Because the client usually configures the director with the proper concrete builder, the client is in a position to know which concrete subclass of Builder is in use and can handle its products accordingly.

The difference here is one of point-of-view. The bridge pattern approaches the question from the point of view of a client of an abstraction, who wants to be able to use it without caring about the underlying implementation. Hence the process of creating the concrete implementation is encapsulated behind an interface that deals only in abstract classes.

The builder patter, on the other hand, approaches the question from the perspesctive of the implementer of a complex algorithm, and it is this algorithm which is encapsulated in the concrete director class.

And this is why thinking about design patterns in terms of language features tends to lead us astray. You sometimes hear design patterns dismissed with variants on the argument that you don’t need design patterns if you have higher-order functions (or macros, or some other higher-level programming technique), but that confuses the implementation with the motivation. This mistake is sometimes reinforced by how design patterns are taught. There’s often an emphasis on implementing the GoF patterns in highly contrived situations, with no discussion of what makes the pattern appropriate for that situation; this is often because the pattern isn’t appropriate for the contrived situation (indeed, this post was in part inspired by my frustration at this sequence of videos, which strike me as a textbook example of how not to teach design patters).

The implementation of design patterns isn’t particularly important. More important is that they provide perspectives from which to see problems, and thereby to see similarities, and also differences between problems. This ability to approach programming at a level of abstraction above that explicitly represented in code, and with the flexibility and imagination that can be spurred by analogical thinking, is important no matter what programming language or paradigm you’re using (there is an interesting debate to be had about the relative value of the analogical thinking encouraged by design patterns, and the formal thinking encouraged by mathematical approaches to programming, but that will have to be another post).

Labels and things

The Birkbeck Computer Science MSc I’m currently taking includes a required module on Programming in Java, with the quite sensible purpose of making sure everyone on the course has a shared facility in a common language (and the MSc is specifically intended for people coming to CS from other disciplines, so it makes sense not to assume this shared skill in advance). I have a fair amount of programming experience, so the aspect of the class about programming in general hasn’t taught me a huge amount (though I have learnt about some of the peculiarities of Java), but it has been useful to observe what people find difficult in learning to program, and to think about ways in which a programming course could ease some of these difficulties.

Once thing that definitely seems to be causing people difficulties is figuring out what names refer to at different parts of the program; for instance, what writing name = "Tim" means exactly, or what happens when you have variables with the same name in different functions. I’ve been thinking about how to structure a programming course to make this as clear as possible.

Expressions and evaluation

I think it makes sense to start witht the idea of expressions and evaluating them. You can start with a simply expression like 5 + 5, in order to introduce the idea that when a program runs, a lot of what it does is taking these expressions and evaluating them, that is, working out a result. You can then go on to consider compound expressions, like (5 + 5) * 10, which gets across the important idea that the program uses the result of evaluating one expression in working out the result of evaluating another expression. This might seem obvious, but I think being very explicit about this right at the beginning would provide a solid foundation for the next few stages.

Labels and things

The next concept to introduce is variables. Like I think many people of my age (i.e, people who started learning to program with BASIC), I was introduced to variables through the metaphor of boxes: a variable is basically a box, oh and by the way it also has a name. I think this view of variables is too low-level to be helpful at the early stages of teaching programming (I should note in passing that I think this may have been something that confused students on the course I’m currently taking: it introduced the distinction between primitive types, stored on the stack, and objects, stored on the heap, very early on, but in Java this is an implementation detail that is almost always irrelevent); my preference would be to introduce variables as a connection between a label and a thing. A variable name, like name is a label, and it is attached to a thing, like the word Tim or the number 100. More specifically, a thing is the result of evaluating an expression; and, neatly, the result of evaluating a label is just the result you got when you evaluated the expression in its definition.

I think it would make things clearer to treat variables as immutable at this point, and perhaps therefore to teach in a language that enforces that (a concise syntax for introducing an immutable binding would be helpful, like val name = "Tim" as used by, among other languages, Kotlin). The question of “what happens when a label refers to different things at different points in the program is a complicated one, and one that should be introduced in its own right.

(You could also introduce the language’s basic IO functions at this point, to allow students to write interactive programs. A very lightweight IO syntax, like Python 3’s print() and input() would be nice.)

Conditionals

I think there are two fundamental operations in how we usually think about programs, the first of which is conditionals. I don’t think these are particularly challenging for people learning programming (but I might be wrong). Following on my recommendation above to teach immutable variables first, I guess it would make sense to teach functional-style conditionals that return a value, rather than the if statements that you get in the imperative languages usually used for teaching. I wonder if there’s any difference in ease of understanding between something like:

val isOddOrEven = if (n % 2 == 0) "Even" else "Odd"

As opposed to:

if n % 2 == 0:
    odd_or_even = "Even"
else:
    odd_or_even = "Odd"

Repetition

The second of the two fundamental operations in programming is repetition, which is more complicated than conditionals because it requires introducing the idea that the same code can do different things. Well, you can begin with a simple unconditional repetition, like the classic logo program to draw a square:

REPEAT 4 [
    FORWARD 100
    RIGHT 90
]

But the critical point, and I think the harder one for people learning programming to grasp, is the conditional loop, like, say:

while (number != 1) {
    if (number % 2 == 0) {
        number = number / 2;
    } else {
        number = 3 * number + 1;
    }
}

There are two ways of explaining this kind of fully general loop - mutable variables, as I’ve used in the example above, or function calls, as in:

collatz number = 
    if number == 1 then 
        () 
    else
        if even number then
            collatz (number `div` 2)
        else
            collatz (3 * number + 1)

What both share, and which I think makes them tricky to understand, is this idea of re-binding variables; that the same symbol (in these examples, number) will refer to different things at different times. I’m tempted to say there are two hard problems in teaching programming - the idea that labels refer to things, and the idea that labels refer to different things at different times. That’s why I started this post by proposing to introduce the distinction betwee labels and things very explicitly early on. But having done this, it seems to me that there’s a significant further hurdle in introducing the idea that labels change what they refer to in predictable but potentially complex ways. Thus I’d like to introduce the idea of re-binding in a limited and controlled way before moving to the full generality of mutability or function arguments.

And it occurs to me that theres an easy to grasp special case of repetition which might make a good introductory step to an explicit discussion of re-binding of variable names: repetition over sequential numbers.

Is it time to revive the BASIC FOR…NEXT loop as a pedagogical tool?

FOR I% = 1 TO 10
    PRINT I%
NEXT