모듈을 설계 할 때 유형 수준 또는 모듈 수준 중 어느 것을 매개 변수화할지 결정하는 방법은 무엇입니까?

Question

ML 스타일 모듈에 대한 깊은 이해를 위해 노력하고 있습니다. 저는 개념이 중요하다고 생각하며 그들이 생각하는 종류의 것을 좋아합니다. 나는 단지 이며 파라 메트릭 유형과 파라 메트릭 모듈간에 발생할 수있는 긴장감을 발견했습니다. 내 프로그램을 구축 할 때 현명한 디자인 결정을 내릴 수 있도록 문제를 생각하는 도구를 찾고 있습니다.

주먹 나는 일반적으로 내 질문을 설명하려고합니다. 그런 다음, 제가 수행중인 학습 프로젝트의 구체적인 예를 으로 제공 할 것입니다. 마지막으로, 일반적인 질문을 다시 한 번 가리켜 설명하겠습니다. 일반적인 용어로

(. 나는 아직 더 간결하게이 질문을 제기하기에 충분를 모르는 미안 해요)

, 내가 발견 한 긴장은 이것이다 : 함수는 대부분의 유연하고 열려 가장 큰 재사용을 위해 매개 변수형 (적절한 경우)을 제공합니다. 그러나 모듈은 모듈 내부에서 함수의 매개 변수화를 봉인하고 대신 지정된 유형의 전체 모듈을 매개 변수화할 때 가장 넓은 재사용을 위해 가장 유연하고 개방적인 입니다.

이 차이의 준비 예 ORD_SET을 구현하는 것과 함께 LIST 서명을 구현 모듈을 비교에서 찾을 수 있습니다. 모듈 List:LIST은 유용한 기능을 제공하며 은 모든 유형에 대해 매개 변수화되었습니다. List 모듈을 정의하거나로드 한 후에는 을 사용하여 모든 유형의 목록을 구성, 조작 또는 처리 할 수있는 기능을 쉽게 적용 할 수 있습니다. 우리는 모두 문자열과 정수 작업하는 경우 예를 들어, 우리는 두 가지 유형의 값을 구성하고 조작하기 위해 하나의 동일한 모듈을 사용할 수 있습니다

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

을 다른 한편으로, 우리는 주문을 처리하려는 경우 문제가 다르다 : 주문 세트는 주문 관계가 모든 요소에 걸쳐 유지되어야하며 모든 유형에 대해 해당 관계를 생성하는 단일 구체 함수 compare : 'a * 'a -> order 이있을 수 없다. 따라서 주문 세트에 넣으려는 각 유형별로 ORD_SET 서명을 충족하는 다른 모듈이 필요합니다.따라서, 문자열 및 정수의 순서화 세트를 구성하거나 조작하기 위해서, 우리는 각각의 타입 [(1)]의 다른 모듈을 구현해야

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

이므로 그 적절한 모듈로부터 피팅 함수를 사용한다 때

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

여기에 매우 간단 트레이드 오프가있다 : 지정된 유형에서 작동 할 LIST 모듈은 모든 종류의 당신을 기쁘게 이상의 범위 기능 제공하지만, 그들은 어떤 관계 을 이용할 수없는 특정 유형의 값 사이를 유지합니다. ORD_SET 모듈은 매개 변수에 제공된 유형으로 필수적으로 제한되는 기능을 제공하지만 동일한 매개 변수화를 통해 에는 내부 구조 및 관계 유형에 대한 특정 정보를 통합 할 수 있습니다.

그것은 우리가 목록 모듈의 대안 가족 를 설계 할 것 곳에 더 복잡한 구조 목록과 같은 데이터 유형을 에 유형과 다른 값을 매개 변수화 제공하기 위해 펑터를 사용하여, 케이스를 상상하기 쉽다 : 예를 들어, 지정 정렬 된 목록의 데이터 형식 또는 자체 균형 조정 바이너리 검색 트리를 사용하여 목록을 나타냅니다.

모듈을 만들 때 이 다형 함수를 제공 할 수 있고 어떤 유형에 을 매개 변수화해야하는 경우를 인식하는 것이 매우 쉽다고 생각합니다. 나에게 더 많은 어려움이있는 것은 무엇보다 모듈 종류가 무엇인지 알아 내려고합니다. 일반적인 용어로

