Đa hình và Kiểu tổng quát

Đa hình cho phép một đoạn mã duy nhất hoạt động thống nhất trên nhiều kiểu, với đa hình tham số (kiểu tổng quát), đa hình đặc thù (nạp chồng và lớp kiểu), và đa hình kiểu con là các dạng chính.

Definition

Đa hình là thuộc tính mà một hàm, kiểu hoặc phép toán duy nhất có thể áp dụng cho các giá trị của nhiều hơn một kiểu; đa hình tham số thực hiện điều này một cách thống nhất thông qua các tham số kiểu (kiểu tổng quát), trong khi đa hình đặc thù điều phối đến các triển khai cụ thể theo kiểu.

Scope

Chủ đề này bao gồm các loại đa hình chính: đa hình tham số được hiện thực hóa bằng kiểu tổng quát và System F, đa hình đặc thù thông qua nạp chồng và lớp kiểu, và đa hình bao hàm (kiểu con). Nó đề cập đến tính tham số và các nguyên tắc suy luận mạnh mẽ mà nó mang lại, cũng như cách các trừu tượng tổng quát được biên dịch và ràng buộc.

Core questions

• Làm thế nào các kiểu tổng quát cung cấp khả năng tái sử dụng mà không làm mất an toàn kiểu?
• Tính tham số là gì và nó mang lại những đảm bảo miễn phí nào?
• Làm thế nào các lớp kiểu hệ thống hóa khả năng nạp chồng đặc thù?
• Các định nghĩa tổng quát được biên dịch như thế nào, và những ràng buộc nào có thể giới hạn các tham số kiểu?

Key theories

Tính tham số (định lý trừu tượng)

Định lý trừu tượng của Reynolds chỉ ra rằng các hàm đa hình tham số hoạt động thống nhất trên các kiểu, một thuộc tính ràng buộc hành vi có thể có của chúng một cách độc lập với việc khởi tạo kiểu cụ thể.

Các định lý miễn phí

Wadler đã chỉ ra rằng chỉ riêng kiểu của một hàm đa hình tham số đã ngụ ý các định lý miễn phí về hành vi của nó, một hệ quả trực tiếp và thực tế của tính tham số.

Lớp kiểu cho khả năng nạp chồng có nguyên tắc

Wadler và Blott đã giới thiệu các lớp kiểu, mang lại cho đa hình đặc thù một cơ sở lý thuyết kiểu mạch lạc, nơi các phép toán nạp chồng được giải quyết bằng cách truyền các từ điển ngầm định của các triển khai phương thức.

Clinical relevance

Kiểu tổng quát và đa hình là trọng tâm của thiết kế thư viện có thể tái sử dụng và các framework tập hợp trong các ngôn ngữ hiện đại. Lớp kiểu và các dạng tương tự của chúng (traits, concepts, protocols) cung cấp khả năng nạp chồng có nguyên tắc, an toàn kiểu, trong khi tính tham số hỗ trợ suy luận tính đúng đắn và tối ưu hóa trình biên dịch.

History

System F, nắm bắt đa hình tham số, được Girard và Reynolds độc lập khám phá vào đầu những năm 1970. ML đã đưa đa hình với suy luận vào thực tiễn. Khảo sát năm 1985 của Cardelli và Wegner đã phân loại các dạng đa hình, Reynolds đã hình thức hóa tính tham số vào năm 1983, và các lớp kiểu năm 1989 của Wadler và Blott đã định hình khả năng nạp chồng trong Haskell và ảnh hưởng đến traits và concepts ở những nơi khác.

Debates

Xóa bỏ so với kiểu tổng quát được hiện thực hóa

Các nhà phát triển ngôn ngữ tranh luận về việc biên dịch kiểu tổng quát bằng cách xóa bỏ kiểu (type erasure), đơn giản nhưng làm mất thông tin kiểu thời gian chạy, so với việc hiện thực hóa các tham số kiểu tại thời gian chạy (reifying type parameters), cho phép nội quan nhưng phải trả giá bằng sự phức tạp và kích thước mã.

Key figures

• John Reynolds
• Jean-Yves Girard
• Philip Wadler
• Luca Cardelli
• Robin Milner

Seminal works

• reynolds1983
• wadler1989free
• wadler1989
• cardelli1985

Frequently asked questions

Sự khác biệt giữa đa hình tham số và đa hình đặc thù là gì?

Đa hình tham số áp dụng một triển khai thống nhất cho tất cả các đối số kiểu (như với kiểu tổng quát), trong khi đa hình đặc thù chọn một triển khai cụ thể theo kiểu, như với nạp chồng hoặc lớp kiểu.

Tính tham số mang lại cho chúng ta điều gì?

Tính tham số đảm bảo rằng một hàm tổng quát xử lý tất cả các thể hiện kiểu một cách thống nhất, điều này mang lại 'các định lý miễn phí' về hành vi của nó có thể suy ra chỉ từ chữ ký kiểu của nó.