C99 전 처리기 Turing이 완료 되었습니까?

C99 전 처리기 Turing이 완료 되었습니까?

---

Boost 전 처리기의 기능을 발견 한 후 저는 궁금해했습니다. C99 전처리 기가 튜링이 완성 되었나요?

그렇지 않다면 자격이없는 것은 무엇입니까?

---

다음 은 튜링 머신을 구현하기 위해 전처리기를 남용하는 예입니다. 전 처리기의 출력을 입력으로 다시 공급하려면 외부 빌드 스크립트가 필요하므로 전 처리기 자체가 튜링이 완전하지 않습니다. 그래도 흥미로운 프로젝트입니다.

이전에 연결된 프로젝트에 대한 설명에서 :

적어도 프로그램이 한 번만 전처리 된 경우 에는 전처리 기가 튜링 완료 가 아닙니다 . 프로그램이 자신을 포함하도록 허용 된 경우에도 마찬가지입니다. (이유는 주어진 프로그램에 대해 전처리 기가 유한 한 수의 상태와 파일이 포함 된 위치로 구성된 스택을 가지고 있기 때문입니다. 이것은 단지 푸시 다운 자동화 일뿐입니다.)

Paul Fultz II의 대답은 전처리 기가 얻을 수 있다고 생각했던 것보다 상당히 인상적이며 확실히 가깝지만 진정한 Turing 기계는 아닙니다. C 전처리 기는 무한한 메모리와 시간이 있더라도 Turing 기계처럼 임의의 프로그램을 실행하지 못하도록하는 특정 제한이 있습니다. C 스펙 의 섹션 5.2.4.1은 C 컴파일러에 대해 다음과 같은 최소 한계를 제공합니다.

• 전체 표현식 내에서 괄호로 묶인 63 개의 중첩 수준
• 내부 식별자 또는 매크로 이름의 63 개의 중요한 초기 문자
• 하나의 전처리 번역 단위에 동시에 정의 된 4095 매크로 식별자
• 논리 소스 행의 4095 자

아래의 카운터 메커니즘에는 값당 매크로 정의가 필요하므로 매크로 정의 제한은 루프 할 수있는 횟수를 제한합니다 ( EVAL(REPEAT(4100, M, ~))정의되지 않은 동작을 생성 함). 이것은 본질적으로 실행할 수있는 프로그램의 복잡성을 제한합니다. 다중 레벨 확장의 중첩 및 복잡성도 다른 한계 중 하나에 도달 할 수 있습니다.

이것은 "무한 메모리"제한과 근본적으로 다릅니다. 이 경우 사양은 특히 표준을 준수하는 C 컴파일러가 무한 시간, 메모리 등이 있더라도 이러한 제한을 준수하는 데만 필요하다고 명시합니다. 이러한 제한을 초과하는 입력 파일은 예측할 수 없거나 정의되지 않은 방식으로 처리 될 수 있습니다. (또는 완전히 거부 됨). 일부 구현에는 더 높은 제한이 있거나 전혀 제한이 없을 수 있지만 이는 표준의 일부가 아닌 "구현 특정"으로 간주됩니다. Paul Fultz II의 방법을 사용하여 특정 컴파일러 구현 에서 Turing 머신과 같은 것을 구현할 수 있습니다.한정된 제한은 없지만 "임의의 표준을 준수하는 C99 전 처리기에서이 작업을 수행 할 수 있습니까?"라는 일반적인 의미에서 대답은 '아니요'입니다. 여기서 한계는 언어 자체에 내장되어 있으며 무한한 컴퓨터를 구성 할 수 없다는 단순한 부작용이 아니기 때문에 튜링의 완전성을 깨뜨립니다.

---

잘 매크로는 재귀 적으로 직접 확장되지 않지만,이를 해결할 수있는 방법이 있습니다.

전 처리기에서 재귀를 수행하는 가장 쉬운 방법은 지연된 표현식을 사용하는 것입니다. 지연된 표현식은 완전히 확장하기 위해 더 많은 스캔이 필요한 표현식입니다.

#define EMPTY()
#define DEFER(id) id EMPTY()
#define OBSTRUCT(...) __VA_ARGS__ DEFER(EMPTY)()
#define EXPAND(...) __VA_ARGS__

#define A() 123
A() // Expands to 123
DEFER(A)() // Expands to A () because it requires one more scan to fully expand
EXPAND(DEFER(A)()) // Expands to 123, because the EXPAND macro forces another scan

