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?
(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")
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
"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.
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>
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.
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.
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.
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.
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.