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?
boost-preprocessorc-preprocessortheoryturing-complete
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?
Best Answer
Well macros don't directly expand recursively, but there are ways we can work around this.
The easiest way of doing recursion in the preprocessor is to use a deferred expression. A deferred expression is an expression that requires more scans to fully expand:
Why is this important? Well when a macro is scanned and expanding, it creates a disabling context. This disabling context will cause a token, that refers to the currently expanding macro, to be painted blue. Thus, once its painted blue, the macro will no longer expand. This is why macros don't expand recursively. However, a disabling context only exists during one scan, so by deferring an expansion we can prevent our macros from becoming painted blue. We will just need to apply more scans to the expression. We can do that using this
EVAL
macro:Now if we want to implement a
REPEAT
macro using recursion, first we need some increment and decrement operators to handle state:Next we need a few more macros to do logic:
Now with all these macros we can write a recursive
REPEAT
macro. We use aREPEAT_INDIRECT
macro to refer back to itself recursively. This prevents the macro from being painted blue, since it will expand on a different scan(and using a different disabling context). We useOBSTRUCT
here, which will defer the expansion twice. This is necessary because the conditionalWHEN
applies one scan already.Now this example is limited to 10 repeats, because of limitations of the counter. Just like a repeat counter in a computer would be limited by the finite memory. Multiple repeat counters could be combined together to workaround this limitation, just like in a computer. Furthermore, we could define a
FOREVER
macro:This will try to output
?
forever, but will eventually stop because there are no more scans being applied. Now the question is, if we gave it an infinite number of scans would this algorithm complete? This is known as the halting problem, and Turing completeness is necessary to prove the undecidability of the halting problem. So as you can see, the preprocessor can act as a Turing complete language, but instead of being limited to the finite memory of a computer it is instead limited by the finite number of scans applied.