After discovering the Boost preprocessor's capabilities I found myself wondering: Is the C99 preprocessor Turing complete?
If not, what does it lack to not qualify?
+3
A:
It's Turing complete within limits (as are all computers since they don't have infinite RAM). Check out the kinds of things you can do with Boost Preprocessor.
Edit in response to question edits:
The main limitation on Boost is the maximum macro expansion depth which is compiler-specific. Also, the macros that implement recursion (FOR..., ENUM..., etc.) aren't truly recursive, they just appear that way thanks to a bunch of near-identical macros. In the big picture, this limitation is no different than having a maximum stack size in an actually recursive language.
The only two things that are really necessary for limited Turing-completeness (Turing-compatibility?) are iteration/recursion (equivalent constructs) and conditional branching.
Cogwheel - Matthew Orlando
2010-06-28 22:52:32
hi. That was actually what prompted my question, I have been using preprocessor for a while.
aaa
2010-06-28 22:54:26
Erp.. yeah, go me reading the question ><
Cogwheel - Matthew Orlando
2010-06-28 22:55:05
digging around in BOOST_PP's source code is the best way to figure out how it's done.
Cogwheel - Matthew Orlando
2010-06-28 22:55:33
I *believe* that macros can't do recursion. Boost just seems to simulate them by having hardcoded macros named like `macro0`, `macro1` .. `macro255`. I'm not sure whether that counts as "turing complete". The preprocessor has an explicit rule that forbids going from `macro255` back to `macro0` :( It seems like trying to build a verifyer for fully parenthesized expressions using a finite state automaton. It can work for a limited number of parentheses, but that's not a general verifyer anymore. I've no clue about boost.pp inner workings though, so i could likely be wrong on this.
Johannes Schaub - litb
2010-06-28 23:23:45
@Johannes Schaub: yes you're right. I had confused that with vararg when i wrote this initially. I updated the answer.
Cogwheel - Matthew Orlando
2010-06-28 23:30:03
@Johannes: The chaos preprocessor doesn't have any macros like that. Check it out here: http://sourceforge.net/projects/chaos-pp/
Joe D
2010-08-24 21:01:24
+7
A:
Here is an example of abusing the preprocessor to implement a Turing machine. Note that an external build script is needed to feed the preprocessor's output back into its input, so the preprocessor in and of itself isn't Turing complete. Still, it's an interesting project.
bta
2010-06-28 23:10:43