Functional Programming with C++ Templates

About 10 years ago I bought C++ Template Metaprogramming by David Abrahams and Aleksey Gurtovoy. I read the book and even dabbled at template metaprogramming in the never-finished version 2.0 of KScope. My career, however, soon took me very far away from modern C++, and I have not had a chance to get fully immersed in the techniques described in the book.

A few weeks ago I decided to give the book another chance, and this time try to understand the concepts rather than the syntax of the MPL library. Things went south fairly quickly.

C++ template metaprogramming as implemented by MPL is essentially a new functional language built on top of C++ templates. The data manipulated by the language consists of types (int, long, double, structs and classes, etc.) and the manipulation is done by functions that take and return types. These functions (or metafunctions as they are referred to in the book), use template parameters as arguments and type definitions to return a result. For example, the following function takes a type T and returns a type that is a pointer to T:

struct add_pointer
    typedef T* type;

So far so good, as it is easy to draw parallels from the description of this language to other functional languages, such as Scheme. But this warm, fuzzy feeling of familiarity doesn’t last long.

One of the most important characteristics of functional languages is the ability to write higher-order functions, which are functions that take and/or return other functions. Chapter 3 in the book introduces higher-order functions using an example: the function twice, which takes a function and an argument, and returns the application of the function twice on that argument, i.e.:

twice(f, x) = f(f(x))

The problem is that with the book’s definition of a metafunction it is impossible to write one that takes another metafunction as an argument:

  1. Metafunctions are templates that take types as arguments
  2. A template is not a type

The rest of the chapter is devoted to techniques that turn metafunctions into types (metafunction classes, placeholder expressions) so that they can be passed around to and from other metafunctions.

It took me a while to understand what it is that bothers me with the treatment of this fundamental topic of functional languages by the book. I went back to my 20-year-old copy of Structure and Interpretation of Computer Programs by Abelson and Sussman (x2) and reread the introduction to higher-order functions. Let us consider how twice would have been implemented in Scheme. First, a Scheme function is really a lambda expression with a name (which, in my opinion, is better than to say that a lambda expression is an unnamed function):

(define (sum a b) (+ a b))

is really syntactic sugar (SIoCP’s favourite expression) for

(define sum (lambda (a b) (+ a b)))

Since lambda expressions in Scheme can be freely passed around as arguments to other lambda expressions, and be returned by other lambda expressions, we have a language that naturally implements higher-order functions. We can make twice a function that takes a function and returns another function which will apply the first one twice to its argument (note that we are returning a new function, not the application of a function to an argument):

(define (twice f) (lambda (x) (f (f x))))

And since twice is really just a name for a lambda expression, it can be passed around as a parameter to other functions or be returned by them.

How can we implement the same concept in C++?

First, let us change the way a metafunction is implemented from a template to a structure with a member template called lambda, which, in turn, defines a type called result (this is similar to how the book defines a metafunction class):

struct add_pointer
    template<typename A>
    struct lambda
        typedef A* result;

Invoking the function consists of instantiating the result type, e.g.:

int a = 5;
add_pointer::lambda<int>::result p = &a;
std::cout << *p << std::endl;

With the new definition, we can implement twice as a function that takes a function and returns a function:

// The function's name.
struct twice
    // The lambda expression that takes a function as an argument.
    template<typename F>
    struct lambda
        // The result, which is itself a type.
        struct result
            // The result is a lambda expression that, when invoked,
            // applies the function F twice to its argument.
            template<typename A>
            struct lambda
                typedef typename F::template lambda<A>::result once;
                typedef typename F::template lambda<once>::result result;

We can then name the new function that twice returns when invoked with add_pointer as its argument:

typedef twice::lambda<add_pointer>::result add_pointer_pointer;

and invoke the new function:

add_pointer_pointer::lambda<int>::result pp = &p;
std::cout << **pp << std::endl;

My approach is considerably more verbose than the one taken by MPL, and it is quite possible that it is severely limited in some way. Nevertheless, it seems to me that it is more in-line with traditional functional languages and as such easier to follow if you are familiar with functional programming.

Desclaimer: The above should in no way be read as criticism of either the book, its authors or the MPL. My extremely limited experience with template metaprogramming prevents me from passing judgement. The article is about my struggle with understanding the subject and the way I found to elucidate the important topic of higher-order functions using C++ templates.


A Quick Update

It has been several months since I published the blog post on the QNX 7 desktop. While I haven’t been able to dedicate much time to this project, there have been some notable updates that I would like to share. The desktop code itself has been enhanced and now supports window resizing and window switching with ALT+TAB. On the application-support front, the desktop sports a modern browser, based on Google’s Blink engine.


