Jazyk modulu ML

Modulový jazyk ML je modulový systém používaný především v programovacích jazycích rodiny ML , který má aplikační sémantiku, jinými slovy jde o malý funkcionální jazyk , který pracuje s moduly [1] .

Je to nejrozvinutější systém modulů mezi těmi, které se nacházejí v programovacích jazycích [2] [3] .

Obecné informace

Ve své nejjednodušší podobě se modulový jazyk skládá ze tří druhů modulů:

Podpis lze považovat za popis struktury, respektive strukturu za implementaci podpisu. Mnoho jazyků poskytuje podobné konstrukce, obvykle pod různými názvy: podpisy se často nazývají rozhraní nebo specifikace balíčků a struktury se často nazývají implementace nebo balíčky. Bez ohledu na terminologii je myšlenkou přiřadit typ celému kusu kódu. Na rozdíl od mnoha jazyků je v ML vztah mezi podpisy a strukturami mnoho - k - mnoho spíše než mnoho-jednomu nebo jeden - k-jednomu . Podpis může popisovat mnoho různých struktur a struktura může odpovídat mnoha různým podpisům. Většina ostatních jazyků je vázána přísnějšími omezeními, která vyžadují, aby daná struktura měla jeden podpis, nebo aby daný podpis byl odvozen z jediné struktury. To není případ ML [4] .

V běžných objektově orientovaných jazycích, jako je C++ nebo Java , je abstrakce poskytována prostřednictvím tříd , které kombinují řadu funkcí ( dědičnost , podtypování a dynamické odesílání ) v jednom konceptu najednou, což ztěžuje jejich formalizaci. a při neopatrném používání může vést k nežádoucím následkům. Na rozdíl od tříd se modulový jazyk ML zaměřuje výhradně na abstrakci , poskytuje širokou škálu jejích forem a poskytuje pevný formální základ pro jejich studium. [5] Poskytuje správu hierarchie jmenného prostoru , jemné přizpůsobení rozhraní , abstrakci na straně implementátora a abstrakci na straně klienta .

Funktory jsou jedinečný koncept, který nemá ve většině jazyků obdobu . Jsou to funkce nad strukturami, to znamená, že počítají nové struktury na základě již vypočítaných, přirozeně, v souladu s určitými signaturami. To vám umožňuje řešit širokou škálu problémů strukturování složitých programů .

V tomto případě jsou splněny dva požadavky [6] :

V praxi se ne vždy využívá možnost samostatné kompilace – existují plně optimalizující kompilátory, které otevírají rámec modulů pro výrazné zvýšení výkonu programů .

Jazyk

Struktury a podpisy

Prostředí ( angl.  environment ) v jádru ML ( angl.  Core ML ) je soubor definic ( typů včetně funkčních a hodnot včetně funkčních a exkluzivních ). Prostředí je lexikálně vymezeno .

Struktura ( structure) je "materializované" prostředí, přeměněné na hodnotu, se kterou lze manipulovat [7] . Ve vztahu k raným implementacím jazyka modulů je tato definice poněkud konvence, protože původně bylo možné struktury definovat nebo hodnotit pouze na nejvyšší úrovni kódu (v globálním prostředí). Následná práce rozvíjí jazyk modulu na prvotřídní úroveň .

Zavedení pojmu struktura vyžaduje revizi definice prostředí v jádru jazyka. Od této chvíle je prostředí souborem typů, hodnot a struktur. Struktura je tedy soubor typů, hodnot a dalších struktur. Rekurzivní vnořování struktur není povoleno, ačkoli je některé implementace podporují [5] .

Hlavním prostředkem pro definování struktur jsou zapouzdřené deklarace , tedy deklarace uzavřené v syntaktických závorkách struct...end. Například následující struktura implementuje zásobník , který definuje vnitřní organizaci objektů algebraického typu „stack“ a minimální požadovanou sadu funkcí nad ním:

typ struktury 'a t = 'a seznam val empty = [] val isEmpty = null val push = op :: val pop = List . getItem end

"Hodnotou" této zapouzdřené deklarace je struktura. Chcete-li použít tuto hodnotu, musíte jí přiřadit identifikátor:

struktura Zásobník = struct typ 'a t = 'a seznam val empty = [] val isEmpty = null val push = op :: val pop = List . getItem end

Ke komponentám struktury lze nyní přistupovat prostřednictvím složených (nebo kvalifikovaných) názvů, jako jsou Stack.push, Stack.empty : Stack.t.

Signatura ( signature) je výčet popisů prvků struktury, tedy rozhraní struktury. Každý prvek tohoto výčtu se nazývá specifikace. Pokud je u hodnoty v podpisu xuveden typ t , pak ve struktuře xmusí být identifikátor svázán s hodnotou typu t . Podpis si můžete představit jako druh „ typu “ struktury, ale podpis není typem v přísném slova smyslu, protože typ je sada hodnot a „hodnota podpisu“ může obsahovat typy (které v ML nejsou hodnoty). Každý identifikátor v podpisu musí být jedinečný. Není dodrženo pravidlo lexikálního stínování jmen v signaturách, nezáleží tedy na pořadí jejich výčtu, ale typy je nutné deklarovat před jejich použitím, proto se tradičně umisťují na začátek signatury.

Definice podpisu je zapsána v syntaktických závorkách sig...end. Struktura Stackmá například následující podpis (překladač to odvodí automaticky):

struktura Zásobník : sig typ 'a t = 'a list val empty : 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) možnost konec

Hlavní vlastností podpisů je , že s nimi lze porovnávat struktury .  Struktura je srovnatelná s daným podpisem, pokud obsahuje alespoň typy, hodnoty a vnořené struktury uvedené v podpisu [8] . Existují dvě formy porovnávání struktur s podpisy: transparentní ( anglicky  transparentní ) a tmavé ( anglicky  neprůhledné ). Obecně se možnost volby formy podepisování nazývá vlastnost průsvitnosti podpisů  [ 9 ] [10] .

Kompilátorem odvozený „výchozí podpis“ je obvykle nadbytečný, protože odhaluje implementační informace svých komponent veřejnosti, což je porušení principu abstrakce . Programátor proto ve většině případů výslovně popíše požadovaný podpis a provede podepsání podpisem ( anglický  popis podpisu ) nebo pečetí ( anglicky  pečetění ) [5] [3] [11] [12] , čímž zajistí, že komponenty jím zvolené struktury jsou před zbytkem programu skryty [13] . Přesněji se provádí vazba přizpůsobené struktury.

Vývojář může například definovat podpis popisující různé datové toky (datové struktury se sekvenčním přístupem) a přiřadit mu identifikátor:

podpis STREAM = sig typ 'a t val prázdný : 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * ' a t ) možnost konec

Vlastní signatura struktury může obohatit ( anglicky  obohacovat ) signaturu, se kterou se provádí porovnání, tedy obsahovat více komponent, více typů a tyto typy mohou být obecnější. Obohacovací vztah se formálně zapisuje jako (podpis obohacuje podpis ).

V tomto případě můžete napsat :

Transparentní párování má tradičně " S : SS" syntaxi, zatímco tmavé párování má syntaxi " " S :> SS. Tvůrci OCaml však zcela upustili od podpory transparentního párování, což znamená, že všechna mapování v OCaml jsou tmavá, ale pro jednoduchost je použita " " syntaxe. S : SS

V nejjednodušších případech můžete podpis podepsat okamžitě, aniž byste k němu přiřadili samostatný identifikátor:

struktura Zásobník :> typ sig 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) možnost konec = struct type 'a t = 'a list val empty = [] val isEmpty = null val push = op :: val pop = List . getItem end

V praxi jsou však bezejmenné podpisy poměrně vzácné, protože použití podpisů není omezeno na skrytí .

Jedna struktura v různých kontextech může být mapována na různé podpisy a jeden podpis může sloužit jako rozhraní pro různé struktury. Signatura definuje třídu struktur (v matematickém smyslu termínu " třída ") [14] . Odlišný „vnější pohled“ na jednu strukturu s různými stupni abstrakce může poskytnout několik signatur s různou sadou specifikací [15] . Na pořadí prohlášení nezáleží a nemá vliv na srovnatelnost struktur s podpisy.

To lze považovat za nejjednodušší analog abstraktních tříd (z hlediska objektově orientovaného programování ) v tom smyslu, že podpis popisuje společné rozhraní a struktury s ním srovnatelné implementují toto rozhraní různými způsoby. V ML však není vztah rodič-potomek explicitně deklarován, protože systém typů ML má strukturální , to znamená, že přiřazování struktury k podpisu se provádí stejným mechanismem jako přiřazování hodnoty 5k typu int.

Například lze definovat strukturu, která implementuje frontu , ale která je také srovnatelná s podpisem STREAM:

struktura Queue = struct datový typ 'a t = T of 'a list * 'a seznam val empty = T ([], []) val isEmpty = fn T ([], _) => true | _ => false val normalize = fn ([], ys ) => ( rev ys , []) | q => q fun push ( y , T ( xs , ys )) = T ( normalizovat ( xs , y::ys )) val pop = fn ( T ( x::xs , ys )) => NĚKTERÉ ( x , T ( normalizovat ( xs , ys ))) | _ => ŽÁDNÝ konec

Vzhledem k tomu, že struktura Stacknebyla explicitně podepsána horší signaturou, externí program "ví", že typ tje shodný s typem lista může tuto znalost využít ke zpracování objektů tohoto typu pomocí standardních modulových metod List. Pokud je později nutné změnit implementaci struktury Stack(například reprezentací zásobníku předem alokovaným polem ), bude to vyžadovat přepsání veškerého kódu, který tyto znalosti používal. Totéž platí pro strukturu Queue. Navíc, pokud byl modul parametrizován s vlastní signaturou struct , pak mu nebude možné předat strukturu jako parametr . StackQueue

