The Folly of Floating-Point for Robust Geometric Computation

Rob Smallshire from Good With Computers

Computational geometry - a world where lines have zero thickness, circles are perfectly round and points are dimensionless. Creating robust geometric algorithms using finite precision number types such as float is fiendishly difficult because it's not possible to exactly represent numbers such as one-third, which rather gets in the way of performing seemingly simple operations like dividing a line into exactly three equal segments. In this short series of posts, we'll look at some of the pitfalls of geometric computation, with examples in Python, although the key messages are true with finite-precision floating point numbers in any language.

Rational numbers, modelled by Python's Fraction [1] type can be useful for implementing robust geometric algorithms. These algorithms are often deeply elegant and surprising because they must avoid any detour into the realm of irrational numbers which cannot be represented in finite precision, which means that using seemingly innocuous operations like square root, for example to determine the length of a line using Pythagoras, are not permitted.

One algorithm which benefits from rational numbers is a simple collinearity test determining whether three points lie on the same line. This can be further refined to consider whether a query point \(p\) is above, exactly on, or below the line. Now there are many ways to approach writing such a function, and like many questions in computational geometry the naïve approaches are either overly complex, inefficient, or just plain wrong, albeit in subtle ways. I won't cover the story of how to arrive at a robust algorithm, that story is entertaining covered in Writing Programs for "The Book" by Brian Hayes. [2] Rather, we'll start where Brian leaves off by showing how to implement the algorithm in Python using both floating-point and exact arithmetic so we can understand the tradeoffs between performance and correctness inherent in these choices. Along the way, we'll perhaps touch on some aspects of Python which may be new to you.

Collinearity test

Whether p is above, exactly on, or below line p, r can be determined from the orientation of triangle p, q, r.

You don't need to understand the mathematics of the orientation test to appreciate the point of what we're about to demonstrate, suffice to say that the orientation of three two-dimensional points can be concisely found by computing the sign of the determinant of a three by three matrix containing the \(x\) and \(y\) coordinates of the points in question, where the determinant happens to be the signed area of the triangle formed by the three points:

\begin{equation*} \newcommand{\sgn}{\mathop{\rm sgn}\nolimits} o(p, q, r) = \sgn \begin{vmatrix} 1 & p\_x & p\_y\\1 & q\_x & q\_y\\1 & r\_x & r\_y \end{vmatrix} \end{equation*}

The function \(o\) returns \(+1\) if the polyline \(p\), \(q\), \(r\) executes a left turn and the loop is counterclockwise, \(0\) if the polyline is straight, or \(-1\) if the polyline executes a right turn and the loop is clockwise. These values can in turn be interpreted in terms of whether the query point \(p\) is above, on, or below the line through \(q\) and \(r\).

To cast this formula in Python, we need a sign function and a means of computing the determinant. Both of these are straightforward, although perhaps not obvious, and give us the opportunity to explore a little appreciated aspect of Python. First, the sign() function. You may be surprised to learn − and you wouldn't be alone − that there is no built-in or library function in Python which returns the sign of a number as \(-1\), \(0\) or \(+1\), so we need to roll our own. The simplest solution is probably something like this:

>>> def sign(x):
...     if x < 0:
...         return -1
...     elif x > 0:
...         return 1
...     return 0
...
>>> sign(5)
1
>>> sign(-5)
-1
>>> sign(0)
0

This works well enough. A more elegant solution would be to exploit an interesting behaviour of the bool type, specifically how it behaves under subtraction. Let's do a few experiments:

>>> False - False
0
>>> False - True
-1
>>> True - False
1
>>> True - True
0

Intriguingly, subtraction of bool objects has an integer result! In fact, when used in arithmetic operations this way, True is equivalent to positive one and False is equivalent to zero. We can use this behaviour to implement a most elegant sign() function:

>>> def sign(x):
...     return (x > 0) - (x < 0)
...
>>> sign(-5)
-1
>>> sign(5)
1
>>> sign(0)
0

Now we need to compute the determinant. In our case this turns out to reduce down to simply:

\begin{equation*} \det = (q\_x - p\_x)(r\_y - p\_y) - (q\_y - p\_y)(r\_x - p\_x) \end{equation*}

so the definition of our orientation() function using tuple coordinate pairs for each point becomes just:

def orientation(p, q, r):
    d = (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])
    return sign(d)

Let's test this on on some examples. First we set up three points a, b and c:

>>> a = (0, 0)
>>> b = (4, 0)
>>> c = (4, 3)

Now we test the orientation of a ➔ b ➔ c:

>>> orientation(a, b, c)
1

This represents a left turn, so the function returns positive one. On the other hand the orientation of a ➔ c ➔ b is negative one:

>>> orientation(a, c, b)
-1

Let's introduce a fourth point d which is collinear with a and c. As expected our orientation() function returns zero for the group a ➔ c ➔ d:

>>> d = (8, 6)
>>> orientation(a, c, d)
0

So far so good. Everything we have done so far is using integer numbers which, in Python, have arbitrary precision. Our function only uses multiplication and subtraction, with no division to result in float values, so all of that precision is preserved. But what happens if we use floating point values as our input data? Let's try some different values using floats. Here are three points which lie on a diagonal line:

>>> e = (0.5, 0.5)
>>> f = (12.0, 12.0)
>>> g = (24.0, 24.0)

As we would expect, our orientation test determines that these points are collinear:

>>> orientation(e, f, g)
0

Furthermore, moving the point e up a little, by increasing its \(y\) coordinate by even a tiny amount, gives the answer we would expect:

>>> e = (0.5, 0.5000000000000018)
>>> orientation(e, f, g)
1

Now let's increase the \(y\) coordinate just a little more. In fact, we'll increase it by the smallest possible amount to the next representable [3] floating point number:

>>> e = (0.5, 0.5000000000000019)
>>> orientation(e, f, g)
0

Wow! According to our orientation function the points e, f and g are collinear again. This cannot possibly be! In fact, we can go through the next 23 successive floating point values up to,

