Jak zdecydować o parametryzacji na poziomie typu lub modułu podczas projektowania modułów?

Question

Pracuję nad głębokim zrozumieniem modułów w stylu ML: Myślę, że koncepcja jest ważna i uwielbiam ten rodzaj myślenia, który zachęcają. Jestem właśnie teraz odkrywam napięcie, które może powstać pomiędzy parametrycznymi typami a parametrycznymi modułami . Szukam narzędzi do myślenia o sprawach, które pomogą mi w podejmowaniu decyzji dotyczących inteligentnego projektu podczas tworzenia moich programów.

Pięść Spróbuję opisać ogólnie moje pytanie. Następnie przedstawię konkretny przykład z projektu nauczania, nad którym pracuję. Na koniec ponownie przejdę do pytania ogólnego, aby narysować je do pewnego punktu.

(. Przepraszam, że nie wiem jeszcze na tyle, aby stwarzać to pytanie bardziej zwięźle)

W ujęciu ogólnym, napięcie odkryłem to: funkcje są najbardziej elastyczny i otwarty do najszerszego ponownego wykorzystania, gdy dostarczymy im sygnatury typu parametrycznego (w stosownych przypadkach). Jednak moduły są najbardziej elastyczne i otwierają się do największego ponownego użycia, gdy uszczelniamy parametryzację funkcji wewnątrz modułu , a zamiast tego parametryzujemy cały moduł na danym typie.

Gotowy przykładem tej różnicy można znaleźć w porównywaniu moduły wdrożenia LIST podpis z tych, które realizować ORD_SET. Moduł List:LIST udostępnia szereg użytecznych funkcji, sparametryzowanych na dowolnym typie. Po zdefiniowaniu lub załadowaniu modułu List możemy łatwo zastosować dowolną z funkcji, które tworzy, manipulować lub analizować listy dowolnego typu. Na przykład, jeśli pracujemy z obu łańcuchów i liczb, możemy skorzystać z jednego i tego samego modułu do budowy i manipulować wartości obu typów:

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

Z drugiej strony, jeśli chcemy zająć się zamawiać zestawy, sprawy są różne: zestawy zamówione wymagają, aby relacja zamawiania obejmowała wszystkie ich elementy, i nie może być pojedynczej konkretnej funkcji compare : 'a * 'a -> order , tworząc taką relację dla każdego typu. W związku z tym wymagany jest inny moduł spełniający sygnaturę ORD_SET dla każdego typu, który chcemy umieścić w zestawach zamówionych .Tak więc, w celu skonstruowania lub manipulowania zbiorów uporządkowanych ciągów i całkowite musi wdrażać różne moduły do ​​każdego rodzaju [1]:

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

A trzeba następnie użyć funkcji okucia z odpowiedniego modułu gdy chcą działać na danym typie:

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

jest to dość proste kompromis tutaj: LIST moduły zapewniają funkcje które wahają się nad wszelkiego rodzaju proszę, ale nie mogą skorzystać z wszelkich stosunków że trzymaj się wartości dowolnego rodzaju; Moduły ORD_SET dostarczają funkcji, które są koniecznie ograniczone do typu dostarczonego w parametrze funktory , ale dzięki tej samej parametryzacji są w stanie , zawierając konkretne informacje o wewnętrznej strukturze i relacjach z ich typami docelowymi.

Łatwo sobie wyobrazić przypadki, w których chcielibyśmy zaprojektować alternatywną rodzinę modułów lista korzystając funktory do parametryzacji typów i inne wartości do zapewnić typy danych list-jak o bardziej skomplikowanej strukturze: np, aby określić typ danych dla uporządkowanej listy lub do reprezentowania list przy użyciu samowyzwalacza binarnego drzewek wyszukiwania.

Podczas tworzenia modułu, wydaje mi się, że dość łatwo jest rozpoznać, kiedy będzie on w stanie zapewnić funkcje polimorficzne i kiedy będzie trzeba sparametryzować na niektórych typach. To, co wydaje mi się trudniejsze, polega na zastanawianiu się, na jakie moduły powinieneś polegać, pracując nad czymś innym w dół.

