Trình biên dịch tiền xử lý C++ có được lập trình đầy đủ không?

Question

Tôi biết lập trình meta mẫu C++ là Turing-complete. Điều tương tự có giữ cho lập trình meta lập trình trước không?

Answer 1

No. Bộ tiền xử lý C++ không cho phép trạng thái không giới hạn. Bạn chỉ có một số hữu hạn các trạng thái bật/tắt, cộng với một chồng bao gồm. Điều này làm cho nó một automaton đẩy xuống, không phải là một máy turing (điều này bỏ qua cũng là một thực tế là tiền xử lý đệ quy bị hạn chế - nhưng như vậy là đệ quy mẫu). Tuy nhiên, nếu bạn bẻ cong các định nghĩa của mình một chút, điều này có thể bằng cách gọi bộ tiền xử lý nhiều lần - bằng cách cho phép bộ tiền xử lý tạo ra một chương trình gọi lại bộ tiền xử lý và vòng lặp bên ngoài, là indeed possible to make a turing machine with the preprocessor. Ví dụ được liên kết sử dụng C, nhưng nó phải thích ứng với C++ một cách dễ dàng.

Answer 2

Các macro tốt không trực tiếp mở rộng đệ quy, nhưng có nhiều cách chúng tôi có thể giải quyết vấn đề này.

Cách dễ nhất để thực hiện đệ quy trong bộ tiền xử lý là sử dụng biểu thức trì hoãn. Biểu thức trì hoãn là biểu thức yêu cầu quét nhiều hơn để mở rộng hoàn toàn:

#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 

Tại sao điều này quan trọng? Khi một macro được quét và mở rộng, nó sẽ tạo ra một bối cảnh vô hiệu hóa. Ngữ cảnh vô hiệu hóa này sẽ gây ra một mã thông báo, có nghĩa là macro hiện đang mở rộng, được tô màu xanh lam. Vì vậy, một khi màu xanh sơn của nó, vĩ mô sẽ không còn mở rộng. Đây là lý do tại sao các macro không mở rộng đệ quy. Tuy nhiên, một bối cảnh vô hiệu hóa chỉ tồn tại trong một lần quét, do đó bằng cách trì hoãn việc mở rộng, chúng tôi có thể ngăn các macro của chúng tôi trở thành màu xanh sơn. Chúng tôi sẽ chỉ cần áp dụng nhiều lần quét hơn cho biểu thức. Chúng ta có thể làm điều đó bằng EVAL macro này:

#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__ 

Bây giờ nếu chúng ta muốn thực hiện một REPEAT vĩ mô sử dụng đệ quy, đầu tiên chúng ta cần một số tăng và sụt lần các nhà khai thác để xử lý tình trạng:

#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 

Tiếp theo chúng ta cần thêm một vài macro để thực hiện logic:

#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) 

Bây giờ với tất cả các macro này, chúng tôi có thể viết macro đệ quy REPEAT. Chúng tôi sử dụng macro REPEAT_INDIRECT để tự quay lại chính nó. Điều này ngăn macro bị sơn màu xanh, vì nó sẽ mở rộng trên một lần quét khác (và sử dụng ngữ cảnh vô hiệu hóa khác). Chúng tôi sử dụng OBSTRUCT tại đây, điều này sẽ trì hoãn việc mở rộng hai lần. Điều này là cần thiết vì có điều kiện WHEN áp dụng một lần quét.

#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 

Ví dụ này được giới hạn trong 10 lần lặp lại do giới hạn của bộ đếm. Giống như một bộ đếm lặp lại trong máy tính sẽ bị giới hạn bởi bộ nhớ hữu hạn. Nhiều bộ đếm lặp lại có thể được kết hợp với nhau để giải quyết hạn chế này, giống như trong máy tính. Hơn nữa, chúng ta có thể định nghĩa một macro FOREVER:

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

này sẽ cố gắng ra ? mãi mãi, nhưng cuối cùng sẽ dừng lại vì không có nhiều quét được áp dụng. Bây giờ câu hỏi đặt ra là, nếu chúng ta cho nó một số lần quét vô hạn thì thuật toán này có hoàn thành không? Điều này được gọi là vấn đề tạm dừng, và sự hoàn chỉnh của Turing là cần thiết để chứng minh tính không thể giải quyết của vấn đề dừng.Như bạn có thể thấy, bộ tiền xử lý có thể hoạt động như một ngôn ngữ hoàn chỉnh Turing, nhưng thay vì bị giới hạn trong bộ nhớ hữu hạn của một máy tính, nó được thay thế giới hạn bởi số lần quét hữu hạn được áp dụng.