Tính dự báo là gì?

Question

Tôi có trực giác khá tốt về các loại Haskell cấm là "không chính thức": cụ thể là những nơi mà một forall xuất hiện trong một đối số cho một nhà xây dựng kiểu khác với ->. Nhưng chỉ là sự dự báo là gì? Điều gì làm cho nó quan trọng? Làm thế nào nó liên quan đến từ "vị ngữ"?

Answer 1

Hãy để tôi chỉ thêm một điểm liên quan đến vấn đề "từ nguyên", vì câu trả lời khác của @DanielWagner bao hàm phần lớn nền tảng kỹ thuật.

Vị từ trên một cái gì đó như a là a -> Bool. Bây giờ một logic vị ngữ là một lý do có ý nghĩa về các biến vị ngữ - vì vậy nếu chúng ta có một số vị ngữ P và chúng ta có thể nói về một số a, P(a), bây giờ trong một "vị ngữ logic" (chẳng hạn như logic bậc nhất) chúng tôi cũng có thể nói ∀a. P(a). Vì vậy, chúng tôi có thể định lượng các biến và thảo luận về hành vi của các vị từ trên những thứ như vậy.

Bây giờ, đến lượt chúng tôi nói một tuyên bố là dự đoán nếu tất cả những điều mà vị từ được áp dụng được giới thiệu trước cho nó. Vì vậy, câu lệnh được "dựa trên" những thứ đã tồn tại. Đổi lại, một tuyên bố là không phù hợp nếu nó có thể trong một số ý nghĩa đề cập đến chính nó bằng "bootstraps" của nó.

Vì vậy, trong trường hợp ví dụ: các id ví dụ trên, chúng ta thấy rằng chúng tôi có thể cung cấp một loại để id như vậy mà nó có cái gì đó của loại của id đến cái gì khác của loại của id. Vì vậy, bây giờ chúng tôi có thể cung cấp cho một chức năng một loại nơi một biến số lượng (giới thiệu bởi forall a.) có thể "mở rộng" để được cùng loại như của toàn bộ chức năng chính nó!

Do đó, tính không thực tế giới thiệu khả năng "tự tham chiếu" nhất định. Nhưng chờ đợi, bạn có thể nói, sẽ không một điều như vậy dẫn đến mâu thuẫn? Câu trả lời là: "tốt, đôi khi." Đặc biệt, "Hệ thống F" là phép tính lambda đa hình và "cốt lõi" cốt lõi của ngôn ngữ "cốt lõi" của GHC cho phép một dạng impredicativity mà dù sao có hai cấp độ - mức giá trị, và mức loại, được phép định lượng chính nó. Trong phân tầng hai cấp này, chúng ta có thể có tính không khoan nhượng và không phải là mâu thuẫn/nghịch lý.

Mặc dù lưu ý rằng lừa gọn gàng này được rất tinh tế và dễ dàng để vít lên bởi việc bổ sung các tính năng hơn, như bộ sưu tập này của bài viết bởi Oleg chỉ: http://okmij.org/ftp/Haskell/impredicativity-bites.html

Answer 2

Câu hỏi trung tâm của các hệ thống kiểu này là: "Bạn có thể thay thế một loại đa hình cho biến kiểu không?". Các hệ thống kiểu dự đoán là câu trả lời không có nghĩa vô nghĩa, "TUYỆT ĐỐI KHÔNG", trong khi các hệ thống kiểu dự tính là bạn thân vô tư của bạn, người nghĩ rằng âm thanh như một ý tưởng thú vị và điều gì có thể sai?