이것이 왜 중요한가요? 매크로가 스캔되고 확장되면 비활성화 컨텍스트가 생성됩니다. 이 비활성화 컨텍스트는 현재 확장중인 매크로를 참조하는 토큰이 파란색으로 표시되도록합니다. 따라서 파란색으로 칠해지면 매크로가 더 이상 확장되지 않습니다. 이것이 매크로가 재귀 적으로 확장되지 않는 이유입니다. 그러나 비활성화 컨텍스트는 한 번의 스캔 동안에 만 존재하므로 확장을 연기하면 매크로가 파란색으로 칠 해지는 것을 방지 할 수 있습니다. 표현식에 더 많은 스캔을 적용하면됩니다. 다음 EVAL매크로 를 사용하여 수행 할 수 있습니다 .

#define EVAL(...)  EVAL1(EVAL1(EVAL1(__VA_ARGS__)))
#define EVAL1(...) EVAL2(EVAL2(EVAL2(__VA_ARGS__)))
#define EVAL2(...) EVAL3(EVAL3(EVAL3(__VA_ARGS__)))
#define EVAL3(...) EVAL4(EVAL4(EVAL4(__VA_ARGS__)))
#define EVAL4(...) EVAL5(EVAL5(EVAL5(__VA_ARGS__)))
#define EVAL5(...) __VA_ARGS__

이제 REPEAT재귀를 사용하여 매크로 를 구현 하려면 먼저 상태를 처리하기 위해 증가 및 감소 연산자가 필요합니다.

#define CAT(a, ...) PRIMITIVE_CAT(a, __VA_ARGS__)
#define PRIMITIVE_CAT(a, ...) a ## __VA_ARGS__

#define INC(x) PRIMITIVE_CAT(INC_, x)
#define INC_0 1
#define INC_1 2
#define INC_2 3
#define INC_3 4
#define INC_4 5
#define INC_5 6
#define INC_6 7
#define INC_7 8
#define INC_8 9
#define INC_9 9

#define DEC(x) PRIMITIVE_CAT(DEC_, x)
#define DEC_0 0
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC_4 3
#define DEC_5 4
#define DEC_6 5
#define DEC_7 6
#define DEC_8 7
#define DEC_9 8

다음으로 로직을 수행하려면 몇 가지 매크로가 더 필요합니다.

#define CHECK_N(x, n, ...) n
#define CHECK(...) CHECK_N(__VA_ARGS__, 0,)

#define NOT(x) CHECK(PRIMITIVE_CAT(NOT_, x))
#define NOT_0 ~, 1,

#define COMPL(b) PRIMITIVE_CAT(COMPL_, b)
#define COMPL_0 1
#define COMPL_1 0

#define BOOL(x) COMPL(NOT(x))

#define IIF(c) PRIMITIVE_CAT(IIF_, c)
#define IIF_0(t, ...) __VA_ARGS__
#define IIF_1(t, ...) t

#define IF(c) IIF(BOOL(c))

#define EAT(...)
#define EXPAND(...) __VA_ARGS__
#define WHEN(c) IF(c)(EXPAND, EAT)

Now with all these macros we can write a recursive REPEAT macro. We use a REPEAT_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 use OBSTRUCT here, which will defer the expansion twice. This is necessary because the conditional WHEN applies one scan already.

#define REPEAT(count, macro, ...) \
    WHEN(count) \
    ( \
        OBSTRUCT(REPEAT_INDIRECT) () \
        ( \
            DEC(count), macro, __VA_ARGS__ \
        ) \
        OBSTRUCT(macro) \
        ( \
            DEC(count), __VA_ARGS__ \
        ) \
    )
#define REPEAT_INDIRECT() REPEAT

//An example of using this macro
#define M(i, _) i
EVAL(REPEAT(8, M, ~)) // 0 1 2 3 4 5 6 7

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:

#define FOREVER() \
    ? \
    DEFER(FOREVER_INDIRECT) () ()
#define FOREVER_INDIRECT() FOREVER
// Outputs question marks forever
EVAL(FOREVER())

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.

---

To be Turing complete, one needs to define recursion that may never finish -- one calls them mu-recursive operator.

To define such an operator one needs an infinite space of defined identifiers (in case that each identifier is evaluated a finite number of times), as one cannot know a priori an upper limit of time in which the result is found. With a finite number of operators inside the code one needs to be able to check an unlimited number of possibilities.

So this class of functions cannot be computed by the C preprocessor because in C preprocessor there is a limited number of defined macros and each one is expanded only once.

The C preprocessor uses the Dave Prosser's algorithm (written by Dave Prosser for the WG14 team in 1984). In this algorithm a macro is painted blue in the moment of the first expansion; a recursive call (or mutual recursive call) does not expand it, as it has already been painted blue in the moment when the first expansion starts. So with a finite number of preprocessing lines it is impossible to make infinite calls of functions(macros), which characterizes the mu-recursive operators.

The C preprocessor can compute only sigma-recursive operators .

For details see the course of computation of Marvin L. Minsky (1967) -- Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J. etc.

---

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.

참고URL : https://stackoverflow.com/questions/3136686/is-the-c99-preprocessor-turing-complete