Re: c macros -- turing complete?

"Jimka" <jimka@xxxxxxxxx> 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.
.

Relevant Pages

  • Re: three macro systems
    ... You can escape from the Turing ... I agree that explicit rules are needed. ... This will be the case for an implementation of one of the other macro ... SYNTAX-RULES in terms of SYNTAX-CASE already exist, which I don't think is a ...
    (comp.lang.lisp)
  • Re: macros
    ... 2- the use of cpp macro introduce weird syntactic shifts. ... and the characters that can be included as ... NEW-LINES inside macro arguments). ... but it's rather like trying to build the Empire State Building ...
    (comp.lang.lisp)
  • Re: To bean or not to bean
    ... The TEST_macro uses it. ... Those who bust on the CPP overlook CC, ... don't find a language that does not balance "" and operators, ... >> invited to write db, with all these features, in your favorite ...
    (comp.lang.cpp)
  • Macro trouble
    ... I am trying to create macro in VC7.1 to instert blank .h and .cpp ... selecting File->Add New Item and choosing header file ... macro recording. ...
    (microsoft.public.vc.ide_general)
  • Re: To bean or not to bean
    ... >> and the Cpp than he does. ... > Putting them all together yields this killer trace macro: ... > invited to write db, with all these features, in your favorite language. ... the time has come to be serious about macro-free C++ programming." ...
    (comp.lang.cpp)