Rob Smallshire from Good With Computers
In this series we look in detail at the behaviour of one of the simplest geometric functions, demonstrate its flawed behaviour when implemented with floating point numbers, and fix it using an exact number type provided in the Python Standard Library.
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.
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:
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:
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. |
Pete Barber from C#, C++, Windows & 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.
The Lone C++ Coder's Blog from The Lone C++ Coder's Blog
First, a confession - I actually occasionally call myself a coder, but in a tongue in cheek, post-modern and ironic way. Heck, it does make for a good blog title and license plate. Nevertheless, with all the recent “coding schools” cropping up all over the place - at least if you are in the Bay Area - it does seem that being able to code in the context of a reasonably sought after web technology without much further formal training is the path to new, fulfilling careers and of course untold riches in an economy where recent graduates in all fields have problems finding work.Pete Barber from C#, C++, Windows & other ramblings
--- Begin updateThe Lone C++ Coder's Blog from The Lone C++ Coder's Blog
Like pretty much every other programmer with a Mac, I’m currently looking at Swift. Will I write anything but toy programs in it? I don’t know yet - I don’t really write any Mac-ish software on my Mac, just unix-ish programs. If Swift doesn’t escape the OS X and iOS ecosystems it’ll be a nice exercise in a neat language that’s not really that relevant to the world at large, or at least to my part of the world at large.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
Day 2, June 5, 2014
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 Lone C++ Coder's Blog from The Lone C++ Coder's Blog
For those of us who remember when the BBC Micro was the home computer with the fastest Basic implementation available, a long time ago, and was pretty legendary in home computing circles in Europe. It didn’t sell that much outside of the UK, mostly because of its price. It was also the target system for the original implementation of Elite. Matt Godbolt is building an emulator in JavaScript. First post of his series can be found here.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. |
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.
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.
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.