Tại sao xác định xem một hàm có khó khăn không?

Question

Tôi đã có mặt tại hội nghị Ngày của nhà phát triển StackOverflow ngày hôm qua, và một trong những diễn giả đã nói về Python. Ông đã cho thấy một chức năng Memoize, và tôi hỏi nếu có bất kỳ cách nào để giữ cho nó khỏi được sử dụng trên một chức năng không thuần túy. Ông nói không, đó là cơ bản không thể, và nếu ai đó có thể tìm ra một cách để làm điều đó nó sẽ làm cho một luận án tiến sĩ tuyệt vời.

Đó là loại nhầm lẫn tôi, bởi vì nó không có vẻ như tất cả những gì khó khăn cho một trình biên dịch/thông dịch viên để giải quyết đệ quy. Trong mã giả:

function isPure(functionMetadata): boolean; 
begin 
    result = true; 
    for each variable in functionMetadata.variablesModified 
     result = result and variable.isLocalToThisFunction; 
    for each dependency in functionMetadata.functionsCalled 
     result = result and isPure(dependency); 
end; 

Đó là ý tưởng cơ bản. Rõ ràng bạn cần một số loại kiểm tra để ngăn chặn đệ quy vô hạn về các chức năng phụ thuộc lẫn nhau, nhưng đó không phải là quá khó khăn để thiết lập.

Hàm bậc cao có chức năng con trỏ có thể có vấn đề, vì chúng không thể được xác minh tĩnh, nhưng câu hỏi ban đầu của tôi giả định rằng trình biên dịch có một số hạn chế về ngôn ngữ để chỉ định đến một tham số nhất định. Nếu có, có thể được sử dụng để đáp ứng điều kiện. Rõ ràng điều này sẽ dễ dàng hơn trong một ngôn ngữ biên dịch hơn là một giải thích, vì tất cả con số này-crunching sẽ được thực hiện trước khi chương trình được thực hiện và do đó không chậm bất cứ điều gì, nhưng tôi không thực sự thấy bất kỳ vấn đề cơ bản sẽ làm cho nó không thể đánh giá.

Có ai có kiến ​​thức nhiều hơn trong lĩnh vực này biết tôi đang thiếu gì không?

Answer 1

Điều này đặc biệt khó trong Python. Vì anObject.aFunc có thể được thay đổi tùy ý trong thời gian chạy, bạn không thể xác định tại thời gian biên dịch mà chức năng sẽ gọi anObject.aFunc() hoặc ngay cả khi nó sẽ là một chức năng.

Answer 2

Đây là điều đầu tiên xuất hiện trong đầu khi tôi đọc câu hỏi của bạn.

Lớp tầng nấc

Xác định nếu một biến được sửa đổi bao gồm các hành vi đào bới mọi phương pháp duy nhất mà được kêu gọi biến để xác định xem nó đột biến. Đây là ... hơi thẳng về phía trước cho một loại kín với một phương pháp phi ảo.

Nhưng hãy xem xét các phương pháp ảo. Bạn phải tìm mọi loại dẫn xuất đơn và xác minh rằng mọi ghi đè đơn lẻ của phương thức đó không làm thay đổi trạng thái. Việc xác định điều này đơn giản là không thể trong bất kỳ ngôn ngữ/khuôn khổ nào cho phép tạo mã động hoặc chỉ đơn giản là động (nếu có thể, nó cực kỳ khó). Lý do tại sao là tập hợp các kiểu dẫn xuất không cố định vì một kiểu mới có thể được tạo ra khi chạy.

Lấy C# làm ví dụ. Không có gì ngăn cản tôi tạo ra một lớp dẫn xuất tại thời gian chạy mà ghi đè phương thức ảo đó và sửa đổi trạng thái. Một xác minh tĩnh sẽ không thể phát hiện loại sửa đổi này và do đó không thể xác nhận phương thức là thuần túy hay không.

Answer 3

Bạn cũng cần phải chú thích mỗi cuộc gọi hệ thống, mỗi FFI, ...

Và hơn nữa các 'rò rỉ' nhỏ nhất có xu hướng bị rò rỉ vào cơ sở mã chung.

Nó không phải là một vấn đề về mặt lý thuyết, nhưng trong thực tế nó là rất rất khó khăn để làm trong một thời trang mà toàn bộ hệ thống không cảm thấy giòn.

Là một sang một bên, tôi không nghĩ rằng điều này làm cho một luận án tiến sĩ tốt; Haskell hiệu quả đã có (một phiên bản của) này, với đơn nguyên IO.

Và tôi chắc chắn rất nhiều người tiếp tục xem 'thực tế' này. (đầu cơ hoang dã) Trong 20 năm chúng ta có thể có điều này.

Answer 4

Ngoài các câu trả lời xuất sắc khác ở đây: Mã giả của bạn chỉ xem xét liệu một hàm có sửa đổi biến hay không. Nhưng điều đó không thực sự có nghĩa là "thuần khiết". "Tinh khiết" thường có nghĩa là một cái gì đó gần gũi hơn với "minh bạch tham chiếu". Nói cách khác, đầu ra hoàn toàn phụ thuộc vào đầu vào. Vì vậy, một cái gì đó đơn giản như đọc thời gian hiện tại và làm cho rằng một yếu tố trong kết quả (hoặc đọc từ đầu vào, hoặc đọc trạng thái của máy, hoặc ...) làm cho chức năng không tinh khiết mà không sửa đổi bất kỳ biến.

Ngoài ra, bạn có thể viết hàm "thuần túy" đã sửa đổi biến.

Answer 5

Tôi nghĩ rằng vấn đề chính sẽ làm hiệu quả.

Ngôn ngữ D có các hàm thuần túy nhưng bạn phải chỉ định chúng, do đó trình biên dịch sẽ biết kiểm tra chúng. Tôi nghĩ nếu bạn tự xác định chúng thì sẽ dễ dàng hơn.

Answer 6

Quyết định xem một chức năng cụ thể có thuần túy hay không, để quyết định xem có chương trình nào bị tạm dừng hay không và nó được biết là vấn đề không thể giải quyết một cách hiệu quả.

Answer 7

Lưu ý rằng độ phức tạp cũng phụ thuộc vào ngôn ngữ. Đối với các ngôn ngữ động hơn, bạn có thể xác định lại bất kỳ thứ gì bất kỳ lúc nào. Ví dụ: trong Tcl

proc myproc {a b} { 
    if { $a > $b } { 
     return $a 
    } else { 
     return $b 
    } 
} 

Mọi phần có thể được sửa đổi bất cứ lúc nào. Ví dụ:

• "nếu" lệnh có thể được viết lại để sử dụng và cập nhật các biến toàn cục
• sự "trở lại" lệnh, những đường lối cũ, có thể làm điều tương tự
• có thể là một thực dấu vết trên lệnh if, khi "if" được sử dụng, lệnh return được xác định lại dựa trên các đầu vào cho lệnh if

Phải thừa nhận rằng, Tcl là trường hợp cực đoan; một trong những ngôn ngữ năng động nhất. Điều đó đang được nói, nó làm nổi bật vấn đề khó có thể xác định độ tinh khiết của một hàm ngay cả khi bạn đã nhập nó.