Export nepotřebných informací ze struktur tedy výrazně zhoršuje modifikovatelnost programů. Pro zvýšení úrovně abstrakce by měly být struktury podepsány s horšími podpisy, například:

struktura Zásobník :> STREAM = struct type 'a t = 'a seznam val empty = [] val isEmpty = null val push = op :: val pop = List . getItem end

Struktura je Stackna signaturu namapována STREAMtmavým způsobem, takže externí program bude schopen plně pracovat s hodnotami typu Stack.t, ale nebude mít přístup k její implementaci a ke všem možným hodnotám tohoto typu, bude moci použít pouze hodnotu Stack.empty(opět „aniž byste věděli », že se rovná nil). Jakékoli zpracování dat tohoto typu bude prováděno abstraktně , bez zohlednění jeho implementace, a lze jej provádět pouze prostřednictvím funkcí Stack.pusha Stack.pop.

Ale nikde nejsou signatury důležitější a užitečnější než při použití funktorů [16] .

Dědičnost

Struktury mohou být vnořeny do sebe:

struktura E = struktura struktura A struktura B ... konec

Signatury vám přirozeně umožňují popisovat vnořené struktury. V tomto případě, stejně jako v jiných případech, je vnořování struktur řízeno na základě podpisů, a nikoli na základě identické náhody:

podpis D = sig struktura A : C struktura B : C konec

Podpisy mohou být zahrnuty (syntaxe include S) do sebe a postupně obohacují rozhraní:

signatura POOR = sig typ 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) možnost konec signatura RICH = sig include CHUDÝ val prázdný : 'a t end

Lze poznamenat, že podle popsané sémantiky nemusí být podpis podpisu proveden okamžitě. Pokud potřebujete vyvinout určitou sadu úzce propojených modulů, které jsou k sobě „přátelštější“ než ke zbytku programu, můžete po dokončení jeho vývoje podepsat struktury s horšími podpisy:

struktura SomeModule :> RICH = struct ... end ... struktura SomeModule :> POOR = SomeModule

Poslední řádek by neměl být považován za destruktivní úkol . Tento idiom je založen na lexikální viditelnosti , která je nedílnou součástí sémantiky jakéhokoli aplikačního jazyka . Jak v jádru ML , tak na úrovni modulu konstrukce x = avždy znamená vazbu hodnoty na identifikátor. Vazba není přiřazení , „vytváří“ nový identifikátor, který nemá nic společného s (možná) dříve definovaným [17] . Původní struktura SomeModulev programu stále existuje, ale následný kód nemá přístup k těm z jeho komponent, které nejsou součástí horší signatury (v tomto případě je to konstanta empty).

Strukturu lze otevřít (syntaxe open S). V nejjednodušším případě to lze považovat za syntaktický cukr , který slouží pro pohodlí použití definic zapouzdřených v modulu (analogický konstruktu withv jazyce Pascal ):

fun foo x = nechat otevřít SMLofNJ .Cont in fun f x = callcc ( fn k => ... hodit k ...) fun g x = izolovat ... konec

Pokud je totéž provedeno na nejvyšší úrovni programu (v globálním prostředí), lze to považovat za analogii konstruktu using namespacev jazyce C++ . Například struktury, které implementují standardní typy a operace na nich ( Int, Real, Stringa další), jsou ve výchozím nastavení otevřené (více o tom viz ovládání čísel ). Možnost otevírání struktur však existuje i uvnitř jiných struktur a v tomto případě slouží otvor jako nástroj pro začleňování struktur do sebe za účelem důsledného rozšiřování funkčnosti (obdobně jako u nejjednodušší dědičnosti tříd ). Například:

struktura B = struktura otevřená A ... konec

Struktura Bzahrnuje všechny definice struktury Aa doplňuje je o nové definice. To je stejné jako explicitní výpis všech definic Av B. Tato možnost má dvě nevýhody [18] :

  • pokud jsou v otevírané struktuře identifikátory, které odpovídají již existujícím identifikátorům v daném kontextu, pak se tyto stanou nepřístupnými pro přímý přístup. Naopak definice po otevření zastíní importované komponenty. Nedochází ke konfliktu názvů – je viditelná pouze poslední definice – ale to může být pro vývojáře nepohodlné. Výjimkou je, pokud se názvy typů shodují s existujícími názvy hodnot, protože kompilátor ML může vždy určit význam identifikátoru z kontextu jeho použití [19] (viz odvození typu ). Problém stínování názvů je zvláště aktuální, když zahrnuje dvě nebo více struktur.
  • někdy je obtížné určit, co přesně je zahrnuto z otevřené struktury, zejména při otevírání velkých struktur, které definují velký počet identifikátorů.

Proto se často doporučuje místo otevření použít zavedení krátkého místního identifikátoru [18] , například:

struktura SomeModule :> sig fun f x : ... fun g x : ... ... end = struct lokální struktura C = SMLofNJ . Pokračovat v ... zábava f x = C . callcc ( fn k => ... C . hod k ...) fun g x = C . izolovat ... _ _

Někdy však může být přednost poslední definice použita k záměrnému "předefinování" identifikátoru (což však není přetížení ).

Historické pozadí

Dříve v definici SML'90 [20] bylo možné otevřít v podpisech. Tato funkce byla kritizována kvůli zhoršení autodokumentace (naučení se rozhraní jednoho modulu při jeho používání vás nutí odkazovat na jiný) [21] a byla zrušena v revizi jazyka SML'97. Zde je důležité poznamenat, že otevření ( open) se zásadně liší od zahrnutí ( include), protože každý identifikátor musí být uvnitř podpisu jedinečný a pravidlo stínování jména se nedodržuje, takže identifikátor ze zahrnutého podpisu, který se shoduje s identifikátorem v podpisu nový vede k chybě kompilace.

V SML'90 [20] existoval zvláštní poddruh podpisu - abstractiona pro běžné podpisy existovala pouze jedna forma shody - transparentní ( S : SS). Při revizi jazyka v roce 1997 byla tato část jazyka modulu zjednodušena: místo abstraktních signatur byla  zavedena tmavá ( neprůhledná ) shoda s signaturou ( S :> SS) ( řešení je založeno na kalkulu Harper-Lilybridge translucent součty ).

Funktory

Funktor ( functor) je funkce nad strukturami , tedy funkce, která vezme strukturu jako vstup a vytvoří novou strukturu [22] . Někdy se na funktor vizuálně nahlíží jako na "parametrizovanou strukturu", tedy strukturu, jejíž definice je sestavena překladačem na základě nějaké jiné struktury podle pravidel určených programátorem. Ortodoxie však tvrdí, že funktory by měly být považovány za zvláštní funkce [23] .

Signatura hraje roli typu parametru funktoru. Všechny druhy struktur, které lze spárovat s tímto podpisem, hrají roli hodnot patřících k tomuto typu a předávaných funktoru k hodnocení nových struktur [22] . Struktura získaná aplikací funktoru má vlastní signaturu (i když obecně řečeno se nemusí lišit od signatury parametru).

Obecná forma definice funktoru vypadá takto:

funktor F ( X : S1 ) : S2 = tělo

Příklady použití:

struktura B1 = F ( A1 ) struktura B2 = F ( A2 ) struktura B3 = F ( A3 ) ...

Funktory vám umožňují popsat typově bezpečným způsobem nejrozmanitější formy vztahů mezi komponentami programu, řešící širokou škálu problémů se strukturováním kódu [24] :

  • Implementace generických algoritmů a správy závislostí. Funktory vám umožňují kombinovat velké komponenty podobného chování, ale různé implementace v programu a podle potřeby je nahradit. To je užitečné zejména ve fázi rychlého prototypování , kdy musíte testovat systém po částech nebo simulovat chování zjednodušeným způsobem (viz například kontrola čísel a testování struktury ).
  • Automatické rozšíření funkčnosti. Funktory vám ušetří rutinní práci, když potřebujete implementovat stejnou funkcionalitu pro různé typy. Pokud chcete například definovat množiny z prvků různých datových typů, pak v ML stačí definovat funktor, který generuje strukturu definující množinu na základě struktury, která definuje typ jednoho prvku. V jiných jazycích se tento druh problému řeší pomocí generativního programování .
  • Instanciační moduly se zapouzdřeným proměnlivým stavem . Pokud struktura zapouzdřuje proměnlivý stav a program potřebuje mít několik jeho instancí s nezávislými stavy, pak vám funktory umožňují automatizovat konstrukci takových struktur.

Tyto možnosti nejlépe ilustrují názorné příklady .

Někteří programátoři však místo struktur používají funktory (tj. popisují funktor a definují strukturu jako jeho jedinou aplikaci na známý parametr a někdy i funktor s prázdným parametrem). Tento přístup se na první pohled zdá přehnaný, ale v praxi poskytuje dvě výhody, které zvyšují produktivitu vývojářů ve velkých projektech [25] [26] :

  • na jedné straně je správná organizace rozhraní zajištěna okamžitě ve fázi kompilace sotva napsaného modulu, a nikoli v průběhu vývoje projektu (protože vzájemné závislosti struktur na sobě jsou v tomto případě řízeny mechanismem porovnávání typů a nejsou detekovány během montáže)
  • na druhou stranu se struktury na sobě stávají "více nezávislé", takže mohou být vyvíjeny v libovolném pořadí a programátoři v týmu mohou pracovat přesně opačnými směry ( shora dolů nebo zdola nahoru ).

co-use .

Ekvivalence typu

Při programování ve velkém měřítku , kdy jsou moduly propojeny za účelem vytvoření nových, složitějších, vyvstává otázka konzistence abstraktních typů exportovaných z těchto modulů. K vyřešení tohoto problému poskytuje jazyk modulu ML speciální mechanismus, který vám umožňuje explicitně označit identitu dvou nebo více typů nebo struktur:

podpis D = sig struktura A : C struktura B : C typ sdílení A .t = B . t konec

