macro recursion

Discussion in 'C Programming' started by W Karas, Oct 12, 2012.

  1. W Karas

    W Karas Guest

    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?
    W Karas, Oct 12, 2012
    #1
    1. Advertising

  2. W Karas

    Lew Pitcher Guest

    On Friday 12 October 2012 18:24, in comp.lang.c, wrote:

    > 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

    --
    Lew Pitcher
    "In Skills, We Trust"
    Lew Pitcher, Oct 12, 2012
    #2
    1. Advertising

  3. W Karas

    James Kuyper Guest

    On 10/12/2012 06:24 PM, W Karas wrote:
    > 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))
    James Kuyper, Oct 12, 2012
    #3
  4. W Karas

    W Karas Guest

    Tha

    On Friday, October 12, 2012 6:59:08 PM UTC-4, James Kuyper wrote:
    > On 10/12/2012 06:24 PM, W Karas wrote:
    >
    > > 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))


    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.
    W Karas, Oct 14, 2012
    #4
  5. W Karas

    James Kuyper Guest

    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.
    --
    James Kuyper
    James Kuyper, Oct 15, 2012
    #5
  6. W Karas

    W Karas Guest

    On Sunday, October 14, 2012 8:04:07 PM UTC-4, James Kuyper wrote:
    > 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.
    >
    > --
    >
    > James Kuyper


    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.
    W Karas, Oct 15, 2012
    #6
  7. W Karas

    Eric Sosman Guest

    On 10/14/2012 10:00 PM, W Karas wrote:
    >[...]
    > 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
    d
    Eric Sosman, Oct 15, 2012
    #7
  8. W Karas

    W Karas Guest

    On Sunday, October 14, 2012 10:38:03 PM UTC-4, Eric Sosman wrote:
    > On 10/14/2012 10:00 PM, W Karas wrote:
    >
    > >[...]

    >
    > > 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.
    W Karas, Oct 15, 2012
    #8
  9. W Karas

    Kaz Kylheku Guest

    On 2012-10-15, W Karas <> wrote:
    > 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.
    Kaz Kylheku, Oct 15, 2012
    #9
  10. W Karas

    Kaz Kylheku Guest

    On 2012-10-15, W Karas <> wrote:
    > 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.
    Kaz Kylheku, Oct 15, 2012
    #10
  11. W Karas

    Jens Gustedt Guest

    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
    Jens Gustedt, Oct 15, 2012
    #11
  12. On Monday, October 15, 2012 2:27:01 PM UTC+8, Kaz Kylheku wrote:
    > On 2012-10-15, W Karas <> wrote:
    >
    > > 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.


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

    The language level support and the OS level support are different.
    88888 Dihedral, Oct 15, 2012
    #12
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dead RAM
    Replies:
    20
    Views:
    1,106
    John Harrison
    Jul 14, 2004
  2. D Senthil Kumar

    macro name from macro?

    D Senthil Kumar, Sep 20, 2003, in forum: C Programming
    Replies:
    1
    Views:
    576
    Jack Klein
    Sep 21, 2003
  3. sounak

    to get macro name from macro value

    sounak, Nov 22, 2005, in forum: C Programming
    Replies:
    17
    Views:
    500
    Mark McIntyre
    Nov 22, 2005
  4. Patrick Kowalzick
    Replies:
    5
    Views:
    468
    Patrick Kowalzick
    Mar 14, 2006
  5. Replies:
    8
    Views:
    733
    John Reye
    Apr 26, 2012
Loading...

Share This Page