>>> e = (0.5, 0.5000000000000044)
>>> orientation(e, f, g)
0

with our function still reporting that the three points are collinear, until we get to this value,

>>> e = (0.5, 0.5000000000000046)

at which point things settle down and become well behaved again:

>>> orientation(e, f, g)
1

What's happening here is that we've run into problems with the finite precision of Python floats at points very close the diagonal line, and the mathematical assumptions we make in our formula about how numbers work break down due to the fact that floating point numbers are a far from a perfect model of real numbers. Next time, we'll investigate more thoroughly, the behaviour of this orientation test at the limits of floating-point precision.

[1]The Fraction type which models rational numbers is defined in the Python Standard Library fractions module.
[2]Hayes, Brian. (2007) Writing Programs for "The Book". In: Oram, A. & Wilson, G., eds. Beautiful Code O'Reilly Media. pp. 539–551.
[3]In C we could use the nextafter() function to generate the next representable floating point number. Unfortunately, nextafter() is not exposed to Python. Various workarounds are available, including a version built into Numpy, directly calling the C version using ctypes and a pure Python implementation.

XCode 5 versus XCode 6 default generated Game (Sprite Kit) project and scene sizes

Pete Barber from C#, C++, Windows &amp; other ramblings

As a way to learn about Swift I've been trying to write a simple game using Sprite Kit. My initial plan was to just allow a ball to be dragged around the screen and ensure it was constrained by the screen edges. This was a little harder than originally envisioned. This was partly because the default Game project generated by Xcode 6 is slightly different to that generated by Xcode 5 and so none of the existing Sprite Kit tutorials referred to this area.

My main issue was that I could move the ball around and when the drag finished the ball was endowed with velocity so it travelled after release and despite writing some simple code to ensure if the additional travel would take it off the screen this would bound it.

func boundPosToScene(newPos : CGPoint) -> CGPoint
{
  var retVal
  let radius = ball.size.width / 2

  if newPos.xradius < 0
  {
    retVal.xradius
  }

  if newPos.xradius > self.size.width
  {
    retVal.x = self.size.widthradius
  }

  if newPos.yradius < 0
  {
    retVal.yradius;
  }

  if newPos.yradius > self.size.height
  {
    retVal.y = self.size.heightradius
  }

  return retVal;

}

Where ball is a member variable of the class containing this method that is an instance of SKSpriteNode.

Despite this the ball kept disappearing. Reading various online articles, tutorials & StackOverflow posts there seemed to be an issue with Sprite Kit projects always starting up in landscape mode. When I added some debug to this statement (& else where), i.e.


println("view.bounds\(view.bounds), self.frame:\(self.frame), self.size:\(self.size)")

I got:

view.bounds(0.0,0.0,320.0,568.0), scene:(0.0,0.0,1024.0,768.0), scene.size:(1024.0,768.0)

OK. The view looks good but the scene is in landscape and even if orientated to portrait it's a lot larger than the actual view. But why? There were lots of posts about the landscape issues but nothing about the non-aligned size with Xcode 5. Well, a quick test by generating projects with 5 & 6 (NOTE: I'm new to Sprite Kit as well as Swift so I hadn't used it with 5) shows that the generated 'Game' Xcode 5 projects programmatically creates a scene that is sized to the view:

- (void)viewDidLoad
{
    [super viewDidLoad];

    // Configure the view.
    SKView * skView = (SKView *)self.view;
    skView.showsFPS = YES;
    skView.showsNodeCount = YES;
    
    // Create and configure the scene.
    SKScene * scene = [MyScene sceneWithSize:skView.bounds.size];
    scene.scaleMode = SKSceneScaleModeAspectFill;
    
    // Present the scene.
    [skView presentScene:scene];
}

whereas with XCode 6 it uses an SKS file (called GameScene):

override func viewDidLoad() {
  super.viewDidLoad()

  if let scene = GameScene.unarchiveFromFile("GameScene") as? GameScene {
    // Configure the view.
    let skView = self.view as SKView
    skView.showsFPS = true
    skView.showsNodeCount = true
            
    /* Sprite Kit applies additional optimizations to improve rendering performance */
    skView.ignoresSiblingOrder = true
            
    /* Set the scale mode to scale to fit the window */
    scene.scaleMode = .AspectFill

  }
}

Looking at the GameScene.sks:



You can see that the default scene size is 1024x768, i.e. iPad in landscape mode. Changing this to 320x576 (for iPhone 4 inch) fixes the problem.

NOTE: When making this change make sure you explicitly save the changes. Just modifying the values and building/running the project often seems to result in them being reset. I make sure I navigate away from the Size boxes before pressing Cmd-S.

Of course this is inflexible as it doesn't size to device. As I'd like my app to run on multiple device types I'm probably better of following the Xcode 5 generated code or perhaps just adding re-sizing code once the Scene has been loaded from the SKS file; as I'm not sure what else that gives me.

If you do this. In GameViewController.swift you'll also probably want to change

scene.scaleMode = .AspectFill

to

scene.scaleMode = .ResizeFill

Anyway, this difference in the generated starter apps is something to be aware of & the fact that the initial landscape startup issue reported against Xcode 5 seems to be present though possibly in a different guise. Certainty in the generated app from Xcode 5 it all works fine for me. When I added logging code to display the View and Scene size they were both reported as 320x568.

Subclassing Objective-C classes in Swift and the perils of Initializers

Pete Barber from C#, C++, Windows &amp; other ramblings

--- Begin update

1. The post below applies to Xcode 6 Beta 2. With Beta 3 & 4 the relationships between the Swift and Objective-C regarding the calling of super class initializers has been formalized.

1a. A Swift class can have multiple non-convenience initializers but in this case they must all property initialize any properties. Also, a non-convenience initializer cannot invoke another initializer, i.e. it cannot call self.init(...)

