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

`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;

}

`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);

}

}

`#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)

`#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))

A very nice post. Congratulations.

ReplyDeleteIf I understand correctly, there is a minor mistake. I don't think what you are doing is continuation passing style. Following the link to Wikipedia it says "continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation." What you do here is passing data, not control.

Jorge, thanks for the observation. I've corrected that bit of explanation.

ReplyDelete