Làm cách nào để quyết định có tham số hóa ở cấp loại hoặc cấp mô-đun khi thiết kế mô-đun không?

Question

Tôi đang làm việc hướng tới một sự hiểu biết sâu sắc về các mô-đun kiểu ML: Tôi nghĩ khái niệm là quan trọng và tôi thích loại suy nghĩ mà họ khuyến khích. Tôi chỉ là bây giờ phát hiện ra sự căng thẳng có thể phát sinh giữa các loại tham số và mô-đun tham số. Tôi đang tìm kiếm các công cụ để suy nghĩ về vấn đề sẽ giúp tôi đưa ra các quyết định thiết kế thông minh khi tôi xây dựng các chương trình của mình.

Nắm tay Tôi sẽ cố gắng mô tả câu hỏi của tôi nói chung. Sau đó, tôi sẽ cung cấp một ví dụ cụ thể từ một dự án học tập mà tôi đang làm việc. Cuối cùng, tôi sẽ truy cập lại câu hỏi chung để vẽ câu hỏi đó đến một điểm.

(. Tôi xin lỗi mà tôi chưa biết đủ để đặt ra câu hỏi này một cách ngắn gọn hơn)

Nói chung, sự căng thẳng tôi đã phát hiện ra là thế này: chức năng có nhiều linh hoạt, và cởi mở để tái sử dụng rộng nhất, khi chúng tôi cung cấp cho họ tham số chữ ký loại (nếu thích hợp). Tuy nhiên, các mô-đun linh hoạt nhất và mở để tái sử dụng rộng nhất khi chúng tôi đóng dấu tham số của các hàm bên trong mô-đun và thay vì tham số hóa toàn bộ mô-đun trên một loại đã cho.

Có thể tìm thấy ví dụ sẵn sàng về sự khác biệt này khi so sánh các mô-đun triển khai chữ ký LIST với chữ ký triển khai ORD_SET. Một mô-đun List:LIST cung cấp một loạt các chức năng hữu ích, được tham số hóa trên bất kỳ loại nào. Khi chúng tôi đã xác định hoặc tải mô-đun List, chúng tôi có thể dễ dàng áp dụng bất kỳ chức năng nào mà nó cung cấp để xây dựng, thao tác hoặc kiểm tra danh sách thuộc bất kỳ loại nào. Ví dụ, nếu chúng ta đang làm việc với cả hai dây và số nguyên, chúng ta có thể sử dụng một và cùng một module để xây dựng và vận dụng giá trị của cả hai loại:

val strList = List.@ (["a","b"], ["c","d"]) 
val intList = List.@ ([1,2,3,4], [5,6,7,8]) 

Mặt khác, nếu chúng ta muốn để đối phó với lệnh bộ, vấn đề khác nhau: bộ đặt hàng yêu cầu giữ mối quan hệ đặt hàng trên tất cả các phần tử của chúng, và không thể có hàm bê tông đơn lẻ compare : 'a * 'a -> order tạo mối quan hệ đó cho mọi loại. Do đó, chúng tôi yêu cầu một mô-đun khác nhau đáp ứng chữ ký ORD_SET cho mỗi loại mà chúng tôi muốn đưa vào các bộ đặt hàng.Vì vậy, để xây dựng hoặc điều khiển bộ thứ tự các chuỗi và số nguyên, chúng ta phải thực hiện các module khác nhau đối với từng loại [1]:

structure IntOrdSet = BinarySetFn (type ord_key = int 
            val compare = Int.compare) 
structure StrOrdSet = BinarySetFn (type ord_key = string 
            val compare = String.compare) 

Và sau đó chúng ta phải sử dụng chức năng phù hợp từ các mô-đun thích hợp khi chúng ta muốn hoạt động trên một loại nhất định:

val strSet = StrOrdSet.fromList ["a","b","c"] 
val intSet = IntOrdSet.fromList [1,2,3,4,5,6] 

