From: Jimka
Subject: c macros -- turing complete?
Date: 
Message-ID: <1162127623.687286.100560@i42g2000cwa.googlegroups.com>
I'd like to make a claim in an article i'm writing:

The lisp macro facility is Turing complete, whereas the C macro system
is not.

Does anyone know whether that is a correct statement?

From: Alex Mizrahi
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <4544bcda$0$49205$14726298@news.sunsite.dk>
(message (Hello 'Jimka)
(you :wrote  :on '(29 Oct 2006 05:13:43 -0800))
(

 J> I'd like to make a claim in an article i'm writing:

 J> The lisp macro facility is Turing complete, whereas the C macro system
 J> is not.

i suspect C preprocessor is turing-complete. you can get recursion/looping 
via include, and change some state.
here's a link:

http://www.ioccc.org/2001/herrmann1.hint

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity") 
From: Frank Buss
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <18ojlhl9svwe8$.76a9xuynx4mw$.dlg@40tude.net>
Alex Mizrahi wrote:

> i suspect C preprocessor is turing-complete. you can get recursion/looping 
> via include, and change some state.
> here's a link:
> 
> http://www.ioccc.org/2001/herrmann1.hint

Nice link. If you read this page you can see that the C preprocessor is not
turing-complete, if you don't use additional external programs, like the
build script used on the page, which feeds the output as new input to the
preprocessor, until the output doesn't change anymore.

-- 
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Pascal Bourguignon
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <87slh7gk9n.fsf@thalassa.informatimago.com>
"Jimka" <·····@rdrop.com> writes:

> I'd like to make a claim in an article i'm writing:
>
> The lisp macro facility is Turing complete, whereas the C macro system
> is not.
>
> Does anyone know whether that is a correct statement?

If cpp is not Turing Complete, it's very close...

You can do loops including the current file,
you can change the state with #define and #undef,
and you can test with #ifdef and #if.


Unfortunately, #define cannot compute:
#define a 42
#define a ((a)+1)
doesn't make a = 43
Theorically, you can test with #if a = 43, and macros are expanded here,
but since a is defined in terms of a, you don't get ((42)+1) but ((a)+1)
and this is not equal to 43, but to 1.

And #if can test only integer values, not strings, so you cannot fall
back to even simple string processing.

Perhaps we can do something with just #define and #ifdef, but it's
harder to test for equality.



Finally, if may hit the very small limits there are in cpp, like 200
levels of #include max, etc.
Is a computer with so little memory you cannot even implement a TM in
it still TC, even ignoring the "unlimited tape length"?

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

CAUTION: The mass of this product contains the energy equivalent of
85 million tons of TNT per net ounce of weight.
From: Brian Downing
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <P-2dnbocrI8untrYnZ2dnUVZ_oWdnZ2d@insightbb.com>
In article <··············@thalassa.informatimago.com>,
Pascal Bourguignon  <···@informatimago.com> wrote:
> You can do loops including the current file,

You can do loops even without including the current file:

    #include "order/interpreter.h"

    ORDER_PP
    (8let((8B, 8fn(8N,
                   8cond((8greater(8N, 1),
                          8separate(8N, 8quote(bottles)))
                         (8equal(8N, 1),
                          8quote(1 bottle))
                         (8else,
                          8quote(no more bottles))))),
          8for_each_in_range
          (8fn(8N,
               8print(8ap(8B, 8N) (of beer on the wall,) 8space
                      8ap(8B, 8N) (of beer,) 8space
                      (take one down, pass it around,) 8space
                      8ap(8B, 8dec(8N)) (of beer on the wall.))),
           100, 1)))

That is a valid preprocessor program that emits tokens printing the
lyrics to "99 bottles of beer on the wall", on one line of course.

It is written in the "Order" preprocessor language.  From the
documentation:

    Order is a complete programming language designed to be interpreted
    using the C preprocessor.  Rather than being a general purpose
    language, Order is a metalanguage that can be used to generate
    sequences of preprocessing tokens.

    Order is a high-level functional language with call-by-value
    semantics, providing first-class anonymous functions with lexically
    scoped variables and supporting partial application of functions. The
    Order interpreter is implemented in continuation passing style
    and is fully tail recursive. Order is a reflective language
    providing first class continuations, first class environments and an
    eval-function. Memory management in Order is implicit. Order provides
    arbitrary-precision arithmetic on natural numbers, a comprehensive
    set of primitive and higher-order functions for an aggregate data
    type called sequence and more.

For more, start at the (well-documented) 99 bottles example at:

http://chaos-pp.cvs.sourceforge.net/chaos-pp/order-pp/example/bottles.c?revision=1.10&view=markup

A far more pleasant language for "metaprogramming" than C++ templates
if I do say so myself.

Now back to your regularly scheduled Lisp where we don't have to worry
about crap like this.  :-)

-bcd
-- 
*** Brian Downing <bdowning at lavos dot net> 
From: Stefan Scholl
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <0T3j5aiaIm4Nv8%stesch@parsec.no-spoon.de>
Jimka <·····@rdrop.com> wrote:
> The lisp macro facility is Turing complete, whereas the C macro system
> is not.
> Does anyone know whether that is a correct statement?

Maybe the guys in the C newsgroups? This is the Lisp newsgroup.
From: Rob Thorpe
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <1162311556.655126.23690@m7g2000cwm.googlegroups.com>
Jimka wrote:
> I'd like to make a claim in an article i'm writing:
>
> The lisp macro facility is Turing complete, whereas the C macro system
> is not.
>
> Does anyone know whether that is a correct statement?

Common Lisp's macro facility is Turing complete.

Standard C++ with it's macro pre-processor is Turing complete in that
any computation can be done at compile time.  It does require C++ & the
pre-processor to do this though.

The standard C pre-processor isn't Turing complete, but many real
pre-processors are due to extra features.

All AFAIK.  As Stefan mentions you would get a better answer in
comp.lang.c.  Asking in comp.std.c might also be interesting.
From: Kaz Kylheku
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <1162326497.906424.132720@i42g2000cwa.googlegroups.com>
Jimka wrote:
> I'd like to make a claim in an article i'm writing:
>
> The lisp macro facility is Turing complete, whereas the C macro system
> is not.

Thanks for the warning. I will go out of my way to avoid reading your
article, profoundly interesting as it may be to some people.
From: Jimka
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <1162329411.646348.185850@f16g2000cwb.googlegroups.com>
I'd guess the that fact that you won't read the article is even less
interesting
to more people than the article itself.

Kaz Kylheku wrote:

> Thanks for the warning. I will go out of my way to avoid reading your
> article, profoundly interesting as it may be to some people.
From: Kaz Kylheku
Subject: Re: c macros -- turing complete?
Date: 
Message-ID: <1162343290.129921.320590@f16g2000cwb.googlegroups.com>
Jimka wrote:
> I'd guess the that fact that you won't read the article is even less
> interesting
> to more people than the article itself.

True, but that uninteresting fact has at least the virtue of brevity.