1b. When calling an Objective-C any initializer can be called but unlike what happened in Beta 2 if the initializer invoked is not the Objective-C 'designated' initializer and thus calls it this DOES NOT now result in a virtual like call to an initializer with that signature in the subclass, i.e. the main problem that led to the writing of this blog post.

2. If you want to subclass an SKSpriteNote in Beta 4 the following StackOverflow post shows how.

3. It seems that for some OS classes, in my case SpriteKit either Apple directly or some Xcode magic now provides a shim Swift wrapper of the Objective-C interface (the one for SKSpriteNode has a comment with a date of 2011 but when attempting to "show in Finder" nothing happens). As such all the initializers for SKSpriteNode are marked as convenience except for the 'designated' initializer, e.g.

class MySpriteNode : SKSpriteNode {}

3a. This is now essentially a Swift only project with the MySpriteNode now deriving from SKSpriteNode which is a Swift class. As such the Swift rules must be followed. This means that any convenience initializers in MySpriteNode can only call non-convenience initializers for MySpriteNode and these MUST in turn call a non-convenience initializers in the superclass. In the case of SKSpriteNode there is a only a single designated initializer which is:

   /**
     Designated Initializer
     Initialize a sprite with a color and the specified bounds.
     @param texture the texture to use (can be nil for colored sprite)
     @param color the color to use for tinting the sprite.
     @param size the size of the sprite in points
     */

    init(texture: SKTexture!, color: UIColor!, size: CGSize)

Therefore from a derived class it's impossible to use the super class convenience methods which is what Swift demands but is a shame as it often means re-implementing similar code in the derived class, as per the StackOverflow link.

It's not perfect by any means but it's a lot more consistent than Beta 2. I don't (yet) understand where the magic shim comes from and this is update is based on Beta 4 whereas of writing Beta 5 has just been released!

--- End update

As a way to learn Swift I decided to have a play with Sprite Kit. One of the first things I did was to create a subclass of SKSpriteNode. This has a very handy initializer:

init(imageNamed name: string) (in Swift)
-(instanceType)initWithImageNamed:(NString*)name (in Objective-C)

I then derived from this resulting in:

class Ball : SKSpriteNode
{
    init()
    {
        super.init(imageNamed: "Ball")
    }
}

and added it to my scene as follows:

var ball = Ball()
ball.position = CGPoint(x:CGRectGetMidX(self.frame), y:CGRectGetMidY(self.frame))
self.addChild(ball)

Having successfully written similar code using SKSpriteKitNode directly:

var ball = SKSpriteNode(imageNamed: "Ball")
ball.position = CGPoint(x:CGRectGetMidX(self.frame), y:CGRectGetMidY(self.frame))
self.addChild(ball)

I was expecting it to work. However I received the following runtime error:

fatal error: use of unimplemented initializer 'init(texture:)' for class 'Ploing.Ball'

The odd thing was that it was complaining about the lack of initializer in the Ball class. Why would calling a base class initializer result in a call back to the derived class? I wasn't sure but to work around this I decided to add the missing initializer:

init(texture: SKTexture!)
{
    super.init(texture: texture)
}

Having duly done this I then got the next error:

fatal error: use of unimplemented initializer 'init(texture:color:size:)' for class 'Ploing.Ball'

Ok, same process add that one to the Ball class. 

init(texture texture: SKTexture!, color color: UIColor!, size size: CGSize)
{
    super.init(texture: texture, color: color, size: size)
}

That time it worked but I was puzzled as to why. What seems to be happening is that the derived class is calling the non-designated initializer in the super class which is then calling the designated (or another non-designated one in between). However, when this initializer is called rather than calling the super class implementation it calls one in the derived class, whether it exists or not. In the case of Ball they didn't hence the error.

It turns out that in the middle of the the Initialization section of the The Swift Programming Language there is the following:

Initializer Inheritance and Overriding
Unlike subclasses in Objective-C, Swift subclasses do not not inherit their superclass initializers by default. Swift’s approach prevents a situation in which a simple initializer from a superclass is automatically inherited by a more specialized subclass and is used to create a new instance of the subclass that is not fully or correctly initialized.
If you want your custom subclass to present one or more of the same initializers as its superclass—perhaps to perform some customization during initialization—you can provide an overriding implementation of the same initializer within your custom subclass.
This explains it. Basically, in Swift, initialization methods work like virtual functions in fact super virtual functions. If a super class initializer is invoked and that in turns calls another initializer (designated or not) then it forwards the call to the derived class. The upshot of this seems to be that for any derived class in Swift it would need to re-implement all of the super classes initializers or at least any which may be invoked from the the other initializers.

Time for some experiments

I therefore set out to confirm this with a simple Swift example:

class Foo
{
    var one: Int;
    var two: Int;

    init(value value:Int)
    {
        self.init(value: value, AndAnother:7)
    }

    init(value value:Int, AndAnother value1:Int)
    {
        one = value;
        two = value1;
    }

    func print()
    {
        println("One:\(one), Two:\(two)")
    }
}

class Bar : Foo
{
    init()
    {
        super.init(value:1);
    }
}

let bar = Bar()
bar.print()

This wouldn't compile. 

Designated initializer for 'Foo' cannot delegate (with 'self.init'); did you mean this to be a convenience initializer?
Must call a designated initializer of the superclass 'Foo'

Whereas in Objective-C the designated initializer is effectively advisory, in Swift it's enforced. If a initializer isn't marked with the convenience  keyword then it seems (at least during compilation) all initializers are treated as being the designated initializor and not at the same time. In this case the compilation failed as there was no designated initializer for Bar.init to call and as Foo.init(value value:Int) wasn't marked as a connivence initializer it was assumed to the designated one and is thus forbidden from calling another initializer in its own class; somewhat paradoxically.

These two rules prevent issues that occur with Objective-C's advisory initializer. All but the designated initializer must be prefixed with the convenience keyword. Secondly this is the only initializer permitted to call the super class initializer meaning all the the convenience initializers can only (cross) call other convenience or the designated initializer for their class. Following these rules gives a working example:

