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

Groups > comp.lang.c > #72414

Re: Is the C preprocessor turing-complete?

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web