Bây giờ, Haskell lúng túng thảo luận một chút vì nó tin rằng đa hình nên hữu ích nhưng vô hình. Vì vậy, đối với phần còn lại của bài đăng này, tôi sẽ viết bằng một phương ngữ của Haskell nơi sử dụng của forall không chỉ được cho phép mà được yêu cầu. Bằng cách này, chúng ta có thể phân biệt giữa loại a, là một loại đơn hình vẽ giá trị của nó từ môi trường nhập mà chúng ta có thể xác định sau và loại forall a. a, là một trong những loại đa hình khó khăn hơn để sinh sống. Chúng tôi cũng sẽ cho phép forall di chuyển khá nhiều ở bất kỳ đâu - như chúng ta sẽ thấy, GHC hạn chế cú pháp kiểu của nó như là một cơ chế "không nhanh" thay vì yêu cầu kỹ thuật.

Giả sử chúng tôi đã thông báo cho trình biên dịch id :: forall a. a -> a. Sau đó chúng tôi có thể yêu cầu sử dụng id như thể nó có loại (forall b. b) -> (forall b. b) không? Hệ thống kiểu hiển thị phù hợp với điều này, bởi vì chúng tôi có thể khởi tạo trình định lượng theo kiểu của id thành forall b. b và thay thế forall b. b cho a ở mọi nơi trong kết quả. hệ thống kiểu Vị ngữ rất thận trọng về điều đó nhiều hơn một chút: Các loại chỉ monomorphic được phép trong

Có một câu chuyện tương tự về [] :: forall a. [a] và (:) :: forall a. a -> [a] -> [a]. (Vì vậy, nếu chúng ta có một đặc biệt b, chúng ta có thể viết id :: b -> b.). Trong khi người bạn vô tư của bạn có thể được chấp nhận với [] :: [forall b. b] và (:) :: (forall b. b) -> [forall b. b] -> [forall b. b], thì người làm việc dự đoán thì không, rất nhiều. Trong thực tế, như bạn có thể thấy từ hai nhà xây dựng danh sách duy nhất, có là không có cách nào để tạo danh sách chứa các giá trị đa hình mà không tạo biến kiểu trong các hàm tạo của chúng thành giá trị đa hình. Vì vậy, mặc dù loại [forall b. b] là được phép trong phương ngữ của chúng tôi về Haskell, nó không thực sự hợp lý - không có (chấm dứt) các điều khoản của loại đó. Điều này thúc đẩy quyết định của GHC khiếu nại nếu bạn thậm chí nghĩ về một loại như vậy - đó là cách của trình biên dịch để nói với bạn "đừng bận tâm". *

Vâng, điều gì làm cho nhà trường nghiêm ngặt như vậy? Như thường lệ, câu trả lời là về việc giữ kiểu kiểm tra và kiểu suy luận. Loại suy luận cho các loại dự đoán là đúng. Loại kiểm tra seems like it might be possible, nhưng nó phức tạp đẫm máu và không ai muốn duy trì điều đó.

Mặt khác, một số có thể phản đối rằng GHC là hoàn toàn hài lòng với một số loại có vẻ như yêu cầu impredicativity:

> :set -Rank2Types 
> :t id :: (forall b. b) -> (forall b. b) 
{- no complaint, but very chatty -} 

Nó chỉ ra rằng một số phiên bản hơi hạn chế của impredicativity không quá xấu: đặc biệt , loại kiểm tra các loại xếp hạng cao hơn (cho phép các biến kiểu được thay thế bằng các loại đa hình khi chúng chỉ là đối số cho (->)) là tương đối đơn giản. Bạn làm mất suy luận kiểu trên cấp bậc 2, và các loại chính trên cấp bậc 1, nhưng đôi khi các loại xếp hạng cao hơn chỉ là những gì bác sĩ đã ra lệnh.

Không biết về từ nguyên của từ!

* Bạn có thể tự hỏi liệu bạn có thể làm một cái gì đó như thế này:

data FooTy a where 
    FooTm :: FooTy (forall a. a) 

Sau đó, bạn sẽ nhận được một thuật ngữ (FooTm) có loại có một cái gì đó đa hình như một tham số để một cái gì đó khác hơn (->) (cụ thể là, FooTy), bạn không phải vượt qua nhà trường để làm điều đó, và vì vậy niềm tin "áp dụng các công cụ không phải (->) cho các loại đa hình không hữu ích vì bạn không thể làm cho chúng" sẽ bị vô hiệu. GHC không cho phép bạn viết FooTy và tôi sẽ thừa nhận rằng tôi không chắc chắn có lý do chính đáng cho việc hạn chế hay không.

