Hacker News new | past | comments | ask | show | jobs | submit login

So the expression of unbounded recursion can be expressed like this:

    #define EMPTY()
    #define DEFER(id) id EMPTY()

    #define FOREVER() \
        ? \
        DEFER(FOREVER_INDIRECT) () ()
    #define FOREVER_INDIRECT() FOREVER
This will print out `?` infinitely. Here is the machinery to evaluate the expression:

    #define EVAL(...) A(A(A(__VA_ARGS__)))
    #define A(...) B(B(B(__VA_ARGS__)))
    #define B(...) C(C(C(__VA_ARGS__)))
    #define C(...) D(D(D(__VA_ARGS__)))
    #define D(...) E(E(E(__VA_ARGS__)))
    #define E(...) __VA_ARGS__

    EVAL(FOREVER())
Which will expand to something like this:

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? FOREVER_INDIRECT () ()
Well at the end we see `FOREVER_INDIRECT () ()` which means the algorithm can expand further, so we could just apply more scans:

    EVAL(EVAL(FOREVER()))
And we get more `?`. And we didn't have to change the expression of the algorithm just the machinery to evaluate it.

This is why I say the C preprocessor can act as Turing-complete, because the expression and machinery, while separate, is both in the language itself. This is different than BlooP, which the only possible way to express Turing completeness is through an external source(such as an input file).

Of course, for all practical purposes, the C preprocessor is near Turing-complete enough. The whole goal of the preprocessor is to output a file, we don't need it run indefinitely. We can express almost any useful algorithm, and if it reaches the recursion limit, we just simply apply more scans.




This is why I say the C preprocessor can act as Turing-complete, because the expression and machinery, while separate, is both in the language itself.

Unfortunately, "can act as Turing-complete" is not a well defined concept. It is clearly not the same thing, and the distinction is important. Consider, as pointed out elsewhere in this thread, that we can always solve the halting problem for a C preprocessor program. We're in danger of violent agreement, though: I think we agree on the main points, just perhaps not on their relevance.

Since we've gone this far down the rabbit hole, I'd like to point out that C++ templates are Turing complete: http://netvor.sk/~umage/docs/3rdparty/C++%20Templates%20are%...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: