Prove it – factorial is bigger than 2^n

Frances Buontempo from BuontempoConsulting

I've been doing the scala coursera and wanted to write down the proof that

factorial(n) ≥ 2n when n ≥ 4

since it uses induction and I am out of practise.

Base case

For n = 4

factorial(4) = 4*3*2*1 = 24
and 24 = 2*2*2*2 = 16
and 24 ≥ 16

so factorial(n) ≥ 2n when n = 4

Induction step

For n >= 4 assume we have

factorial(n) >= 2n

and consider

factorial(n+1) = factorial(n) × (n+1)
 ≥ 2n × (n+1)
 ≥ 2n × 2 since (n+1) ≥ 2 when n ≥ 4
 = 2n+1

QED
(I also wanted to learn about writing maths in html)

Dear Apple, are you really forcing me to choose between buying new hardware and a Windows license?

The Lone C++ Coder's Blog from The Lone C++ Coder's Blog

We have an early 2008 MacBook “Blackbook” that is still working perfectly well and does everything we ask from it. It’s one of the reasons I love Apple hardware - it’s well engineered and works without a major fuss. Obviously we’re not playing games on it but it’s perfect for us to use for tasks that need a bit more power or typing than you’d want to do on a tablet.

Acid Air Pollution on the Cowley Road Oxford Uk

Tim Pizey from Tim Pizey

The Long Wall which Long Wall Street is named for always has a light line of white sand at its base, and nearly always has ongoing masonry works to repair it.

These pictures are taken at another Oxford road junction.

On the eastern edge of Oxford another set of traffic lights, at the junction of Cowley Road and Between Towns Road, again causes stationary traffic.

The local limestone is not very hard, and is constantly eroded, with the damage to the mortar being worse than that to the stone.

The damage is worst at ground level up to one metre.

The damage is worst near the ground and is caused by acidic exhaust fumes.

Here all the lichen has been killed and the brick looks as though it has been cleaned with brick acid.

We know that breathing in small particles from diesel exhaust is dangerous, as the particle size is small enough to pass deep into the lungs. The pattern of the effect on the walls shows that the concentration is particularly strong under one metre in height. There are two primary schools, one on either side of this junction.

Iffley Village Oxford Rag Stone

The quality of Oxford stone can be pretty shaky, and the stone that was used for field and road boundary walls was presumably of lower quality than that used for houses as good quality stone is scarce on the clay. This wall in Iffley is a charming example, but note what is happening to the bottom metre.

Who should we be claiming financial damages from? Shell? BP? Exxon?

Modern C++ Testing

Phil Nash from level of indirection

Back in August I took my family to stay for a week at my brother's house in (Old) South Wales. I've not been to Wales for a long time and it was great to be back there - but that's not what this post is about, of course.

The thing about Wales is that it has mountains (and where there are no mountains there are plenty of hills and valleys and cliffs). Mobile cell coverage is non-existent in much of the country - particularly where my brother lives.

So the timing was particularly bad when, just as we were driving along the south cost (somewhere between Cardiff and Swansea, I think), I started getting emails and tweets from people pointing out that Catch was riding high on HackerNews! Someone had recently discovered Catch and was enjoying it enough that they wanted to share it with the community. Which is awesome!

Except that, between lack of mobile reception and spending time with my family, I didn't have opportunity to join the discussion.

When I got back home a week later I read through the comments. One of them stuck out because it called me out on describing Catch as a "Modern C++" framework (the commenter recommended another framework, Bandit, as being "more modern").

When I first released Catch, back in 2010, C++11 was still referred to as C++1x (or even C++0x!) and the final release date was still uncertain. So Catch was written to target C++03. It used a few "modern" idioms of the time - but the modernity was intended more as being a break from the past - where most C++ frameworks were just reimplementations of JUnit in C++. So I think the label was somewhat justified at the time.

Of course since then C++11 has not only been standardised but is fully, or nearly fully, implemented by many leading, mainstream, compilers. I think adoption is still not high enough, at this point, that I'd be willing to drop support for C++03 in Catch (there is even an actively maintained fork for VC6!). But it is enough that the baseline for what constitutes "modern C++" has definitely moved on. And now C++14 is here too - pushing it even further forward.

"Modern" is not what it used to be

What does it mean to be a "Modern C++ Test Framework" these days anyway? Well the most obvious thing for the user is probably the use of lambdas. Along with a few other features, lambdas allow for a lot of what previously required macros to be done in pure C++. I'm usually the first to hold this up as A Good Thing. In a moment I'll get to why I don't think it's necessarily as good a step as you might think.