Ogólnie, moje pytanie brzmi: kiedy jestem projektowaniu systemu różnie powiązanych modułów, w jaki sposób można dowiedzieć się, czy zaprojektować wokół modułów zapewniając polimorficzne funkcje lub moduły wytwarzane za pomocą funktorów parametryzowane w sprawie rodzajów i wartości ?

Mam nadzieję zilustrować dylemat i dlaczego ma to znaczenie w następującym przykładzie: wzięty z projektu zabawek, nad którym pracuję.

Mam functor PostFix (ST:STACK) : CALCULATOR_SYNTAX. To wymaga implementacji struktury danych stosu w postaci i tworzy parser, który odczytuje notację w postfixie ("reverse polish") w abstrakcyjnej składni (która ma być oceniana przez downstream modułu kalkulatora) i na odwrót. Teraz byłem za pomocą standardowego interfejsu stosu, który zapewnia polimorficzny rodzaj stosu i szereg funkcji, które działają na nim:

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 

to działa prawidłowo i daje mi pewną elastyczność, jak mogę skorzystać z listy na stosie lub na stosie wektorowym, lub cokolwiek innego. Ale, powiedzmy, chcę dodać prostą funkcję logowania do modułu stosu, tak aby za każdym razem, gdy element został przesunięty do, lub stosem, wydrukowałby bieżący stan stosu. Teraz będę potrzebować fun toString : 'a -> string dla typu zebranego przez stos, i tego, jak rozumiem, nie można włączyć do modułu STACK.Teraz I trzeba uszczelnić typ w module i sparametryzować moduł na typ zebrany w stosie i funkcję toString, która pozwoli mi wyprodukować reprezentację wydrukowanego typu z . Więc muszę coś podobnego

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

a to nie produkować moduł odpowiadający podpis STACK, ponieważ nie stanowią rodzaj polimorficzny. Dlatego muszę zmienić wymagany podpis dla funktora PostFix. Jeśli mam dużo innych modułów, muszę je wszystkie zmienić również na . To może być niewygodne, ale prawdziwym problemem jest to, że I nie może już używać moich prostych, opartych na listach lub opartych na wektorach modułów STACK w kamerze PostFix, gdy I nie chce rejestrować się w trybie. Teraz wygląda na to, że muszę cofnąć się o i przepisać te moduły, aby mieć również zapieczętowany typ.

Tak, aby powrócić do, rozszerzać, i (na szczęście) skończyć pytanie:

1. Czy jest jakiś sposób określania podpis modułów produkowanych przez StackFn tak, że oni skończyć jako " specjalne przypadki "z STACK?
2. Alternatywnie, czy istnieje sposób pisać podpis dla modułu PostFix która pozwoliłaby na obu modułów produkowanych przez StackFn i tych, które zaspokoić STACK?
3. Ogólnie rzecz biorąc, czy istnieje sposób myślenia o związku między modułami , który pomógłby mi złapać/przewidzieć tego rodzaju rzeczy w przyszłości?

(Jeśli czytać tak daleko. Dziękuję bardzo!)

Answer 1

Jak odkryto, istnieje napięcie między polimorfizmem parametrycznej i funktorów/modułu w SML i SML. Wynika to głównie z charakteru modułów "w dwóch językach" i braku polimorfizmu ad hoc. 1ML i modular implicits oba zapewniają różne rozwiązania tego problemu. Pierwszym z nich jest zjednoczenie dwóch rodzajówizmów, późniejszy, pozwalając w razie potrzeby na iskrzenie jakiegoś ad hoc polimorfizmu.

Powrót do praktycznych rozważań. W przypadku funktorów jest dość łatwe (ale pełne/denerwujące) do monomorfizacji danej struktury danych. Oto przykład (w OCaml). Dzięki temu nadal można pisać ogólne implementacje i specjalizować je później (poprzez zapewnienie funkcji drukowania).

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