class Foo
{
    var one: Int;
    var two: Int;

    convenience init(value value:Int)
    {
        self.init(value: value, AndAnother:7)
    }

    init(value value:Int, AndAnother value1:Int)
    {
        one = value;
        two = value1;
    }

    func print()
    {
        println("One:\(one), Two:\(two)")
    }
}

class Bar : Foo
{
    init()
    {
        super.init(value: 7, AndAnother: 8)
    }
}

let bar = Bar()
bar.print()

Which gives the results:

One:7, Two:8

It also completely bypasses the convenience method of the superclass rendering it useless for calling from a derived class.

As for explaining the original problem this doesn't help either as the new rules prevent the problem. Herein lies the clue though. It suggests the problem is not with Swift classes subclassing other Swift classes but when a Swift class subclasses an Objective-C class.

Subclassing Objective-C from Swift

Time for another experiment but this time using a base class written in Objective-C:

Base.h

@interface Base : NSObject

-(id)initWithValue:(NSInteger) value;
-(id)initWithValue:(NSInteger) value AndAnother:(NSInteger) value1;
-(void)print;

@end

Base.m

#import "Base.h"

@interface Base ()
@property NSInteger one;
@property NSInteger two;
@end

@implementation Base

-(id)initWithValue:(NSInteger) value
{
    return [self initWithValue:value AndAnother:2];
}

-(id)initWithValue:(NSInteger) value AndAnother:(NSInteger) value1
{
    if ([super init])
    {
        self.one = value;
        self.two = value1;
    }
    
    return self;
}

-(void)print
{
    NSLog(@"One:%d, Two:%d", (int)_one, (int)_two);
}

@end

main.swift

class Baz : Base
{
    init()
    {
        super.init(value: 7)
    }

    init(value value:Int, AndAnother value1:Int)
    {
        super.init(value: value, andAnother: value1);
    }
}

var baz = Baz()
baz.print()

Looking at Base it's obvious that the desginated initializer is initWithValue:(int)value AndAnother:(int)value1 whereas Baz is calling a 'convenience' initializer. This compiles happily but when run gives the following error:

fatal error: use of unimplemented initializer 'init(value:andAnother:)' for class 'Test.Baz'

This is the same type of error as in the original SKSpriteNote sample. Here, Baz's initializer is successfully invoking the Base.initWihValue:(int) value but when it invokes Base's designated initializer this is when the super virtual functionality of the initializers comes into play and an attempt is made to call this non-existent method on Baz. This is easily fixed by adding that method such as it calls the super class method as in:

class Baz : Base
{
    init()
    {
        super.init(value: 7)
    }

    init(value value:Int, AndAnother value1:Int)
    {
        super.init(value: value, andAnother: value1);
    }
}

Giving the result:

2014-06-07 17:40:18.632 Test[47394:303] One:7, Two:2

Alternatively and staying true to the Swift way the parameterless intializer which is obviously a convenience initializer should be marked as such. This then causes a compilation failure as this is now forbidden from calling the super class initialzer and instead must make a cross call to the designated initializer giving the following code:

class Baz : Base
{
    convenience init()
    {
        self.init(value: 7, AndAnother: 8)
    }

    init(value value:Int, AndAnother value1:Int)
    {
        super.init(value: value, andAnother: value1);
    }
}

Which gives the result:

2014-06-07 17:40:46.345 Test[47407:303] One:7, Two:8

This differs from the previous version as the connivence initializer now calls the designated one within Baz meaning the  -(id)initWithValue:(NSInteger) value is never called which is why the second value is nolonger 2.

Conclusion

Whilst this explains the behaviour I was seeing when subclassing SKSpriteNode and by providing a mirror of its initializers without marking any as convenience it solves the problem of using the convenient init(imageNamed name: string) method it doesn't do so particularly elegantly nor in a fully Swift style; as it leaves the class with a set of initializers none of which are marked convenience.

A designated initializer could be specified by marking all but the init(texture texture: SKTexture!, color color: UIColor!, size size: CGSize) method as convenience and having them cross call this one. However this would prevent the direct calling of init(imageNamed name: string) which is a lot more convenient than the other methods. 

Ironically, whilst Swift formalizes the designated initializer concept and it looks like it will work well for pure Swift code it can be somewhat inconvenient when subclassing Objective-C classes.

P.S. For those of us who have trouble spelling the keyword convenience is far from convenient. A keywoard to mark the designated initializer may well have been more convenient and probably easier to spell! 

Videos from C++ track on NDC 2014

olvemaudal from Geektalk

As the chair for the C++ track on NDC Oslo, I am happy to report that the C++ track was a huge and massive success! The C++ community in Norway is rather small so even if NDC is a big annual conference for programmers (~1600 geeks) and even with names like Nico, Scott and Andrei as headliners for the track, I was not sure how many people would actually turn up for the C++ talks. I was positively surprised. The first three sessions was packed with people (it was of course a cheap trick to make the three first sessions general/introductory on popular topics). All the other talks were also well attended. The NDC organizers have already confirmed that they want to do this next year as well.

NDC Oslo is an annual five day event. First two days of pre-conference workshops (Andrei did 2 days of Scalable design and implementation using C++) and then 9 tracks of talks for three full days. As usual, NDC records all the talks and generously share all the videos with the world (there are 150+ talks, kudos to NDC!).

I have listed the videos from the C++ track this year. I will also put out a link to the slides when I get them. Enjoy!

Day 1, June 4, 2014

  • C++14, Nico Josuttis (video)
  • Effective Modern C++, Scott Meyers (video)
  • Error Handling in C++, Andrei Alexandrescu (video)
  • Move, noexcept, and push_back(), Nico Josuttis (video)
  • C++ Type Deduction and Why You Care, Scott Meyers (video)
  • Generic and Generative Programming in C++, Andrei Alexandrescu (video)

