Simple template programming

C++ template meta-programming sounds harder than it is.

So long as you can fight through some horrific syntax and understand recursive functions, you can write any algorithm you like and have it run at compile time in your C++ programs.

Slides: Simple Template Programming

Andrei Alexandrescu’s amazing book on using template meta-programming for really useful, cool stuff is: Modern C++ Design.

Goodness in programming languages, part 3 – not doing the same thing more than once

Posts in this series: Syntax, Deployment, Metaprogramming, Ownership

I’m going to use a word here – don’t stop reading: Metaprogramming. Does the language provide what you need to avoid repeating yourself?

Repeating boilerplate code, algorithms and most importantly ideas, slows you down, makes maintenance difficult, and allows all kinds of mistakes to creep in. If a language provides the ability to abstract, name and re-use all the different types of structure it contains, you can avoid harmful repetition.

Here are some things I like:

  • Python, JavaScript and Scheme’s ability to treat functions like any other object. A massive step towards sharing code is being allowed to pass around something that can be called without worrying about what it is.
  • Scheme’s ability to define an algorithm independently of types. In Scheme, there is never a need to write another version of the same function because it deals with different types of thing.
  • Python’s ability to read and modify classes just like any other object. Want a class just like your current one, except it logs every method call? Write a function that copies and modifies the class definition.
  • Scheme’s ability write code about code. In Scheme, code is just some nested lists. It’s trivial to build and modify code without stepping out of the language.
  • C++’s ability to write code that runs at compile time. If you can stand the syntax and (lack of) debugging, C++ template metaprogramming allows you to build C++ code at compile time without stepping out of the compiler environment.
  • Scheme and C’s macro systems. Both Scheme and C (and C++) allow you to write macros that build commonly-repeated code. Scheme’s syntax for this is much easier to work with.

Until you’ve experienced the freedom of totally generic code in a language like Scheme it’s hard to explain why the “Generics” features of some languages are so lacking. Of course, static typed languages work under different constraints. Would it be possible to write a language with very strong generic programming features, but which still allows static typing and compiling to native, non-generic code? I think so.

NNDB 0.1

I’ve managed to get NNDB, my C++ data storage library which is almost, but not entirely unlike SQL, into a fit state for a release.

You can create tables, set indices on columns, insert data, retrieve data using something like a SELECT, filter it using something like WHERE (which uses indices where available), and order it using something like an ORDER BY.

So far it has been a fantastic way to get my hands dirty with some Template metaprogramming, and some C++ as it should be*, but the reason why I started this was to help me think about how databases work, so I’m really looking forward to getting into how to implement JOINs. At the moment I have only very vague ideas.

NNDB is based heavily on the STL (part of C++’s standard library), BOOST (a playground for things that might one day be in C++’s standard library, and hang-out for some of the cleverest people alive), and Loki (the continuation of Andrei Alexandrescu’s Template metaprogramming (but used for good, not evil?) library written for and explained in Modern C++ Design. This book ranks in the top 5 most exciting books I have read). I continue to be more impressed by all three the more I learn.

I have even been having discussions with the Loki devs about some code I needed for NNDB that I think might be helpful for other people using Loki. It’s called ForEachType and it allows you to loop (at runtime) through all the types in a Typelist and do something for each one.

The project is already working in terms of helping me think about databases. For example, I really hadn’t thought before about how expensive ORDER BY is. To implement it I needed to create a temporary std::map covering the entire result set – in a real database this obviously requires reading every single row before we can even begin to return any results. The way to avoid this is to have an index. Which reminds me: the next thing I need to do is make ORDER BY able to use indices (at the moment it’s only WHEREs that take advantage of them).

So next on my list are:

  • ORDER By uses indices
  • Non-unique indices (presumably implemented with a std::multimap)
  • Joins

I am still very excited so you may see more releases over the next few months.

[* NNDB so far contains zero (0) calls to new and zero (0) calls to delete. Obviously the code it uses (e.g. std::vector) calls them, but that code manages all the memory for me, and most of it uses custom allocators to make it very fast. I have no idea how fast NNDB is, but maybe it could be quite fast. I am pretty confident it doesn’t contain any memory errors. Famous last words…]

NNDB’s Not a Database

My latest project is called NNDB.

I’ve worked with databases for quite a long time now, and for a while I’ve been thinking about how they work under the hood. I know very little about it, but I thought I could learn a bit by trying to implement something similar myself.

I’m interested in how queries work against joined tables, how to implement indices and so on.

I’ve also been feeling that I want to do some C++ as an open source project. I do it all day at work, and for some problems it feels like the right tool for the job.

NNDB is sort-of like an in-memory database, but it works with C++ types for its columns, instead of a fixed set like varchar, int etc. You can put your own value-typed classes in the columns, and all values are type-checked at compile time.

It’s always struck me as strange that with a traditional code+SQL setup you have to keep your SQL in sync with your code manually. Of course, there are lots of trendy Object-Relational-Mapping thingies that solve that problem, but I felt it could be approached from another direction: instead of generating code to match your data, or generating SQL to match your code, why not specify your data structure in code?

In NNDB you define a table something like this:

typedef nndb::Values< unsigned long, std::string, std::string, MyDate >

class PersonTable : public nndb::Table
    enum Columns

Actually, defining your own class is unnecessary, but it’s nice to have an enum to name your columns, and making a class gives you a nice place to put it.

To insert a row you do something like this:

PersonTable person_table;
person_table.Insert( PersonValues( 0,
    "Andy", "Balaam", MyDate( 12000000 ) ) );

You can do simple queries with WHERE and ORDER BY clauses, and I’m working on indexes.

After that will come JOINs, and anything else that takes my fancy.

I don’t anticipate NNDB being useful to anyone – it’s really for me to understand why things are as they are in the world of databases. However, you never know – it may turn out to be a fast and convenient way to store data in the C++ world. I think some of the applications that use databases don’t really need the kind of concurrent multi-user network-accessible features they have, but really just want to search, join and store reliably, and NNDB might one day grow into something that can find a niche.

To explore more, check out the complete example.