ngôn ngữ hoàn toàn được suy ra là gì? và hạn chế của ngôn ngữ đó?

Question

Theo như tôi biết, bất kỳ ngôn ngữ lập trình nào không yêu cầu viết chú thích kiểu trong nguồn khi viết một hàm hoặc mô-đun và nếu đoạn mã đó là "đúng kiểu", trình biên dịch sẽ suy ra các kiểu và biên dịch mã. nó có nhiều hơn nữa không?

là (có) có một (các) ngôn ngữ như vậy không? nếu có thì có bất kỳ giới hạn nào đối với hệ thống kiểu của nó không?

Cập nhật 1: Chỉ cần thực sự là rõ ràng, tôi hỏi về ngôn ngữ lập trình được gõ tĩnh, đầy đủ kiểu suy luận không phải là ngôn ngữ lập trình được nhập động.

Answer 1

Giới hạn của suy luận kiểu đầy đủ là nó không hoạt động với nhiều tính năng hệ thống kiểu nâng cao. Ví dụ như xem xét Haskell và OCaml. Cả hai ngôn ngữ này là gần như là được phỏng đoán đầy đủ, nhưng có một số tính năng có thể ảnh hưởng đến suy luận kiểu.

---

Trong Haskell lớp đó là loại kết hợp với kiểu trả về đa hình:

readAndPrint str = print (read "asd") 

đây read là một chức năng của loại Read a => String -> a, có nghĩa là "cho bất kỳ loại a hỗ trợ lớp loại Read chức năng read Vì vậy, nếu f là một phương pháp có int, tôi có thể viết f (read "123") và nó sẽ chuyển đổi "123" thành Int 123 và gọi f với nó. Nó biết rằng nó nên chuyển đổi chuỗi thành một Int vì f mất một Int. Nếu f lấy một danh sách các int, nó sẽ cố gắng chuyển đổi chuỗi thành danh sách các Int thay thế. Không vấn đề gì.

Nhưng đối với hàm readAndPrint phía trên cách tiếp cận đó không hoạt động. Vấn đề ở đây là print có thể lấy một đối số của bất kỳ loại nào có thể được in (đó là bất kỳ loại nào hỗ trợ kiểu chữ Show). Vì vậy, không có cách nào cho trình biên dịch biết liệu bạn có muốn chuyển đổi chuỗi thành int hay danh sách int hay bất kỳ thứ gì khác có thể được in. Vì vậy, trong các trường hợp như thế này, bạn cần phải thêm chú thích kiểu.

---

Trong OCaml tính năng có vấn đề là các chức năng đa hình trong các lớp: Nếu bạn định nghĩa một hàm mang theo một đối tượng như là đối số của nó và gọi một phương thức trên đối tượng đó, trình biên dịch sẽ suy ra một loại monomorphic cho phương pháp đó. Ví dụ:

let f obj = obj#meth 23 + obj#meth 42 

Dưới đây trình biên dịch sẽ suy ra rằng obj phải là một thể hiện của một lớp học có một phương thức có tên meth loại int -> int, tức là một phương pháp mà phải mất một Int và trả về một Int. Bây giờ bạn có thể định nghĩa một loạt các lớp có một phương thức như vậy và truyền các cá thể của lớp đó làm các đối số cho f. Không vấn đề gì.

Sự cố xảy ra nếu bạn xác định một lớp học với một phương thức kiểu 'a. 'a -> int, tức là một phương pháp có thể lấy đối số của bất kỳ loại nào và trả về một int. Bạn không thể chuyển đối tượng của lớp đó làm đối số cho f vì đối tượng đó không khớp với loại được phỏng đoán. Nếu bạn muốn f lấy một đối tượng như đối số của nó, cách duy nhất là thêm chú thích kiểu vào f.

---

Vì vậy, đó là ví dụ về các ngôn ngữ gần như được phỏng đoán đầy đủ và trong trường hợp chúng không đúng. Nếu bạn muốn xóa các tính năng có vấn đề khỏi các ngôn ngữ đó, chúng sẽ được suy luận đầy đủ.

Do đó, các phương ngữ cơ bản của ML không có các tính năng nâng cao như vậy được suy ra đầy đủ. Ví dụ tôi giả định rằng Caml Light được suy luận đầy đủ vì nó cơ bản là OCaml không có các lớp (tuy nhiên tôi không thực sự biết ngôn ngữ, vì vậy đó chỉ là một giả định).

Answer 2

Suy luận kiểu là gì?

