Trường hợp nào GHC xảy ra khi nhận dạng séc?

Question

Kiểm tra GHC xảy ra ngăn bạn xây dựng các loại vô hạn. Đó là mục đích để ngăn ngừa các lỗi phổ biến trong mã hoặc để ngăn chặn các typechecker từ looping vô thời hạn, hoặc cả hai?

Trường hợp nào nó nhận dạng và người dùng độc hại có thể lừa nó (như trong ngữ cảnh An toàn Haskell) vào vòng lặp không? Nếu hệ thống kiểu là turing hoàn thành (là nó?) Tôi không hiểu làm thế nào GHC có thể đảm bảo rằng tính toán sẽ dừng lại.

Answer 1

Suy nghĩ về suy luận kiểu như giải quyết một hệ phương trình. Hãy xem xét một ví dụ :

f x = (x,2) 

Làm sao chúng ta có thể suy ra các loại f? Chúng tôi thấy rằng nó là một chức năng:

f :: a -> b 

Bên cạnh đó, từ cấu trúc của f chúng ta có thể thấy rằng phương trình sau đây giữ simulatenously:

b = (c,d) 
d = Int 
c = a 

Bằng cách giải quyết hệ thống này của phương trình chúng ta có thể thấy rằng loại f là a -> (a, Int). Bây giờ chúng ta hãy nhìn vào những điều sau đây (sai lầm) chức năng:

f x = x : x 

Loại (:) là a -> [a] -> [a], vì vậy đây tạo ra các hệ thống sau phương trình (giản thể):

a = a 
a = [a] 

Vì vậy, chúng ta có được một phương trình a = [a], từ đó chúng tôi có thể kết luận rằng hệ phương trình này không có giải pháp và do đó mã không được đánh máy tốt. Nếu chúng ta không từ chối phương trình a = [a], chúng ta thực sự đi vào một vòng lặp vô hạn để thêm các phương trình a = [a], a = [[a]], a = [[[a]]], v.v ... vào hệ thống của chúng ta. nhưng điều đó sẽ tạo ra các chương trình sai lầm như f x = x : x để đánh máy).

Bạn cũng có thể kiểm tra điều này trong ghci:

> let f x = x : x 

