Let's write some loops. Because we can.
Let's start simple. We'll define a family of REPEAT() macros. Those'll look like this:
#define REPEAT(x) { x; }
#define REPEAT2(x) { x; x; }
#define REPEAT3(x) { x; x; x; }
#define REPEAT4(x) { x; x; x; x; }
#define REPEAT5(x) { x; x; x; x; x; }
Then, we can chain these together:
#define REPEAT10(x) { REPEAT5(x); REPEAT5(x); }
This can get out of hand quickly:
#define REPEAT1000(x) { REPEAT10(REPEAT10(REPEAT10(x))); }
Now, if we write an innocuous-looking statement like
REPEAT1000(printf("Hello, world!\n"));
The compiler will, without complaint, emit the functional equivalent of
for (int i = 0; i < 1000; i++)
printf("Hello, world!\n");
unrolled.
But this isn't complicated enough. We must go deeper.
We can use recursive inclusion to emit the functional equivalent of the above. The basic plan is, we include a file from within that file, each time defining a loop counter to a different value. Here's the first attempt, in a file thisfile.h:
#ifndef MACRO
#define MACRO printf("Hello, world!");
#endif
#ifndef I
#define I 0
#endif
#if I == 0
MACRO
#undef I
#define I 1
#include "thisfile.h"
#endif
#if I == 1
MACRO
#undef I
#define I 2
#include "thisfile.h"
#endif
#if I == 2
MACRO
#undef I
#define I 3
#include "thisfile.h"
#endif
Ad nauseam. We can put brakes on this kind of iteration by testing I against another preprocessor constant, say, USER_CONSTANT, and writing our loops like this:
#if I == 1
MACRO
#if I != USER_CONSTANT
#undef I
#define I 2
#include "thisfile.h"
#endif
#endif
We can use it like this:
int main()
{
#define USER_CONSTANT 3
#include "thisfile.h"
}
There are two problems with this - firstly, we have to manually write out every stage in the loop (which can be circumvented by even more clever macros or scripts), and, secondly, we soon hit a wall with the compiler - the compiler will only go to a depth of 200 includes or so before it craps out. So, let's abandon this technique in favor of something else.
Here's where it gets really fun.
Let's write a recursive macro using some techniques pioneered by a very intelligent man known as Pfultz2 on Github.
Before we get into recursion, there's something important to understand about the way macros are expanded. When a macro is expanded, a disabling context is created, in which the macro being expanded is tagged. Any macros tagged this way can't be expanded this expansion cycle. That's why we can't write recursive macros - if we wrote something like this
#define FACTORIAL(n) ((n) == 1? 1 : FACTORIAL((n)-1))
int x = FACTORIAL(10);
We'd get an error - FACTORIAL is the tagged token in this disabling context. So, we'll have to hack around it.
But, before we go deeper, we have to get some background on control structures in the C preprocessor.
First, we need a macro to splice two names together. This is trivial:
#define CAT(x, ...) CAT_(x, __VA_ARGS__)
#define CAT_(x, ...) x ## __VA_ARGS__
Straightforward so far, right?
Now, we can implement high-level functionality by expanding macros to other macros and forcing other scans. We can do this by writing an eval macro:
#define EVAL(...) __VA_ARGS__
We need to force another scan because otherwise the compiler will say, "Well, we've expanded this macro. I guess we're done here."
And then implementing something trivial. For example, let's implement a COMPLEMENT macro. If a one is passed, it'll evaluate to 0. If a 0 is passed, it'll evaluate to 1.
#define COMPLEMENT(x) EVAL(CAT_(COMPLEMENT_, x))
#define COMPLEMENT_0 1
#define COMPLEMENT_1 0
Now, if we write
COMPLEMENT(1)
It will expand like so:
COMPLEMENT(1) -> EVAL(CAT_(COMPLEMENT_, 1)) ->
EVAL(COMPLEMENT_1) -> COMPLEMENT_1 -> 0
Now, let's implement an if-statement in the preprocessor. First, we'll need a facility to cast predicates to a boolean type we can use. We can do this with the classic NOT-NOT operator, written in the preprocessor.
Pfultz2 has already implemented for us a NOT operator, using a macro called CHECK. It works like this:
First, we define a macro, CHECK.
#define CHECK_N(a, b, ...) b
#define CHECK(...) CHECK_N(__VA_ARGS__, 0)
Then, a NOT operator:
#define NOT(x) CHECK(CAT_(NOT_, x))
#define NOT_0 _foo_, 1
This works, because for CHECK() to expand to anything but 0, it needs two arguments. If anything is passed to NOT() that will not expand to NOT_0 by CAT_()ing the argument with NOT_(), only the result will be passed - only one argument. This means the default second argument, 0, will be passed. Because neither _foo_ nor anything else passed in the first argument will expand, we get no syntax errors.
Neat-o, now we can write a cast to bool:
#define BOOL(x) COMPL(NOT(x))
And now we have something which can expand arbitrary values to 0 or 1.
We're getting close here to an IF statement. The last thing we need is a block. What we need to do is expand a macro to another macro which takes arguments - then we can put the body in the parens. This is trivial, considering what we know already:
#define IF_(c) CAT_(IF_, c)
#define IF_0(t, ...) __VA_ARGS__
#define IF_1(t, ...) t
#define IF(c) IF_(BOOL(c))
And, blam-o, now we have an IF statement. We write IF statements like this:
EVAL(IF(1) ( true(); , false(); ))
So, what's the point of all this?
Now, we can stop a macro from expanding by forcing it to expand to something that won't expand further.
We're almost to recursive macros. We need one last thing - a way of getting around the disabling context.
As it turns out, that's rather trivial. What we need to do is provide a way of accessing the macro from within the disabling context. We can use this by a technique called deferred evaluation.
The technique is simple. First, define a macro, DEFER(), which causes a macro to not be expanded until later.
#define EMPTY()
#define DEFER(x) x EMPTY()
Then, we write a macro to force another scan, so that whatever is deferred can be expanded later:
#define EXPAND(...) __VA_ARGS__
And now we have a system for controlling how macros expand.
We run into one limitation - we can't actually do any arithmetic without complex workarounds, but we can do much simpler stuff. Consider this WHILE macro by Pfultz2:
#define WHILE(pred, op, ...) \
IF (pred(__VA_ARGS__)) ( \
DEFER(WHILE_INDIRECT)() ( \
pred, op, op(__VA_ARGS__) \
),\
__VA_ARGS__ \
)
#define WHILE_INDIRECT WHILE
This macro works by recursively invoking itself whenever pred(__VA_ARGS__) results in a positive integer.
We can invoke this by writing helper macros.
First, the predicate:
#define PREDICATE(x) CAT_(PREDICATE_, x)
#define PREDICATE_3 2
#define PREDICATE_2 1
#define PREDICATE_1 0
Then, a better EVAL macro:
#define EVAL(x) EVAL1(EVAL1(EVAL1(EVAL1(EVAL1(x)))))
#define EVAL1(x) x
Then, the operation:
#define OP(x) printf(x)
Now, we invoke the WHILE macro:
EVAL(WHILE(PREDICATE(3), OP, "Hello, world!\n")))
Which will evaluate to an expression which prints "Hello, world!" 3 times.
Recursive macros are a bit harder to write than recursive includes, but they sure are fun.
Now, let's get the takeaway - these are fun to think about, but not really useful.
But they can be.
Let's examine a real-world application.
Say you wanted to do some loop unrolling for fetching nodes in a linked list. Say you knew at compile-time what node you wanted.
You could write a set of macros as follows, assuming the REPEATx macros from above have been implemented:
#define EVAL(...) __VA_ARGS__
#define CAT(a,b) a ## b
#define LIST_GET_NTH_NODE(list, parser, node) { parser = list; EVAL(CAT(REPEAT, node)(parser = parser->next))}
Where list is the first node in the list, parser is a pointer to a node, and node is a constant number referring to the position of the node in the list.
And just like that, we have a real-world application.
No comments:
Post a Comment