có một sự cân bằng khá đơn giản ở đây: LIST module cung cấp các chức năng rằng dao động trên bất kỳ loại bạn vui lòng, nhưng họ không thể tận dụng lợi thế của bất kỳ mối quan hệ rằng giữ giữa các giá trị của bất kỳ loại cụ thể nào; Các mô-đun ORD_SET cung cấp các hàm nhất thiết bị hạn chế đối với loại được cung cấp trong thông số của functors, nhưng thông qua cùng tham số đó, chúng có khả năng kết hợp thông tin cụ thể về cấu trúc bên trong và mối quan hệ của các loại mục tiêu của chúng. Thật dễ dàng để tưởng tượng các trường hợp chúng tôi muốn thiết kế một mô-đun danh sách thay thế cho các mô-đun, sử dụng functors để tham số hóa các loại và các giá trị khác. loại dữ liệu cho danh sách được sắp xếp hoặc đại diện cho các danh sách bằng cách sử dụng các cây tìm kiếm nhị phân tự cân bằng .

Khi tạo mô-đun, tôi nghĩ cũng khá dễ nhận ra khi nào nó sẽ có thể cung cấp các chức năng đa hình và khi cần tham số trên một số loại. Điều gì có vẻ khó khăn hơn, với tôi, là tìm ra loại mô-đun bạn nên phụ thuộc vào khi làm việc trên thứ gì đó sâu hơn.

Nói chung, câu hỏi của tôi là thế này: khi tôi đang thiết kế một hệ thống module liên quan khác nhau như, làm thế nào tôi có thể tìm hiểu xem thiết kế xung quanh module cung cấp các chức năng đa hình hoặc module được tạo ra sử dụng functors tham số về chủng loại và giá trị ?

Tôi hy vọng sẽ minh họa cho tình huống khó xử và lý do tại sao nó quan trọng với ví dụ sau, lấy từ một dự án đồ chơi mà tôi đang làm việc.

Tôi có functor PostFix (ST:STACK) : CALCULATOR_SYNTAX. Việc này thực hiện việc triển khai cấu trúc dữ liệu ngăn xếp và tạo một trình phân tích cú pháp đọc ký hiệu bê tông ("đánh bóng ngược") thành cú pháp trừu tượng (được đánh giá bởi mô-đun máy tính xuống luồng) và ngược lại. Bây giờ, tôi đã sử dụng một giao diện đống tiêu chuẩn cung cấp một loại đống đa hình và số chức năng để hoạt động trên nó:

signature STACK = 
sig 
    type 'a stack 
    exception EmptyStack 

    val empty : 'a stack 
    val isEmpty : 'a stack -> bool 

    val push : ('a * 'a stack) -> 'a stack 
    val pop : 'a stack -> 'a stack 
    val top : 'a stack -> 'a 
    val popTop : 'a stack -> 'a stack * 'a 
end 

này hoạt động tốt, và mang lại cho tôi một số linh hoạt, như tôi có thể sử dụng một danh sách dựa trên ngăn xếp hoặc ngăn xếp dựa trên vectơ hoặc bất kỳ thứ gì. Nhưng, nói rằng tôi muốn thêm chức năng ghi nhật ký đơn giản vào mô-đun ngăn xếp, để mỗi khi một phần tử được đẩy đến, hoặc xuất hiện, ngăn xếp, nó sẽ in ra trạng thái hiện tại của ngăn xếp. Bây giờ tôi sẽ cần một fun toString : 'a -> string cho loại được thu thập bởi ngăn xếp, và điều này, như tôi hiểu, không thể được kết hợp vào mô-đun STACK.Bây giờ tôi cần phải đóng dấu các loại vào mô-đun, và tham số hóa các mô-đun trên các loại thu thập trong ngăn xếp và một chức năng toString mà sẽ cho phép tôi tạo ra một đại diện có thể in của loại thu thập được. Vì vậy, tôi cần một cái gì đó giống như

