Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #72382 > unrolled thread

Is the C preprocessor turing-complete?

Back to article view | Back to comp.lang.c

Contents

  Is the C preprocessor turing-complete? Anonymous Shadow <rocket.penguin@riseup.net> - 2015-10-10 18:23 +0800
    Re: Is the C preprocessor turing-complete? Philipp Klaus Krause <pkk@spth.de> - 2015-10-10 12:33 +0200
      Re: Is the C preprocessor turing-complete? Les Cargill <lcargill99@comcast.com> - 2015-10-10 13:39 -0500
        Re: Is the C preprocessor turing-complete? raltbos@xs4all.nl (Richard Bos) - 2015-10-14 11:33 +0000
          Re: Is the C preprocessor turing-complete? Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-15 10:44 -0700
            Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-15 11:34 -0700
              Re: Is the C preprocessor turing-complete? Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-16 05:17 -0700
          Re: Is the C preprocessor turing-complete? Les Cargill <lcargill99@comcast.com> - 2015-10-15 20:46 -0500
            Re: Is the C preprocessor turing-complete? Les Cargill <lcargill99@comcast.com> - 2015-10-15 23:21 -0500
            Re: Is the C preprocessor turing-complete? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-16 11:24 +0100
            Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-16 08:43 -0700
              Re: Is the C preprocessor turing-complete? Martin Shobe <martin.shobe@yahoo.com> - 2015-10-16 11:13 -0500
                Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-16 11:42 -0700
                  Re: Is the C preprocessor turing-complete? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-16 21:48 +0100
                    Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-16 14:01 -0700
    Re: Is the C preprocessor turing-complete? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-10-10 03:53 -0700
    Re: Is the C preprocessor turing-complete? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-10-10 11:59 +0000
    Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-10 13:02 -0700
      Re: Is the C preprocessor turing-complete? Anonymous Shadow <rocket.penguin@riseup.net> - 2015-10-11 04:20 +0800
    Re: Is the C preprocessor turing-complete? Michael Barry <barrym95838@yahoo.com> - 2015-10-15 21:45 -0700
      Re: Is the C preprocessor turing-complete? James Kuyper <jameskuyper@verizon.net> - 2015-10-16 09:49 -0400
        Re: Is the C preprocessor turing-complete? Richard Heathfield <rjh@cpax.org.uk> - 2015-10-16 14:54 +0100
          Re: Is the C preprocessor turing-complete? James Kuyper <jameskuyper@verizon.net> - 2015-10-16 10:39 -0400
          Re: Is the C preprocessor turing-complete? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-16 11:25 -0400
            Re: Is the C preprocessor turing-complete? Les Cargill <lcargill99@comcast.com> - 2015-10-16 12:29 -0500
          Re: Is the C preprocessor turing-complete? Robert Wessel <robertwessel2@yahoo.com> - 2015-10-16 10:39 -0500

Page 1 of 2  [1] 2  Next page →

#72382 — Is the C preprocessor turing-complete?

(Sorry, this is probably off topic.)

It is my understanding, that to be Turing complete a language must have
some form of recursion.

Can I have some sort of loop like this:

/* Filename must be recursion.h */
#ifndef COUNT
#  define COUNT 0
#endif

This is iteration COUNT

#if COUNT == 0
#  define COUNT 1
#elif COUNT == 1
#  define COUNT 2
#elif COUNT == 2
#  define COUNT 3
#elif COUNT == 3
#  define COUNT 4
#elif COUNT == 4
#  define COUNT 5
#elif COUNT == 5
#  define COUNT 6
#elif COUNT == 6
#  define COUNT 7
#elif COUNT == 7
#  define COUNT 8
#elif COUNT == 8
#  define COUNT 9
#elif COUNT == 9
#  define COUNT 10
#elif COUNT == 10
#  error "counter has reached limit"

#include "recursion.h"

By the way, this question is just out of curiosity, I am not
planning to implement a programming language in the preprocessor!

--
Daniel Roskams

[toc] | [next] | [standalone]

#72383

On 10.10.2015 12:23, Anonymous Shadow wrote:

You might want to have at Immanuel's winning "Best abuse of the C
preprocessor" entry in the 2001 obfuscated C contest. In particular, see
http://www.ioccc.org/2001/herrmann1.hint

Philipp

[toc] | [prev] | [next] | [standalone]