Taková specifikace omezuje povolený soubor zastupitelných struktur a deklaruje požadavek, že se musí jednat o struktury, které sdílejí ( anglicky  share ) použití stejné specifikace (typ, podpis nebo struktura). S podpisem jsou tedy srovnatelné pouze ty struktury , ve kterých identifikátor znamená stejný typ [27] . Proto se tato specifikace nazývá „ omezení sdílení “.  Dt

Poznámka - v ruskojazyčné literatuře není překlad tohoto termínu ustálen. Jsou možné varianty jako „ specifikace společného použití “ [28] , „ omezení sdílení “, stejně jako sémantický překlad „ požadavek na oddělitelnost “ nebo „ požadavek na sdílení “ . Existuje [29] překlad „ sdíleníomezení “ , což je sémantická chyba.

Sémanticky existují dvě formy takové specifikace – jedna pro podpisy a typy, jedna pro struktury – ale jejich syntaxe je identická. Druhá forma je restriktivnější: dvě struktury si mohou být rovny tehdy a jen tehdy, když jsou výsledkem hodnocení stejné deklarace struktury nebo aplikace stejného funktoru na stejné aktanty [28] .

Specifikace společného použití se také používá k vynucení zúžení rozsahu povolených typů v určitém konkrétním kontextu použití podpisu, který je pro něj „příliš abstraktní“, například:

funktor Try ( Gr : sig typ g typ sdílení g = int hodnota e : g val odrážka : g * g -> g val inv : g -> g end ) = struct val x = Gr . inv ( Gr . odrážka ( 7 , 9 ) ) konec

Signatura parametru funktoru zde klade zvláštní požadavek na složení struktury, kterou mu lze skutečně předat: abstraktní typ g v něm použitý musí být typ int. Případy, kdy je to nutné, jsou poměrně běžné, takže v SML'97 [30] byla pro zjednodušení jejich popisu a možnosti použití pojmenovaných signatur přidána alternativní konstrukce pro specifikaci co-use: where type(v OCaml syntaxe ) : with type

podpis SKUPINA = sig typ g val e : g val odrážka : g * g -> g val inv : g -> g konec funktor Try ( Gr : GROUP kde typ g = int ) = struct val x = Gr . inv ( Gr . odrážka ( 7 , 9 ) ) konec

Obě provedení mají svá omezení.

sharingumožňuje vyjádřit rovnost typů bez konkrétního určení jejich struktury. Konstrukce může mít libovolnou aritu :

podpis S = sig struktura A : S struktura B : S struktura C : S struktura D : S typ sdílení A .t = B . t = C. _ t = D. _ t konec

ale umožňuje odkazovat na abstraktní typy pouze přímo - tzn. vyjádření formy

typ sdílení B .t = A . t * A . t

where typeje unární a má naopak konkretizovat abstraktní typ známým typem (neumožňuje však měnit strukturu již konkretizovaného typu).

Konstrukce není v OCaml podporována , takže byste měli vždy používat . V nástupnickém ML má implementovat jeden nejuniverzálnější konstrukt. sharingwith type

Dalším důležitým aspektem stanovení ekvivalence abstraktních typů je plodnost funktorů .

Standardní ML využívá generativní sémantiku funktorů, což znamená, že každá aplikace funktoru na stejnou strukturu generuje nové definice typu, tzn. dva typy stejného jména a identické struktury, které patří k různým strukturám, nejsou stejné.

OCaml používá aplikační funktory, což znamená, že aplikace funktoru na prokazatelně stejné aktanty automaticky generuje stejný výsledek. To snižuje potřebu specifikace společného užití a je zvláště užitečné při práci s funktory vyššího řádu. Počínaje verzí 4 přidává OCaml možnost učinit funktory rodičovskými.

Rozšíření a dialekty

Funktory vyššího řádu

Funktor dostává jako vstup jednu strukturu specifikovanou signaturou. Aby bylo možné projít několika strukturami, je nutné sestavit další strukturu obalu, která tyto struktury zahrnuje a popíše odpovídající podpis. Definice standardního jazyka ML pro pohodlí poskytuje syntaktický cukr – několik parametrů lze předat jako n-tici a kompilátor automaticky vytvoří obklopující strukturu a její podpis. Jádro ML však poskytuje funkce vyššího řádu a následovat k nim analogii na úrovni modulu znamená zavést curried formu funktorů. Ve skutečnosti jediná věc, kterou je třeba v jazyce implementovat, aby poskytoval tuto schopnost, je podpora pro popis funktorů v signaturách [31] [32] . Nejedná se o zásadní novinku (na rozdíl od prvotřídních modulů ) - curried funktory nic neumožňují, ale klasické prvořádové ne - jejich dostupnost však výrazně zjednodušuje implementaci (a tedy čitelnost ) komplexních víceúrovňové hierarchie komponent [32] .

Nápadným příkladem výhodnosti použití funktorů vyšších řádů je implementace plnohodnotných monadických kombinátorů .

Potenciál pro implementaci funktorů vyššího řádu byl již zaznamenán v komentářích [31] k definici SML'90 [20] . Mnoho standardních kompilátorů ML poskytuje určitou implementaci funktorů vyššího řádu jako experimentální rozšíření [32] . Ocaml implementuje všechny druhy modulů syntakticky jednotným způsobem, takže použití funktorů vyšších řádů je nejpřirozenější.

Poznámka - v ruskojazyčné literatuře dochází [33] k záměně mezi " moduly vyššího řádu " a " moduly první třídy " , což je sémantická chyba.

Objektově orientované prvky