Answer 3

Tôi muốn làm một bình luận trên vấn đề từ nguyên, vì câu trả lời của @ sclv không hoàn toàn đúng (từ nguyên, không phải khái niệm).

Quay lại thời gian, đến ngày Russell khi mọi thứ được đặt lý thuyết - bao gồm logic.Một trong những khái niệm hợp lý về nhập khẩu cụ thể là "nguyên tắc hiểu"; tức là, với một số biến vị ngữ logic φ:A→2, chúng tôi muốn có một số nguyên tắc để xác định tập hợp tất cả các phần tử thỏa mãn vị từ đó, được viết là "{x | φ(x) }" hoặc một số biến thể trong đó. Điểm mấu chốt cần lưu ý là "bộ" và "vị từ" được xem như là những thứ cơ bản khác nhau: các vị từ là ánh xạ từ các đối tượng đến các giá trị chân lý và các bộ là các đối tượng. Vì vậy, ví dụ, chúng tôi có thể cho phép định lượng trên các bộ nhưng không định lượng trên các vị từ.

Bây giờ, Russell khá quan tâm đến nghịch lý cùng tên của mình, và đã tìm cách để loại bỏ nó. Có rất nhiều bản sửa lỗi, nhưng điều quan tâm ở đây là hạn chế nguyên tắc hiểu. Nhưng trước tiên, định nghĩa chính thức của nguyên tắc: ∃S.∀x.S x ↔︎ φ(x); có nghĩa là, đối với một số đối tượng của chúng tôi (ví dụ, thiết lập) S sao cho mỗi đối tượng (cũng là một tập hợp, nhưng được coi là một phần tử) x, chúng tôi có S x (bạn có thể nghĩ rằng điều này có nghĩa là "x∈S" ", mặc dù logicians của thời gian đã cho" ∈ "một ý nghĩa khác với chỉ juxtaposition) là đúng chỉ trong trường hợp φ(x) là đúng sự thật. Nếu chúng ta lấy nguyên tắc chính xác như được viết thì chúng ta sẽ kết thúc với một lý thuyết không rõ ràng. Tuy nhiên, chúng tôi có thể đặt các hạn chế mà trên đó φ chúng tôi được phép thực hiện việc hiểu. (Ví dụ, nếu chúng ta nói rằng φ không được chứa bất kỳ số lượng thứ tự thứ hai nào.) Vì vậy, đối với bất kỳ giới hạn R, nếu một số S được xác định (tức là được tạo ra thông qua hiểu) bởi một số R -predicate, thì chúng ta nói rằng S là "R -predicative". Nếu mỗi bộ trong ngôn ngữ của chúng tôi là R -predicative thì chúng tôi nói rằng ngôn ngữ của chúng tôi là "R -predicative". Và sau đó, như thường là trường hợp với những điều tiền tố hyphenated, tiền tố được thả ra và trái ẩn, whence "predicative" ngôn ngữ. Và, một cách tự nhiên, các ngôn ngữ không mang tính dự đoán là "không đáng kể".

Đó là từ nguyên học cũ. Kể từ những ngày đó, các điều khoản đã biến mất và nhận cuộc sống của riêng họ. Những cách chúng ta sử dụng "dự đoán" và "không mang tính kỷ luật" ngày nay khá khác nhau, bởi vì những điều chúng ta quan tâm đã thay đổi. Vì vậy, đôi khi nó có thể hơi khó để xem cách thức mà sự sử dụng hiện đại của chúng ta liên quan đến công cụ này. Thành thật mà nói, tôi không nghĩ rằng từ nguyên thực sự giúp đỡ bất kỳ trong việc tìm hiểu những gì các từ thực sự về (những ngày này).