macro recursion

W

W Karas

When pre-processing this code:

#define SUM(N) (N + 1 + SUM##N)

#define SUM10 SUM(9)
#define SUM9 SUM(8)
#define SUM8 SUM(7)
#define SUM7 SUM(6)
#define SUM6 SUM(5)
#define SUM5 SUM(4)
#define SUM4 SUM(3)
#define SUM3 SUM(2)
#define SUM2 SUM(1)
#define SUM1 SUM(0)
#define SUM0 0

int sum = SUM10;

the preprocessor seems to halt as soon as it detects the indirect recursion. Why?
 
L

Lew Pitcher

When pre-processing this code:

#define SUM(N) (N + 1 + SUM##N)

#define SUM10 SUM(9)
#define SUM9 SUM(8)
#define SUM8 SUM(7)
#define SUM7 SUM(6)
#define SUM6 SUM(5)
#define SUM5 SUM(4)
#define SUM4 SUM(3)
#define SUM3 SUM(2)
#define SUM2 SUM(1)
#define SUM1 SUM(0)
#define SUM0 0

int sum = SUM10;

the preprocessor seems to halt as soon as it detects the indirect
recursion. Why?

I believe that this is covered in the C standard.

In C 9899:1999 (admittedly, out of date now), Section 6.10.3.4 ("Rescanning
and further replacement") paragraph 2 states
If the name of the macro being replaced is found during this scan of the
replacement list (not including the rest of the source ï¬le’s preprocessing
tokens), it is not replaced.
Furthermore, if any nested replacements encounter the name of the macro
being replaced, it is not replaced. These nonreplaced macro name
preprocessing tokens are no longer available for further replacement even
if they are later (re)examined in contexts in which that macro name
preprocessing token would otherwise have been replaced.
The later C standards should have similar wording wrt macro expansion.

The macro expansion phases would see
SUM10
and expand that to
SUM(9)
and expand that to
(9 + 1 + SUM8)
and expand that to
(9 + 1 + SUM(7))
But, this expansion clearly involves an expansion of the SUM() macro, which
has already been expanded in the previous step. And, this re-expansion of
the SUM() macro satisfies the "nested replacements" condition of 6.10.3..4
 
J

James Kuyper

When pre-processing this code:

#define SUM(N) (N + 1 + SUM##N)

#define SUM10 SUM(9)
#define SUM9 SUM(8)
#define SUM8 SUM(7)
#define SUM7 SUM(6)
#define SUM6 SUM(5)
#define SUM5 SUM(4)
#define SUM4 SUM(3)
#define SUM3 SUM(2)
#define SUM2 SUM(1)
#define SUM1 SUM(0)
#define SUM0 0

int sum = SUM10;

the preprocessor seems to halt as soon as it detects the indirect recursion. Why?

A function-like macro definition specifies a set of tokens that will
replace the thing that looks like a function call, with variable
substitution and # and ## processing.

"After all parameters in the replacement list have been substituted and
# and ## processing has taken place, ... The resulting preprocessing
token sequence is then rescanned, along with all subsequent
preprocessing tokens of the source file, for more macro names to replace.

If the name of the macro being replaced is found during this scan of the
replacement list (not including the rest of the source file’s
preprocessing tokens), it is not replaced. Furthermore, if any nested
replacements encounter the name of the macro being replaced, it is not
replaced. These nonreplaced macro name preprocessing tokens are no
longer available for further replacement even if they are later
(re)examined in contexts in which that macro name preprocessing token
would otherwise have been replaced." (6.10.3.4p1-2)

The Rationale explains why they decided to make such a rule:

"A problem faced by many pre-C89 preprocessors is how to use a macro
name in its expansion without suffering “recursive death.” The C89
Committee agreed simply to turn off the definition of a macro for the
duration of the expansion of that macro."

I've no idea whether the following kind of macro definition played any
role in their decision, but it would not work if macros were allowed to
be recursive:

header.h:
int func(double x);

caller.c:
#include "header.h"
unsigned long func_calls = 0;
#define func(x) (func_calls++,func(x))
 
W

W Karas

Tha

A function-like macro definition specifies a set of tokens that will

replace the thing that looks like a function call, with variable

substitution and # and ## processing.



"After all parameters in the replacement list have been substituted and

# and ## processing has taken place, ... The resulting preprocessing

token sequence is then rescanned, along with all subsequent

preprocessing tokens of the source file, for more macro names to replace.



If the name of the macro being replaced is found during this scan of the

replacement list (not including the rest of the source file�s

preprocessing tokens), it is not replaced. Furthermore, if any nested

replacements encounter the name of the macro being replaced, it is not

replaced. These nonreplaced macro name preprocessing tokens are no

longer available for further replacement even if they are later

(re)examined in contexts in which that macro name preprocessing token

would otherwise have been replaced." (6.10.3.4p1-2)



The Rationale explains why they decided to make such a rule:



"A problem faced by many pre-C89 preprocessors is how to use a macro

name in its expansion without suffering �recursive death.� The C89

Committee agreed simply to turn off the definition of a macro for the

duration of the expansion of that macro."



I've no idea whether the following kind of macro definition played any

role in their decision, but it would not work if macros were allowed to

be recursive:



header.h:

int func(double x);



caller.c:

#include "header.h"

unsigned long func_calls = 0;

#define func(x) (func_calls++,func(x))

Thank you (both) for finding the relevant citations in the Standard.

Compilers are not required to detect run-time infinite recursion, even in limited cases. Even if macro recursion were allowed, infinite macro recursion would still cause an "out of memory" compilation failure, and could be accompanied by a warning that macro recursion occurred. So banning macro recursion seems like swatting the mosquito while bleeding from the jugular.

I would guess this rule was put in place before the addition of token concatenation, on the grounds that all recursion is infinite without a conditional. Seems high time the rule was revisited.

My example is of course trivial. This issue came up for me in some (proprietary) code where the macro corresponding to SUM is several line long, so the reduction is verbosity would have been significant. I further point outthat what I'm doing here is somewhat analogous to partial template specialization in C++, a feature with well-demonstrated usefulness.
 
J

James Kuyper

On 10/14/2012 01:56 PM, W Karas wrote:
....
Compilers are not required to detect run-time infinite recursion,
even in limited cases. Even if macro recursion were allowed,
infinite macro recursion would still cause an "out of memory"
compilation failure, and could be accompanied by a warning that macro
recursion occurred. So banning macro recursion seems like swatting
the mosquito while bleeding from the jugular.

I would guess this rule was put in place before the addition of token
concatenation, on the grounds that all recursion is infinite without
a conditional. Seems high time the rule was revisited.

My example is of course trivial. This issue came up for me in some
(proprietary) code where the macro corresponding to SUM is several
line long, so the reduction is verbosity would have been significant.
I further point out that what I'm doing here is somewhat analogous to
partial template specialization in C++, a feature with
well-demonstrated usefulness.

The C99 Rationale says "The consensus of the C89 Committee is that
preprocessing should be simple and overt, that it should sacrifice power
for clarity." I think you're trying to make of the preprocessor a more
powerful device than the committee ever intended it to be. The macro
your trying to use is probably pushing the limits of what macros were
intended to be good for.
 
W

W Karas

On 10/14/2012 01:56 PM, W Karas wrote:

...
















The C99 Rationale says "The consensus of the C89 Committee is that

preprocessing should be simple and overt, that it should sacrifice power

for clarity." I think you're trying to make of the preprocessor a more

powerful device than the committee ever intended it to be. The macro

your trying to use is probably pushing the limits of what macros were

intended to be good for.

Blocking recursion requires an extra rule, a special case. This is a case of reducing both clarity and power, not trading off power for clarity.
 
E

Eric Sosman

[...]
Blocking recursion requires an extra rule, a special case. This is a case of reducing both clarity and power, not trading off power for clarity.

If you don't like C, don't use it. If you want to use C,
use it as it's defined. If you don't like C as it's defined,
submit a formal change proposal to ISO. But don't just sit
there whining; it's both irritating and useless.
 
W

W Karas

Blocking recursion requires an extra rule, a special case. This is a case of reducing both clarity and power, not trading off power for clarity.



If you don't like C, don't use it. If you want to use C,

use it as it's defined. If you don't like C as it's defined,

submit a formal change proposal to ISO. But don't just sit

there whining; it's both irritating and useless.



--

Eric Sosman

esosman@...

You can't tell if I'm actually whining over the Internet. Also, I could be typing standing up, like Donald Rumsfeld.

I'm sure the ISO C committee would not want to consider proposals that had not been heavily discussed in forums such as these first. Sorry if that bugs you.
 
K

Kaz Kylheku

Blocking recursion requires an extra rule, a special case. This is a case of
reducing both clarity and power, not trading off power for clarity.

Ah, but that the preprocessor can suffer unbounded recursion and crash is an
grave problem which *had* to be addressed.

Whereas that C programs themselves can suffer from unbounded recursion and
crash is of no consequence.
 
K

Kaz Kylheku

I'm sure the ISO C committee would not want to consider proposals that had
not been heavily discussed in forums such as these first. Sorry if that bugs
you.

That evidently seems to be the benchmark for getting a new feature in.
 
J

Jens Gustedt

Am 14.10.2012 19:56, schrieb W Karas:
Compilers are not required to detect run-time infinite recursion,
even in limited cases. Even if macro recursion were allowed,
infinite macro recursion would still cause an "out of memory"
compilation failure, and could be accompanied by a warning that
macro recursion occurred. So banning macro recursion seems like
swatting the mosquito while bleeding from the jugular.
I would guess this rule was put in place before the addition of
token concatenation, on the grounds that all recursion is infinite
without a conditional. Seems high time the rule was revisited.

The lack of easy to implement and to read conditions inside macros are
not the only reason why programming recursively with macros is
difficult. There is also the lack of local definitions (that would
correspond to local variables in your examples of functions) that
makes it very inefficient. The only "local" items are the parameters
of a macro, and thus complicated macros tend to recurse multiple times
in several branches, easily leading to combinatorial explosion at
compile time.
My example is of course trivial. This issue came up for me in some
(proprietary) code where the macro corresponding to SUM is several
line long, so the reduction is verbosity would have been
significant. I further point out that what I'm doing here is
somewhat analogous to partial template specialization in C++, a
feature with well-demonstrated usefulness.

For C++ there is Boost, and for C you could use P99 for a relatively
modest programming with recursion / iteration.

P99 has tools that let you do things up to a depth of 128 or so, which
usually is sufficient for everything that you'd do for a real user
support, such as generating initialisers or default function
arguments.

I wrote it and use it for things like you mention, and it helps to
keep the complexity of the user code relatively low, that complexity
is hidden inside the P99 tools.

Jens
 
8

88888 Dihedral

That evidently seems to be the benchmark for getting a new feature in.

The unicode support part in C is still kind of lousy.

The language level support and the OS level support are different.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top