Plná podpora objektově orientovaného programování podle Abadiho a Cardelliho (viz Objektově orientované programování#Klasifikace podtypů OOP ) znamená zároveň podporu:

  • podtypování vztahů
  • objektů
  • typy objektů
  • třídy (generátory objektů)

To vše již řadu let poskytuje Ocaml . Parametrický polymorfismus se navíc rozšiřuje i na tyto vlastnosti , což činí jazyk ještě výraznějším. Jazyk modulů v OCaml byl samozřejmě vylepšen, aby bylo možné do modulů zahrnout objekty a třídy.

Tato zařízení (možná rozšířená o typy vyššího řádu - viz podtypování vyššího řádu ) se stanou součástí nástupnického ML .

Moduly první třídy

Problém

Slabinou původního jazyka modulů je, že není uzavřený vůči základnímu jazyku: základní typy a hodnoty mohou být součástmi modulů, ale moduly nemohou být součástmi základních typů a hodnot. V SML bylo toto rozdělení jazyka do dvou vrstev provedeno záměrně, protože značně zjednodušilo mechanismus kontroly konzistence typu [31] . To však znemožňuje dynamické propojení modulů, což znamená, že následující výraz je neplatný:

struktura Mapa = if maxElems < 100 pak BinTreeMap jinak HashTableMap (* není povoleno v klasickém ML! *)

Takový zákaz je ostudou tak výrazného modulového systému, protože by byl zcela normální pro jakýkoli objektově orientovaný jazyk [34] .

Jazyk modulu ML ve skutečnosti nemusí být statický [35] (viz část o nízkoúrovňové reprezentaci ). Problém spočívá především ve statické kontrole typu , která je povahou ML . Podpora v ML pro moduly první třídy sama o sobě není problém pro jazyk modulů prvního řádu (který neobsahuje funktory), ale je to kombinace prvotřídních modulů s moduly vyššího řádu jazyka „do jiné reality“ [36] , tedy otevírá obrovské možnosti, ale výrazně komplikuje jak mechanismy pro odvozování a kontrolu konzistence typů jazyka [37] , tak jeho celoprogramovou optimalizaci . Myšlenku prvotřídních modulů pohřbili na mnoho let Harper a Lilybridge tím, že zkonstruovali idealizovanou verzi prvotřídního modulového jazyka pomocí teorie závislých typů a dokázali, že kontrola konzistence typů pro tento model je nerozhodnutelný [9] [38] . Postupem času se však začaly objevovat alternativní modely využívající jiná zdůvodnění.

Balíčky

Na konci 20. století Claudio Russo navrhl [39] [40] nejjednodušší způsob, jak udělat moduly prvotřídní : doplnit seznam primitivních typů jádra jazyka o typ „ package “ ( anglicky  package ) , což je dvojice структура : сигнатура, a seznam výrazů jádra s operacemi sbalení a rozbalení. Jinými slovy, mění se pouze jádro jazyka a jazyk modulů zůstává nezměněn [41] .

Sbalení struktur do balíčků a následné rozbalení umožňuje dynamicky vázat různé struktury na identifikátory (včetně těch, které jsou vypočteny pomocí funktorů). Nejjednodušší příklad [42] :

struktura Mapa = rozbalit ( pokud maxElems < 100 pak zabalit BinTreeMap : MAP jinak zabalit HashTableMap : MAP ) : MAP

Při rozbalování balíku lze strukturu podepsat jiným podpisem, včetně horšího podpisu .

Explicitní přítomnost podpisu v balíčku odstraňuje problém odvození typu a párování během dynamického rozbalování struktury. To vyvrací ranou Harper-Mitchellovu tezi o nemožnosti povýšit struktury v ML na prvotřídní úrovně, aniž by se obětovalo oddělení fází kompilace a běhu a rozhoditelnost systému kontroly konzistence typu [41] , protože místo prvního- řádově závislé typy , rozšíření teorie existenciálních typů se používá jako ospravedlnění Mitchell-Plotkin druhého řádu [43] .

V této podobě jsou od 4. verze implementovány prvotřídní moduly v Alice a v Ocamlu

1ML

Rossberg, inspirovaný F-konverzí , vkládá modul boxing-unboxing hlouběji do sémantiky jazyka, což má za následek monolitický jazyk, ve kterém jsou funktory, funkce a dokonce i typové konstruktory skutečně tím samým primitivním konstruktem a bez rozdílu. vytvořené mezi záznamy , n-ticemi a strukturami - vnitřní reprezentace jazyka je plochý Systém F ω . To přineslo celou řadu pozitivních výsledků [44] :

  • prokazování spolehlivosti jazyka se stává mnohem jednodušším než tradičně pro jazyk modulů (není vyžadováno použití teorie závislých typů );
  • podpora je poskytována pro "materializované" ( angl.  reified ) typy v jádru jazyka, poskytující jazyku vyjadřovací sílu na úrovni systémů se závislými typy (a opět nevyžadující jejich přítomnost v metateorii);
  • jazyk jako celek se ukazuje být jak expresívnější (umožňuje popisovat složité systémy prostorněji a přesněji), tak jednodušší (minimalističtější a jednotnější ve složení).

Jazyk byl nazván „ 1ML “, což odráží jak podporu skutečně prvotřídních modulů, tak sjednocení primitiv a modulů v jediném jazyce (nerozděleném na dvě vrstvy) [44] .

Rozhodnutí bylo založeno na myšlence Harper-Mitchell rozdělit typy na „malé“ a „velké“. Rossberg aplikoval toto rozlišení na pravidlo zahrnutí konzistence typu (základní porovnávání mezi strukturou a podpisem), čímž se stalo řešitelným .

Předpokládá se, že další vývoj 1ML může také poskytnout dostatečnou expresivitu pro podporu mnoha zajímavých modelů, jejichž implementace byla dříve považována za obtížnou: typové třídy , aplikační funktory , rekurzivní moduly atd. Zejména zavedení inline polymorfismu v 1ML pravděpodobně okamžitě umožní vyjádřit podtypování do šířky , což udrží metateorii jednoduchou a zároveň výrazně rozšíří její možnosti. [45]

MixML

MixML [10] je modulový jazyk vytvořený kombinací McQueenova klasického modulového jazyka ML a formalizace modelu mix - in od Bracha & Cook .  Autory MixML jsou Rossberg a Dreyer.

Základní myšlenka MixML je jednoduchá: struktury a podpisy jsou spojeny do jediného konceptu modulu, který kombinuje definice a specifikace, jak transparentní, tak abstraktní.

To umožňuje definovat libovolné grafy závislostí v programech, včetně cyklických. Zejména to umožňuje zabudovat funktory nejen přímou parametrizaci (závislost výstupu na vstupu), ale také rekurzivní (závislost vstupu na výstupu), při zachování podpory samostatné kompilace (na rozdíl od mnoha soukromých modelů, které rozšiřují jazyk modulu ML s podporou rekurze) .

MixML implementuje jeden jednotný zápis pro tradičně párované sémantické modely (pro struktury a signatury zvlášť) a velké množství samostatných mechanismů klasického jazyka modulů ML, jako jsou:

  • dědění (zařazení) podpisů
  • specifikace společného použití
  • dvě formy podpisu podpisu (transparentní a tmavý)
  • aplikace funktorů

Různé

U různých modelů jsou k dispozici také následující rozšíření:

  • lokální moduly
  • mnoho možností pro rekurzivní systém modulů, které umožňují vytvářet cyklické grafy závislostí, z nichž nejvýraznější je systém MixML (většina ostatních neposkytuje možnost samostatné kompilace)
  • rozšířená podpora vnořování modulů
  • zobecněný zápis pro otevírání struktur
  • různé možnosti omezení společného užívání
  • vnořené podpisy, včetně abstraktních
  • deklarace operátorů infix specifikující asociativitu a prioritu v podpisech a vyžadující přesnou shodu

Jazykový ekosystém

Implementace a dialekty

Alice

Jazyk Alice je rozšířením standardu ML , včetně mnoha myšlenek nástupnického projektu ML , stejně jako pokročilých konkurenčních programovacích nástrojů pro vývoj distribuovaných aplikací, podpory silného dynamického psaní a řešení omezení . Navrhl Andreas Rossberg.

Jazyk modulů v Alice je rozšířen o zápis komponent ( angl.  components ), které implementují prvotřídní moduly v podobě balíčků Russo a navíc podporují dynamické typování (ovšem podle stejných pravidel statické sémantiky) a líné načítání (tj. jsou podporovány budoucí struktury a budoucí podpisy – viz budoucí výzva ) [46] [47] . odvození typu je v Alice respektováno a v případě potřeby by měla být použita specifikace co-use . Názorný příklad praktické užitečnosti balíčků přichází s Alice : knihovnou pro serializaci dat , která umožňuje vláknům vyměňovat si dynamické typy a data.

Kromě toho Alice poskytuje syntaktický cukr - schopnost volně používat závorky ve výrazech modulového jazyka, včetně namísto tradičních "závorek" struct...enda sig...end:

val p = pack ( val x = length ) : ( val x : 'a list -> int ) (* val p : package = package{|...|} *) OCaml

V Ocaml je syntaxe jazyka modulu jednotná:

typ modulu S = (* podpis *) sig ... modul M : T (* vnořená struktura *) konec modul X : S = (* struktura *) struktura ... konec modul F ( X : S ) = (* parametrizovaná struktura (funktor) *) struktura ... konec modul G ( X : S ) ( Y : T ) = (* curried parametrizovaná struktura (funktor vyššího řádu) *) struktura ... konec

V sémantice však existuje řada rozdílů [48] .

Počínaje verzí 4 podporuje Ocaml prvotřídní moduly v notaci podobné Aliciným balíčkům . Syntaxe je stále homogenní, to znamená, že vypadá k nerozeznání od vnořených struktur v signaturách.

Od svého založení Ocaml rozšiřuje modulový jazyk o třídy a objekty .

Nejdůležitější rozdíly mezi Standard ML a Ocaml se objevují v sémantice typové ekvivalence (viz část o ekvivalenci typů ).

Správa modulů

K propojení obřích ML programů lze v zásadě použít tradiční linkery pro většinu jazyků , jako je make . Modulový jazyk SML je však mnohem výkonnější než modularizační nástroje jiných jazyků [2] a make nepodporuje jeho výhody, a tím spíše není vhodný pro globální analýzu řídicího toku programů [49] . Proto různé kompilátory nabízejí své vlastní systémy správy modulů: Compilation Manager (CM) v SML/NJ a MLBasis System (MLB) v MLton . SML.NET [50] má vestavěný systém sledování závislostí. MLton také obsahuje konvertor souborů .cm na .mlb .

Většina implementací používá samostatnou kompilaci, což vede k rychlé kompilaci. Pro podporu samostatné kompilace v režimu REPL se používá funkce use, která zkompiluje zadaný soubor a importuje definice. Některé kompilátory (například MLton ) nepodporují REPL , a proto neimplementují podporu pro use. Jiní (například Alice ) naopak implementují další funkce dynamické kompilace a načítání modulů během provádění programu. Poly/ML [51] poskytuje funkci PolyML.ifunctor, která umožňuje interaktivně ladit implementaci funktoru kousek po kousku.

Příklady programů

Navzdory své jednoduchosti je jazyk modulu pozoruhodně flexibilní a poskytuje vysokou úroveň opětovného použití kódu , jak ilustrují následující příklady.

Správa počtu číslic

Tradiční datové typy , jako jsou celá čísla ( inta word), reálná ( real), znak ( chara widechar), řetězec ( stringa widestring), pole ( vectora array) a další, jsou implementovány v dialektech ML, nikoli ve formě primitivních typů a vestavěných operátorů přes jako ve většině jazyků, ale ve formě abstraktních datových typů a odpovídajících funkcí obsažených v signaturách, , , INTEGER, atd . , které jsou poskytovány ve formě standardních knihoven. Implementace konkrétního jazyka mohou poskytnout velmi efektivní reprezentace těchto abstraktních typů (například MLton reprezentuje pole a řetězce stejným způsobem jako jazyk C ). WORDREALCHARSTRING

Například:

podpis INTEGER = sig eqtype int val toLarge : int -> LargeInt . int val fromLarge : LargeInt . int -> int val toInt : int -> Int . int val fromInt : Int . int -> int přesnost valu : Int . int možnost val minInt : možnost int val maxInt : možnost int val ˜ : int -> int val * : ( int * int ) -> int val div : ( int * int ) -> int val mod : ( int * int ) - > int val quot : ( int * int ) -> int val rem : ( int * int ) -> int val + : ( int * int ) -> int val - : ( int * int ) -> int val porovnat : ( int * int ) -> hodnota objednávky > : ( int * int ) -> hodnota bool > = : ( int * int ) -> hodnota bool < : ( int * int ) -> hodnota bool < = : ( int * int ) -> bool val abs : int -> int val min : ( int * int ) -> int val max : ( int * int ) -> int val sign : int -> Int . int val sameSign : ( int * int ) -> bool val fmt : StringCvt . radix -> int -> string val toString : int -> string val fromString : string -> int volba val scan : StringCvt . radix -> ( char , 'a ) StringCvt . reader -> 'a -> ( int * 'a ) možnost end

Struktury , , , a mnoho dalších INTEGERlze porovnat s podpisem . Stejně tak struktury / a / (a ​​případně další) lze spárovat se signaturami / a pro každou variantu budou funktory generovat příslušný I/O zásobník ( , ). Int8Int16Int32Int64IntInfCHARSTRINGCharStringWideCharWideStringStreamIOTextIO

Některé struktury zároveň skrývají tradiční strojovou reprezentaci pod abstraktní definicí (například , Int32) Int64, jiné - bitová pole (například Int1) a struktura IntInfimplementuje dlouhou aritmetiku . Knihovny zároveň mohou intenzivně procházet vztahy mnoho k mnoha : specifikace SML Basis definuje sadu požadovaných a volitelných modulů postavených na implementaci „primitivních“ typů: monomorfní pole, jejich nekopírovací řezy a tak dále. . Dokonce i typy "string" ( ) a "substring" ( ) jsou definovány ve specifikaci SML Basis jako a (nebo a pro ). Pro použití stejných algoritmů s čísly různé kapacity tedy stačí explicitně předat odpovídající strukturu funktoru (otevření nezmění již vypočítané struktury). stringsubstringChar.char vectorChar.char VectorSlice.sliceWideChar.char vectorWideChar.char VectorSlice.sliceWideString

Různé kompilátory poskytují různé sady implementovaných struktur. MLton poskytuje nejbohatší sortiment : od Int1do Int32včetně a Int64, stejnou sadu pro Word(celá čísla bez znaménka), stejně jako IntInf(implementováno knihovnou GNU Multi-Precision Library ) a mnoho dalších, jako jsou Int32Array, PackWord32Big, PackWord32Littlea další.

Ve většině implementací je ve výchozím nastavení na nejvyšší úrovni (v globálním prostředí) otevřená struktura Int32(nebo Int64), to znamená, že použití typu inta operace +ve výchozím nastavení znamená použití typu Int32.inta operace Int32.+(nebo resp Int64.int. Int64.+). Kromě toho jsou poskytovány identifikátory Inta LargeInt, které jsou standardně vázány na určité struktury (například LargeIntobvykle rovno IntInf). Různé kompilátory v závislosti na jejich orientaci mohou standardně používat různé vazby v globálním prostředí a taková jemnost může ovlivnit přenositelnost programů mezi kompilátory. Například konstanta Int.maxIntobsahuje hodnotu největšího možného celého čísla, zabalenou do volitelného typu a musí být získána buď pomocí vzoru, nebo voláním funkce valOf. U typů konečných rozměrů je hodnota a obě metody extrakce jsou ekvivalentní. Ale rovná se , takže přímý přístup k obsahu přes způsobí výjimku . Ve výchozím nastavení je otevřen v kompilátoru Poly/ML [51] , protože je zaměřen na problémy drtiče čísel . IntN.maxIntSOME(m)IntInf.maxIntNONEvalOf OptionIntInf

Abstraktní sady

Knihovny OCaml obsahují modul , který poskytuje funktor . S ním můžete snadno sestavit sadu založenou na daném typu prvku: SetMake

modul Int_set = Set . Make ( typ struktury t = int nech porovnat = porovnat konec )

Generovaný modul celočíselné sady má následující kompilátor - odvozený podpis:

modul Int_set : sig typ elt = int typ t val prázdný : t val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val srovnání : t -> t -> int val rovno : t -> t -> bool val podmnožina : t -> t -> bool val iter : ( elt -> unit ) -> t -> unit val fold : ( elt -> ' a -> ' a ) -> t -> ' a -> ' a val for_all : ( elt -> bool ) -> t -> bool val existuje : ( elt -> bool ) -> t -> bool val filter : ( elt -> bool ) -> t -> t val partition : ( elt -> bool ) -> t -> t * t val cardinal : t -> int val elements : t -> elt list val min_elt : t -> elt val max_elt : t -> elt val zvolte : t -> elt val split : elt -> t -> t * bool * t val find : elt -> t -> elt end

Podobná funkce je obsažena v knihovnách kompilátoru SML/NJ ( ListSetFn). SML Basis poskytuje pouze základní nástroje.

Hlavním účelem použití závislého modulu namísto jednoduché struktury je to, že porovnávací funkce je specifikována jednou a všechny funkce na konkrétní typované sadě používají stejnou porovnávací funkci na typu prvků této sady, takže programátor je tak chráněn před vlastními chybami. Abstraktní množiny by se daly implementovat tak, že každá funkce přes množinu pokaždé předá porovnávací funkci (jak se to dělá např. ve standardní funkci jazyka C qsort – viz parametrický polymorfismus v C a C++ ), ale to by nebylo pouze zvýšilo složitost práce s množinami, ale také by s sebou neslo riziko záměny požadované porovnávací funkce zavedením těžko odhalitelné chyby do programu (viz duplikace kódu ).

Bohužel [24] historicky OCaml přijal signaturu pro porovnávací funkci, která označuje návratovou hodnotu obousměrného ( booleovského ) typu (a konvence tohoto druhu by měly být dodržovány, aby bylo možné široce používat knihovní moduly) . Výkonnější je řešení SML Basis (stejně jako Haskell Prelude ) založené na třícestném typu:

pořadí datových typů = MÉNĚ | EQUAL | VĚTŠÍ val porovnávat : int * int -> pořadí

Strukturální testování

U rapid prototypingu je často nutné testovat systém po částech nebo simulovat chování zjednodušeným způsobem (implementovat tzv. „stub“). Funktory tento úkol zvládají elegantně.

Řekněme například, že existují tři různé implementace nějaké datové struktury , řekněme fronty [52] :

podpis QUEUE = sig type 'a t výjimka E val prázdný : 'a t val enq : 'a t * 'a -> 'a t val null : 'a t -> bool val hd : 'a t -> 'a val deq : 'a t -> 'a t konec struktura Queue1 :> QUEUE = struct ... konec struktura Queue2 :> QUEUE = struct ... konec struktura Queue3 :> QUEUE = struct ... konec

V mnoha jazycích by bylo kvůli nedostatku abstrakce nutné vytvořit samostatné programy pro kopírování a vkládání , aby bylo možné je porovnat . Funktory vám na druhé straně umožňují abstrahovat test od implementace a iterovat je v jediném programu:

funktor TestQueue ( Q : QUEUE ) = struct fun fromList I = foldl ( fn ( x , q ) => Q . enq ( q , x )) Q . prázdný I zábava toList q = if Q . null q pak [] jinak Q . hd q :: toList ( Q . deq q ) konec val ns = až ( 1 , 10000 ) (* val ns = [1, 2, 3, 4, ...] : seznam int *) struktura TQ1 = TestQueue ( Queue1 ) val q1 = TQ1 . fromList ns val l1 = TQ1 . toList q1 l1 = ns (* true : bool *) ... struktura TQ2 = TestQueue ( Queue2 ) struktura TQ3 = TestQueue ( Queue3 ) ...

Poté si můžete vybrat mezi šířkou – nejprve vyhledávání a hloubkou – prvním vyhledáváním pro každou implementaci, vše v jediném programu:

funktor BreadthFirst ( Q : QUEUE ) = struktura ... konec funktor DepthFirst ( Q : QUEUE ) = struktura ... konec struktura BF_Q1 = BreadthFirst ( Queue1 ) struktura BF_Q2 = BreadthFirst ( Queue2 ) struktura BF_Q3 = BreadthFirst ( Queue3 ) struktura DF_Q1 = DeepFirst ( Queue1 ) struktura DF_Q2 = DeepthFirst ( Queue2 ) struktura DF_Q3 = DeepthFirst ( Queue3 ) ...

V budoucnu není nutné implementace „navíc“ mazat. Plně optimalizující kompilátory jako MLton je navíc odstraní samy – viz odstranění mrtvého kódu .

Touto metodou lze měřit i efektivitu, ale v praxi je mnohem pohodlnější (a spolehlivější) měřit ji pomocí profileru zabudovaného v kompilátoru.

Globální typová bezpečnost závislostí mezi komponentami, kterou poskytuje jazyk modulu, je vidět na příkladu chybného pokusu o použití funktoru:

struktura Wrong = BreadthFirst ( List ); (* > Chyba: nespárovaná specifikace typu: t > Chyba: neodpovídající specifikace výjimky: E > Chyba: neodpovídající hodnota: prázdná > Chyba: neodpovídající specifikace hodnoty: enq > Chyba: neodpovídající specifikace hodnoty: deq *)

Monády a typové třídy

Haskell , který je potomkem ML , nepodporuje jazyk modulu ML . Místo toho poskytuje podporu pro rozsáhlé programování (kromě triviálního systému modulů podobných těm, které se používají ve většině jazyků) prostřednictvím monád a typových tříd . První vyjadřují abstraktní chování, včetně modelování proměnlivého stavu z hlediska referenční průhlednosti ; poslední slouží jako prostředek pro řízení kvantifikace typových proměnných implementací ad-hoc polymorfismu . Jazyk modulu ML umožňuje implementovat oba idiomy [53] [11] .

Typová třída není nic jiného než rozhraní, které popisuje sadu operací, jejichž typ je dán nezávislou proměnnou abstraktního typu zvanou parametr třídy. Přirozenou reprezentací třídy z hlediska jazyka modulu tedy bude podpis, který kromě požadované sady operací zahrnuje také typovou specifikaci (představující parametr třídy) [11] :

podpis EQ = sig typ t val eq : t * t -> bool end

Monáda je realizována podpisem:

podpis MONAD = sig typ 'a monad val ret : 'a -> 'a monad val bnd : 'a monad -> ( 'a -> 'b monad ) -> 'b monad end

Příklady jeho použití:

struktura Možnost : MONAD = struct type 'a monad = ' opce fun ret x = SOME x fun bnd ( SOME x ) k = k x | bnd NONE k = NONE end podpis REF = sig typ 'a ref val ref : 'a -> 'a ref IO . monad val ! : 'a ref -> 'a IO . monad val : = : 'a ref -> 'a -> jednotka IO . konec monády

Plnohodnotné monadické kombinátory je obzvláště vhodné implementovat pomocí funktorů vyššího řádu [32] [53] :

(*První objednávka*) podpis MONOID = typ sig t val e : t val plus : t * t -> t konec funktor Prod ( M : MONOID ) ( N : MONOID ) = typ struktury t = M . t * N . t val e = ( M . e , N . e ) zábava plus ( ( x1 , y1 ), ( x2 , y2 )) = ( M . plus ( x1 , x2 ), N . plus ( y1 , y2 )) konec funktor Square ( M : MONOID ) : MONOID = Prod M M struktura Rovina = Čtverec ( typ t = skutečná hodnota e = 0,0 val plus = Skutečná . + ) val x = Rovina . plus ( Letadlo . e , ( 7.4 , 5.4 )) (*vyšší řád*) podpis PROD = MONOID -> MONOID -> MONOID funktor Square ( M : MONOID ) ( Prod : PROD ) : MONOID = Prod M M struktura T = čtvercová rovina Prod val x = T . plus ( T.e , T.e ) _ _ _ _ (*Transparentně*) podpis PROD' = fct M : MONOID -> fct N : MONOID -> MONOID kde typ t = M . t * N . t funktor Square' ( M : MONOID ) ( Prod : PROD' ) : MONOID = Prod M M struktura T' = Čtverec' Rovina Prod val x = T' . plus ( T' . e , (( 7,4 , 5,4 ), ( 3,0 , 1,7 )))

Hodnoty indexované podle typů

Hodnoty indexované podle typů je idiom společný všem raným jazykům rodiny ML , navržený k implementaci ad-hoc polymorfismu ( přetížení funkcí ) prostřednictvím parametrického polymorfismu [54] . Typové třídy , poprvé představené v Haskellu , jsou podporou pro typově indexované hodnoty na jazykové úrovni (a jako takové se snadno implementují v module language ).

Ve své nejjednodušší podobě je tento idiom demonstrován v následujícím příkladu OCaml [55] :

typ modulu Arith = typ sig t val (+) : t -> t -> t val neg : t -> t val nula : t konec modul Build_type ( M : Arith ) = struct let typ x = { Type . plus = M. _ (+); neg = M. _ (-); nula = M. _ nula ; } konec let int = let modul Z = Build_type ( Int ) v Z . typ let int64 = nechat modul Z = Build_type ( Int64 ) v Z . typ let int32 = nechat modul Z = Build_type ( Int32 ) v Z . typ let native = let modul Z = Build_type ( Native_int ) v Z . typ let float = let modulu Z = Build_type ( Float ) v Z. _ typ let complex = let modul Z = Build_type ( Complex ) v Z. _ typ

Objektový model

Pomocí jazyka modulu můžete vytvořit jednoduchý objektový model s dynamickým odesíláním. Tento příklad je zajímavý vzhledem k tomu, že SML neposkytuje žádné objektově orientované programovací prostředky a nepodporuje podtypy .

Nejjednodušší dynamicky odbavitelný objektový model lze snadno sestavit v SML prostřednictvím . Typ záznamu, který obsahuje hodnoty funkcí , hraje roli abstraktní třídy , která definuje podpis metody. Skrytí vnitřních stavových a soukromých metod těchto objektů zajišťuje lexikální rozsah ML ; tedy uzávěry (ML funkce) mohou hrát roli konstruktorů objektů této třídy. Taková implementace neumožňuje budovat složité víceúrovňové hierarchie dědičnosti (to vyžaduje implementaci podtypů, která se provádí komplexní implementací hodnot indexovaných podle typů a pro kterou existuje několik různých metod), ale v praxi je zcela dostačující pro většinu úloh s dobrým designem [12] . Odvození takového objektového modelu na úroveň modulu je zvažováno níže.

Jako základ se používají nejjednodušší datové toky:

podpis ABSTRACT_STREAM = typ sig 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) možnost konec podpis STREAM = sig include ABSTRACT_STREAM val empty : 'a t end struktura Zásobník :> STREAM = struct type 'a t = 'a seznam val empty = [] val isEmpty = null val push = op :: val pop = List . getItem end struktura Fronta :> STREAM = struct datatype 'a t = T of 'a list * 'a seznam val empty = T ([], []) val isEmpty = fn T ([], _) => true | _ => false val normalize = fn ([], ys ) => ( rev ys , []) | q => q fun push ( y , T ( xs , ys )) = T ( normalizovat ( xs , y::ys )) val pop = fn ( T ( x::xs , ys )) => NĚKTERÉ ( x , T ( normalizovat ( xs , ys ))) | _ => ŽÁDNÝ konec

Pomocí funktorů můžete implementovat zobecněné algoritmy , které manipulují s datovými toky neznámého interního zařízení a účelu:

funktor StreamAlgs ( ST : ABSTRACT_STREAM ) = struktura otevřená ST fun pushAll ( xs , d ) = foldl push d xs fun popAll d = let fun lp ( xs , NONE ) = rev xs | lp ( xs , SOME ( x , d )) = lp ( x:: xs , pop d ) na konci lp ([], pop d ) fun cp ( from , to ) = pushAll ( popAll from , to ) end

Instancí tohoto funktoru se strukturami srovnatelnými s podpisem ABSTRACT_STREAMvytváří funkce, které manipulují s odpovídajícími datovými toky:

struktura S = StreamAlgs ( Stack ) struktura Q = StreamAlgs ( Queue ) S. _ popAll ( S . pushAll ([ 1 , 2 , 3 , 4 ], Stack . empty )) (* výsledek: [4,3,2,1] *) Q. _ popAll ( Q . pushAll ([ 1 , 2 , 3 , 4 ], Queue . empty )) (* výsledek: [1,2,3,4] *)

Je třeba poznamenat, že funktor StreamAlgspřebírá parametr signatury ABSTRACT_STREAMa struktury Stacka Queuebyly podepsány signaturou STREAMobohacující signaturu . Z toho vyplývá jedna jemnost: při vývoji je žádoucí řídit se konvencemi přijatými ve standardní knihovně konkrétního dialektu, aby bylo možné širší využití existujících vývojů, zejména standardních funktorů (v SML Basis' jich není tolik 2004, ale v rozšířeních některých kompilátorů a v OCaml jsou velmi zajímavé příklady). ABSTRACT_STREAM

Odvozené struktury obsahují definici typu ST.tz parametru functor, ale jde o různé typy: každá definice typu v ML generuje nový typ. Proto pokus o jejich smíchání vede k chybě konzistence typu . Například následující řádek bude kompilátorem odmítnut:

val q = Q . push ( 1 , zásobník . prázdný )

Rozhraní třídy vláken je pohodlně definováno jako . Z důvodů bezpečnosti typu je vhodnější použít nikoli alias typu, ale funkci konstruktoru , která mapuje takový záznam na objekt třídy:

struktura Stream = struct datový typ 'a t = I of { isEmpty : unit -> bool , push : 'a -> 'a t , pop : unit -> ( 'a * 'a t ) option } fun O m ( I t ) = m t fun isEmpty t = O #isEmpty t () fun push ( v , t ) = O #push t v fun pop t = O #pop t () end

Modul Streamve skutečnosti implementuje podpis ABSTRACT_STREAM( ), ale explicitní podepisování je odloženo na později.

Chcete-li změnit modul vlákna na třídu vláken, musíte k němu přidat dva pojmenované konstruktory , což lze provést pomocí funktoru a otevírací konstrukce :

funktor StreamClass ( D : STREAM ) : STREAM = struct open Stream fun make d = I { isEmpty = fn () => D . isEmpty d , push = fn x => make ( D . push ( x , d )), pop = fn () => case D . pop d of NONE => NONE | SOME ( x , d ) => SOME ( x , make d ) } val empty = I { isEmpty = fn () => true , push = fn x => make ( D . push ( x , D . empty )), pop = fn () => NONE } end

Struktura generovaná funktorem StreamClassobsahuje všechny součásti struktury Stream(včetně konstruktoru I ), ale nejsou zvenčí viditelné, protože výsledek funktoru je podepsán signaturou STREAM.

Nakonec můžete modul utěsnit Stream:

struktura Stream : ABSTRACT_STREAM = Stream

To není nutné z hlediska typové bezpečnosti , protože modul Streamneumožňuje porušení zapouzdření, jak tomu bylo dříve. Skrytí konstruktoru I však poskytuje záruku, že StreamClassk vytvoření podtříd lze použít pouze funktor ABSTRACT_STREAM.

Zřejmé případy použití:

struktura StackClass = StreamClass ( Stack ) struktura QueueClass = StreamClass ( Queue )

Ale to není všechno. Vzhledem k tomu, že výše definovaný funktor StreamAlgsbere jako vstup strukturu typu ABSTRACT_STREAM, může být konkretizován strukturou Stream, která implementuje abstraktní třídu proudu:

struktura D = StreamAlgs ( Stream )

Odvozený modul D, stejně jako modul Stream, funguje s jakoukoli třídou, která dědí z ABSTRACT_STREAM, což lze považovat za dynamické odeslání:

D. _ popAll ( D . pushAll ([ 1 , 2 , 3 , 4 ], StackClass . prázdný )) (* výsledek: [4,3,2,1] *) D. _ popAll ( D . pushAll ([ 1 , 2 , 3 , 4 ], QueueClass . prázdný )) (* výsledek: [1,2,3,4] *)

Je zajímavé poznamenat, že ani Stream, ani Dneobsahují nejen proměnlivý stav , ale ani žádné konstanty - pouze typy a funkce - nicméně, protože je předávána mechanismem parametrů, abstraktní třída je zde ve skutečnosti použita jako hodnota první třídy , a nikoli jen virtuální entita, jako v mnoha objektově orientovaných jazycích.

O jazyce

Nízkoúrovňová reprezentace a efektivita

Tradičně jsou struktury v kompilátoru reprezentovány pomocí záznamů a funktory jsou reprezentovány funkcemi nad těmito záznamy [35] . Existují však alternativní interní reprezentace, jako je sémantika Harper-Stone a 1ML .

Použití funktorů jako prostředku k dekompozici velkého projektu znamená zpomalení přístupu k finálním komponentám programů počítaných jejich prostřednictvím a pro každou úroveň vnoření se ztráty násobí, stejně jako při použití běžných funkcí místo okamžitých hodnot. Plně optimalizující kompilátory ( MLton , MLKit [56] , SML.NET [50] ) rozšiřují rámec modulů a vytvářejí konečné definice funktorových komponent s přihlédnutím k vlastnostem skutečně předávaných struktur, což eliminuje penalizaci výkonu. MLKit také používá rozšíření modulů k odvození regionů, což umožňuje použití jazyka k vývoji aplikací v reálném čase . V tomto případě může být odhalení rámce modulů provedeno různými strategiemi: například MLton provádí „ defunktorizaci programu “ a MLKit „ statickou interpretaci jazyka modulu “. Existuje implementace volitelného defunktorizéru pro OCaml [57] .

Odůvodnění sémantiky

Po mnoho let byl jazyk modulu ML považován na typově teoretické úrovni za aplikaci teorie závislých typů , což umožnilo jazyk dokončit a pečlivě prozkoumat jeho vlastnosti. Ve skutečnosti moduly (ani v prvotřídní roli) nejsou „ skutečně závislé “: podpis modulu může záviset na typech obsažených v jiném modulu, ale ne na hodnotách v něm obsažených [3 ] .

Podrobnosti Mitchell-Plotkinova korespondence Silné McQueenovy sumy

[58]

Průhledné sumy Harper-Lilybridge

Robert Harper a Mark Lillibridge zkonstruovali [9] [59] kalkul průsvitných součtů , aby formálně ospravedlnili jazyk modulů vyšší třídy .  Tento kalkul se používá v sémantice Harper-Stone . Jeho prvky se navíc staly součástí revidované definice SML (SML'97).

Sémantika Harper-Stone

Harper-Stone sémantika ( zkráceně HS sémantika ) je interpretací SML v typovaném rámci .  Ten zahrnuje moduli systém založený na průsvitných sumách Harper-Lilybridge (viz výše). Interpretace je teoreticky elegantní, ale udržuje falešný dojem, že moduly ML je obtížné implementovat: používá typy singleton , závislé typy a komplexní systém efektů [3] .

Rossberg-Rousseau-Dreyer F-transformace

Andreas Rossberg, Claudio Russo a Derek Dreyer společně ukázali, že všeobecná představa o nepřiměřeně vysokém vstupním prahu pro jazyk modulů je falešná. Zkonstruovali transformaci jazyka modulů na plochý Systém F ω ( lambda kalkul druhého řádu), čímž ukázali, že samotný jazyk modulů je ve skutečnosti pouze speciálním případem ( syntaktický cukr ) použití Systému F ω . V tomto smyslu je hlavní výhodou používání modulů oproti práci přímo v Systému F ω značná míra automatizace mnoha komplexních akcí (párování podpisů zohledňující obohacení, implicitní sbalování/rozbalování existencí atd.).

" F-ing sémantika " ( F-ing sémantika ), neboli F-transformace, podporuje včetně funktorů vyšších řádů a prvotřídních modulů ve formě Rousseauových balíčků. Důkaz spolehlivosti F-transformace byl mechanizován metodou „lokálně bezejmenné“ ( Locally Nameless ) v Coq . Autoři shrnuli vykonanou práci jako extrémně bolestivou a nedoporučují tuto metodu v budoucnu používat [3] . Dosažené výsledky dále inspirovaly Rossberga k vytvoření 1ML .

Kritika a srovnání s alternativami

Modulový jazyk ML je nejrozvinutějším systémem modulů v programovacích jazycích [2] a neustále se vyvíjí. Poskytuje kontrolu nad hierarchiemi jmenného prostoru (prostřednictvím ) , jemnozrnnými rozhraními (prostřednictvím signatur ), abstrakcí na straně klienta (prostřednictvím funktorů ) a na straně implementátoru (prostřednictvím psaním ) [ 3] .

Většina jazyků nemá nic srovnatelného s funktory [52] . Nejbližší analogií funktorů jsou pozdější šablony tříd C++ , ale funktory se používají mnohem snadněji [60] , protože nejenže šablony C++ nejsou typově bezpečné , ale trpí také řadou dalších nevýhod [61] . Některé jazyky poskytují makro subsystémy , které umožňují automatické generování kódu a flexibilní správu závislostí v době kompilace ( Lisp , C ), ale často jsou tyto makro subsystémy neověřitelným doplňkem hlavního jazyka, který umožňuje libovolné přepisování programového řádku- by-line, což může vést ke spoustě problémů [62] . Teprve v 21. století byly vyvinuty makrosubsystémy, které jsou typově bezpečné ( Template Haskell , Nemerle ), z nichž některé jsou dostupné současně s funktory (MetaML [63] , MetaOCaml ).

Na funktorech je skvělé, že je lze zkompilovat a typově zkontrolovat , i když v programu není žádná struktura, kterou by jim bylo možné předat jako skutečný parametr [64] . Funktory přitom popisují interakci na úrovni rozhraní spíše než implementací , což umožňuje prolomit závislosti v době kompilace. To obvykle přichází na úkor určité degradace výkonu, ale plně programové optimalizační metody tento problém úspěšně řeší .

Jazyk modulů je často vnímán jako obtížně srozumitelný, důvodem je složitá matematika potřebná k jeho ospravedlnění. Simon Peyton-Jones přirovnal funktory k vozu Porsche pro jejich „ vysoký výkon, ale nízkou hodnotu za peníze “ [65] . Zastánci ML s tímto názorem nesouhlasí a tvrdí, že modulový jazyk není o nic těžší použít/implementovat/pochopit než Haskellovy typové třídy nebo Javaův třídní systém s generiky a zástupnými znaky [ , a je skutečně věcí subjektivní preference. [3] .

Pokud překladač detekuje chyby v definicích modulů, mohou být výstupní chybové zprávy velmi dlouhé, což v případě funktorů, zejména vyšších řádů, může způsobit zvláštní nepříjemnosti. Proto by blok definic typů a funkcí nad nimi měl být formátován jako modul až poté, co byl vyvinut po částech (pro které je ve většině implementací poskytován režim REPL ). Některé implementace (např . Poly/ML [51] ) poskytují svá vlastní rozšíření pro řešení tohoto problému. Jiné (například SML2c) naopak umožňují kompilovat pouze programy na úrovni modulů.

Historie, filozofie, terminologie

Myšlenka jazyka modulu spočívá v tom, že velká sémantika programů by měla opakovat sémantiku jádra ML ( anglicky  Core ML ), to znamená, že závislosti mezi velkými komponentami programu jsou formulovány jako závislosti malého úroveň. V souladu s tím jsou struktury „hodnotami“ úrovně modulu ( anglické hodnoty na úrovni  modulu ); signatury (také nazývané " typy modulů " nebo " typy modulů ") charakterizují "typy" hodnot na úrovni modulu , zatímco funktory charakterizují "funkce" úrovně modulu. Analogie však není totožná: jak obsah modulů, tak vztahy mezi moduly mohou být složitější než v jádru jazyka. Nejvýznamnějšími komplikacemi v tomto smyslu je zahrnutí podstruktur do signatur a omezení společného užívání [4] . V komentáři [31] k definici SML'90 byla zaznamenána potenciální implementace funktorů vyššího řádu (analogie s funkcemi vyššího řádu ), ale jejich implementace se objevily později .

Jazyk modulu původně navrhl David MacQueen [66 ] .  Mnoho vědců v budoucnu nejvýrazněji přispělo k typově teoretickému zdůvodnění a rozšíření jazyka modulů. Práce zahrnuje formalizaci rekurzivních , vnořených, lokálních, vyšších a prvotřídních modulů a také opakovanou revizi jejich zdůvodnění s cílem zjednodušit jak samotný model, tak jeho podpůrnou metateorii a prokázat jeho spolehlivost. Vývoj jazyka modulu se úzce prolíná s vývojem jádra ML a je poznamenán desítkami prací mnoha vědců, lze však rozlišit následující klíčové milníky:

  • 1984 - McQueen - prvotní nápad [66] .
  • 1990 - Milner, Harper, McQueen, Tofty - model oddělený od jádra jazyka jako součást definice, důkaz jeho spolehlivosti prostřednictvím tzv. generativního typu těsnění [20] .
  • 1994 - Appel, McQueen - samostatná kompilace [6] .
  • 1995 - Leroy - zjednodušení metateorie na transparentní typy (negenerující), aplikační funktory [67] .
  • 1994 - Harper, Lilybridge - Typ - teoretický základ se závislými typy [9] .
  • 1999-2000 - Rousseau - zjednodušení metateorie na druhý řád, prvotřídní moduly ve formě balíčků [39] [40] .
  • 2000 - Harper-Stone sémantika .
  • 2010 - Rossberg, Rousseau, Dreyer - zjednodušení metateorie na plochý systém F , mechanizace důkazu jeho spolehlivosti v Coq [3] .
  • 2015 - Rossberg - 1ML , jednotný model s jádrem jazyka [34] .

Další dialekt ML - jazyk Caml - původně podporoval modulový jazyk s řadou rozdílů . Následně se vyvinul do jazyka Objective Caml , který modulový jazyk doplnil o objektově orientovaný programovací subsystém , který organicky rozvíjel myšlenky modulového jazyka . OCaml se neustále vyvíjel a do poloviny roku 2010 byl jeho modulový jazyk doplněn o řadu experimentálních funkcí. Jednotlivé implementace SML podporují některé z těchto funkcí jako rozšíření. Nejvýraznější novinkou jsou prvotřídní moduly, které podporuje i jazyk Alice .

Aplikace

V různých jazycích

Sémantika jazyka modulu je zcela nezávislá na skutečnosti, že ML je striktní jazyk – lze jej použít i v líných jazycích [68] . Kromě toho byly navrženy soukromé implementace jazyka modulu nad jádry sémanticky odlišných jazyků (například Prolog a Signal ).

Parametrický růst jazyků

V roce 2000 navrhl Xavier Leroy (vývojář OCaml ) implementaci zobecněného generativního modelu, který umožňuje vybudovat jazyk modulu ML nad jádrem libovolného (v poměrně širokém rozsahu) jazyka s vlastním typovým systémem ( například C ) [1] . Tento model je implementován prostřednictvím jazyka modulu samotného - ve formě funktoru , parametrizovaného údaji o jádru jazyka a popisem mechanismu kontroly jeho typové konzistence .

Moduly jako základ pro jádro jazyka

Po třech desetiletích vývoje jazyka modulů jako doplňku k jádru jazyka navrhl Andreas Rossberg (vývojář Alice ) v roce 2015 namísto tradičního navázání jazyka modulů na jádrový jazyk, použít modulový jazyk jako zprostředkující jazyk pro reprezentaci konstruktů základního jazyka. Díky tomu jsou moduly skutečně prvotřídní hodnoty (nevyžadují balení do balíčků) - viz 1ML .

Poznámky

  1. ↑ 12 Leroy, "Modulární modulový systém", 2000 .
  2. ↑ 1 2 3 Cardelli, "Typeful programming", 1991 , 2. Typeful languages, str. 5.
  3. ↑ 1 2 3 4 5 6 7 8 Rossberg, Russo, Dreyer, "F-ing Modules", 2010 .
  4. ↑ 1 2 Harper, "Programování v SML", 2011 .
  5. ↑ 1 2 3 Dreyer, „Evolving the ML Module System“, 2005 .
  6. ↑ 1 2 Appel, MacQueen, "Separate Compilation for Standard ML", 1994 .
  7. ↑ Harper, „Úvod do SML“, 1986 , str. padesáti.
  8. ↑ Paulson, "ML for the Working Programmer", 1996 , 7.4 Zamýšlený podpis pro fronty, str. 264.
  9. ↑ 1 2 3 4 Harper, Lillibridge, "Typově teoretický přístup k modulům vyššího řádu se sdílením", 1994 .
  10. ↑ 1 2 Dreyer, Rossberg, "MixML", 2008 .
  11. ↑ 1 2 3 Dreyer, Harper, "Modular Type Classes", 2007 .
  12. ↑ 1 2 Objektově orientované programování ve standardním ML
  13. ↑ Paulson, "ML for the Working Programmer", 1996 , 2.22 Signatures, s. 62.
  14. ↑ Paulson, "ML for the Working Programmer", 1996 , 2.19 Úvod do modulů, str. 59.
  15. ↑ Paulson, "ML for the Working Programmer", 1996 , 7.5 Signature constraints, str. 264.
  16. ↑ Pucella, "Poznámky k programování SML/NJ", 2001 , str. 58.
  17. ↑ Harper, „Úvod do SML“, 1986 , str. 13.
  18. ↑ 1 2 Paulson, "ML for the Working Programmer", 1996 , 7.14 openDeklarace, s. 299-305.
  19. ↑ Harper, „Úvod do SML“, 1986 , str. 36.
  20. ↑ 1 2 3 4 Definice SML, 1990 .
  21. ↑ Appel, "A Critique of Standard ML", 1992 , otevřeno v podpisech, s. 17.
  22. ↑ 1 2 Paulson, "ML for the Working Programmer", 1996 , Referenční příručka k modulům, str. 309.
  23. ↑ Mix objektů : funktory a runtime vs kompilační čas
  24. ↑ 1 2 Minsky přeložil DMK, 2014 , Kapitola 9. Funktory.
  25. ↑ Harper, „Úvod do SML“, 1986 , str. 75-76.
  26. ↑ Paulson, "ML for the Working Programmer", 1996 , 7.13 Plně funkční programování, str. 294.
  27. ↑ Harper, „Úvod do SML“, 1986 , str. 77.
  28. ↑ 1 2 Harper, "Úvod do SML", 1986 , str. 77-78.
  29. ↑ Minsky přeložil DMK, 2014 .
  30. ↑ Definice SML: Revize, 1997 .
  31. ↑ 1 2 3 4 Komentář k SML, 1991 .
  32. ↑ 1 2 3 4 HOF v SML/NJ .
  33. ↑ Minsky přeložil DMK, 2014 , str. 235.
  34. ↑ 1 2 Rossberg, "1ML - Core and Modules United", 2015 .
  35. ↑ 1 2 Frisch, Garrigue, "Prvotřídní moduly v OCaml", 2010 .
  36. ↑ Rossberg - Functors a runtime vs kompilační čas .
  37. ↑ Neis, Dreyer, Rossberg, "Neparametrická parametričnost", 2009 , str. 1-2.
  38. ↑ Rossberg, "1ML - Core and Modules United", 2015 , str. 2.
  39. ↑ 1 2 Russo, "Nezávislé typy modulů", 1999 .
  40. ↑ 1 2 Russo, "Prvotřídní struktury", 2000 .
  41. ↑ 1 2 Russo, "Prvotřídní struktury", 2000 , str. 17.
  42. ↑ Alice - Balíčky .
  43. ↑ Russo, "Prvotřídní struktury", 2000 , str. čtrnáct.
  44. ↑ 1 2 Rossberg, "1ML - Core and Modules United", 2015 , str. 3.
  45. ↑ Rossberg, "1ML - Core and Modules United", 2015 , str. 13.
  46. ↑ Rossberg, "Dynamické komponenty", 2006 .
  47. ↑ Alice - ExtModules .
  48. ↑ SML vs. OCaml .
  49. ↑ M.L.Basis
  50. ↑ 1 2 Kompilátor SML.NET
  51. ↑ 1 2 3 Stránka kompilátoru Poly/ML
  52. ↑ 1 2 Paulson, "ML for the Working Programmer", 1996 , 7.8 Testování struktur fronty, str. 274.
  53. ↑ 1 2 Harper, "ML samozřejmě má Monady!" .
  54. ↑ Typově indexované hodnoty
  55. ↑ Yaron Minsky – Pracovní programátorská příručka k hodnotám indexovaným podle typu
  56. ↑ MLKit komiler (downlink) . Získáno 21. ledna 2015. Archivováno z originálu 7. ledna 2016. 
  57. ↑ Defunktorizer pro OCaml .
  58. ↑ MacQueen, "Závislé typy expresních modulů", 1986 .
  59. ↑ Reynolds, "Teorie programovacích jazyků", 1998 , 18. Specifikace modulu, s. 398-410.
  60. ↑ Vanden Berghe .
  61. ↑ K. Czarnecki, J. O'Donnell, J. Striegnitz, W. Taha. Implementace DSL v metaocaml, šabloně haskell a C++ . — University of Waterloo, University of Glasgow, Research Center Julich, Rice University, 2004. Archivováno z originálu 5. března 2016.
  62. ↑ Appel, "A Critique of Standard ML", 1992 , Nedostatek maker, s. 9.
  63. ↑ Steven E. Ganz, Amr Sabry, Walid Taha . Makra jako vícestupňové výpočty: Typově bezpečná, generativní, vazebná makra v MacroML . - International Conference on Functional Programming, ACM Press, 2001. Archivováno z originálu 23. září 2015.
  64. ↑ Tofte, "Základy modulů SML", 1996 .
  65. ↑ Simon Peyton Jones . Nošení košile s vlasy: retrospektiva na Haskell. — POPL, 2003.
  66. ↑ 1 2 MacQueen, "Modules for Standard ML", 1984 .
  67. ↑ Xavier Leroy, "Aplikační funktory", 1995 .
  68. ↑ Tofte, "Základy modulů SML", 1996 , s. jeden.

Literatura

Tutoriály, průvodce, referenční knihy, použití

Standardní jazyk ML
  • Robert Harper . Úvod do standardního ML (neurčité). - Carnegie Mellon University, 1986. - ISBN PA 15213-3891.
    • Překlad do ruštiny:
      Robert Harper. Úvod do standardního ML  (neopr.) . - Carnegie Mellon University, 1986. - 97 s. — ISBN PA 15213-3891.
  • Lawrence C. Paulson. ML pro pracujícího programátora  (neopr.) . — 2. - Cambridge, Velká Británie: Cambridge University Press, 1996. - 492 s. - ISBN 0-521-57050-6 (vázáno), 0-521-56543-X (vázáno).
Jazyk OCaml
  • Minsky, Madhavapeddy, Hickey. Skutečný svět OCaml: Funkční programování pro masy  (neurčeno) . - O'Reilly Media, 2013. - 510 s. — ISBN 9781449324766 .
    • Překlad do ruštiny:
      Minsky, Madhavapeddy, Hickey. Programování v jazyce OCaml  (neopr.) . - DMK, 2014. - 536 s. - (Funkcionální programování). - ISBN 978-5-97060-102-0 .
Jazyk modulu
  • Jazyk modulu . (Kapitola online verze Développement d'applications avec Objective Caml od Emmanuela Chaillouxe, Pascala Manouryho a Bruna Pagana)
  • Michael P. Fourman. Moduly SML (  (anglicky) ). — 2010.

Historie, analýza, kritika

  • Robin Milner , Mads Tofte, Robert Harper. Definice standardního ML  (neopr.) . - The MIT Press, 1990. - ISBN 0-262-63181-4 .
  • Luca Cardelli . Typové programování( (anglicky)) // IFIP State-of-the-Art Reports. - New York: Springer-Verlag, 1991. -Sv. Formální popis programovacích konceptů. —S. 431–507.
  • Andrew W. Appel. Kritika standardního ML (  (anglicky) ). — Princetonská univerzita, revidovaná verze CS-TR-364-92, 1992.
  • John C. Reynolds. Teorie programovacích jazyků . - Cambridge University Press, 1998. - ISBN 978-0-521-59414-1 (pevná vazba), 978-0-521-10697-9 (brožovaná).
  • Claudio Russo. Nezávislé typy modulů (  ( anglicky) ) // Principy a praxe deklarativního programování. — Principy a praxe deklarativního programování, 1999.
  • Xavier Leroy. A Modular Module System (  (anglicky) ) // sv. 10, vydání 3. - Journal of Functional Programming, 2000. - S. 269-303 .
  • Andreas Rossberg, Claudio Russo, Derek Dreyer. Moduly F-ing (  (anglicky) ). — TLDI, 2010.

Odkazy