2

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'

cwallenpoole
  • 79,954
  • 26
  • 128
  • 166
  • (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 Sep 06 '11 at 14:00
  • 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 Sep 06 '11 at 14:01
  • 1
    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. –  Sep 06 '11 at 14:02
  • @delnan So, Lispers were deceptive then? (Can't remember if this was Paul Graham or Conrad Barski who made the assertion) – cwallenpoole Sep 06 '11 at 14:04
  • 7
    "yet another point where Lispers are over-zealous" Yet _another_ sweeping generalisation. C++ers _always_ make sweeping generalisations. – Seth Carnegie Sep 06 '11 at 14:05
  • 1
    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](http://stackoverflow.com/questions/tagged/homoiconicity), at least it usually is when that topic comes up... –  Sep 06 '11 at 14:05
  • @Seth I am not claiming that they are any more or less zealous than any other entity. C and C++ proponents can be equally zealous. Even in grouping them I realize that I do, in fact, raise the very serious risk of being told that they are not the same language (though, if I am not mistaken, in macros the syntax is almost exactly the same). – cwallenpoole Sep 06 '11 at 14:07
  • @Oli Macros aren’t Turing complete? I’m not convinced. Boost.PP certainly seems to achieve a lot. – Konrad Rudolph Sep 06 '11 at 14:11
  • @Konrad: The preprocessor doesn't have any looping, and recursion (as in, macro expansion in text that resulted from macro expansion) is too limited for turing completeness. Boost is likely using tricks and lots and lots of different macros to achive enough for *most* usecases without turing completeness. Nobody said you need turing completeness to do some useful useful (SQL isn't turing complete!). –  Sep 06 '11 at 14:15
  • @delnan OK, I’ve done some research, see my answer below. “Boost is likely using tricks” – oh yes they are, but there’s nothing wrong with that. – Konrad Rudolph Sep 06 '11 at 14:18

2 Answers2

4

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.

Community
  • 1
  • 1
Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • As the top answer on that question states, the PP itself isn't turing complete, it needs to build script to make it run several times. I guess this is because the PP refuses to expand recursive macros. –  Sep 06 '11 at 14:19
3

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 :-).

thiton
  • 35,651
  • 4
  • 70
  • 100