Day 2, June 5, 2014

  • C++ – where are we headed?, Hubert Matthews (video)
  • Three Cool Things about D, Andrei Alexandrescu (video)
  • The C++ memory model, Mike Long (video, slides)
  • C++ for small devices, Isak Styf (video)
  • Brief tour of Clang, Ismail Pazarbasi (video)
  • Insecure coding in C and C++, Olve Maudal (video, slides)
  • So you think you can int? (C++), Anders Knatten (video)

With this great lineup I hope that NDC Oslo in June has established itself as a significant annual C++ event in Europe together with Meeting C++ Berlin in December and ACCU Bristol in April.

Save the date for NDC next year, June 15-19, 2015. I can already promise you a really strong C++ track at NDC Oslo 2015.

A final note: Make sure you stay tuned on isocpp.org for global news about C++.

The Primacy of Testability: Modularity

Austin Bingham from Good With Computers

In the first post in this series I set the stage for a discussion of how testability can serve as a proxy or enabler for other, more directly desirable qualities in a software system. In this post I'd like to look at the first such quality, modularity.

Modularity is perhaps the most obvious quality to correlate with testability. Modularity is a bit like motherhood and apple pie, and we generally recognize it as a "good thing." Most good developers instinctively foster modularity and reject non-modular designs, both because they've been taught that modularity is good and because they've learned through experience that it's important for many, many reasons.

What do we mean by modularity? A simple definition of modularity is "breaking designs into pieces", but that obviously misses important points. We don't just pull a system into arbitrary pieces, but instead we create modules with specific qualities in order to support and foster the goals of whatever it is we're building. A typical (and important) goal with modules is to have high internal cohesion and low external coupling. A highly cohesive module is one in which all of the module elements are related, work together, and are necessary for performing the work that the module does. A module with low coupling is one that doesn't rely unnecessarily or too extensively on other modules.

There are plenty of ways to ways to discuss and even measure modularity in software designs [1], but for our purposes the basic concepts of cohesion and coupling suffice. So how does modular code - code structured as modules with high internal cohesion and low external coupling - correlate with testability? The short answer is that modular code is generally very testable, so let's see how and why.

One way to see the relationship between testability and modularity is to recognize that modular code, by virtue of its low coupling, is easier to instantiate and execute in isolation. The fewer things (classes, services, whatever) that a module needs, the less work it is to write tests for it. That is, you simply have to type less for each test. Likewise, tests for modules with fewer external dependencies often execute more quickly - at least marginally so - because there's less stuff to do for each test. The result is that developers can run the tests more often and will be more inclined to do so.

If you use mocks in your testing system, low coupling means that you generally have to design fewer mock objects (because your modules have fewer dependencies that need mocking). Moreover, your mocks will often be simpler because they won't have to simulate interactions between far-flung dependencies.

The relationship between modularity and testability goes even deeper, though. Beyond the somewhat mechanical questions of instantiation times, test length, and so forth, there are serious cognitive problems associated with testing poorly-modularized code. The first of these problems is that your tests can end up testing the wrong thing. If a test for some bit of functionality has to invoke code in other modules, the success or failure of the test depends not just on the code under test but on all of those other modules. On some level this is unavoidable [2], but unnecessary dependencies unnecessarily increase the risk that the results you're seeing for your tests are caused by faults in other modules. These kinds of external failures take time to debug, can distort tests as developers try to work around them, or - in the case of incorrectly passing tests - can mask actual defects. [3] Ideally, the output from your tests should give you precise and unambiguous information about just the element under test, and reducing coupling helps developers approach that ideal.

A second way that poorly modularized code increases cognitive load for test developers is that it increases the state space with which a test developer needs to contend. For every external element that plays a role in a module's functionality, the state space that needs to be considered for testing grows to include the potential states of that element. For example, if a test relies on the some global state managed by an external module - perhaps something like an application object managed by the GUI library - then test developers need to ensure that this external object is in the correct state when the test is executed. This means that no matter what other tests have been run, what order they've been run in, or their results, the test developer needs to ensure that this external state is acceptable. As external test dependencies grow, this management of external state can become a significant or even dominant aspect of test development. In other words, the more unnecessary dependencies a module has, the more time a developer will need to spend thinking about those dependencies rather than focusing on testing the functionality at hand. Babysitting unnecessary dependencies doesn't generate information or value. [4]

So we can see that poorly modularized code is generally harder to test, and that's good to know. But the goal of this series is to explore how testability reflects other qualities, not the other way around. How, then, can the testability of our code inform us about its modularity?

The important point is this: if you find that your code is easy to test, then that's a good indication that your code is modular! If you sit down to write some tests and you find that your fixtures are easy to write, the extent of the tests is easy to define, and you don't find that you're constantly needing to consider distant side-effects, then you're probably testing modular code. To carry on with the barometer metaphor, you've got high-pressure, and you can see blue skies and little white puffy clouds. It's time for a picnic.

On the other hand, if your testing efforts involve lots of ceremony - instantiating objects, wiring them together, and bootstrapping subsystems - or if you feel like your really just shotgunning tests at the code rather than pinpointing the "obvious" testing points, then chances are that you've got some modularity issues.

Like I said, modularity is perhaps the most obvious quality that we can associate with testability. And the way to leverage testability in this case is to pay attention to what your testing efforts tell you. There's a lot of information in the work involved in developing tests, and drawing insight from this work is a valuable doubling-up of that effort.

A corollary to this insight is that, when you find yourself having difficulty writing some tests, step back and ask yourself if these problems stem from poor modularity. Testing can be a bit repetitive, though often with minor tweaks, and this is a wonderful environment in which to find repeated bad patterns. And sometime consideration of these patterns will show where you might have an opportunity for better modularization of your code.

[1]See for example some of Martin Fowler's thoughts on the topic, discussions about the interaction between type-systems and modularity, and even some information-theoretic approaches.
[2]Operating systems and standard libraries are "other modules" by most measures.
[3]Consider a test for a specific exception. If some dependency is throwing that exception and the function under test is, in fact, not throwing the exception, then the test is passing erroneously.
[4]And as Gerald Weinberg says, tests are about producing information.