#72408

Stefan Ram wrote:
> Philipp Klaus Krause <pkk@spth.de> writes:
>> You might want to have at Immanuel's winning "Best abuse of the C
>> preprocessor" entry in the 2001 obfuscated C contest. In particular, see
>> http://www.ioccc.org/2001/herrmann1.hint
>
>    Immanuel says that the reason the preprocessor is not
>    Turing-complete is that it has a finite number of states.
>    Every C program also has only a finite number of states,
>    since the volume of the usable universe is finite and
>    a state cannot occupy less volume than a Planck volume,
>    so C is not Turing-complete either.
>


Turing machines are only potentially infinite in the time
dimension.

-- 
Les Cargill

[toc] | [prev] | [next] | [standalone]

#72823

Les Cargill <lcargill99@comcast.com> wrote:

> Stefan Ram wrote:
> > Philipp Klaus Krause <pkk@spth.de> writes:
> >> You might want to have at Immanuel's winning "Best abuse of the C
> >> preprocessor" entry in the 2001 obfuscated C contest. In particular, see
> >> http://www.ioccc.org/2001/herrmann1.hint
> >
> >    Immanuel says that the reason the preprocessor is not
> >    Turing-complete is that it has a finite number of states.
> >    Every C program also has only a finite number of states,
> >    since the volume of the usable universe is finite and
> >    a state cannot occupy less volume than a Planck volume,
> >    so C is not Turing-complete either.
> 
> Turing machines are only potentially infinite in the time
> dimension.

Surely if you're allowed infinite time, then for certain algorithms you
_must_ also be allowed infinite storage?

That said, the above is not the reason the preprocessor is
non-Turing-complete anyway. It's non-complete simply because it doesn't
have _any_ form of looping at all.

Richard

[toc] | [prev] | [next] | [standalone]

#72966

raltbos@xs4all.nl (Richard Bos) writes:

> Les Cargill <lcargill99@comcast.com> wrote:
>
>> Stefan Ram wrote:
>>> Philipp Klaus Krause <pkk@spth.de> writes:
>>>> You might want to have at Immanuel's winning "Best abuse of the C
>>>> preprocessor" entry in the 2001 obfuscated C contest.  In particular, see
>>>> http://www.ioccc.org/2001/herrmann1.hint
>>>
>>>    Immanuel says that the reason the preprocessor is not
>>>    Turing-complete is that it has a finite number of states.
>>>    Every C program also has only a finite number of states,
>>>    since the volume of the usable universe is finite and
>>>    a state cannot occupy less volume than a Planck volume,
>>>    so C is not Turing-complete either.
>>
>> Turing machines are only potentially infinite in the time
>> dimension.
>
> Surely if you're allowed infinite time, then for certain algorithms you
> _must_ also be allowed infinite storage?
>
> That said, the above is not the reason the preprocessor is
> non-Turing-complete anyway.  It's non-complete simply because it doesn't
> have _any_ form of looping at all.

The preprocessor does admit one form of looping, in that
a file may #include itself.  What isn't obvious is whether
this looping ability is rich enough to get all the way
to Turing completeness.  I have heard that it is, based on
second-hand reports of an old Obfuscated C entry, but
haven't taken the time to investigate enough to resolve
the question.

[toc] | [prev] | [next] | [standalone]

#72975

On Thursday, October 15, 2015 at 12:44:34 PM UTC-5, Tim Rentsch wrote:
> The preprocessor does admit one form of looping, in that
> a file may #include itself.  What isn't obvious is whether
> this looping ability is rich enough to get all the way
> to Turing completeness.  I have heard that it is, based on
> second-hand reports of an old Obfuscated C entry, but
> haven't taken the time to investigate enough to resolve
> the question.

Does anything in the Standard require that a preprocessor allow a file to
#include itself even once?  It requires that things like #include <stdio.h>
must work, but I don't think there's any requirement that a system would
have to support any other form of #include.  I would think it would be
possible to have a legitimate implementation which could accept and
immediately run a program submitted via the terminal (not unworkable if
the terminal includes a high-speed paper tape reader) but did not include
any form of writable filesystem.  If there couldn't possibly exist any
files that could be used with an #include directive that didn't specify
a standard name, a compiler couldn't be expected to usefully process such
a directive.

