Tập 83: Generics V0 — Quyền lực và Hạn mức

Generics là trái tim của khả năng tái sử dụng mã nguồn trong các ngôn ngữ hiện đại, cho phép định nghĩa các cấu trúc dữ liệu tổng quát như List[T]. Nhưng generics cũng là cỗ máy đốt dung lượng binary khét tiếng. Trong C++, template instantiation có thể dễ dàng biến một thư viện nhỏ thành một binary vài megabyte chỉ vì compiler sinh mã máy trùng lặp cho hàng chục kiểu dữ liệu khác nhau (code-size explosion).

Sprint 140 mang Generics V0 đến với compiler native của DUY qua cơ chế monomorphization tĩnh nhưng có kiểm soát. Cú pháp:

struct Pair[T] {
  first: T,
  second: T
}

fn identity[T](val: T) -> T {
  return val;
}

Để ngăn chặn sự phình to mã nguồn ngoài tầm kiểm soát, compiler duy trì một bảng instantiation map tĩnh. Nếu một struct hoặc function generic được khởi tạo với cùng một kiểu dữ liệu ở nhiều module khác nhau, compiler sẽ tự động thực hiện gom cụm và loại bỏ trùng lặp (deduplication) trước khi phát sinh object file. Đồng thời, chúng tôi đặt một hard limit (cap) cho độ sâu của đệ quy kiểu (type recursion). Nếu anh cố tình viết một cấu trúc đệ quy vô hạn như struct Node[T] { next: Node[Node[T]] }, compiler sẽ từ chối biên dịch kèm thông báo lỗi rõ ràng thay vì im lặng crash do tràn bộ nhớ (stack overflow) của compiler driver.

Thử thách kỹ thuật lớn nhất của sprint này nằm ở việc Type Checker phải xác thực các trait bound trên generic parameters. Khi viết fn print_item[T: Show](item: T), checker phải chứng minh ở compile-time rằng kiểu dữ liệu thay thế cho T thực sự có một block impl Show hợp lệ, nếu không sẽ chặn đứng quá trình biên dịch ngay lập tức.

Tôi nhớ đêm tôi viết thuật toán phân giải ràng buộc kiểu (constraint solver) cho generics. Giải thuật đệ quy phân giải trait lồng nhau liên tục bị tràn stack do gặp phải một vòng lặp logic vô hạn trong code kiểm thử. Tôi phải thức trắng đêm để viết thêm một cơ chế phát hiện chu kỳ (cycle detection) cho constraint solver. Khi gõ lệnh chạy thử và nhìn thấy compiler từ chối biên dịch với thông báo lỗi rõ ràng Circular trait constraint detected, tôi biết mình đã thuần hóa được cỗ máy generics đầy quyền lực này.

---