The Power of CPP, part II.
Henry Baker
In my previous posting, I bemoaned the fact that the C preprocessor (CPP)
has been neutered by restricting the rewrite of a macro 'foo' to no longer
expand an occurrences of 'foo'. I suspect that this rule gelds C macros
so that they can no longer expand arbitrarily.
After studying the code in the 'Obfuscated C' contest, and 'zsmall.c' in
particular, it became clear that '#include' has no such restriction. Thus,
if we define every macro-like thingy in a separate file, there appears to
be no restriction on recursive #include's -- at least to the depth of the
#include stack, which ANSI C requires to be at least 8 deep. Metrowerks
C for the Mac appears to handle nested includes deeper than 8 deep, but I didn't
go to the trouble to find out exactly how deep it would go.
We can now program the (iterative) factorial function as follows.
-----fact.h------
#if x==0
y
#else
#define newy (y*x)
#include "assignnewy.h"
#define newx (x-1)
#include "assignnewx.h"
#include "fact.h"
#endif
-----------------
------fact-driver.h----
/* set up arguments x and y, then 'call' factorial 'macro'. */
#define x 5
#define y 1
#include "fact.h"
-----------------------
Think BASIC. The idea here is to utilize the 'variables' x, y to hold the
'arguments' to the factorial 'macro' which is the file "fact.h". To 'assign' x
a new value, we first define its new value by means of a macro 'newx', and then
'call' the 'macro' (file) "assignnewx.h" which does the assignment x := newx.
The hard part is "assignnewx.h", which has to evaluate the new expression and
'assign' it to x. It turns out that this has to be done bit-by-bit for
the binary encoding of x. Thus, we compute newx0, newx1, newx2, newx3, etc.,
where newx<i> is the i'th bit of newx:
#if (newx%16)-(newx%8)
#define newx3 8
#else
#define newx3 0
#endif
etc.
We must then do the assignment x<i> := newx<i>, as follows:
/* Perform the assignment x3 := newx3 */
#undef x3
#if newx3
#define x3 8
#else
#define x3 0
#end
etc.
Finally, we put the updated x back together again:
#undef x
#define x (x15+x14+x13+x12+x11+x10+x9+x8+x7+x6+x5+x4+x3+x2+x1+x0)
We also have to kill off the newx's:
#undef newx
#undef newx0
#undef newx1
etc.
"assignnewy.h" is similar.
I programmed the above, and it does indeed work.
With a bit more work it should be possible to program recursive fibonacci
completely in the C preprocessor, and cause one of the longest CPP runs in
history! (Handling a stack/vector seems to require a bit more thought.)
Question: Can fact be done _without_ converting x to binary?
Question: Can fact be done _without_ creating a separate file for each
variable name?