Thus, I'd say the ability of using #include to perform looping is something
of a gray area from the standpoint of the Standard, though I will note that
I believe that a compiler which allowed arbitrary nesting would be able to
solve NP-hard problems written out in polynomial space, and if one had the
ability to include files from the console it might be possible to solve
problems requiring a pushdown automaton, but without a "define and flatten"
directive I don't think there's any way to avoid creating a limit on the
size of "tape" a program can support.

It would probably be possible to have the size of tape that a given set of
source files could handle grow hyper-exponentially with the total size of
the source files, or possibly even faster than that, such that a moderate
volume of source files would, in the absence of compiler limitations, be
able to handle any Turing File where the number of characters worth of
tape required was less than the number of atoms in the universe.  Of course,
any real-world compiler would choke long before that limit was reached, but
at the same time it would fall short of the amount of tape space that may
be required by even some twelve-state machines.

[toc] | [prev] | [next] | [standalone]

#73024

supercat@casperkitty.com writes:

> On Thursday, October 15, 2015 at 12:44:34 PM UTC-5, Tim Rentsch wrote:
>> The preprocessor does admit one form of looping, in that
>> a file may #include itself.  What isn't obvious is whether
>> this looping ability is rich enough to get all the way
>> to Turing completeness.  I have heard that it is, based on
>> second-hand reports of an old Obfuscated C entry, but
>> haven't taken the time to investigate enough to resolve
>> the question.
>
> Does anything in the Standard require that a preprocessor allow a
> file to #include itself even once?  [snip elaboration]

It's easy to discover an answer to this question, but I see no
reason to bother, since it doesn't affect the purely theoretical
interest of the Turing completeness question.

[toc] | [prev] | [next] | [standalone]

#73008

Richard Bos wrote:
> Les Cargill <lcargill99@comcast.com> wrote:
>
>> Stefan Ram wrote:
>>> Philipp Klaus Krause <pkk@spth.de> writes:
>>>> You might want to have at Immanuel's winning "Best abuse of the C
>>>> preprocessor" entry in the 2001 obfuscated C contest. In particular, see
>>>> http://www.ioccc.org/2001/herrmann1.hint
>>>
>>>     Immanuel says that the reason the preprocessor is not
>>>     Turing-complete is that it has a finite number of states.
>>>     Every C program also has only a finite number of states,
>>>     since the volume of the usable universe is finite and
>>>     a state cannot occupy less volume than a Planck volume,
>>>     so C is not Turing-complete either.
>>
>> Turing machines are only potentially infinite in the time
>> dimension.
>
> Surely if you're allowed infinite time, then for certain algorithms you
> _must_ also be allowed infinite storage?
>

The tape need not be ... perfectly infinite, it just needs to be long
enough to not run out during the operation of that particular Turing 
machine.

"Imagine if you will that Turing machines are produced with a very long 
but finite tape and if the machine ever runs out of space you can just 
order some more tape. This is the difference between the tape actually 
being infinitely long or just unlimited…"

http://www.i-programmer.info/babbages-bag/23-turing-machines.html

Again, infinite only *over time* :)

> That said, the above is not the reason the preprocessor is
> non-Turing-complete anyway. It's non-complete simply because it doesn't
> have _any_ form of looping at all.
>
> Richard
>
-- 
Les Cargill

[toc] | [prev] | [next] | [standalone]

#73012

Stefan Ram wrote:
> Les Cargill <lcargill99@comcast.com> writes:
>> The tape need not be ... perfectly infinite, it just needs to be long
>> enough to not run out during the operation of that particular Turing
>> machine.
>> "Imagine if you will that Turing machines are produced with a very long
>> but finite tape and if the machine ever runs out of space you can just
>> order some more tape. This is the difference between the tape actually
>> being infinitely long or just unlimited"
>
>    »Infinite« means that any operation can run on the tape,
>    whatever it's tape requirements are. When one can always
>    order more tape, than the tape /is/ /perfectly/ infinity.
>    The order process is just an implementation detail

"... just an implementation detail..." :)

>    of infinity.
>    »Not infinite« means that eventually one tape order will fail.
>    And this is going to happen according to current world models.
>
>    »Infinite« and »unlimited« are two words for the same thing.


Unbounded and unlimited ( there exists no limit N such that ... ) are 
the same. Infinite has a few other details that make it different.