Về mặt lịch sử, suy luận kiểu (hoặc loại tái thiết) có nghĩa là tất cả loại trong một chương trình có thể được bắt nguồn mà không đòi hỏi cơ bản bất kỳ rõ ràng kiểu chú thích. Tuy nhiên, trong những năm gần đây, nó đã trở nên thịnh hành trong dòng chính ngôn ngữ lập trình để gắn nhãn ngay cả những hình thức nhỏ nhất của loại khấu trừ từ dưới lên dưới dạng "suy luận kiểu" (ví dụ: khai báo auto mới của C++ 11). Vì vậy, mọi người đã bắt đầu thêm "đầy đủ" để chỉ điều "thực".

đầy đủ suy luận loại nào?

Có phổ rộng với mức độ ngôn ngữ có thể suy ra các loại, và trong thực tế, hầu như không có ngôn ngữ nào hỗ trợ suy luận kiểu "đầy đủ" theo nghĩa hẹp nhất (lõi ML là ví dụ duy nhất). Nhưng yếu tố phân biệt chính là liệu các loại có thể được bắt nguồn cho các ràng buộc không có một "định nghĩa" gắn liền với chúng — cụ thể, các tham số của hàm. Nếu bạn có thể viết, giả sử,

f(x) = x + 1 

và hệ thống kiểu con số ra rằng f. có loại Int → Int, sau đó nó có ý nghĩa để gọi suy luận kiểu này. Hơn nữa, chúng ta nói về đa hình suy luận kiểu khi nào, ví dụ,

g(x) = x 

được gán kiểu generic & forall; (t) t → t tự động.

Suy luận kiểu được phát minh trong bối cảnh phép tính lambda đơn giản, và suy luận kiểu đa hình (còn gọi là suy luận kiểu Hindley/Milner, được phát minh vào thập niên 1970) là yêu sách của họ ML ngôn ngữ (Standard ML) , OCaml, và được cho là Haskell).

Giới hạn của suy luận kiểu đầy đủ là gì?

Core ML có sự sang trọng của suy luận kiểu đa hình "đầy đủ". Nhưng nó bản lề trên những hạn chế nhất định của đa hình trong hệ thống kiểu của nó. Đặc biệt, chỉ các định nghĩa mới có thể là chung, chứ không phải các đối số hàm. Đó là,

id(x) = x; 
id(5); 
id(True) 

hoạt động tốt, vì id có thể được loại đa hình khi định nghĩa được biết đến. Nhưng

f(id) = (id(5); id(True)) 

không nhập kiểm tra ML, vì id không thể đa hình làm đối số chức năng.Nói cách khác, hệ thống kiểu không cho phép các loại đa hình như & forall; (t) t → t, nhưng không được gọi là các loại đa hình bậc cao như (& forall; (t) t → t) → Bool, trong đó các giá trị đa hình được sử dụng theo cách thứ nhất (mà, chỉ cần rõ ràng, ngay cả rất ít ngôn ngữ được gõ một cách rõ ràng cho phép).

Tính toán lambda đa hình (còn được gọi là "Hệ thống F"), được nhập rõ ràng, cho phép sau này. Nhưng nó là một kết quả tiêu chuẩn trong lý thuyết loại mà tái thiết cho toàn bộ hệ thống F là không thể xác định. Hindley/Milner đạt được một vị trí ngọt ngào của một hệ thống kiểu ít biểu cảm hơn mà việc tái thiết loại vẫn là quyết định.

Có nhiều tính năng hệ thống kiểu nâng cao hơn cũng làm cho việc xây dựng lại kiểu không thể xác định được. Và có những người khác giữ cho nó rõ ràng nhưng vẫn làm cho nó không khả thi, ví dụ: sự hiện diện của quá tải hoặc subtyping ad-hoc, bởi vì điều đó dẫn đến vụ nổ tổ hợp.

Answer 3

Giới hạn khác là các loại xếp hạng cao hơn. Ví dụ, chương trình sau đây không không typecheck bằng các ngôn ngữ với ML phong cách suy luận kiểu:

foo = let bar f = (f ['a', 'b', 'c'], f [1,2,3]) in bar reverse 

Trình kiểm tra kiểu có thể gán cho f kiểu [Char] -> [Char] hoặc [Int] -> [Int], nhưng không bỏ qua a. [A] -> [a]. Trong ML, Ocaml và F # không có cách nào để sửa lỗi này, vì bạn thậm chí không thể viết các loại xếp hạng cao hơn.

Nhưng Haskell (thông qua phần mở rộng GHC) và Frege hỗ trợ các loại xếp hạng cao hơn. Nhưng vì chỉ có thể kiểm tra loại xếp hạng cao hơn (trái ngược với suy luận kiểu xếp hạng cao hơn), trình lập trình được yêu cầu cung cấp chú thích kiểu, ví dụ:

foo = let bar (f :: forall a.[a]->[a]) = (f ['a', 'b', 'c'], f [1,2,3]) in bar reverse