mark++

A couple of weeks ago I was bemoaning the lack of a C/C++ analog to Perl’s require statement. Today, I realized we’ve already solved this problem. Just google for __GNUC__ or _MSC_VER to see what I mean.

Let me back up for a second. Do you have copies of the C and C++ language specifications? Which versions? More to the point, I’d bet $10 you don’t really understand them (I sure as heck don’t).

But it’s OK — it doesn’t matter. Despite the noble efforts of our beloved standards body, we are only truly beholden to the de facto standard that is our compiler and library implementation.

Simply moving from the ACME C/C++ 8.0 to ACME C/C++ 8.1 may well require so many source changes as to be considered porting. And don’t feel safe just because you compiled and linked! We’ve got to test the whole shebang all over again. The newsgroups are rife with tiny snippets of code which are enough to invoke the specter of “undefined behavior.” Not to mention the fact that compilers have bugs too. Yes, even your code could be the next addition to ACME’s compiler QA suite!

So why fret over backwards compatibility? People with existing source code have existing compilers and libraries. They can just continue using them. Case in point:

   mark@turing ~ $ file `which gcc`
   /usr/bin/gcc: symbolic link to `gcc-4.0'
   mark@turing ~ $ ls /usr/bin/gcc-*
   /usr/bin/gcc-2.95
   /usr/bin/gcc-3.2
   /usr/bin/gcc-3.3
   /usr/bin/gcc-4.0

Maybe we can just forget this whole versioning thing and get on with improving C++.

Here’s my attempt at writing a higher-order-function in C++ which allows one to memoize a function. It’s not complete. It doesn’t work for functions with signatures much more complicated than int fib(int).

Perhaps most disappointing is that there appears to be no way to generically memoize the recursive calls, the way Memoize.pm can.

#include <boost/function.hpp>
#include <map>
#include <iostream>

using namespace std;

template< typename T >
struct memoized_function;

template< typename R, typename A >
class memoized_function : public boost::function
{
   private:
   mutable std::map m;
   typedef boost::function super;

   public:
   template< typename T >
   memoized_function( const T& x ) : super(x) {}

   R operator()(A& a) const
   {
      if( m.find(a) != m.end() )
         return m[a];

      m[a] = super::operator()(a);
      return m[a];
   }
};

template< typename T >
memoized_function memoize( const T& f )
{
   return memoized_function(f);
}

int fib( int n )
{
   cout << "called fib(" << n << ")\\n";

   if( n < 2 )
      return n;

   return fib(n-1) + fib(n-2);
}

int main()
{
   cout << fib(5) << endl << endl;

   typedef boost::function func;
   func fastfib = memoize( fib );
   cout << fastfib(5) << endl;
   cout << fastfib(5) << endl;  // just a look up
}