It's the difference between an unbounded loop and an infinite loop.


>    The latin word »finis« means »limit« and the latin prefix
>    »in-« is used with certain words to reverse their meaning.
>    in-finite = un-limited.
>

-- 
Les Cargill

[toc] | [prev] | [next] | [standalone]

#73019

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Les Cargill <lcargill99@comcast.com> writes:
>>The tape need not be ... perfectly infinite, it just needs to be long
>>enough to not run out during the operation of that particular Turing 
>>machine.
>>"Imagine if you will that Turing machines are produced with a very long 
>>but finite tape and if the machine ever runs out of space you can just 
>>order some more tape. This is the difference between the tape actually 
>>being infinitely long or just unlimited"
>
>   »Infinite« means that any operation can run on the tape,
>   whatever it's tape requirements are. When one can always
>   order more tape, than the tape /is/ /perfectly/ infinity.
>   The order process is just an implementation detail of infinity.
>   »Not infinite« means that eventually one tape order will fail.
>   And this is going to happen according to current world models.

I prefer Les Cargill's use of terms here.  I don't think there is any
disagreement about facts here, but the physical metaphor of a tape make
the use of terms like "infinite" potentially misleading.  "The tape"
refers both to what's on it (the machine's current, always finite, data)
and to the unlimited resource where future data may be put.

If, instead, we model the store of the machine as a single integer, I
think you can see that talking about this integer as "infinite" is wrong
(or at least very confusing).  It is unbounded or, to put it
differently, drawn from an infinite set.  Had the storage of a Turing
machine always been described as "a number" then nothing about it would
ever be talked about as being infinite.

Going back to tapes, your analogy of buying more is a good one, but I'd
take it further.  I'd think of the tape as always finite but when a
transition occurs, the tape is replaced by a new finite tape.  In that
picture, "the tape" is not infinite.  The only infinite thing is the set
of possible tapes.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#73037

On Thursday, October 15, 2015 at 8:42:47 PM UTC-5, Les Cargill wrote:
> The tape need not be ... perfectly infinite, it just needs to be long
> enough to not run out during the operation of that particular Turing 
> machine.

For any given combination number of states N, all Turing machines with that
number of states that are started with a blank tape will do one of two
things [note that a machine with N states, started with M symbols on the tape,
is equivalent to a machine with N+M state started with a blank tape].

1. Finish within some amount of time f(N)

2. Within that indicated amount of time achieve a scenario where its state
   and the content of all tape locations that it will ever again examine
   are the same as they have been previously.

Thus if the size of the Turing machine and its initial tape content are
known there is no need for unbounded storage; there is some amount of
storage which, if ordered in advance, will be enough.  Only one slight
problem: f(N) grows so mind-bogglingly fast as to defy description.
If one can imagine *any* computable function g(N) which would yield a
finite result for arbitrary N, there will be some n0 such that for all
N>n0, f(n0) exceeds g(n0).

[toc] | [prev] | [next] | [standalone]

#73042

On 10/16/2015 10:43 AM, supercat@casperkitty.com wrote:
> On Thursday, October 15, 2015 at 8:42:47 PM UTC-5, Les Cargill wrote:
>> The tape need not be ... perfectly infinite, it just needs to be long
>> enough to not run out during the operation of that particular Turing
>> machine.
>
> For any given combination number of states N, all Turing machines with that
> number of states that are started with a blank tape will do one of two
> things [note that a machine with N states, started with M symbols on the tape,
> is equivalent to a machine with N+M state started with a blank tape].
>
> 1. Finish within some amount of time f(N)
>
> 2. Within that indicated amount of time achieve a scenario where its state
>     and the content of all tape locations that it will ever again examine
>     are the same as they have been previously.

"That indicated amount of time" doesn't appear to have a reference.

> Thus if the size of the Turing machine and its initial tape content are
> known there is no need for unbounded storage; there is some amount of
> storage which, if ordered in advance, will be enough.  Only one slight
> problem: f(N) grows so mind-bogglingly fast as to defy description.
> If one can imagine *any* computable function g(N) which would yield a
> finite result for arbitrary N, there will be some n0 such that for all
> N>n0, f(n0) exceeds g(n0).
>

When does the following do either 1 or 2? How large a tape do you need?