But before I get to that; one other thing: For me, as a framework author, the biggest difference C++11/14 would make to something like Catch would be in the internals. Large chunks of code could be removed, reduced or at least cleaned up. The "no dependencies" policy means that Catch has complete implementations of things like shared pointers, optional types and function objects - as well as many things that must be done the long way round (such as iterating collections - I long for range for loops - or at least BOOST_FOREACH).

The competition

I've come across three frameworks that I'd say qualify as truly trying to be "modern C++ test frameworks". I'm sure there are others - and I've not really even used these ones extensively - but these are the ones I'll reference in this discussion. The three frameworks are:

  • Lest - by Martin Moene, an active contributor to Catch - and partly based on some Catch ideas - re-imagined for a C++11 world.
  • Bandit - this is the one mentioned in the Hacker News comment I kicked off with
  • Mettle - I saw this in a tweet from @MeetingCpp last week and it's what kicked off the train of thought that led me to this post

The case for test case macros

But why did I say that the use of lambdas is not such a good idea? Actually I didn't quite say that. I think lambdas are a very good idea - and in many ways they would certainly clean up at least the mechanics of defining and registering test cases and sections.

Before lambdas C++ had only one place you could write a block of imperative code: in a function (or method). That means that, in Catch, test cases are really just functions - which must have a function signature - including a name (which we hide - because in Catch the test name is a string). Those functions must be captured somehow. This is done by passing a pointer to the function to the constructor of a small class - who's sole purposes is to forward the function pointer onto a global registry. Later, when the tests are being run, the registry is iterated and the function pointers invoked.

So a test case like this:

    TEST_CASE( "test name", "[tags]" )
    {
        /* ... */
    }

...written out in full (after macro expansion) looks something like:

    static void generatedFunctionName();
    namespace{ ::Catch::AutoReg generatedNameAutoRegistrar
        (   &generatedFunctionName, 
       	    ::Catch::SourceLineInfo( __FILE__, static_cast<std::size_t>( __LINE__ ) ), 
            ::Catch::NameAndDesc( "test name", "[tags]") ); 
    }
    static void generatedFunctionName()
    {
        /* .... */
    }

(generatedFunctionName is generated by yet another macro, which combines root with the current line number. Because the function is declared static the identifier is only visible in the current translation unit (cpp file), so this should be unique enough)

So there's a lot of boilerplate here - you wouldn't want to write this all by hand every time you start a new test case!

With lambdas, though, blocks of code are now first class entities, and you can introduce them anonymously. So you could write them like:

    Catch11::TestCase( "test name", "[tags]", []() 
    {
        /* ... */
    } );

This is clearly far better than the expanded macro. But it's still noisier than the version that uses the macro. Most of the C++11/14 test frameworks I've looked at tend to group tests together at a higher level. The individual tests are more like Catch's sections - but the pattern is still the same - you get noise from the lambda syntax in the form of the []() or [&]() to introduce the lambda and an extra ); at the end.

Is that really worth worrying about?

Personally I find it's enough extra noise that I think I'd prefer to continue to use a macro - even if it used lambdas under the hood. But it's also small enough that I can certainly see the case for going macro free here.

Assert yourself

But that's just test cases (and sections). Assertions have traditionally been written using macros too. In this case the main reasons are twofold:

  1. It allows the expression evaluation to be wrapped in an exception handler.
  2. It allows us the capture the file and line number to report on.

(1) can arguably be handled in whatever is holding the current lambda (e.g. it or describe in Bandit, suite, subsuite or expect in Mettle). If these blocks are small enough we should get sufficient locality of exception handling - but it's not as tight as the per-expression handling with the macro approach.

