C preprocessor tail recursion

The C preprocessor gives the false impression of being functional in nature, but its capacities are more limited than expected; for instance, function reentrancy does not work: consider the following attempt at recursively defining the factorial function using Boost.Preprocessor:

‎#define FACTORIAL(n) \
‎BOOST_PP_IF( \
‎  n, \
‎  BOOST_PP_MUL(n,FACTORIAL(BOOST_PP_DEC(n))), \
‎  1)

The expression FACTORIAL(5) does not expand to 120, however, but to

‎BOOST_PP_TUPLE_ELEM_3_0 BOOST_PP_IIF_BOOST_PP_BOOL_FACTORIAL(4)(
‎BOOST_PP_WHILE_2, (0, 5, FACTORIAL(4)) BOOST_PP_TUPLE_EAT_3)(BOO
‎ST_PP_MUL_P, BOOST_PP_MUL_O, (5, 5, BOOST_PP_DEC_FACTORIAL(4)))

The rules of the C preprocessor mandate that during the expansion of the function macro FACTORIAL internal occurrences of this token are not further expanded, thus ruling out the very core of recursion. A simpler example illustrates this:

‎#define A B
‎#define B A
‎
‎A

The last line of the snippet above does not enter into infinite recursion, but simply causes the expansion rules A→B→A to be applied, stopping here because A is met inside the expansion of A itself.

Despite these serious limitations, Boost.Preprocessor is able to provide constructs for bounded iteration implemented with very sophisticated techniques. Let us see how to use BOOST_PP_WHILE to simulate tail recursion, a special form of recursion in which recursivity is applied exactly at the end of the recursive function body. The usual formulation of the factorial function is not tail recursive:

‎int factorial(int n)
‎{
‎  if(n>0)return n*factorial(n-1);
‎  else   return 1;
‎}

But it can be rewritten to be so as follows:

‎int factorial(int n,int res=1)
‎{
‎  if(n>0)return factorial(n-1,n*res);
‎  else   return res;
}

The idea is that the recursive function passes all the relevant contextual information as part of the recursive call, thus delegating the work that otherwise should be done after the recursion returns; in this way, recursing (except when terminating recursion) is exactly the last thing that the function does. Let us know apply the following trasformation f → f' to a tail recursive function f:

• If f stops and returns res, f' returns the sequence (stop,res).
  
• If f recursively calls f(args), f' returns the sequence (iterate,args).
  

That is, f' does not recurse but instead returns the computation state if recursion is to occur, or the final return value otherwise. The following pseudocode illustrates the transformation process for factorial:

‎factorial_body(int n,int res=1)
‎{
‎  if(n>0)return (iterate,n-1,n*res);
‎  else   return (stop,res);
‎}

f' is no longer recursive, but it can be used to compute f as follows:

‎recurse(body,args)
‎{
‎  state=(iterate,args);
‎  while(state[0]!=stop){
‎    state=body(state.args);
‎  }
‎}

The interesting fact about this process is that recursion (and so reentrancy) has been eliminated in favor of iteration: f' is called repeatedly until it signals termination. We can very easily implement this idea using Boost.Preprocessor:

‎#define RECURSE(body,args) \
‎RECURSE_RES(BOOST_PP_WHILE(RECURSE_PRED,RECURSE_OP,(body)ITERATE args))
‎
‎#define RECURSE_PRED(d,state) \
‎BOOST_PP_SEQ_ELEM(1,state)
‎
‎#define RECURSE_OP(d,state) \
‎(RECURSE_BODY(state))RECURSE_BODY(state)(BOOST_PP_SEQ_REST_N(2,state))
‎
‎#define RECURSE_BODY(state) \
‎BOOST_PP_SEQ_ELEM(0,state)
‎
‎#define RECURSE_RES(state) \
‎BOOST_PP_SEQ_ELEM(2,state)
‎
‎#define STOP (0)
‎
‎#define ITERATE (1)

which allows us to implement our factorial macro in a reasonably straightforward manner:

‎‎#define FACTORIAL(n) RECURSE(FACTORIAL_BODY,(n)(1))
‎
‎#define FACTORIAL_BODY(args) \
‎FACTORIAL_BODY_IMPL( \
‎  BOOST_PP_SEQ_ELEM(0,args),BOOST_PP_SEQ_ELEM(1,args))
‎
‎#define FACTORIAL_BODY_IMPL(n,res) \
‎BOOST_PP_IF( \
‎  n, \
‎  ITERATE(BOOST_PP_DEC(n))(BOOST_PP_MUL(n,res)), \
‎  STOP(res))

Arguments are packed using Boost.Preprocessor sequences. A complete implementation program is provided. Unfortunately, the process seems to be very onerous for common implementations of the C preprocessor, as internal limits are generally reached with arguments greater than 5. This problem could deserve further investigation in a later entry.