<interactive>:2:15: 
    Occurs check: cannot construct the infinite type: a0 = [a0] 
    In the second argument of `(:)', namely `x' 
    In the expression: x : x 
    In an equation for `f': f x = x : x 

Như các câu hỏi khác của bạn: hệ thống kiểu GHC Haskell là không Turing hoàn tất và typechecker được đảm bảo để ngăn chặn - trừ khi bạn kích hoạt UndecidableInstances, trong trường hợp này về mặt lý thuyết nó có thể đi vào vòng lặp vô hạn. GHC, tuy nhiên, đảm bảo chấm dứt bằng cách có ngăn xếp đệ quy có độ sâu cố định, do đó không thể xây dựng chương trình mà nó không bao giờ dừng lại (chỉnh sửa: theo nhận xét của CAMcCann. của đệ quy đuôi trên mức loại cho phép lặp mà không tăng độ sâu ngăn xếp). Tuy nhiên, nó có thể làm cho quá trình biên dịch mất nhiều thời gian tùy ý, vì sự phức tạp của suy luận kiểu Hindley-Milner là theo cấp số nhân trong điều tồi tệ nhất (nhưng không phải là trung bình!).) Trường hợp:

dup x = (x,x) 

bad = dup . dup . dup . dup . dup . dup . dup . dup 
     . dup . dup . dup . dup . dup . dup . dup . dup 
     . dup . dup . dup . dup . dup . dup . dup . dup 
     . dup . dup . dup . dup . dup . dup . dup . dup 

Safe Haskell sẽ không bảo vệ bạn khỏi này - hãy nhìn vào mueval nếu bạn muốn cho phép người dùng có khả năng độc hại biên dịch chương trình Haskell trên hệ thống của bạn.

Answer 2

Tôi có thư tuyệt vời sau đây trong dấu trang của mình: There's nothing wrong with infinite types! Ngay cả với các loại vô hạn, không có nguy cơ thực sự nào khi tạo vòng lặp kiểm tra lỗi. Hệ thống kiểu không hoàn thành Turing (trừ khi bạn yêu cầu nó một cách rõ ràng với một cái gì đó giống như phần mở rộng UndecidableInstances).

Answer 3

Kiểm tra xảy ra GHC ngăn bạn xây dựng các loại vô hạn.

Điều này chỉ đúng theo nghĩa đen ngăn ngừa các loại là cú pháp vô hạn. Điều thực sự xảy ra ở đây chỉ là loại đệ quy, trong đó thuật toán thống nhất sẽ cần, theo nghĩa nào đó, nội tuyến đệ quy.

Bạn luôn có thể xác định chính xác cùng một loại bằng cách thực hiện đệ quy một cách rõ ràng. Điều này thậm chí có thể được thực hiện quát, sử dụng một phiên bản loại cấp fix:

newtype Fix f = Fix (f (Fix f)) 

Như một ví dụ, loại Fix ((->) a) tương đương với thống nhất b với (a -> b).

Trong thực tế, các lỗi "loại vô hạn" hầu như luôn luôn biểu thị lỗi trong mã (vì vậy nếu lỗi đó bị hỏng, có thể bạn không nên Fix nó). Kịch bản thông thường là trộn thứ tự đối số hoặc nếu không có biểu thức ở sai vị trí trong mã không sử dụng chữ ký kiểu rõ ràng.

Hệ thống suy luận kiểu vô cùng ngây thơ đúng cách có khả năng mở rộng đệ quy cho đến khi hết bộ nhớ, nhưng vấn đề dừng lại không đi vào nó - nếu một loại cần hợp nhất với một phần của chính nó , điều đó sẽ không bao giờ hoạt động (ít nhất là trong Haskell, có thể có các ngôn ngữ thay vì xử lý nó tương đương với một cách rõ ràng đệ quy newtype ở trên).

Không kiểm tra kiểu và loại suy luận trong GHC là Turing-complete trừ khi bạn bật UndecidableInstances, trong trường hợp này bạn có thể thực hiện tính toán tùy ý thông qua các phụ thuộc chức năng hoặc họ nhóm.

Haskell an toàn không thực sự nhập hình ảnh chút nào. Thật dễ dàng để tạo ra các loại suy đoán rất lớn sẽ làm giảm bộ nhớ hệ thống mặc dù là hữu hạn, và nếu bộ nhớ phục vụ cho tôi Haskell an toàn không hạn chế sử dụng UndecidableInstances anyway.

Answer 4

Mục đích (trong trình biên dịch Haskell) là để ngăn ngừa các lỗi phổ biến trong mã. Có thể xây dựng một bộ kiểm tra kiểu và công cụ suy luận sẽ hỗ trợ đệ quy vô hạn các kiểu. Có thêm một số thông tin trong số this question.

OCaml triển khai các loại đệ quy với -rectypes, vì vậy, điều đó hoàn toàn có thể xảy ra. Cộng đồng OCaml sẽ thông thạo nhiều hơn trong một số vấn đề phát sinh (hành vi bị tắt theo mặc định).

Kiểm tra xảy ra xác định mở rộng loại vô hạn. Ví dụ: mã này:

Prelude> let a = [a] 
<interactive>:2:10: 
    Occurs check: cannot construct the infinite type: t0 = [t0] 
    In the expression: a 
    In the expression: [a] 
    In an equation for `a': a = [a] 

nếu bạn cố gắng loại ra bằng tay, loại là [ [ [ [ ... ] ] ] ]. Không thể viết các loại như vậy bằng tay, bởi vì chúng vô hạn.

Kiểm tra xảy ra xảy ra trong khi hội thảo loại, đây là một giai đoạn riêng biệt từ kiểm tra loại.Các loại vô hạn sẽ phải được suy ra, bởi vì chúng không thể được chú thích theo cách thủ công. Suy luận kiểu Haskell-98 là decidable, vì vậy không thể lừa trình biên dịch thành vòng lặp (chặn các lỗi của khóa học, mà tôi nghi ngờ khai thác this example). GHC theo mặc định sử dụng một tập hợp con bị hạn chế của Hệ thống F cho kiểu suy luận kiểu nào cũng có thể giải quyết được. Với một số phần mở rộng, chẳng hạn như RankNTypes, GHC không cho phép mã mà suy luận kiểu là không thể xác định, nhưng sau đó yêu cầu chú thích kiểu, do đó, một lần nữa không có nguy cơ của vòng lặp suy luận loại suy luận.

Vì Turing ngôn ngữ hoàn chỉnh là không thể xác định, hệ thống loại mặc định không thể hoàn thành Turing. Tôi không biết liệu hệ thống kiểu GHC có hoàn thành Turing hay không với một số kết hợp các tiện ích được bật, nhưng một số tiện ích mở rộng nhất định (ví dụ: UndecidableInstances) cho phép viết mã sẽ làm hỏng trình biên dịch với tràn ngăn xếp.

Ngẫu nhiên, vấn đề chính với việc vô hiệu hóa kiểm tra xảy ra là nhiều lỗi mã hóa phổ biến dẫn đến lỗi loại vô hạn, do đó, vô hiệu hóa nó thường dẫn đến nhiều sự cố hơn giải quyết. Nếu bạn có ý định sử dụng một loại vô hạn, một wrapper newtype sẽ cho phép nó mà không cần ký hiệu thừa.