Thuật toán Hindley-Milner: sử dụng các loại để đảm bảo ràng buộc được áp dụng

Question

Tôi đang triển khai thuật toán suy luận kiểu Hindley-Milner, theo các hướng dẫn của Mark Jones và Oleg Kiselyov. Cả hai có một "áp dụng cam kết ràng buộc" hoạt động với một loại xấp xỉ của mẫu

applyBindings :: TyEnv -> Type -> Type 

mà áp dụng tyvar -> ty bindings trong TyEnv đến Type nhất định. Tôi đã tìm thấy nó một sai lầm phổ biến trong mã của tôi để quên gọi applyBindings và tôi không nhận được sự trợ giúp từ hệ thống kiểu của Haskell, vì ty có cùng loại với applyBindings tyenv ty. Tôi đang tìm kiếm một cách để thực thi bất biến sau đây trong hệ thống kiểu:

khi thực hiện kiểu suy luận, các ràng buộc phải được áp dụng trước khi trở về một 'chính thức' kết quả

Khi làm suy luận kiểu cho một monomorphic ngôn ngữ đối tượng, có một cách tự nhiên để thực hiện điều này, như thực hiện trong Wren ng thornton của unification-fd package: chúng ta định nghĩa hai kiểu dữ liệu cho Type s:

-- | Types not containing unification variables 
type Type = ...   -- (Fix TypeF) in wren's package 

-- | Types possibly containing unification variables 
type MutType = ...  -- (MutTerm IntVar TypeF) in wren's package 

và cung cấp cho applyBindings loại

-- | Apply all bindings, returning Nothing if there are still free variables 
-- otherwise just 
applyBindings :: TyEnv -> MutType -> Maybe Type 

(chức năng này thực sự là freeze . applyBindings trong hợp nhất-fd). Điều này thực thi bất biến của chúng ta - nếu chúng ta quên applyBindings, thì chúng ta sẽ gặp lỗi kiểu.

Đây là loại giải pháp mà tôi đang tìm kiếm, nhưng đối với các ngôn ngữ đối tượng có tính đa hình. Cách tiếp cận trên, không áp dụng, vì các kiểu ngôn ngữ của chúng ta có thể có các biến kiểu - thực sự, nếu có biến miễn phí sau khi áp dụng các ràng buộc, chúng ta không muốn trả về Nothing, nhưng chúng ta muốn khái quát hóa qua các biến này.

Có giải pháp nào dọc theo các dòng tôi mô tả, tức là giải pháp cho phép applyBindings loại khác từ const id? Làm trình biên dịch thực sự sử dụng cùng một punning (giữa các biến thống nhất và biến kiểu ngôn ngữ đối tượng) mà Mark và Oleg của hướng dẫn làm gì?

Answer 1

Tôi đang tham gia một đâm trong bóng tối ở đây, bởi vì tôi nghĩ rằng có thể có những vấn đề khác với các giải pháp bạn đề xuất, nhưng tôi có thể giải quyết ít nhất một khó khăn:

• kiểm tra kiểu của bạn nên có các đại diện khác nhau cho biến loại hợp nhất và biến loại ngôn ngữ đối tượng.

Biến thể này không khó thực hiện và trên thực tế, tôi cho rằng trình kiểm tra loại GHC hoạt động theo cách này, ít nhất một lần. Bạn có thể muốn kiểm tra giấy Practical Type Inference for Arbitrary-Rank Types; phụ lục chứa rất nhiều mã rất hữu ích.