1. Is the current position blank?
1a. Yes? Write one and go to step 2.
1b. No? Move right and go to step 1.
2. Is the current position 1?
2a. Yes? Move left and go to step 2.
2b. No? Move right and go to step 1.

Martin Shobe

[toc] | [prev] | [next] | [standalone]

#73054

On Friday, October 16, 2015 at 11:13:25 AM UTC-5, Martin Shobe wrote:
> > 1. Finish within some amount of time f(N)
> >
> > 2. Within that indicated amount of time achieve a scenario where its state
> >     and the content of all tape locations that it will ever again examine
> >     are the same as they have been previously.
> 
> "That indicated amount of time" doesn't appear to have a reference.

Some function f(N) whose value depends sole upon N.

> When does the following do either 1 or 2? How large a tape do you need?
> 
> 1. Is the current position blank?
> 1a. Yes? Write one and go to step 2.
> 1b. No? Move right and go to step 1.
> 2. Is the current position 1?
> 2a. Yes? Move left and go to step 2.
> 2b. No? Move right and go to step 1.

Some definitions of a Turing machine specify that moving past the left
edge is forbidden; the set of programs that are computable with a single-
or double-ended tape are equivalent.

As for your program, if the tape extends to the left of the starting point,
any time the machine enters state 1, all of the locations that are ever
going to be visited will be blank.  If the tape were looped through a
scrubber, so that locations which passed out once side of the reader would
be cleared and presented to the other side, your program would be unaffected
even if the loop were nothing more than a single location.

[toc] | [prev] | [next] | [standalone]

#73074

supercat@casperkitty.com writes:

> On Friday, October 16, 2015 at 11:13:25 AM UTC-5, Martin Shobe wrote:
>> > 1. Finish within some amount of time f(N)
>> >
>> > 2. Within that indicated amount of time achieve a scenario where its state
>> >     and the content of all tape locations that it will ever again examine
>> >     are the same as they have been previously.
>> 
>> "That indicated amount of time" doesn't appear to have a reference.
>
> Some function f(N) whose value depends sole upon N.

Ah, I wondered that too.

>> When does the following do either 1 or 2? How large a tape do you need?
>> 
>> 1. Is the current position blank?
>> 1a. Yes? Write one and go to step 2.
>> 1b. No? Move right and go to step 1.
>> 2. Is the current position 1?
>> 2a. Yes? Move left and go to step 2.
>> 2b. No? Move right and go to step 1.
>
> Some definitions of a Turing machine specify that moving past the left
> edge is forbidden; the set of programs that are computable with a single-
> or double-ended tape are equivalent.
>
> As for your program, if the tape extends to the left of the starting point,
> any time the machine enters state 1, all of the locations that are ever
> going to be visited will be blank.

I don't think so.  The tape/state pairs are

  1, [ ]
  2, [1]
  2, [ ]1
  1, [1]
  1, 1[ ]
  2, 1[1]
  2, [1]1
  2, [ ]11
  1, [1]1
  1, 1[1]
  1, 11[ ]
  2, 11[1]

and so on.  At every point the locations that are going to be visited
will be mixture of blank and non-blank symbols (specifically a sequence
of consecutive '1' squares followed by a visit to a single blank).

> If the tape were looped through a
> scrubber, so that locations which passed out once side of the reader would
> be cleared and presented to the other side, your program would be unaffected
> even if the loop were nothing more than a single location.

I don't see how this answers Martin's question.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#73078

On Friday, October 16, 2015 at 3:48:26 PM UTC-5, Ben Bacarisse wrote:
> I don't think so.  The tape/state pairs are

Hmm... You're write.  Mea culpa.  Any program that can ever terminate will
use a finite amount of time and tape which are bounded by some function of
the program complexity, but programs which don't terminate can manipulate
an ever-expanding quantity of tape.

[toc] | [prev] | [next] | [standalone]

#72385

On Saturday, October 10, 2015 at 11:23:41 AM UTC+1, Anonymous Shadow wrote:
> (Sorry, this is probably off topic.)
> 
> It is my understanding, that to be Turing complete a language must have
> some form of recursion.
> 
It needs arbitrary depth recursion.

We can maybe do it by #including recursion.h from itself, #defining
A as T, #defining B as A, #undefing A, then using the concatenation
operator to #define A as B##T. Then we can terminate when A goes
to our result. 

