Macro Recursion
author: Kevin Lynx
Preface
本文可能是<代碼自動生成-宏帶來的奇技淫巧>的續(xù)寫。我盡力闡述如何讓宏遞歸（或者說重復）地有規(guī)律地產(chǎn)生一
些符號，而讓我們少寫很多重復代碼，也許這些代碼只有那么一點點的不同。將這項小技巧用于底層庫的編寫，會讓代碼
看起來干凈不少，同時文件尺寸也會驟然下降。
Problem
如果你曾經(jīng)寫過functor，那么你肯定對某些代碼進行粘貼復制然后修改。更讓人郁悶的是，這些代碼基本是一樣的。
例如，一個典型的functor可能為：
template <typename Prototype>
class functor;
template <typename R, typename P1>
class functor<R(P1)>;
template <typename R, typename P1, typename P2>
class functor<R(P1,P2)>;
//好，接下去你可能厭煩了，可能會復制一個帶有兩個參數(shù)的functor，然后修改為處理3個參數(shù)的。
這只是一個很簡單的問題。宏不是c++里的東西，本文自然也不是討論各種花哨的模板技術(shù)的。如果我之前那篇關(guān)于
宏的文章只是讓你去分析問題以及更深層次地認識宏，那么現(xiàn)在我將分享我的這部分思想給你。
關(guān)于上面的問題，我們期待得到這樣的解決方案：
template <typename R, DEF_PARAM( 2 )>
class functor<R( DEF_ARG( 2 ) )>;
那么，它將自動生成：
template <typename R, typename P1, typename P2>
class functor<R(P1,P2)>;
也就是說，DEF_PARAM(n)這個宏將根據(jù)n值自動生成一串符號，例如DEF_PARAM(2)就生成typename P1, typename P2。
同樣，DEF_ARG(n)也會根據(jù)參數(shù)生成類似于P1,P2,...,Pn的符號串。
思考
仔細思考下，我們可以看出DEF_PARAM和DEF_ARG這樣的宏具有一種遞歸的特性（其實說成重復可能更合適）：每次展
開的內(nèi)容基本一樣，不斷調(diào)用自身直到遇到終止條件。
那么，我們的目標鎖定于，用宏來實現(xiàn)遞歸。
Pre-Implement
在開始之前，我需要告訴你一些基本的東西：
在閱讀一個宏時，你最好按照預處理的處理方式去逐個展開。當我說到展開時，我的意思是把宏替換為宏體。預處理器
展開宏的過程大致為：如果宏參數(shù)也是個宏，那么先將宏參數(shù)全部展開，再展開該宏；這個時候會掃描展開后的宏，如果
遇到其他宏，則繼續(xù)展開。例如有一下宏：
#define PI 3.14
#define MUL_PI( n ) n * PI
#define TWO 2
當我們寫下MUL_PI( TWO )時，預處理發(fā)現(xiàn)MUL_PI的參數(shù)TWO 是個宏，那么先將TWO展開得到2，然后將2放進宏體展開
得到 2 * PI；預處理器對 2 * PI 進行掃描，發(fā)現(xiàn)還有宏P(guān)I，于是對PI做展開，得到 2 * 3.14。這個過程是遞歸的。
但是也有例外，如果MUL_PI對宏參數(shù)進行了#或者##，那么該宏參數(shù)不會被展開。（參見以前那篇文章吧）
任何時候，你可以通過以下宏去查看某個宏展開后的樣子，可以方便你調(diào)試你的宏：
#define TO_STRING( x ) TO_STRING1( x )
#define TO_STRING1( x ) #x
（為什么要寫個TO_STRING1，因為這是為了讓x充分展開，避免上面提到的那個例外）
其他規(guī)則我會在文中需要的地方提出來。
實現(xiàn)
就像大部分介紹遞歸函數(shù)時候給的例子，這里我也將階乘作為例子。考慮如下典型的階乘函數(shù)：
int fac( int n )
{
if( n == 1 ) return 1;
return n * fac( n - 1 );
}
其核心部分在于 n * fac( n - 1 )，我們假設我們的宏也可以寫成這樣的的形式：
#define FAC( n ) n * FAC( n - 1 )
但是這樣的宏是有問題的：
當宏被展開時，如果遇到了自身，那么將被處理為一般符號，例如展開FAC( 3 )時，會遇到 FAC( 2 )，那么就把FAC
( 2 )中的FAC當成了一搬符號。
這樣的限制注定了我們無法讓宏真正地調(diào)用自身來實現(xiàn)遞歸。于是，我們不得不寫下以下丑陋的符號，從而去模擬遞
歸的每一次符號調(diào)用：
#define FAC_1( n ) 1
#define FAC_2( n ) n * FAC_##(n-1)( n - 1 )
#define FAC_3( n ) n * FAC_##(n-1)( n - 1 )
這系列宏有點別扭（如果你足夠細心），因為我們明顯知道FAC_2返回的將是2，而FAC_3返回的當時6。我們這里只是
模擬，同樣，這使得我們可以把FAC_1作為遞歸的終止條件。
我們的預想是，當調(diào)用FAC_3時，它把n-1的值2合并到FAC_中，從而調(diào)用FAC_2，以此類推。
但是這依然有問題，編譯器會提示‘找不到符號FAC_’。導致這個問題的原因在于：宏展開只是單純的字符替換，是我們
想太多了，預處理器并不會去計算( n - 1 )的值是多少，也就是我們無法得到FAC_2這個宏。
所以，F(xiàn)AC_3( 3 ) 會被初次替換為 3 * FAC_(3-1)( 3 - 1 )。這個時候編譯器就把FAC_當成了一個普通符號。我們可以
自己定義個FAC_來證明這一點：
#define FAC_( n ) T
那么，F(xiàn)AC_3( 3 )就被替換為 3 * T(3-1)( 3 - 1 )。
解決這個問題的辦法關(guān)鍵在于，讓預處理器自動計算出( n - 1 )。記住，我們解決問題的唯一辦法是：字符替換。
所以，我們可以寫下如下代碼：
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC( n ) DEC_##n
通過，DEC( n )這個宏，我們可以獲取到一個( n -1 )的數(shù)。例如，DEC( 3 )被替換為 DEC_3，繼續(xù)替換為 2。
于是，我們新的FAC系列宏變?yōu)椋?
#define FAC_1( n ) 1
#define FAC_2( n ) n * FAC_##DEC( n )( n - 1 )
#define FAC_3( n ) n * FAC_##DEC( n )( n - 1 )
不好意思，這樣依然是不正確的！預處理器直接把FAC_和DEC( n )連接成符號了，而不是單個地先處理他們，最后再
合并他們。
OK，先解決這個問題：先處理FAC_和DEC( n )，再合并他們，而不是先合并他們。要解決這個問題，可以通過第三個宏
來實現(xiàn)：
#define CHR( x, y ) x##y
作為連接兩個符號為一個符號的宏，這個宏顯然是不正確的，因為宏展開還有個規(guī)則：如果宏體對宏參數(shù)使用了#或##，
那么宏參數(shù)不會被展開，也就是說：如果CHR( FAC_, DEC( 3 ) 那么得到的只會是 FAC_DEC( 3 )。通常情況下我們是
再寫個宏：
#define CHR( x, y ) CHR1( x, y )
#define CHR1( x, y ) x##y
從而可以保證在正式連接x和y前，x和y都被完全展開。
這個時候，我們的FAC系列宏變?yōu)椋?
#define FAC_1( n ) 1
#define FAC_2( n ) n * CHR( FAC_, DEC( n ) )( n - 1 )
#define FAC_3( n ) n * CHR( FAC_, DEC( n ) )( n - 1 )
結(jié)果呢？結(jié)果還是有問題。= =
我們假設CHR( FAC_, DEC( n ) )已經(jīng)真的按我們預想展開為 FAC_2了，那么FAC_3( 3 )會被展開為什么呢？
被展開為 3 * FAC_2( 3 - 1 )。這是錯誤的，傳給 FAC_2 的參數(shù)是 3 - 1就意味著錯誤。我們又臆想預處理器會
幫我們計算 3 - 1的結(jié)果了。我們必須保證傳給 FAC_2的參數(shù)是個數(shù)字2。解決這個問題的辦法就是通過DEC(n)宏。
于是，F(xiàn)AC系列宏變?yōu)椋?
#define FAC_1( n ) 1
#define FAC_2( n ) n * CHR( FAC_, DEC( n ) )( DEC( n ) )
#define FAC_3( n ) n * CHR( FAC_, DEC( n ) )( DEC( n ) )
這個時候，F(xiàn)AC_3( 3 )將會被替換為：3*2*1。這就是我們要的結(jié)果。
In practice
以上只是向你展示一個過程，用宏去計算階乘，就像用模板去計算階乘（模板元編程）一樣，只是一個用于展示的東西，
沒有什么實際價值。接下來我們開始有實際的工作，完成之前的預想：
template <typename R, typename P1, typename P2, typename P3>
class functor<R (P1, P2, P3)>
直接:
template <typename R, PARAM( 3 )>
class functor<R (ARG( 3 ))>
先考慮PARAM宏，該宏的任務就是生成類似于：typename P1, typename P2, typename P3這樣的符號。我們假象它每一次
遞歸都生成 typename Pn, 的字符串，那么當他遞歸完時，可能就生成typename P1, typename P2, typename P3, 結(jié)果
多了個逗號，也許最后一次結(jié)果不該有逗號。
ARG宏和PARAM宏本質(zhì)上相同，只是重復的符號不是typename Pn，而是Pn。
最直接想到的是：
#define PARAM_1( n ) typename P##n
#define PARAM_2( n ) CHR( PARAM_, DEC( n ) )( DEC( n ) )##,typename P##n
#define PARAM_3( n ) CHR( PARAM_, DEC( n ) )( DEC( n ) )##,typename P##n
結(jié)果我們得到了個錯誤的展開結(jié)果：
typename PDEC( 2 ),typename PDEC( 3 ),typename P3
這個問題出在：PARAM_3( 3 )當替換為 PARAM_2( DEC( n ) )時，因為PARAM_2(n)宏對于宏參數(shù)n使用了##，也就是那個
typename P##n，所以這里不會把 DEC( n )展開，而是直接接到P后面。所以就成了typename PDEC( 3 )。
為了消除這個問題，我們改進PARAM為：
#define TYPE( n ) ,typename P##n
#define PARAM_1( n ) CHR( typename P, n )
#define PARAM_2( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define PARAM_3( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
之所以加入TYPE(n)，是因為 ,typename P##n 這個宏本身存在逗號，將其直接用于宏體會出現(xiàn)問題。
于是，我們得到了正確的結(jié)果。
其實，PARAM系列宏宏體基本是一樣的，除了終止條件那個宏，為什么我們要寫這么多呢？理由在于宏體不能自己調(diào)用
自己，所以才有了PARAM_3, PARAM_2。
我們可以將上面的一系列宏抽象化，使其具有可復用性：
#define PARAM( n ) ,typename P##n
#define PARAM_END typename P
#define ARG( n ) ,P##n
#define ARG_END P
#define PARAM_1( n ) CHR( typename P, n )
#define PARAM_2( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define PARAM_3( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define REPEAT_1( n, f, e ) CHR( e, n )
#define REPEAT_2( n, f, e ) CHR( CHR( REPEAT_, DEC( n ) )( DEC( n ), f, e ), f( n ) )
#define REPEAT_3( n, f, e ) CHR( CHR( REPEAT_, DEC( n ) )( DEC( n ), f, e ), f( n ) )
#define DEF_PARAM( n ) REPEAT_##n( n, PARAM, PARAM_END )
#define DEF_ARG( n ) REPEAT_##n( n, ARG, ARG_END )
我們創(chuàng)建了可重用的REPEAT系列宏，用于創(chuàng)建諸如typename P1, typename P2, typename P3或者P1,P2,P3之類的符號，
通過更上層的DEF_PARAM(n)和DEF_ARG(n)，就可以直接創(chuàng)建出我們上面所需要的符號串，例如：
DEF_PARAM( 3 ) 就得到 typename P1, typename P2, typename P3
DEF_ARG( 3 ) 就得到 P1, P2, P3
More in practice
下載中提供了我使用這個宏遞歸技術(shù)寫的lua_binder(如果你看過<實現(xiàn)自己的LUA綁定器-一個模板編程挑戰(zhàn) >)，你
可以與上一個版本做一下比較，代碼少了很多。
同樣，我希望你也能獲取這種宏遞歸的思想。
相關(guān)下載
使用宏遞歸的lua_binder