functor StackFn (type t 
       val toString: t -> string) = 
struct 
    ... 
end 

và điều này sẽ không tạo ra một mô-đun phù hợp với chữ ký STACK, vì nó không cung cấp một loại đa hình. Do đó, tôi phải thay đổi chữ ký bắt buộc cho hàm f2tor PostFix. Nếu tôi có nhiều mô-đun khác, tôi cũng phải thay đổi tất cả các mô-đun đó. Điều đó có thể bất tiện, nhưng vấn đề thực sự là tôi không còn có thể sử dụng các mô-đun STACK dựa trên danh sách đơn giản hoặc dựa trên vector của mình trong số PostFix functor khi tôi không muốn đăng nhập. Bây giờ, có vẻ như, tôi phải quay trở lại và viết lại các mô-đun đó để có một loại niêm phong là tốt.

Vì vậy, để quay trở lại, mở rộng theo, và (thương xót) kết thúc câu hỏi của tôi:

1. Có một số cách để xác định chữ ký của các module được tạo ra bởi StackFn để họ sẽ kết thúc như " trường hợp đặc biệt "của STACK?
2. Cách khác, có cách viết chữ ký cho mô-đun PostFix cho phép cả mô-đun được tạo bởi StackFn và các mô-đun thỏa mãn STACK?
3. Nói chung, có cách suy nghĩ về mối quan hệ giữa các mô-đun có thể giúp tôi nắm bắt/dự đoán loại điều này trong tương lai không?

(Nếu bạn đã đọc đến đây. Cảm ơn bạn rất nhiều!)

Answer 1

Như bạn đã phát hiện ra, có một sự căng thẳng giữa đa hình tham số và functors/mô-đun trong SML và OCaml. Điều này chủ yếu là do tính chất "hai ngôn ngữ" của các mô-đun và sự thiếu đa hình đặc biệt. 1ML và modular implicits đều cung cấp các giải pháp khác nhau cho vấn đề đó. Việc đầu tiên bằng cách thống nhất trở lại hai loại parametrism, sau này bằng cách cho phép lấp lánh một số đa hình ad-hoc khi cần thiết.

Quay lại cân nhắc thực tế. Với functors, nó khá dễ dàng (nhưng tiết ra/khó chịu) để định hình một datastructure đã cho. Đây là một ví dụ (trong OCaml). Với điều này, bạn vẫn có thể viết các triển khai chung và chuyên về chúng sau này (bằng cách cung cấp chức năng in).

module type POLYSTACK = sig 
    type 'a stack 
    exception EmptyStack 

    val empty : 'a stack 
    val isEmpty : 'a stack -> bool 

    val push : ('a * 'a stack) -> 'a stack 
    val pop : 'a stack -> 'a stack 
    val top : 'a stack -> 'a 
    val popTop : 'a stack -> 'a stack * 'a 
    val toString : ('a -> string) -> 'a stack -> string 
end 

module type STACK = sig 
    type elt 
    type t 
    exception EmptyStack 

    val empty : t 
    val isEmpty : t -> bool 

    val push : (elt * t) -> t 
    val pop : t -> t 
    val top : t -> elt 
    val popTop : t -> t * elt 
    val toString : t -> string 
end 

module type PRINTABLE = sig 
    type t 
    val toString : t -> string 
end 

module Make (E : PRINTABLE) (S : POLYSTACK) 
    : STACK with type elt = E.t and type t = E.t S.stack 
= struct 
    type elt = E.t 
    type t = E.t S.stack 
    include S 
    let toString = S.toString E.toString 
end 

module AddLogging (S : STACK) 
    : STACK with type elt = S.elt and type t = S.t 
= struct 
    include S 
    let push (x, s) = 
    let s' = S.push (x, s) in print_string (toString s') ; s' 
end