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