, 내 질문은 이것이다 : 나는 다양하게 관련 모듈 시스템을 설계하고 때 어떻게 알아낼 수 종류와 값에 대한 매개 변수 펑 을 사용하여 생성 된 다형성 기능 또는 모듈을 제공하는 모듈 주위를 설계 할 수 있는지 여부 ?

내가 작업하고있는 장난감 프로젝트에서 가져온 다음 예제를 통해 딜레마와 왜 중요한지를 설명하기 바랍니다.

나는 functor PostFix (ST:STACK) : CALCULATOR_SYNTAX입니다. 이것은 스택 데이터 구조의 구현을 취하고 추상 구문 ( 은 계산기 모듈 다운 스트림으로 계산 됨)으로 콘크리트 접미사 ("역 폴란드어") 표기법을 읽는 구문 분석기를 생성하며 그 반대의 경우도 마찬가지입니다.

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 

이 잘 작동, 나는 목록을 사용할 수있는, 나에게 약간의 유연성을 제공 : 지금, 나는 그것을 작동 다형성 스택 종류와 기능 를 제공 표준 스택 인터페이스를 사용하여 있었다 기반 스택 또는 벡터 기반 스택 또는 기타. 하지만 간단한 로킹 함수를 스택 모듈에 추가하여 요소가 푸시 될 때마다 또는 스택에서 이 튀어 나올 때마다 스택의 현재 상태를 출력합니다. 이제 은 스택에 의해 수집 된 유형에 대해 fun toString : 'a -> string을 필요로하며, 은 이것을 이해할 수 있으며 STACK 모듈에 통합 할 수 없습니다.이제 은 모듈에 유형을 봉인하고 스택에 수집 된 유형 및 toString 함수를 통해 모듈을 매개 변수화하여 인쇄 유형을 생성 할 수 있도록합니다. 그래서

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

같은 뭔가가 필요하고 이 다형성 타입을 제공하지 않기 때문에이 하지는 STACK 서명과 일치하는 모듈을 생성합니다. 따라서 PostFix 펑터에 대해 이 필요한 서명을 변경해야합니다. 다른 모듈이 많이있는 경우 을 모두 변경해야합니다. 그게 불편할 수도 있지만 진짜 문제는 내가 로깅을 원하지 않는다면 은 더 이상 내 간단한 목록 기반 또는 벡터 기반 STACK 모듈을 PostFix functor에 사용할 수 없다는 것입니다. 이제, 나는 다시 으로 가서 그 모듈을 봉인 된 유형으로 다시 작성해야합니다. 그들은 "로 오게 그래서 StackFn에 의해 생성 된 모듈의 서명을 지정하는 몇 가지 방법이 있나요

1. :

   그래서으로 돌아에 확장 (는 자비) 내 질문을 마칩니다 특별한 경우 "가 STACK일까요?

2. 달리, StackFn 의해 생성 모듈 STACK 만족 그들 모두 허용 것이다 PostFix 모듈 대한 서명을 작성하는 방법이 있는가?
3. 일반적으로 말하자면, 내가 이런 종류의 것을 미래에 잡으거나 예상하는 데 도움이되는 모듈 간의 관계에 대해 생각해 보는 방법이 있습니까?

(당신이 이것을 멀리 읽는 경우에. 대단히 감사합니다!)

Answer 1

당신이 발견으로, SML 및 OCaml의 파라 메트릭 다형성 및 펑/모듈 사이에 긴장이있다. 이것은 주로 모듈의 "2 개 언어"특성과 특수한 다형성의 부족 때문입니다. 1ML 및 modular implicits 모두 이러한 문제에 대한 다른 해결책을 제공합니다. 첫 번째는 두 종류의 매개 변수를 통합하여 나중에 필요에 따라 임의의 다형성을 발산하도록 허용하는 것입니다.

실제적인 고려 사항으로 돌아갑니다. 펑터 (functor)를 사용하면 주어진 데이터 구조를 단일체로 만드는 것이 매우 쉽습니다 (그러나 장황한/짜증나는). 다음은 OCaml에서의 예제입니다. 이를 통해 일반 구현을 작성하고 나중에 인쇄 기능을 제공하여 나중에 특수화 할 수 있습니다.

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