Chúng tôi biết rằng C++ template metaprogramming is Turing complete, nhưng preprocessor metaprogramming is not.Tính toán dựa trên constexpr Turing có hoàn thành không?
C++ 11 cho chúng ta một dạng lập trình meta mới: tính toán các hàm constexpr. Đây có phải là dạng tính toán Turing-complete? Tôi nghĩ rằng kể từ khi đệ quy và toán tử có điều kiện (? :) được cho phép trong các hàm constexpr, nó sẽ là, nhưng tôi muốn một người có chuyên môn hơn để xác nhận.
tl; dr: constexpr trong C++ 11 không hoàn chỉnh, do lỗi trong đặc tả ngôn ngữ, nhưng lỗi đó đã được giải quyết trong các bản thảo sau của tiêu chuẩn và đã thực hiện sửa lỗi .
constexpr, như được chỉ định trong tiêu chuẩn quốc tế ISO C++ 11, không hoàn thành Turing. bằng chứng Phác thảo: Mỗi constexpr chức năng kết quả
f 's (hoặc không chấm dứt) trên một trình tự cụ thể của các đối số, a..., được xác định duy nhất bởi các giá trị của a...[basic.types]p10 là một trong hai:
a... mà f có thể nhận được là hữu hạn, vì vậy bất kỳ hữu hạn mô tả constexpr hệ thống là một máy trạng thái hữu hạn, và do đó không Turing hoàn tất.Tuy nhiên, kể từ khi xuất bản tiêu chuẩn C++ 11, tình hình đã thay đổi.
Vấn đề được mô tả trong câu trả lời của Johannes Schaub là std::max() and std::min() not constexpr được báo cáo cho ủy ban tiêu chuẩn hóa C++ là vấn đề cốt lõi 1454. Tại cuộc họp WG21 tháng 2 năm 2012, chúng tôi quyết định đây là lỗi trong tiêu chuẩn và độ phân giải đã chọn bao gồm khả năng để tạo các giá trị của các kiểu lớp với con trỏ hoặc các thành viên tham chiếu chỉ định thời gian. Điều này cho phép một số lượng thông tin vô biên được tích lũy và xử lý bởi một hàm constexpr và đủ để thực hiện đánh giá Turing-complete (giả định rằng việc triển khai hỗ trợ đệ quy đến độ sâu không bị chặn).
Để chứng minh Turing-đầy đủ của constexpr cho một trình biên dịch mà thực hiện các giải pháp đề xuất vấn đề cốt lõi 1454, tôi đã viết một Turing máy mô phỏng cho bộ kiểm tra kêu vang của:
http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp
phiên bản Trunk của cả g ++ và clang thực hiện độ phân giải của vấn đề cốt lõi này, nhưng việc thực hiện g ++ hiện không thể xử lý mã này.
Hãy xem chúng. Tôi biên soạn các ví dụ và họ làm việc trong GCC 4.6: Compile-time computations, Parsing strings at compile-time - Part I, Parsing strings at compile-time - Part II
+1: OMG bây giờ tôi thấy những gì mới điên rồ/khiếp sợ làm cho có thể bởi constexpr họ đã nói về trong hội nghị hội nghị GoingNative O__O; – Klaim
Phân tích cú pháp chuỗi là nơi điện toán dịch chuyển trở nên đẹp. – ex0du5
Có khả năng đọc một chuỗi ký tự không có nghĩa là Turing hoàn thành (ví dụ: nó không chứng tỏ làm thế nào để viết trên một băng vô hạn (không bán vô hạn)). – kennytm
Nếu chúng ta lấy trong các hạn chế tài khoản của máy tính thực - ví dụ như bộ nhớ hữu hạn và giá trị hữu hạn các MAX_INT - sau đó, tất nhiên, constexpr (và cũng có thể toàn bộ C++) không phải là Turing-complete. Tuy nhiên, nếu chúng ta sẽ loại bỏ hạn chế này - ví dụ, nếu chúng ta sẽ nghĩ về int như một số nguyên dương hoàn toàn arbitary - thì có, phần constexpr của C++ sẽ được Turing hoàn thành. Nó rất dễ dàng để thể hiện bất kỳ chức năng đệ quy một phần nào.
0, S (n) = n + 1 và bộ chọn I_n^m (x_1, ..., x_n) = x_m và chồng chất rõ ràng có thể được biểu diễn bằng cách sử dụng constexpr.
đệ quy nguyên thủy có thể được thực hiện nó theo cách thẳng:
constexpr int h(int x1, ..., int xn, int y) {
return (xn == 0) ? f(x1, ..., xn) : g(x1, ..., xn, y-1, h(x1, ..., xn, y-1));
}
Và đối với đệ quy một phần chúng ta cần một thủ thuật đơn giản:
constexpr int h(int x1, ... int xn, int y = 0) {
return (f(x1, ... xn, y) == 0) ? y : h(x1, ..., xn, y+1);
}
Vì vậy, chúng tôi nhận được bất kỳ chức năng đệ quy một phần như một constexpr.
Thú vị! Nếu tôi hiểu một cách chính xác, sự khác biệt đó dựa trên thực tế là một chương trình chỉ có thể có một số lượng hữu hạn các đối tượng của thời gian lưu trữ tĩnh, nhưng nó có thể có một số lượng thời gian vô hạn tiềm tàng. Bạn có thể giải thích lý do tại sao? – HighCommander4
@ HighCommander4 Mỗi đối tượng của thời gian lưu trữ tĩnh được giới thiệu bởi một khai báo trong mã nguồn (trong đó chỉ có một số hữu hạn, và mỗi giới thiệu chỉ một số hữu hạn các đối tượng địa chỉ riêng), trong khi đệ quy không giới hạn có thể giới thiệu một số không bị chặn của thời gian. Quan điểm này chỉ áp dụng cho máy trừu tượng C++ - mỗi lần triển khai thực sự cuối cùng sẽ đạt đến một dạng giới hạn tài nguyên nào đó, vì vậy vẫn có một số ràng buộc hữu hạn (nhưng thường không rõ). –
Làm thế nào rất Tóm tắt :-) –