What Turing complete macro languages are available for C/C++

2
votes

Preamble

One of the major points which Lispers claim as a bonus over more "mainstream" languages is that the macro language is actually Turing complete (I cannot recall if this was Paul Graham in On Lisp or if it was Conrad Barski in Land Of Lisp)1, and to an outsider, at least, this seems true -- pre-processor directives in C/C++ do not seem to be Turing complete (honestly, they feel like more of an annotation syntax).

And now... the question

  1. Is this an accurate assessment? Having only dabbled in C, this strikes me as yet another point where Lispers are over-zealous
  2. Are there any Turing complete macro languages (for C/C++) which are worth noting?
    • Are there any which are in the works or abortive attempts which might be worth looking for in the future?
    • I have heard that Python can now serve as a backbone to compile C/C++ (implying that Python can be used to write the macros), but I have not seen confirmation of this. Is it true?

(I will refrain from asking the opinion questions like "what are the best...")

1. Both are really good books by the way, just sayin'

2
c++ccompiler-constructionmacros
(you may wish to pause for a minute to consider the humor in the Lisper position -- Lisp comes from the Church/McCarthy school and yet it is talking about Turing completeness (which is not to say that the two are mutually exclusive! Simply that the origins portray a cross-standard.)) – cwallenpoole
What do you mean by "macro languages"? The only macros in C and C++ are #define macros, and templates. Templates are Turing-complete, #define macros are not. If you're just talking about code generation, then obviously, you can generate C/C++ code from an application written in any language. – Oliver Charlesworth
C++ templates are turing complete. They're just really hard to work with and can't create and manipulate code in the same way lisp can manipulate lisp code. – user395760
"yet another point where Lispers are over-zealous" Yet another sweeping generalisation. C++ers always make sweeping generalisations. – Seth Carnegie
They wouldn't be the first to "forget" some fact when comparing their favourite language with another. But before you raise the accusation, you may want to check whether they were actually talking about C++ and not explicitly about the preprocessor. Plus, I'm pretty sure the main point isn't turing completeness but homoiconicity, at least it usually is when that topic comes up... – user395760

2 Answers

4
votes

C macros are in fact Turing complete, if processed more than once. Check out this related question and in particular the Turing machine implementation linked to in the accepted answer.

But yes, this is cheating. The solution used there strongly implies that C macros really aren’t Turing complete.

3
votes

The assessment that the C preprocessor is not Turing-complete is as accurate as pointless. Any computation that is too complex for the C preprocessor is very likely to be too hard to understand if formulated in preprocessor (e.g. code text manipulation) terms and should be coded.

C++ templates are the established successor to preprocessor magic, and a little easier to understand than those. So, the Lispers are again perfectly right and missing the point, just as always :-).