[toc] | [prev] | [next] | [standalone]

#72390

On Sat, 2015-10-10, Anonymous Shadow wrote:
> (Sorry, this is probably off topic.)
>
> It is my understanding, that to be Turing complete a language must have
> some form of recursion.

Recursion or "while" loops.  You may need more things, but you do need
one of those.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#72413

On Saturday, October 10, 2015 at 5:23:41 AM UTC-5, Anonymous Shadow wrote:
> It is my understanding, that to be Turing complete a language must have
> some form of recursion.

It must have a means of revisiting output and state.  Recursion as such is
not necessary, but a Turing machine may simulate recursion by keeping a
"stack" as start of its state.

The amount of work required to preprocess any C program will be bounded
unless it makes use of either recursive #include files or can use
specially-formed file names to cause things to happen outside the
preprocessor [e.g. #include "/dev/tty3" might be able to accept arbitrary
text from a certian console during processsing.]

Since the C Standard does not specify exactly how file names are to be
processed, and neither requires compilers to support recursive usage of
the same C file, nor forbids applications from recursively using the
same file, it would be possible on some systems to get the preprocessor
into a loop, recursively including the same file over and over again.  In
practice, most preprocessors would probably quit after a fairly shallow
recursion depth, but in theory it would be possible to make a preprocessor
loop arbitrarily long.

On the other hand, I don't think there's any way to get around the fact
that even with the ability to scan code an unlimited number of times, there
is no way to define a macro in terms of the contents of another macro, and
the fact that macros are not expanded recursively and cannot contain
definitions for other macros, would seem to severely curtail what can be
done.

[toc] | [prev] | [next] | [standalone]

#72414

On Sunday, October 11, 2015 04:02 AM, supercat@casperkitty.com wrote:
> On Saturday, October 10, 2015 at 5:23:41 AM UTC-5, Anonymous Shadow wrote:
>> It is my understanding, that to be Turing complete a language must have
>> some form of recursion.
>
> It must have a means of revisiting output and state.  Recursion as such is
> not necessary, but a Turing machine may simulate recursion by keeping a
> "stack" as start of its state.
>
> The amount of work required to preprocess any C program will be bounded
> unless it makes use of either recursive #include files or can use
> specially-formed file names to cause things to happen outside the
> preprocessor [e.g. #include "/dev/tty3" might be able to accept arbitrary
> text from a certian console during processsing.]

#include "/dev/zero" on my GCC preprocessor it uses up all the memory
and crashes OS... could make a ``preprocessor bomb'' out of this.
>
> Since the C Standard does not specify exactly how file names are to be
> processed, and neither requires compilers to support recursive usage of
> the same C file, nor forbids applications from recursively using the
> same file, it would be possible on some systems to get the preprocessor
> into a loop, recursively including the same file over and over again.  In
> practice, most preprocessors would probably quit after a fairly shallow
> recursion depth, but in theory it would be possible to make a preprocessor
> loop arbitrarily long.

You are right, the same GCC preprocessor stops after exactly 200
recursions.

Here was the header file:

Hello World!
#include "stuff.h"

and then:

$ cpp -P stuff.h 2>/dev/null | wc -l
200
$ ...
>
> On the other hand, I don't think there's any way to get around the fact
> that even with the ability to scan code an unlimited number of times, there
> is no way to define a macro in terms of the contents of another macro, and
> the fact that macros are not expanded recursively and cannot contain
> definitions for other macros, would seem to severely curtail what can be
> done.

Searching around a bit I found a page which discusses this:
github.com/pfultz2/Cloak/wiki/Is-the-C-preprocessor-Turing-complete?

--
Daniel Roskams

[toc] | [prev] | [next] | [standalone]

#73013

On Saturday, October 10, 2015 at 3:23:41 AM UTC-7, Anonymous Shadow wrote:
> ...
> Can I have some sort of loop like this:
> 
> [ snip ]
> 
> By the way, this question is just out of curiosity, I am not
> planning to implement a programming language in the preprocessor!
> 
> --
> Daniel Roskams

Check this out, Daniel:

http://99-bottles-of-beer.net/language-c-c++-preprocessor-115.html

I don't really understand what Wim Rijnders is doing there, but it
 looks like it could help provide an answer to your question.

Mike B.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web