Decorated Functions in C++… Almost

2013-04-28 21:56

Many languages now include the concept of annotations that can be applied to definitions of functions, classes, or even variables and fields. The term ‘annotation’ comes from Java, while other languages use different names: attributes (C#), decorators (Python), tags (Go), etc.
Besides naming disparities, those features also tend to differ in terms of offered power and flexibility. The Python ones, for example, allow for almost arbitrary transformations, while Go tags are constrained to struct fields and can only consist of text labels. The archetypal annotations from Java lie somewhere in between: they are mostly for storing metadata, but they can also be (pre)processed during compilation or runtime.

Now, what about C++? We know the language has a long history of lacking several critical features (*cough* delegates *cough*), but the recent advent of C++11 fixed quite a few of them all at once.
And at first sight, the lack of annotation support seems to be among them. New standard introduces something called attributes, which appears to fall in into the same conceptual bucket:

  1. [[dllexport]] void SomeFunction(int x);

That’s misleading, though. Attributes are nothing else than unified syntax for compiler extensions. Until C++11, the job of attributes were done by custom keywords, such as __attribute__ (GCC) or __declspec (Visual C++). Now they should be replaced by the new [[squareBracket]] syntax above.
So there is nothing really new about those attributes. At best, you could compare them to W3C deciding on common syntax for border-radius that forces both -webkit-border-radius and -moz-border-radius to adapt. Most importantly, there is no standard way to define your custom attributes and introspect them later.

That’s a shame. So I thought I could try to fix that, because the case didn’t look completely lost. In fact, there is a precedent for a mainstream language where some people implemented something-kinda-almost-like annotations. That language is JavaScript, where annotations can be realized as functions arranged into a pipeline. Here’s an example from Express framework:

  1. app.get('/home', [loginRequired, cached({minutes:30})], function(req, res){
  2.     res.render('home');
  3. });

Both loginRequired and cached(...) are functions, tied together by app.get with the actual request handler at the end. They “decorate” that handler, wrapping it inside a code which offers additional functionality.

But that’s JavaScript, with its dynamic typing and callback bonanza. Can we even try to translate the above code into C++?…
Well yes, we actually can! Two new features from C++11 allow us to attempt this: lambda functions and initializer lists. With those two – and a healthy dose of functional programming – we may achieve at least something comparable.

Minimum viable product

Let’s start by simplifying the task a bit. We eventually want to “decorate” arbitrary functions, but for now it’ll be easier if we settle for a specific kind. Let it be functions mapping integers to integers:

  1. #include <functional>
  2. using namespace std;
  3.  
  4. typedef function<int (int)> IntIntFunc;

with the all-too-well known example of Fibonacci series:

  1. int fib(int x) {
  2.     int a = 0, b = 1;
  3.     for (; x; --x) {
  4.         swap(a, b);
  5.         b = a + b;
  6.     }
  7.     return b;
  8. }

Suppose we want to apply the memoization technique to it, which is essentially a way of caching function results. Normally, we would add the relevant code directly into function’s body, but that’s just clutter that would obscure its main algorithm. So instead, we will implement a “decorator” function that provides memoization-as-a-feature:

  1. #include <vector>
  2.  
  3. IntIntFunc memoize(IntIntFunc fn) {
  4.     const int UNUSED = -1; // naive, but it's just an example :)
  5.     vector<int>& memory = *new vector<int>(1, UNUSED);
  6.     return [fn, &memory] (int x) -> int {
  7.         if (x >= (int)memory.size()) {
  8.             memory.resize(x + 1, UNUSED);
  9.         }
  10.         int val = memory[x];
  11.         if (val == UNUSED) {
  12.             memory[x] = val = fn(x);
  13.         }
  14.         return val;
  15.     };
  16. }
  17.  
  18. auto memoizedFib = memoize(fib);

It’s pretty meta: it takes a function as an argument and returns another function as a result. That result has simple caching code backed in, and only calls the original procedure if memory doesn’t contain a value for its argument yet.

Sugaring

By writing this (relatively) simple code, we now have a true function decorator. However, we don’t have any good, more declarative syntax of applying such decorators – especially when there is more than one:

  1. auto beefedFib = memoize(optimize(requireThursday(add42(fib))));

To get the equivalent of app.get from the previous JavaScript example, we need a call that takes a list of decorators and applies them one by one to given function. Such a call could, for example, look like this:

  1. auto beefedFib = decor(
  2.     {memoize, optimize, requireThursday, add42},
  3.     fib);

The curly braces denote initializer list which is a pretty awesome feature that finally allows to specify whole collections inline, also within function arguments. They are represented as the template type std::initializer_list, functionally equivalent to a singly-linked list of elements.

With this, the implementation of decor is surprisingly simple:

  1. #include <list>
  2.  
  3. typedef function<IntIntFunc (IntIntFunc)> IntIntDecorator;
  4.  
  5. IntIntFunc decor(
  6.     initializer_list<IntIntDecorator> decorators,
  7.     IntIntFunc func)
  8. {
  9.     list<IntIntDecorator> decors(decorators);
  10.     decors.reverse();
  11.    
  12.     for (auto d : decors) {
  13.         func = d(func);
  14.     }
  15.     return func;
  16. }

Having this, we can indeed apply decorators inline with function definition:

  1. auto fib = decor({memoize}, [] (int x) -> int {
  2.     int a = 0, b = 1;
  3.     for (; x; --x) {
  4.         swap(a, b);
  5.         b = a + b;
  6.     }
  7.     return b;
  8. });

Success!

Generalize this

So that works for ints. What about making the solution universal, so that we can use decor for arbitrary functions?…

Now that’s actually tricky, as it requires opening this can of worms, full of incidental and poorly conceived functionality, commonly known as “C++ templates”. Their recent major enhancement is dubbed variadic templates; it allows for indeterminate number of template<> parameters, similar to unspecified number of arguments in functions such as printf.
I mention them because they are actually crucial for generalizing decor; that’s how you can hope to support functions with multiple arguments while maintaining portability and type safety.

Unfortunately, the straightforward approach doesn’t really work. There is a subtle issue with implicit conversion of lambdas to std::function which foils the compiler’s attempt to perform template arguments’ deduction.

Of course, this doesn’t mean there is no way to make this work. It’s probably just my template-fu being insufficient here :) So if you know better, don’t hesitate to suggest a better approach in the comments.



2 comments for post “Decorated Functions in C++… Almost”.
  1. KrzaQ:
    April 29th, 2013 o 9:16

    I don’t think you can deduce a functor’s parameter list. On the other hand, if you’re willing to wait for C++14 you could make use of return type deduction and return lambdas instead of std::function. In fact, it should be easier for the compiler to optimize too, because it doesn’t have to account for std::function’s type erasure.

  2. Kos:
    April 29th, 2013 o 9:36

    Allowing a decorator to change the function type looks like fun :-).

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.