Most importantly, though, is that I got Emacs to work (though only in terminal mode). My initial attempt at porting Emacs failed when the build generated a binary that filled the entire hard drive. This turned out to be due to Emacs’s use of sbrk(), which QNX has not supported for many years, but which is still implemented by the system as a stub that returns -1. The Emacs code took -1 to mean the 64-bit address 0xffffffffffffffff, and tried to write a binary of a size approaching 2^64 bytes. With help from the Emacs maintainers (who have been very supportive) I switched to using the “hybrid-malloc” option, used by the Cygwin port, that doesn’t rely on sbrk().

The Emacs port also requires an implementation of openat(), fstatat() and fdopendir(). These have been on our to-do list for a long time. The implementation of these functions in a micro-kernel architecture is not trivial, as there is no one service that owns a directory, and in fact the same directory can contain nodes from multiple services (unioned file systems, pipe). I realized, however, that the at() functions can be treated as a generalization of chdir(), and proceeded to write an implementation along these lines. Emacs is now fully functional.


Building a BlackBerry QNX 7 Desktop

BlackBerry QNX officially released version 7 of its Software Development Platform (SDP) last month. This release is the first to support 64-bit architectures, including x86-64 and aarch64. It also brings with it new features and over two years stability fixes.

As is the case for any release of an operating system that is not backwards-compatible with an earlier version, we were faced with the problem of a lack of content for SDP 7. Yes, the code has been thoroughly tested in the lab on a variety of boards and yes, Alpha and Beta versions of the release have been used by our partners to bring up new versions of their systems. Nevertheless, it was felt that a crucial part was missing in the test cycle, that of eating one’s own dog food.

BlackBerry QNX is an embedded operating system targeting applications in the automotive, general embedded, and medical markets. However, it is not your garden-variety embedded OS: QNX is a full-blown, UNIX-like, POSIX-compliant operating system with all of the features you would expect of a desktop or sever-class OS. Compatibility with other systems means that, at least in theory, porting various open source projects to SDP 7 should be a relatively easy task. And so, while there is no official support in this release for a desktop environment, there is nothing precluding someone from building such a system. With that in mind, I set myself the task of building a BlackBerry QNX 7 desktop.

The hardware consists of an ASRock IMB-151 mini ITX board, with a 4-core Intel Celeron processor. We used this board in the early development stage of the x86-64 architecture, and so had a few lying around. I bought a nice small case to house it and, despite it being advertised as a fanless board, attached a big fan to the top of the case, just to be on the safe side. Not a very clean job but hey, I’m a software developer.


It is interesting to note that in order to measure the effect of the fan on the board I had to read a machine-specific register, which can only be done in Ring 0. It seems like an odd architectural decision to require the highest privilege level just to tell how hot is the CPU.

The standard board-support package for x86-64 works well on this board, so installing SDP 7 on it was straight-forward. Installation involves booting the board from a USB stick which was flashed with an Image File System (IFS) containing the necessary tools (shell, PCI server, disk driver, file system, network stack, and daemons) to create a QNX6 file system on the board’s flash drive and copy over the necessary binaries. Once done, the IFS itself is copied to the flash drive and the USB stick is no longer required.

Working Hard

As I use computers primarily for software development, my first step was to create a development environment. Typically, development for embedded systems is done on a different machine (the host) than the one on which the embedded software runs (the target). There are two main reasons for host-side development (also known as cross-compilation):

  1. Embedded environments typically do not support self-hosted build tools
  2. The target hardware is often considerably less powerful than a modern desktop

As was mentioned earlier, BlackBerry QNX is not your typical embedded system, and our tools team provided me with the GNU tool chain (compiler, linker, debugger) built to run on an SDP 7 system. And while the target I chose is certainly not as fast as my T440s laptop, it is more than adequate for most compilation tasks. That said, some of the porting efforts described below were still done in a cross-compilation environment, as even software that is itself portable does not always use a portable build system.

Software development requires code to be written. The version of vi shipped with SDP 7 may be sufficient for editing /etc/resolv.conf, but it is a far cry from a modern editor. The first project I tackled was therefore Vim 7.4.

(Disclaimer: I do most of my development work on Emacs. However, Emacs requires Gtk+. Porting Gtk+ to SDP 7 is left as an exercise to the reader.)

Porting Vim proved to be a somewhat harder task than might have been expected. Self-hosted building was unsuccessful as the configuration script insisted on using GNU Grep, even though any Grep implementation should have been sufficient (note that this is not a requirement of Vim itself, only of the build). Cross-compiling Vim is not very well documented, and many of the configuration steps do not work in such an environment. Reading through the configuration script yielded the following, somewhat unwieldy, command line:

# vim_cv_memmove_handles_overlap=yes vim_cv_stat_ignores_slash=yes vim_cv_getcwd_broken=no vim_cv_toupper_broken=no vim_cv_terminfo=yes vim_cv_tty_group=world ./configure --build=x86_64-pc-linux-gnu --host x86_64-pc-nto-qnx7.0.0 --with-tlib=ncurses

(Given the amount of effort involved in cross-compiling Vim, it would have probably been easier to port GNU Grep and other build dependencies to SDP 7.)

Vim was now ready to be compiled. The only obstacle I ran into at this stage was a legacy QNX-specific function in the Vim code, which is no longer applicable and had to be removed. Other than that compilation went smoothly. I copied the binary and the supporting files to the target and now had a working, modern, vi clone.

The next project was Subversion, which is needed for OS development at QNX. Building SVN is not hard, but it does require a few other libraries, namely APR, APR Util and libserf. The latter uses Scons as its build system and, for some reason, insists on building with the ‘-std=c89’ compiler option, which I had to remove.

Tool chain, editor, source control. Ready for work.

Having Fun

Some of us get very excited at the sight of a C program being compiled and linked into an executable. The masses, however, need their entertainment.

If you search the web for open-source games, you will notice that many of them use the Simple DirectMedia Layer (SDL) library. Given that observation, I decided to try and port this library (version 2.0.5) next. Porting SDL, however, goes beyond building the code, as the library depends on OS-specific implementation of its API for graphics (2D and 3D), audio and input devices. The task proved much easier than I had anticipated, though. Most of SDL’s graphics functions correspond to native functions in Screen, the QNX compositing window manager. For audio, I found that SDL already had code for QNX, albeit with a crippling bug. Nevertheless, once spotted, the bug was very easy to fix. The SDL mixer, TTF and image libraries followed, but with the main library already ported these were easy to build.

Armed with a port of SDL 2 I went hunting for some games to try. I found a couple of clones of well-known old-time games that worked very well. Unfortunately, while the games themselves are open-sourced, the ones which they clone are not, so no screenshots for those.

This activity only took a couple of days. My kids had a blast bossing around certain plumbers who shall go unnamed.

A Qt Little Thing

SDP 7 comes with a port of Qt, version 5.6.2. In theory, it should be trivial to port Qt applications. The problem is that the QNX plugin for Qt is very embedded-oriented, designed for full-screen applications with either touch or keyboard input. I wrote a naive clipboard library (which in hindsight should have been written as a resource manager) to satisfy desktop applications. One major annoyance is the placement of drop-down menus. Qt treats all pop-up menus as top-level windows and uses absolute coordinates to position them on the screen. QNX Screen, however, does not allow non-privileged applications to position windows with absolute coordinates. This is not a problem for embedded applications, as these typically do not use traditional menu bars, but is quite a limitation for a desktop environment. I have yet to find a solution to this problem and would love to hear from any Qt experts out there.

Having Qt allowed me to port one of my favourite applications, SpeedCrunch. It was a simple matter of running ‘qmake’ followed by ‘make’. Next, I ported the QTermWidget library so that I could have terminal windows.

Putting It All Together

I now had an arsenal of useful (and less than useful) applications at my disposal, but still not a true desktop environment. Each application could only be launched separately, in full screen mode.

As mentioned earlier, SDP 7 does not target the desktop market. Nevertheless, it comes with the necessary building blocks to create a desktop manager, including a compositing window manager, USB and HID stacks for handling input devices, and libraries for drawing images and rendering fonts. (As a side note, using the PNG, font-config and freetype libraries directly rather than via a high-level toolkit was quite educating.)

The desktop manager does the following:

  1. Draws frames (title bars and borders) around windows
  2. Positions windows (x, y and z axes)
  3. Allows a window to be moved around by dragging its title bar
  4. Handles the title bar buttons (drawing alternative images when a button is clicked and taking the appropriate action for that window)

A few weekends later (sorry, kids) I had my desktop manager. It is written in C++, and currently uses less than 2500 lines of code (and over a thousand lines of comments – credit goes to my brother in law, Noam Dror, who taught me the importance of documenting code many years ago). The window decorations are less than stellar (damn it, Jim, I’m a kernel developer, not a UI designer!), but the whole thing looks quite reasonable. A launcher bar written in Qt and a background image of QNX’s home town complete the scene.


This activity has been a challenge, dealing with many different subsystems and code from a variety of sources. It has also been very satisfying – after years of kernel development, I had forgotten the thrill of writing code that does things you can actually see. Most importantly, it provided for a great way to follow the old maxim: “always eat your own dog food before you serve it to others”, canine or human.