The Primacy of Testability

Austin Bingham from Good With Computers

The job of a software architect [1] is difficult, just like almost every role in software development. They have to keep track of many subtly interacting quality attributes, often on multiple projects, any one of which may be too big or evolving too quickly to meaningfully keep in mental cache. To make matters worse, architects don't have near the level of tool support - compilers, static analysis tools, auto-completion - available to developers. They are much more reliant on experience, awareness, intuition, and heuristics.

In light of this, it's interesting and useful to consider what tools are available to help architects. In particular, I want to look at the role of testability in the architect's job, and to try to show how it can serve as a meaningful proxy for other, perhaps more important qualities in a software system. Testability is a quality that can promote the health of other desirable qualities, and it can serve as an indicator of whether these requirements are being met. The metaphor I like to use is that testability is a kind of barometer for software architects. A barometer only really tells you the air-pressure, but you can often use this to determine if there's going to be rain. Testability only really tells you how amenable your code is to useful testing, but you can often use this to help determine if your system is modular, organizationally scalable, and so forth.

What is testability anyway?

To meaningfully discuss testability as a tool, we need to establish some definition of what it means. Like "software architect", there is no perfect answer. On some level all software is testable in that you can test it. By hook or by crook you can write some code that verifies the behavior of pretty much anything with a specification. So clearly just "being testable" isn't a sufficient definition.

At the same time, it's also pretty clear that it's simpler to test some software than other. It may be easy to test for a number of reasons. Perhaps it's easy to understand, so that you have a clear understanding of how to test it thoroughly and properly. Perhaps the chunk of code is easy to instantiate without requiring a whole bunch of scaffolding and support objects. This not only saves on keystrokes but it also has other big benefits: it isolates behavior, it may mean your tests are faster, and it generally means that your tests are easier to understand and thus maintain.

If you do a little poking around you'll find that people have hit upon certain code qualities that generally influence the testability of a piece of code. [2] But in the end we don't really have a "testability-o-meter" that we can point at a piece of code. There's no accepted way to assign a "testability rating" to software that tells you if code is more or less testable than other code, or even if it's "easy to test" or "hard to test". We can sometimes get these kinds of numbers for other qualities like modularity or complexity, and things like "scalability" also lend themselves to being measured, but testability isn't (yet) in that realm.

Instead, determining if something is testable is a decision that people need to make, and it's a decision that you can only make in an informed way if you understand code. And this is why my definition of "software architect" - from a practical standpoint - includes being able to understand code well at many levels. You have to be able to recognize when, say, dependency injection could replace local object construction to reduce coupling in a system. You need to be able to spot - or at least know to be on the lookout for - circular dependencies between modules. And in general you're going to need to be able to do this not only with code that you're writing but with code that you only see in reviews or maybe only see described in documents.

Why testability?

So I've just told you that testability is hard to measure or even to define. In fact, I've told you that to make heads or tails of it you need to be an experienced programmer. On its face, then, it sounds like the cure is worse than the disease: yes, you've got complexity in your projects to deal with, but now I want to you do something even harder to make those problems go away.

On some level that's true! Gauging testability isn't simple and it's not perfect, but by targetting testability we get a couple of important benefits because testability is special.

Testability represents your first customer, your first users: your tests! Tests are very often the first place your code is used outside of your head. This means that this is where you'll first spot difficult APIs or awkward relationships that slipped through your design.

Tests force us to use code, and they force us to consider it at many different zoom levels - from unit tests to functional tests to integration tests, we get to see it all. And tests can - and should - happen early and often in the development process. This is how you get maximum benefit from them.

If you're paying attention you'll notice that I just made a significant shift in terminology. I went from talking about "testability" to "tests", from "code that can be tested" to "code with tests". I guess it's arguable that you can have testable code without actually having tests, but that seems a bit academic to me. I've gone on and on about how difficult it is to measure testability, but one of most effective and practical ways to asses testability is to simply test your code!

So for my purposes, testable code is also tested code. I won't quibble able precisely how much testing is enough, or at what level it should be done; there are plenty of other people who are happy to tell you that. [3]

But if your tests add value to your software system, then I'd wager that they exercise your code enough to highlight a lot of the software qualities for which testability is a barometer.

Qualities correlated with testability

This article lays the foundation for the rest of this series in which we'll look at various software qualities that correlate with testability. Some of these qualities, such as modularity, are directly reflected in the testability of a system. Other qualities, like performance, are supported or enabled by testability but aren't directly related to it.

[1]This is an ill-defined term, to be sure, but I'm essentially talking about the person tasked with shepherding the so-called non-functional requirements...whether their job title is "software architect" or not.
[2]Wikipedia's got a nice, non-controversial list of things like "observability", "heterogeneity", and "understandability", and all of these things certainly would influence how easy or hard it is to test a piece of code.
[3]See for example TDD, BDD, or James Coplien's thoughts.

Series: The Primacy of Testability

Austin Bingham from Good With Computers

In this series we look at how software architects - or really anyone involved in creating software - can use testability to help manage other quality attributes. From modularity to performance to the SOLID principles, testability can act as a proxy and an enabler for many of the cross-cutting, interacting concerns that architects need to shepherd. Over several articles we'll explore testability's relationship to these qualities, and we'll see how paying attention to testability can help simplify the job of managing them.

How to write Boost.Python type converters

Austin Bingham from Good With Computers

Boost.Python [1] makes it possible to write C++ that "feels" like Python. The library is powerful and sometimes subtle. This is as compared with the Python C API, where the experience is very far removed from writing Python code.

Part of making C++ feel more like Python is allowing natural assignment of C++ objects to Python variables. For instance, assigning an standard library string to a Python object looks like this:

// Create a C++ string
std::string msg("Hello, Python");

// Assign it to a python object
boost::python::object py_msg = msg;

Likewise (though somewhat less naturally), it is also important to be able to extract C++ objects from Python objects. Boost.Python provides the extract [2] type for this:

boost::python::object obj = ... ;
std::string msg = boost::python::extract(obj);

To allow this kind of natural assignment, Boost.Python provides a system for registering converters between the languages. Unfortunately, the Boost.Python documentation does a pretty poor job of describing how to write them. A bit of searching on the internet will turn up a few links. [3]

While these are fine (and, in truth, are the basis for what I know about the conversion system), they are not as explicit as I would like.

So, in an effort to clarify the conversion system both for myself and (hopefully) others, I wrote this little primer. I'll step through a full example showing how to write converters for Qt's QString [4] class. In the end, you should have all the information you need to write and register your own converters.

Converting QString

A Boost.Python type converter consists of two major parts. The first part, which is generally the simpler of the two, converts a C++ type into a Python type. I'll refer to this as the to-python converter. The second part converts a Python object into a C++ type. I'll refer to this as the from-python converter.

In order to have your converters be used at runtime, the Boost.Python framework requires you to register them. The Boost.Python API provides separate methods for registering to-python and from-python converters. Because of this, you are free to provide conversion in only one direction for a type if you so choose.

Note that, for certain elements of what I'm about to describe, there is more than one way to do things. For example, in some cases where I choose to use static member functions, you could also use free functions. I won't point these out, but if you wear your C++ thinking-cap you should be able to see what is mandatory and what isn't.

To-python Converters

A to-python converter converts a C++ type to a Python object. From an API perspective, a to-python converter is used any time that you construct a boost::python::object [5] from another C++ type. For example:

// Construct object from an int
boost::python::object int_obj(42);

// Construct object from a string
boost::python::object str_obj = std::string("llama");

// Construct object from a user-defined type
Foo foo;
boost::python::object foo_obj(foo);

You implement a to-python converter using a struct with static member function named convert(), which takes the C++ object to be converted as its argument, and it returns a PyObject*. A to-python converter for QStrings looks like this:

/* to-python convert to QStrings */
struct QString_to_python_str
{
    static PyObject* convert(QString const& s)
    {
        return boost::python::incref(
            boost::python::object(
                s.toLatin1().constData()).ptr());
    }
};

The crux what this does is as follows:

  1. Extract the QString's underlying character data using toLatin1().constData()
  2. Construct a boost::python::object with the character data
  3. Retrieve the boost::python::object's PyObject* with ptr()
  4. Increment the reference count on the PyObject* and return that pointer.

That last step bears a little explanation. Suppose that you didn't increment the reference count on the returned pointer. As soon as the function returned, the boost::python::object in the function would destruct, thereby reducing the ref-count to zero. When the PyObject's reference count goes to zero, Python will consider the object dead and it may be garbage-collected, meaning you would return a deallocated object from convert().

Once you've written the to-python converter for a type, you need to register it with Boost.Python's runtime. You do this with the aptly-named to_python_converter [6] template:

// register the QString-to-python converter
boost::python::to_python_converter<
    QString,
    QString_to_python_str>()

The first template parameter is the C++ type for which you're registering a converter. The second is the converter struct. Notice that this registration process is done at runtime; you need to call the registration functions before you try to do any custom type converting.

From-python Converters

From-python converters are slightly more complex because, beyond simply providing a function to convert from Python to C++, they also have to provide a function that determines if a Python type can safely be converted to the requested C++ type. Likewise, they often require more knowledge of the Python C API.

From-python converters are used whenever Boost.Python's extract type is called. For example:

// get an int from a python object
int x = boost::python::extract(int_obj);

// get an STL string from a python object
std::string s = boost::python::extract(str_obj);

// get a user-defined type from a python object
Foo foo = boost::python::extract(foo_obj);

The recipe I use for creating from-python converters is similar to to-python converters: create a struct with some static methods and register those with the Boost.Python runtime system.

The first method you'll need to define is used to determine whether an arbitrary Python object is convertible to the type you want to extract. If the conversion is OK, this function should return the PyObject*; otherwise, it should return NULL. So, for QStrings you would write:

struct QString_from_python_str
{

    . . .

    // Determine if obj_ptr can be converted in a QString
    static void* convertible(PyObject* obj_ptr)
    {
        if (!PyString_Check(obj_ptr)) return 0;
        return obj_ptr;
    }

    . . .

};

This simply says that a PyObject* can be converted to a QString if it is a Python string.

The second method you'll need to write does the actual conversion. The primary trick in this method is that Boost.Python will provide you with a chunk of memory into which you must in-place construct your new C++ object. All of the funny "rvalue_from_python" stuff just has to do with Boost.Python's method for providing you with that memory chunk:

struct QString_from_python_str
{

    . . .

    // Convert obj_ptr into a QString
    static void construct(
        PyObject* obj_ptr,
        boost::python::converter::rvalue_from_python_stage1_data* data)
    {
        // Extract the character data from the python string
        const char* value = PyString_AsString(obj_ptr);

        // Verify that obj_ptr is a string (should be ensured by
        convertible())
        assert(value);

        // Grab pointer to memory into which to construct the new QString
        void* storage = (
            (boost::python::converter::rvalue_from_python_storage*)
            data)->storage.bytes;

        // in-place construct the new QString using the character data
        // extraced from the python object
        new (storage) QString(value);

        // Stash the memory chunk pointer for later use by boost.python
        data->convertible = storage;
    }

  . . .

};

The final step for from-python converters is, of course, to register the converter. To do this, you use boost::python::converter::registry::push_back(). [7] The first argument is a pointer to the function which tests for convertibility, the second is a pointer to the conversion function, and the third is a boost::python::type_id for the C++ type. In this case, we'll put the registration into the constructor for the struct we've been building up:

struct QString_from_python_str
{
    QString_from_python_str()
    {
        boost::python::converter::registry::push_back(
            &convertible,
            &construct,
            boost::python::type_id());
    }

    . . .

};

Now, if you simply construct a single QString_from_python_str object in your initialization code (just like you how you called to_python_converter() for the to-python registration), conversion from Python strings to QString will be enabled.