(2) simply cannot be done without involving the preprocessor in some way (whether it's to pass __FILE__ and __LINE__ manually, or to encapsulate that with a macro). How much does that matter? Again it's a matter of taste but you get several benefits from having that information. Whether you use it to manually locate the failing assertion or if you're running the reporter in an IDE window that automatically allows you to double-click the failure message to take you to the line - it's really useful to be able to go straight to it. Do you want to give that up in order to go macro free? Perhaps. Perhaps not.

Interestingly lest still uses a macro for assertions

Weighing up

So we've seen that a truly modern C++ test framework, using lambdas in particular, can allow you to write tests without the use of macros - but at a cost!

So the other side of the equation must be: what benefit do you get from eschewing the macros?

Personally I've always striven to minimise or eliminate the use of macros in C++. In the early days that was mostly about using const, inline and templates. Now lambdas allow us to address some of the remaining cases and I'm all for that.

But I also tend to associate a much higher "cost" to macro usage when it generates imperative code. This is code that you're likely to find yourself needing to step through in a debugger at runtime - and macros really obfuscate this process. When I use macros it tends to be in declarative code. Code that generates purely declarative statements, or effectively declarative statements (such as the test case function registration code). It tends to always generate the exact same machinery - so should not be sensitive to its inputs in ways that will require debugging.

How do Catch's macros play out in that regard? Well the test case registration macros get a pass. Sections are a grey area - they are on the path of code that needs to be stepped over - and, worse, hide a conditional (a section is really just an if statement on a global variable!). So score a few points down there. Assertions are also very much runtime executable - and are frequently on the debugging path! In fact stepping into expressions being asserted on in Catch tests can be quite a pain as you end up stepping into some of the "hidden" calls before you get to the expression you supplied (in Visual Studio, at least, this can be mitigated by excluding the Catch namespace using the StepOver registry key).

Now, interestingly, the use of macros for the assertions was never really about C++03 vs C++11. It was about capturing extra information (file/ line) and wrapping in a try-catch. So if you're willing to make that trade-off there's no reason you can't have non-macro assertions even in C++03!

Back to the future

One of my longer arcs of development on Catch (that I edge towards on each refactoring) is to decouple the assertion mechanism from the guts of the test runner. You should be able to provide your own assertions that work with Catch. Many other test frameworks work this way and it allows them to be much more flexible. In particular it will allow me to decouple the matcher framework (and maybe allow third-party matchers to work with Catch).

Of course this would also allow macro-less assertions to be used (as it happens the assertions in bandit and mettle are both matcher-like already).

So, while I think Catch is committed to supporting C++03 for some time yet, that doesn't mean there is no scope for modernising it and keeping it relevant. And, modern or not, I still believe it is the simplest C++ test framework to get up and running with, and the least noisy to work with.

Add new lines to end of files with missing line ends

Tim Pizey from Tim Pizey

A Sonar rule: Files should contain an empty new line at the end convention
Some tools such as Git work better when files end with an empty line.

To add a new line to all files without one place the following in a file called newlines


FILES="$@"
for f in $FILES
do
c=tail -c 1 $f
if [ "$c" != "" ];
then
echo "$f No new line"
echo "" >> $f
continue
fi
done

Then invoke:

$ chmod +x newlines
$ find * -name *.java |xargs ./newlines

Right now, it’s a good idea to check for FreeBSD bash port updates daily

The Lone C++ Coder's Blog from The Lone C++ Coder&#039;s Blog

If you haven’t heard about the bash “shellshock” bug yet, it may be time to peek out from underneath the rock you’ve been under ;). While bash isn’t installed as standard on FreeBSD, there’s a very good chance that someone either installed it because it’s their preferred shell or because one of the ports lists it as a dependency. Either way, now would be a really good time to check if your machine has bash installed if you haven’t done so already.

Some Boost.Test notes

The Lone C++ Coder's Blog from The Lone C++ Coder&#039;s Blog

These are just a couple of notes for some neat tips and tricks I’ve discovered over the years when using Boost.Test. They may not be all that useful to everybody else but they’re the ones I tend to forget about and then end up rediscovering. I’m using most of these with recent versions of Boost and these were tested with 1.54. You can nest test suites. I don’t use this feature and was surprised to discover it, but it makes a lot of sense if you’re dealing with large test suites that can be easily broken down into smaller logical chunks.

Writing: Testing Times

Pete Goodliffe from Pete Goodliffe

My latest Becoming a Better Programmer column is published in the September issue of C Vu magazine (26.4). It called Testing Times and surveys the world of developer testing, covering the what, why, and how of programmer-driven testing. We look at feedback loops, TDD, unit testing, integration testing, system testing and more.

C Vu is a magazine produced by the ACCU - an excellent organisation for programmers. It has a great community, great publications, and an awesome conference. Check it out.

Meanwhile, my book: Becoming a Better Programmer, is nearing print. It's gone through tech review, copy edit, and layout is almost complete. You can still access the early release at http://shop.oreilly.com/product/0636920033929.do.