Giải quyết việc nhập và xuất mô-đun Haskell cạnh trường hợp

Question

Tôi đang viết một trình biên dịch Haskell nhỏ, và tôi muốn triển khai càng nhiều Haskell 2010 càng tốt. Trình biên dịch của tôi có thể phân tích cú pháp một mô-đun, nhưng việc hoàn thành các mô-đun cho một chương trình có vẻ là một nhiệm vụ không tầm thường. Tôi đã thực hiện một số ví dụ về các khó khăn, nhưng, mô-đun Haskell có lẽ hợp lệ:

module F(G.x) where 
    import F as G 
    x = 2 

Đây module F xuất khẩu G.x, nhưng G.x cũng giống như F.x, vì vậy mô-đun F xuất khẩu x nếu, và chỉ nếu, nó xuất khẩu x.

module A(a) where 
    import B(a) 
    a = 2 

module B(a) where 
    import A(a) 

Trong ví dụ này, để giải quyết xuất khẩu của module A trình biên dịch có để kiểm tra xem a nhập khẩu từ B là giống như tuyên bố a = 2, nhưng B xuất khẩu a nếu, và chỉ nếu, A xuất khẩu a.

module A(f) where 
    import B(f) 

module B(f) where 
    import A(f) 

Trong việc giải quyết các mô-đun A, trình biên dịch may've cho rằng f nhập khẩu từ B tồn tại, ngụ ý rằng A xuất khẩu f, do đó B có thể nhập A(f) và xuất khẩu f. Vấn đề duy nhất là không có f được xác định ở bất cứ đâu :).

module A(module X) where 
    import A as X 
    import B as X 
    import C as X 
    a = 2 

module B(module C, C.b) where 
    import C 
    b = 3 

module C(module C) 
    import B as C 
    c = 4 

Xuất tại đây khiến danh sách xuất phụ thuộc lẫn nhau.

Tất cả các ví dụ này phải hợp lệ Haskell, như được xác định bởi thông số kỹ thuật của Haskell 2010.

Tôi muốn hỏi liệu có bất kỳ ý tưởng nào về cách thực hiện đúng và hoàn toàn các mô-đun Haskell không?

Giả sử rằng một module chứa chỉ (đơn giản) bindings biến, import s (có thể với as hoặc qualified), và xuất khẩu danh sách các biến thể có trình độ và module ... chữ viết tắt. Thuật toán có để có thể:

• tính toán danh sách hữu hạn của biến xuất khẩu của mỗi mô-đun
• liên kết mỗi biến xuất khẩu sang ràng buộc
• liên kết của nó mỗi (có thể đủ điều kiện) biến được sử dụng trong tất cả các mô-đun để ràng buộc của nó

Answer 1

Bạn có thể quan tâm đến A Formal Specification for the Haskell 98 Module System.

Tôi cũng bao gồm một số trường hợp cạnh thú vị trong một loạt bài đăng trên blog, trong đó chỉ có first one được xuất bản kể từ bây giờ.

Cuối cùng, tôi đang làm chính xác điều đó - một thư viện xử lý các mô-đun Haskell. Nó được gọi là haskell-names.

Tùy thuộc vào mục tiêu của bạn, bạn có thể chỉ cần sử dụng nó trong trình biên dịch của bạn, nghiên cứu mã nguồn hoặc đóng góp. (Ví dụ của bạn sẽ làm cho các trường hợp thử nghiệm xuất sắc.)

---

Để trả lời câu hỏi của bạn: các mô-đun đệ quy được xử lý bằng cách tính toán điểm cố định.

Bạn bắt đầu với thành phần được kết nối mạnh trong biểu đồ mô-đun. Đối với mỗi mô-đun trong thành phần này, bạn bắt đầu với một giả định rằng nó không xuất khẩu. Sau đó, bạn truy cập lại các mô-đun này và tính toán các danh sách xuất mới dựa trên thông tin mới. Bạn có thể chứng minh rằng quá trình này là đơn điệu - mỗi khi danh sách xuất khẩu tăng (hoặc ít nhất, không co lại). Sớm hay muộn nó ngừng phát triển - sau đó bạn đã đạt đến điểm cố định.

Bạn có thể tối ưu hóa thuật toán này bằng cách mượn một số ý tưởng từ phân tích tĩnh (cộng đồng rất giỏi tính điểm cố định), nhưng gói của tôi hiện đang thực hiện thuật toán ngây thơ (code).