Taking a reference to the PyObject in convert()

One gotcha to be aware of in your construct() function is that the PyObject argument is a 'borrowed' reference. That is, its reference count has not already been incremented for you. [8] If you plan to keep a reference to that object, you must use Boost.Python's borrowed construct. For example:

class MyClass
{
public:
    MyClass(boost::python::object obj) : obj_ (obj) {}

private:
    boost::python::object obj_;
};

struct MyClass_from_python
{
    . . .

    static void construct(
        PyObject* obj_ptr,
        boost::python::converter::rvalue_from_python_stage1_data* data)
    {
        using namespace boost::python;

        void* storage = (
            (converter::rvalue_from_python_storage*)
                data)->storage.bytes;

        // Use borrowed to construct the object so that a reference
        // count will be properly handled.
        handle<> hndl(borrowed(obj_ptr));
        new (storage) MyClass(object(hndl));

        data->convertible = storage;
    }
};

Failing to use borrowed() in this situation will generally lead to memory corruption and/or garbage collection errors in the Python runtime.

There are a number of useful resources on the web for finding more information on Boost.Python objects, handles, and reference counting. [9]

When converters don't exist

Finally, a cautionary note. The Boost.Python type-conversion system works well, not only at the job of moving objects across the C++-python languages barrier, but at making code easier to read and understand. You must always keep in mind, though, this comes at the cost of very little compile-time checking.

That is, the boost::python::object copy-constructor is templatized and accepts any type without complaint. This means that your code will compile just fine even if you're constructing boost::python::object s from types that have no registered converter. At runtime these constructors will find that they have no converter for the requested type, and this will result in exceptions.

These exceptions [10] will tend to happen in unexpected places, and you could spend quite a bit of time trying to figure them out. I say all of this so that maybe, when you encounter strange exceptions when using Boost.Python, you'll remember to check that your converters are registered first. Hopefully it'll save you some time.

Resources

Boost.Python is fairly complex and can be difficult to understand all at once. Here are few more useful resources that might help you come up to speed on this useful technology:

  • This IPython notebook-based tutorial covers a lot of the major (and some of the more obscure) topics in Boost.Python.
  • The Boost.Python wiki contains a lot of collected Boost.Python knowledge.
  • And of course, the Boost.Python documentation itself is very useful.

Appendix: Full code for QString converter

struct QString_to_python_str
{
    static PyObject* convert(QString const& s)
    {
        return boost::python::incref(
            boost::python::object(
                s.toLatin1().constData()).ptr());
    }
};

struct QString_from_python_str
{
    QString_from_python_str()
    {
        boost::python::converter::registry::push_back(
            &convertible,
            &construct,
            boost::python::type_id());
    }

    // Determine if obj_ptr can be converted in a QString
    static void* convertible(PyObject* obj_ptr)
    {
        if (!PyString_Check(obj_ptr)) return 0;
        return obj_ptr;
    }

    // Convert obj_ptr into a QString
    static void construct(
        PyObject* obj_ptr,
        boost::python::converter::rvalue_from_python_stage1_data* data)
    {
        // Extract the character data from the python string
        const char* value = PyString_AsString(obj_ptr);

        // Verify that obj_ptr is a string (should be ensured by convertible())
        assert(value);

        // Grab pointer to memory into which to construct the new QString
        void* storage = (
            (boost::python::converter::rvalue_from_python_storage*)
            data)->storage.bytes;

        // in-place construct the new QString using the character data
        // extraced from the python object
        new (storage) QString(value);

        // Stash the memory chunk pointer for later use by boost.python
        data->convertible = storage;
    }
};

void initializeConverters()
{
    using namespace boost::python;

    // register the to-python converter
    to_python_converter<
        QString,
        QString_to_python_str>();

    // register the from-python converter
    QString_from_python_str();
}
[1]The Boost.Python homepage.
[2]boost::python::extract<> documentation.
[3]For example the Boost.Python FAQ.
[4]The Qt QString documentation.
[5]The boost::python::object documentation.
[6]The to_python_converter documentation.
[7]The boost::python::converter::registry documentation.
[8]Python reference counting details.
[9]For example, this discussion from the C++-sig discussion list, the Boost.Python documentation, and David Abrahams' guidelines. for handle<> on the Python wiki.))
[10]Boost.Python uniformly uses boost::python::error_already_set to communicate exceptions from Python to C++..

Speaking: Words in Code

Pete Goodliffe from Pete Goodliffe

The slides from my ACCU 2014 talk, Words in Code, are available on SlideShare, from http://www.slideshare.net/petegoodliffe/words-in-code.

Here's the synopsis:

As software developers we do not just write code. We write many, many words too.

We write documentation, comments, manuals, specifications, technical articles, wiki documentation, and more. Maybe even magazine articles and books.

This talk discusses some practicalities of writing well, both stylistically and practically. We'll talk about prose, but also about the right "geek" way of writing, the storage formats, toolchains, and the storage of our words.

We'll cover:
- writing style
- what's appropriate: what to write what not to write
- keeping track: "source control" for words
- toolchains: what toolsets to use to write and prepare output
- markup languages vs "wysiwyg" tools
- sharing your words with non-geeks

At the end of this talk, you'll have a good idea how to put together an example "document toolchain" taking source-controlled words in a humane markup style, and creating high-quality HTML, PDF (fully styled, print-ready) ePub and Kindle output, as well as Word-friendly versions.

Top four JavaZone 2013 talk – The Unreasonable Effectiveness of Dynamic Typing

Rob Smallshire from Good With Computers

I'm very happy to see that my talk on The Unreasonable Effectiveness of Dynamic Typing was rated fourth of all the talks in the show. Thanks to everyone who attended and voted.

This talk is perhaps deliberately provocative, but only with the intention of provoking critical thinking and empiricism around the tools we use. I'm genuinely curious as to why programs in dynamic languages are as reliable as they are, although I confess I don't yet have many of the answers.