Limbajul modulului ML

Limbajul modulului ML este un sistem de module utilizat în principal în limbaje de programare din familia ML , care are semantică aplicativă , cu alte cuvinte, este un limbaj funcțional mic care funcționează cu module [1] .

Este cel mai dezvoltat sistem de module dintre cele găsite în limbajele de programare [2] [3] .

Informații generale

În forma sa cea mai simplă, un limbaj modul este format din trei tipuri de module:

Semnătura poate fi considerată ca o descriere a structurii, iar structura, respectiv, ca implementare a semnăturii. Multe limbi oferă constructe similare, de obicei sub nume diferite: semnăturile sunt adesea numite interfețe sau specificații de pachet, iar structurile sunt adesea numite implementări sau pachete. Indiferent de terminologie, ideea este de a atribui un tip unei întregi bucăți de cod. Spre deosebire de multe limbi, în ML, relația dintre semnături și structuri este mai degrabă mai multe - la - mulți decât multi-la-unu sau unu - la-unu . O semnătură poate descrie multe structuri diferite, iar o structură poate corespunde multor semnături diferite. Majoritatea celorlalte limbi sunt supuse unor restricții mai puternice, care impun ca o anumită structură să aibă o singură semnătură sau ca o anumită semnătură să fie derivată dintr-o singură structură. Acesta nu este cazul pentru ML [4] .

În limbajele principale orientate pe obiecte , cum ar fi C++ sau Java , abstracția este furnizată prin clase care combină o serie de caracteristici ( moștenire , subtipări și trimitere dinamică ) într-un singur concept simultan, ceea ce le face dificil de oficializat și poate duce la consecințe nedorite atunci când o utilizare neglijentă. Spre deosebire de clase, limbajul modulului ML se concentrează în întregime pe abstractizare , oferind o gamă largă de forme și oferind o bază formală solidă pentru studiul lor. [5] Oferă managementul ierarhiei spațiilor de nume , personalizarea fină a interfeței , abstracția implementatorului și abstracția la nivelul clientului .

Functorii sunt un concept unic care nu are echivalent în majoritatea limbilor . Sunt funcții peste structuri, adică calculează structuri noi pe baza celor deja calculate, firesc, în conformitate cu anumite semnături. Acest lucru vă permite să rezolvați o mare varietate de probleme de structurare a programelor complexe .

În acest caz, sunt îndeplinite două cerințe [6] :

În practică, posibilitatea de compilare separată nu este întotdeauna utilizată - există compilatoare de optimizare completă care deschid cadrul de module pentru a crește semnificativ performanța programelor .

Limba

Structuri și semnături

Environment ( ing.  mediu ) în ML de bază ( ing.  Core ML ) este o colecție de definiții ( tipuri , inclusiv funcționale , și valori , inclusiv funcționale și exclusive ). Mediul este definit din punct de vedere lexical .

O structură ( structure) este un mediu „materializat”, transformat într-o valoare care poate fi manipulată [7] . În legătură cu implementările timpurii ale limbajului modulului, această definiție este oarecum o convenție, deoarece inițial structurile puteau fi definite sau evaluate doar la nivelul superior al codului (în mediul global). Lucrările ulterioare dezvoltă limbajul modulului la un nivel de primă clasă .

Introducerea conceptului de structură necesită o revizuire a definiției mediului în centrul limbajului. De acum înainte, mediul este o colecție de tipuri, valori și structuri. În consecință, o structură este o colecție de tipuri, valori și alte structuri. Imbricarea recursive a structurilor nu este permisă, deși unele implementări le suportă [5] .

Principalele mijloace de definire a structurilor sunt declarațiile încapsulate , adică declarațiile cuprinse între paranteze sintactice struct...end. De exemplu, următoarea structură implementează o stivă , definind organizarea internă a obiectelor de tip algebric „stivă” și setul minim necesar de funcții peste acesta:

struct type 'a t = 'a list val empty = [] val isEmpty = null val push = op :: val pop = List . getItem sfârşitul

„Valoarea” acestei declarații încapsulate este o structură. Pentru a utiliza această valoare, trebuie să îi atribuiți un identificator:

structure Stack = struct type 'a t = 'a list val empty = [] val isEmpty = null val push = op :: val pop = List . getItem sfârşitul

Componentele structurii pot fi acum accesate prin nume compuse (sau calificate), cum ar fi Stack.push, Stack.empty : Stack.t.

Semnătura ( signature) este o enumerare a descrierilor elementelor structurii, adică interfața structurii. Fiecare element al acestei enumerari se numeste specificatie. Dacă tipul este specificat pentru o valoare din semnătură , atunci în structură identificatorul trebuie să fie legat la o valoare de tip . Vă puteți gândi la o semnătură ca la un fel de „ tip ” al unei structuri, dar o semnătură nu este un tip în sens strict, deoarece un tip este un set de valori , iar o „valoare de semnătură” poate conține tipuri (care în ML nu sunt valori). Fiecare identificator din semnătură trebuie să fie unic. Nu este respectată regula umbririi lexicale a numelor în semnături, deci nu contează ordinea de enumerare a acestora, dar tipurile trebuie declarate înainte de a fi folosite, așa că în mod tradițional sunt plasate la începutul semnăturii. x tx t

Definiția semnăturii este scrisă între paranteze sintactice sig...end. De exemplu, o structură Stackare următoarea semnătură (compilatorul o deduce automat):

structura Stivă : tip sig '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 ) sfârșitul opțiunii

Proprietatea principală a semnăturilor este că structurile pot fi corelate cu ele .  O structură este comparabilă cu o semnătură dată dacă conține cel puțin tipurile, valorile și structurile imbricate enumerate în semnătură [8] . Există două forme de potrivire a structurilor cu semnături: transparent ( engleză  transparent ) și închis ( engleză  opac ). În general, capacitatea de a alege forma de semnare se numește proprietatea de transluciditate a  semnăturilor [ 9] [10] .

„ Semnătura implicită” dedusă de compilator este de obicei redundantă, deoarece expune publicului informațiile de implementare a componentelor sale, ceea ce reprezintă o încălcare a principiului abstracției . Prin urmare, în cele mai multe cazuri, programatorul descrie în mod explicit semnătura dorită și efectuează semnarea cu o semnătură ( English  signature description ) sau sigilare ( English  sealing ) [5] [3] [11] [12] , asigurându-se astfel că componentele structura aleasă de el sunt ascunse de restul programului [13] . Mai precis, se realizează legarea a structurii potrivite.

De exemplu, un dezvoltator poate defini o semnătură care descrie diverse fluxuri de date ( structuri de date cu acces secvenţial) şi îi poate atribui un identificator:

semnătură STREAM = tip sig 'a t val empty : 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * ' a t ) sfârșitul opțiunii

Semnătura proprie a unei structuri poate îmbogăți ( eng.  enrich ) semnătura cu care se face comparația, adică să conțină mai multe componente, mai multe tipuri, iar aceste tipuri pot fi mai generale. Relația de îmbogățire este scrisă formal ca (semnătura îmbogățește semnătura ).

În acest caz, puteți scrie :

Potrivirea transparentă are în mod tradițional S : SSsintaxa " ", în timp ce potrivirea întunecată are sintaxa " " S :> SS. Cu toate acestea, creatorii OCaml au renunțat complet la suportul pentru potrivirea transparentă, ceea ce înseamnă că toate mapările din OCaml sunt întunecate, dar sintaxa „ ” este folosită pentru simplitate. S : SS

În cele mai simple cazuri, puteți semna imediat o semnătură fără a-i atribui un identificator separat:

structura Stivă :> tip sig 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) opţiunea final = struct type 'a t = 'a list val empty = [] val isEmpty = null val push = op :: val pop = List . getItem sfârşitul

Cu toate acestea, în practică, semnăturile fără nume sunt destul de rare, deoarece utilizarea semnăturilor nu se limitează la ascunderea .

O structură în contexte diferite poate fi mapată la semnături diferite, iar o semnătură poate servi ca interfață pentru diferite structuri. Semnătura definește o clasă de structuri (în sensul matematic al termenului „ clasă ”) [14] . O „vedere exterioară” diferită pentru o structură, cu grade diferite de abstractizare , poate fi furnizată de mai multe semnături cu un set diferit de specificații [15] . Ordinea declarațiilor nu contează și nu afectează comparabilitatea structurilor cu semnături.

Acesta poate fi văzut ca cel mai simplu analog al claselor abstracte (în termeni de programare orientată pe obiecte ), în sensul că o semnătură descrie o interfață comună , iar structurile comparabile cu aceasta implementează acea interfață în moduri diferite. Cu toate acestea, în ML, relația părinte-copil nu este declarată în mod explicit, deoarece sistemul de tip ML are structurală , adică potrivirea unei structuri cu o semnătură se realizează prin același mecanism ca și potrivirea unei valori cu un tip . 5int

De exemplu, se poate defini o structură care implementează o coadă , dar care este și comparabilă cu o semnătură STREAM:

structure Queue = struct datatype 'a t = T of 'a list * 'a list val empty = T ([], []) val isEmpty = fn T ([], _) => true | _ => false val normalize = fn ([], ys ) => ( rev ys , []) | q => q fun push ( y , T ( xs , ys )) = T ( normalize ( xs , y::ys )) val pop = fn ( T ( x::xs , ys )) => SOME ( x , T ( normaliza ( xs , ys ))) | _ => NIMIC sfârșit

Deoarece structura Stacknu a fost semnată în mod explicit cu o semnătură mai slabă, programul extern „știe” că tipul teste identic cu tipul listși poate folosi aceste cunoștințe pentru a procesa obiecte de acest tip folosind metode standard ale modulelor List. Dacă implementarea structurii trebuie schimbată ulterior (de exemplu, prin reprezentarea stivei cu o matriceStack prealocată ), atunci aceasta va necesita rescrierea întregului cod care a folosit aceste cunoștințe. Același lucru este valabil și pentru structură . Mai mult, dacă un modul a fost parametrizat cu propria semnătură struct , atunci nu va fi posibil să-i treacă un struct ca parametru . QueueStackQueue

Astfel, exportul de informații inutile din structuri înrăutățește semnificativ modificabilitatea programelor. Pentru a crește nivelul de abstractizare , structurile ar trebui să fie semnate cu semnături mai slabe, de exemplu:

structure Stack :> STREAM = struct type 'a t = 'a list val empty = [] val isEmpty = null val push = op :: val pop = List . getItem sfârşitul

Structura este Stackmapată la semnătură STREAMîntr-un mod întunecat, astfel încât un program extern va putea opera pe deplin pe valorile tipului Stack.t, dar nu va avea acces la implementarea sa și la toate valorile posibile ale acestuia. tip, va putea folosi doar valoarea Stack.empty(din nou, „fără a ști » ​​că este egală cu nil). Orice prelucrare a datelor de acest tip se va efectua în mod abstract , fără a se lua în considerare implementarea acesteia, și se poate face numai prin intermediul funcțiilor Stack.pushși Stack.pop.

Dar nicăieri semnăturile nu sunt mai importante și mai utile decât atunci când folosiți functorii [16] .

Moștenire

Structurile pot fi imbricate unele în altele:

structura E = structura structura A structura B ... sfârşitul

Desigur, semnăturile vă permit să descrieți structuri imbricate. În acest caz, ca și în alte cazuri, imbricarea structurilor este controlată pe baza semnăturilor, și nu pe coincidențe identice:

semnătură D = sig structura A : C structura B : C capăt

Semnăturile pot fi incluse (sintaxă include S) unele în altele, îmbogățind secvențial interfața:

semnătură POOR = tip sig 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) opţiunea sfârşit semnătură BOGAT = sig include POOR val empty : 'a t end

Se poate observa că, conform semanticii descrise, semnarea semnăturii nu trebuie să se facă imediat. Dacă trebuie să dezvoltați un anumit set de module strâns interconectate, care sunt mai „prietenos” între ele decât cu restul programului, atunci după finalizarea dezvoltării acestuia, puteți semna structurile cu semnături mai slabe:

structura SomeModule :> RICH = struct ... final ... structura SomeModule :> POOR = SomeModule

Ultima linie nu trebuie considerată o misiune distructivă . Acest idiom se bazează pe vizibilitatea lexicală , care este o parte integrantă a semanticii oricărui limbaj aplicativ . Atât la baza ML , cât și la nivel de modul, construcția x = aînseamnă întotdeauna legarea unei valori la un identificator. Legarea nu este o atribuire , ea „creează” un nou identificator care nu are nimic de-a face cu (eventual) definit anterior [17] . Structura originală SomeModuleîncă există în program, dar codul ulterior nu are acces la acele componente ale sale care nu fac parte din semnătura mai slabă (în acest caz, este o constantă empty).

Structura poate fi deschisă (sintaxă open S). În cel mai simplu caz, acesta poate fi considerat zahăr sintactic , servind pentru comoditatea utilizării definițiilor încapsulate în modul (analog cu constructul withîn limbajul Pascal ):

fun foo x = lasa deschiderea SMLofNJ .Cont in fun f x = callcc ( fn k => ... arunca k ...) fun g x = izolare ... final

Dacă același lucru se face la nivelul superior al programului (în mediul global), acesta poate fi considerat ca un analog al constructului using namespaceîn limbajul C++ . De exemplu, structurile care implementează tipuri standard și operațiuni pe ele ( Int, Realși Stringaltele) sunt deschise în mod implicit (pentru mai multe despre acest lucru, consultați controlul numerelor ). Cu toate acestea, posibilitatea deschiderii structurilor există și în interiorul altor structuri și, în acest caz, deschiderea servește ca instrument de includere a structurilor una în cealaltă pentru a extinde în mod constant funcționalitatea (analog cu cea mai simplă moștenire de clasă ). De exemplu:

structura B = structura deschisă A ... capăt

Structura Binclude toate definițiile structurii Ași le completează cu noi definiții. Aceasta este aceeași cu listarea explicită a tuturor definițiilor Adin B. Această posibilitate are două dezavantaje [18] :

  • dacă în structura deschisă există identificatori care se potrivesc cu identificatorii deja existenți în contextul dat, atunci aceștia din urmă vor deveni inaccesibili pentru acces direct. În schimb, definițiile după deschidere vor umbri componentele importate. Nu există niciun conflict de nume - doar ultima definiție este vizibilă - dar acest lucru poate fi incomod pentru dezvoltator. Excepția este dacă numele tipurilor se potrivesc cu numele valorilor existente, deoarece compilatorul ML poate determina întotdeauna semnificația unui identificator din contextul utilizării acestuia [19] (vezi inferența tipului ). Problema umbririi numelor este deosebit de relevantă atunci când includ două sau mai multe structuri.
  • uneori devine dificil să se determine ce anume este inclus din structura deschisă, mai ales când se deschid structuri mari care definesc un număr mare de identificatori.

Prin urmare, se recomandă adesea să folosiți introducerea unui identificator local scurt [18] în loc să deschideți , de exemplu:

structura SomeModule :> sig fun f x : ... fun g x : ... ... end = struct local structure C = SMLofNJ . Cont în ... distracție f x = C . callcc ( fn k => ... C . arunca k ...) fun g x = C . izola ... _ _

Cu toate acestea, uneori, precedența ultimei definiții poate fi folosită pentru a „redefini” în mod deliberat un identificator (care nu este, totuși, o supraîncărcare ).

Context istoric

Anterior, în Definiția SML'90 [20] , se putea deschide în semnături. Această caracteristică a fost criticată din cauza deteriorării auto-documentării (învățarea interfeței unui modul în timp ce îl utilizați vă obligă să vă referiți la altul) [21] și a fost desființată în SML'97 Language Revision. Este important de reținut aici că deschiderea ( open) este fundamental diferită de includerea ( include), deoarece fiecare identificator trebuie să fie unic în interiorul semnăturii și nu este respectată regula de umbrire a numelui, astfel încât un identificator din semnătura inclusă să se potrivească cu cel din semnătură. unul nou duce la o eroare de compilare.

În SML'90 [20] exista o subspecie specială de semnătură - abstraction, iar pentru semnăturile obișnuite exista o singură formă de potrivire - transparent ( S : SS). Când limbajul a fost revizuit în 1997, această parte a limbajului modulului a fost simplificată: în loc de semnături abstracte ,  a fost introdusă potrivirea întunecată ( opace ) cu semnătura ( S :> SS) ( soluția se bazează pe calculul translucidului Harper-Lilybridge). sume ).

Functorii

Un functor ( functor) este o funcție peste structuri , adică o funcție care ia o structură ca intrare și construiește o nouă structură [22] . Uneori, un functor este privit vizual ca o „structură parametrizată”, adică o structură a cărei definiție este construită de compilator pe baza unei alte structuri conform regulilor specificate de programator. Cu toate acestea, ortodoxiile susțin că functorii ar trebui considerați ca funcții specifice [23] .

Semnătura joacă rolul tipului de parametru al functorului. Toate tipurile de structuri care pot fi asortate cu această semnătură joacă rolul unor valori aparținând acestui tip și trecute la functor pentru a evalua noi structuri [22] . Structura obținută ca urmare a aplicării functorului are propria semnătură (deși, în general, poate să nu difere de semnătura parametrului).

Forma generală a definiției unui functor arată astfel:

functor F ( X : S1 ) : S2 = corp

Exemple de utilizare:

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

Functorii vă permit să descrieți într-un mod sigur de tip cele mai diverse forme de relații între componentele programului, rezolvând o gamă largă de probleme de structurare a codului [24] :

  • Implementarea algoritmilor generici si managementul dependentelor. Functorii vă permit să combinați componente mari cu comportament similar, dar implementări diferite într-un program și să le înlocuiți după cum este necesar. Acest lucru este util în special în timpul etapei de prototipare rapidă , când trebuie să testați sistemul în părți sau să simulați comportamentul într-un mod simplificat (vezi, de exemplu, controlul numerelor și testarea structurii ).
  • Extindere automată a funcționalității. Functorii vă scutesc de munca de rutină atunci când trebuie să implementați aceeași funcționalitate pentru diferite tipuri. De exemplu, dacă doriți să definiți mulțimi din elemente de diferite tipuri de date, atunci în ML este suficient să definiți un functor care generează o structură care definește o mulțime, pe baza unei structuri care definește tipul unui element. În alte limbi, acest tip de problemă este rezolvată folosind programarea generativă .
  • Instanțierea modulelor cu stare mutabilă încapsulată . Dacă o structură încapsulează o stare mutabilă și programul trebuie să aibă mai multe instanțe ale acesteia cu stări independente, atunci functorii vă permit să automatizați construcția unor astfel de structuri.

Aceste posibilități sunt cel mai bine ilustrate cu exemple ilustrative .

Cu toate acestea, unii programatori folosesc functori în loc de structuri (adică descriu un functor și definesc o structură ca singura sa aplicație la un parametru cunoscut și, uneori, un functor cu un parametru gol). Această abordare pare exagerată la prima vedere, dar în practică oferă două avantaje care măresc productivitatea dezvoltatorilor în proiecte mari [25] [26] :

  • pe de o parte, organizarea corectă a interfețelor este asigurată imediat în etapa de compilare a unui modul abia scris, și nu pe măsură ce proiectul se dezvoltă (deoarece dependențele structurilor unele față de altele în acest caz sunt controlate de mecanismul de potrivire a tipurilor și nu sunt detectate în timpul asamblarii)
  • pe de altă parte, structurile devin „mai independente” unele de altele, astfel încât să poată fi dezvoltate în orice ordine, iar programatorii dintr-o echipă sunt liberi să lucreze în direcții exact opuse ( de sus în jos sau de jos în sus ).

co-use .

Echivalența tipului

Când se programează la scară largă , când modulele sunt legate pentru a crea altele noi, mai complexe, se pune întrebarea despre consistența tipurilor abstracte exportate din aceste module. Pentru a rezolva această problemă, limbajul modulului ML oferă un mecanism special care vă permite să indicați în mod explicit identitatea a două sau mai multe tipuri sau structuri:

semnătură D = sig structura A : C structura B : C partajare tip A .t = B . t sfârşit

O astfel de specificație impune o constrângere asupra setului permis de structuri substituibile, declarând cerința ca acestea să fie structuri care împărtășesc ( eng  . share ) utilizarea aceleiași specificații (tip, semnătură sau structură). Astfel, doar acele structuri sunt comparabile cu semnătura , în care identificatorul înseamnă același tip [27] . Prin urmare, această specificație se numește „ constrângere de partajare ”.  Dt

Notă - în literatura în limba rusă, traducerea acestui termen nu a fost stabilită. Sunt posibile variante precum „ specificația de coutilizare ” [28] , „ constrângerea de partajare ”, precum și traducerea semantică „ cerința de separare ” sau „ cerința de partajare ” . Există [29] traducerea „ restricțiipartajare ” , care este o eroare semantică.

Din punct de vedere semantic, există două forme ale unei astfel de specificații - una pentru semnături și tipuri, una pentru structuri - dar sintaxa lor este identică. A doua formă este mai restrictivă: două structuri pot fi egale dacă și numai dacă rezultă din evaluarea aceleiași declarații de structură sau aplicarea aceluiași functor la argumente egale [28] .

Specificația de coutilizare este, de asemenea, utilizată pentru a forța o restrângere a gamei de tipuri permise într-un anumit context de utilizare a unei semnături care este „supra-abstractă” pentru aceasta, de exemplu:

functor Try ( Gr : tip sig g tip partajare g = int val e : g val bullet : g * g -> g val inv : g -> g end ) = struct val x = Gr . inv ( Gr . glonţ ( 7 , 9 ) ) sfârşit

Aici, semnătura parametrului functor impune o cerință specială asupra compoziției structurii care poate fi efectiv transmisă acesteia: tipul abstract g folosit în el trebuie să fie un tip int. Cazurile în care acest lucru este necesar sunt destul de frecvente, așa că în SML'97 [30] pentru a simplifica descrierea lor și posibilitatea de a folosi semnături numite, a fost adăugată o construcție alternativă pentru specificația de co-utilizare: where type(în OCaml sintaxa ) : with type

semnătură GROUP = tip sig g val e : g val glonț : g * g -> g val inv : g -> g final functor Try ( Gr : GROUP unde tip g = int ) = struct val x = Gr . inv ( Gr . glonţ ( 7 , 9 ) ) sfârşit

Ambele modele au limitele lor.

sharingvă permite să exprimați egalitatea tipurilor fără a specifica în mod specific structura acestora. Construcția poate avea o aritate arbitrară :

semnătură S = structura sig A : S structură B : S structură C : S structură D : S tip partajare A .t = B . t = C. _ t = D . t sfârşit

dar vă permite să vă referiți la tipurile abstracte doar direct - adică. expresia formei

partajarea tip B .t = A . t * A . t

where typeeste unară și are scopul, dimpotrivă, de a instanția un tip abstract printr-un tip cunoscut (dar nu permite modificarea structurii unui tip care a fost deja instanțiat).

Construcția nu este acceptată în OCaml , așa că ar trebui să utilizați întotdeauna . În succesorul ML , se presupune că va implementa un singur construct cel mai universal. sharingwith type

Un alt aspect important al stabilirii echivalenței tipurilor abstracte este capacitatea de generare a functorilor .

ML standard utilizează semantica generativă a functorilor, ceea ce înseamnă că fiecare aplicare a unui functor la aceeași structură generează noi definiții de tip, de exemplu. două tipuri cu același nume și identice ca structură, aparținând unor structuri diferite, nu sunt egale.

OCaml folosește functori aplicativi, ceea ce înseamnă că aplicarea unui functor la argumente probabil egale generează automat același rezultat. Acest lucru reduce necesitatea unei specificații de co-utilizare și este util în special atunci când aveți de-a face cu functori de ordin superior. Începând cu versiunea 4, OCaml adaugă capacitatea de a face functorii parentali.

Extensii și dialecte

Functori de ordin superior

Functorul primește o structură specificată de semnătură ca intrare. Pentru a trece mai multe structuri, este necesar să construiți o structură suplimentară de înveliș care să includă aceste structuri și să descrieți semnătura corespunzătoare. Definiția limbajului Standard ML pentru comoditate prevede zahăr sintactic - mai mulți parametri pot fi trecuți ca un tuplu , iar compilatorul construiește automat structura de anexare și semnătura acesteia. Cu toate acestea, core ML furnizează funcții de ordin superior , iar urmarea analogiei la nivel de modul cu acestea înseamnă introducerea unei forme de functori curry . De fapt, singurul lucru care trebuie implementat în limbaj pentru a oferi această capacitate este suportul pentru descrierea functorilor în semnături [31] [32] . Aceasta nu este o inovație fundamentală (spre deosebire de modulele de primă clasă ) - nu există nimic ce ar permite functorii curried , dar cei clasici de ordinul întâi nu ar - cu toate acestea, disponibilitatea lor simplifică semnificativ implementarea (și, prin urmare, lizibilitatea ) ierarhii de componente pe mai multe niveluri [32] .

Un exemplu izbitor care arată comoditatea utilizării functorilor de ordin superior este implementarea combinatorilor monadici cu drepturi depline .

Potențialul de implementare a functorilor de ordin superior a fost deja notat în Comentariile [31] la Definiția SML'90 [20] . Multe compilatoare Standard ML oferă o implementare a functorilor de ordin superior ca extensie experimentală [32] . Ocaml implementează tot felul de module într-un mod uniform sintactic, deci folosirea functorilor de ordin superior este cea mai naturală.

Notă - în literatura în limba rusă există [33] confuzie între „ module de ordin superior ” și „ module de primă clasă ” , ceea ce este o eroare semantică.

Caracteristici orientate pe obiecte

Suport complet pentru programarea orientată pe obiecte conform lui Abadi și Cardelli (vezi Programare orientată pe obiecte#Clasificarea subtipurilor de POO ) înseamnă suport în același timp:

  • subtipărirea relaţiilor
  • obiecte
  • tipuri de obiecte
  • clase (generatoare de obiecte)

Toate acestea sunt furnizate de Ocaml de mulți ani . Mai mult, polimorfismul parametric se extinde și la aceste caracteristici , ceea ce face limbajul și mai expresiv. Desigur, limbajul modulului din OCaml a fost îmbunătățit pentru a permite ca obiectele și clasele să fie incluse în module.

Aceste facilități (eventual extinse la tipuri de ordin superior - vezi subtipărirea de ordin superior ) vor deveni parte a succesorului ML .

Module de primă clasă

Problemă

Un punct slab al limbajului original al modulului este că nu este închis la limbajul de bază: tipurile și valorile de bază pot fi componente ale modulelor, dar modulele nu pot fi componente ale tipurilor și valorilor de bază. În SML, această separare a limbajului în două straturi a fost făcută intenționat, deoarece a simplificat foarte mult mecanismul de verificare a consistenței tipului [31] . Cu toate acestea, acest lucru face imposibilă legarea dinamică a modulelor, ceea ce înseamnă că următoarea expresie este invalidă:

structura Map = dacă maxElems < 100 , atunci BinTreeMap altfel HashTableMap (* nu este permis în ML clasic! *)

O astfel de interdicție este o rușine pentru un astfel de sistem de module expresiv, deoarece ar fi complet normal pentru orice limbaj orientat pe obiecte [34] .

De fapt, limbajul modulului ML nu trebuie să fie static [35] (vezi secțiunea despre reprezentarea la nivel scăzut ). Problema constă în primul rând cu verificarea statică a tipului care este natura ML . Suportul în ML pentru module de primă clasă în sine nu este o problemă pentru un limbaj de modul de ordinul întâi (care nu conține functori), dar este combinația de module de primă clasă cu module de ordin superior care ia limbajul „la o altă realitate” [36] , adică deschide posibilități uriașe, dar complică semnificativ atât mecanismele de derivare și verificare a consistenței tipurilor de limbaj [37] , cât și optimizarea completă a programului . Ideea modulelor de primă clasă a fost îngropată de mulți ani de către Harper și Lilybridge , prin construirea unei versiuni idealizate a limbajului modulului de primă clasă folosind teoria tipurilor dependente și demonstrând că verificarea consistenței tipului pentru acest model este indecidabil [9] [38] . Cu toate acestea, în timp, au început să apară modele alternative, folosind alte justificări.

Pachete

La sfârșitul secolului al XX-lea, Claudio Russo a propus [39] [40] cel mai simplu mod de a face module de primă clasă : completarea listei de tipuri primitive ale nucleului limbii cu tipul „ pachet ” ( pachetul englezesc  ) , care este o pereche și lista de expresii de nucleu cu operațiuni de împachetare și dezambalare. Cu alte cuvinte, doar nucleul limbajului se schimbă, iar limba modulelor rămâne neschimbată [41] . структура : сигнатура

Împachetarea structurilor în pachete și despachetarea ulterioară vă permite să legați dinamic diferite structuri la identificatori (inclusiv cele calculate folosind functori). Cel mai simplu exemplu [42] :

structura Map = unpack ( dacă maxElems < 100 , atunci pack BinTreeMap : MAP alt pachet HashTableMap : MAP ) : MAP

La despachetarea unui pachet, structura poate fi semnată cu o altă semnătură, inclusiv cu semnătura mai slabă .

Prezența explicită a semnăturii în pachet înlătură problema deducerii tipului și potrivirii în timpul dezambalării dinamice a structurii. Acest lucru respinge teza timpurie Harper-Mitchell despre imposibilitatea ridicării structurilor în ML la niveluri de primă clasă fără a sacrifica separarea fazelor de compilare și de rulare și decizibilitatea sistemului de verificare a consistenței de tip [41] , deoarece în loc de primul- Tipuri dependente de ordine , o extensie a teoriei tipurilor existențiale este folosită ca justificare de ordinul doi Mitchell-Plotkin [43] .

În această formă, modulele de primă clasă sunt implementate în Alice și în Ocaml , începând cu versiunea a 4-a.

1ML

Inspirat de conversia F , Rossberg încorporează modul boxing-unboxing mai profund în semantica limbajului, rezultând un limbaj monolitic în care functorii, funcțiile și chiar constructorii de tip sunt într-adevăr același construct primitiv și nu există nicio distincție. realizat între înregistrări , tupluri și structuri - reprezentarea internă a limbajului este un sistem plat F ω . Acest lucru a dat o mulțime de rezultate pozitive [44] :

  • demonstrarea fiabilității limbajului devine mult mai simplă decât în ​​mod tradițional pentru limbajul modulelor (nu este necesară utilizarea teoriei tipurilor dependente );
  • se acordă suport pentru tipurile „materializate” ( ing.  reificate ) în miezul limbajului, oferind limbajului putere expresivă la nivelul sistemelor cu tipuri dependente (și iarăși necerând prezența lor în metateorie);
  • limbajul în ansamblu se dovedește a fi atât mai expresiv (vă permite să descrieți sisteme complexe cu mai multă capacitate și mai multă acuratețe), cât și mai simplu (mai minimalist și mai uniform în compoziția sa).

Limbajul a fost numit „ 1ML ”, ceea ce reflectă atât suportul unor module cu adevărat de primă clasă, cât și unificarea primitivelor și modulelor într-o singură limbă (nu împărțită în două straturi) [44] .

Decizia sa bazat pe ideea lui Harper-Mitchell de a subdiviza tipurile în „mici” și „mari”. Rossberg a aplicat această distincție regulii de includere a consistenței tipului (potrivirea structura-la-semnătură subiacentă), făcând-o astfel rezolvabilă .

Probabil, dezvoltarea ulterioară a 1ML poate oferi, de asemenea, suficientă expresivitate pentru a susține multe modele interesante, a căror implementare era considerată anterior dificilă: clase de tip , functori aplicativi , module recursive etc. În special, introducerea polimorfismului inline în 1ML va permite probabil imediat exprimarea subtipării în lățime , ceea ce va menține metateoria simplă, în timp ce își va extinde semnificativ capacitățile. [45]

MixML

MixML [10] este un limbaj modul construit prin combinarea limbajului clasic al modulului ML al lui McQueen și formalizarea modelului mix -in - uri de către Bracha & Cook .  Autorii MixML sunt Rossberg și Dreyer.

Ideea de bază a MixML este simplă: structurile și semnăturile sunt combinate într-un singur concept de modul, combinând definiții și specificații, atât transparente, cât și abstracte.

Acest lucru face posibilă definirea graficelor de dependență arbitrare în programe, inclusiv în cele ciclice. În special, acest lucru vă permite să construiți functori nu numai parametrizare directă (dependența ieșirii de intrare), ci și recursivă (dependența intrării de ieșire), menținând în același timp suport pentru compilarea separată (spre deosebire de multe modele private care se extind limbajul modulului ML cu suport pentru recursivitate) .

MixML implementează o singură notație unificată pentru modelele semantice pereche în mod tradițional (pentru structuri și semnături separat) și un număr mare de mecanisme separate ale limbajului clasic al modulelor ML, cum ar fi:

  • moștenirea (includerea) semnăturilor
  • specificații de
  • două forme de semnătură (transparentă și întunecată)
  • aplicații de functor

Diverse

Următoarele extensii sunt disponibile și pe diferite modele:

  • module locale
  • multe opțiuni pentru sistemul recursiv de module care vă permit să formați grafice de dependență ciclică, dintre care cel mai expresiv este sistemul MixML (majoritatea celorlalte nu prevăd posibilitatea de compilare separată)
  • suport extins pentru imbricarea modulelor
  • notatie generalizata pentru structuri de deschidere
  • diverse opțiuni pentru limitarea co-utilizarii
  • semnături imbricate, inclusiv cele abstracte
  • declarații ale operatorilor infixi care specifică asociativitatea și precedența în cadrul semnăturilor și care necesită o potrivire exactă

Ecosistemul lingvistic

Implementări și dialecte

Alice

Limbajul Alice este o extensie a Standard ML , incluzând multe dintre ideile succesorului proiectului ML , precum și instrumente avansate de programare competitivă pentru dezvoltarea de aplicații distribuite , suport pentru tastare dinamică puternică și soluție de constrângeri . Proiectat de Andreas Rossberg.

Limbajul modulelor din Alice este extins la notarea componentelor ( ing.  componente ), care implementează module de primă clasă sub formă de pachete Russo și suportă suplimentar tastarea dinamică (dar după aceleași reguli de semantică statică) și încărcare leneșă (adică, structurile viitoare sunt suportate și semnăturile viitoare - vezi apelul viitor ) [46] [47] . derivarea tipului este respectată în Alice , iar specificația de co-utilizare ar trebui folosită atunci când este necesar . Un exemplu ilustrativ al utilității practice a pachetelor vine cu Alice : o bibliotecă de serializare a datelor care permite firelor de execuție să schimbe tipuri și date dinamice.

În plus, Alice oferă zahăr sintactic - abilitatea de a folosi liber parantezele în expresiile limbajului modulului, inclusiv în loc de „paranteze” tradiționale struct...endși sig...end:

val p = pachet ( val x = lungime ) : ( val x : 'o listă -> int ) (* val p : pachet = pachet{|...|} *) OCaml

În Ocaml , sintaxa limbajului modulului este uniformă:

tipul modul S = (* semnătură *) sig ... modul M : T (* structură imbricată *) sfârșit modul X : S = (* struct *) struct ... sfârşit modul F ( X : S ) = (* structură parametrizată (functor) *) struct ... sfârșit modulul G ( X : S ) ( Y : T ) = (* structură parametrizată curried (functor de ordin superior) *) struct ... sfârșit

Cu toate acestea, există o serie de diferențe în semantică [48] .

Începând cu versiunea 4, Ocaml acceptă module de primă clasă într-o notație similară cu pachetele ale lui Alice . Sintaxa este încă omogenă, adică nu se distinge de structurile imbricate din semnături.

De la începuturile sale, Ocaml a extins limbajul modulului cu clase și obiecte .

Cele mai importante diferențe dintre Standard ML și Ocaml apar în semantica echivalenței de tip (a se vedea secțiunea despre echivalența de tip ).

Managementul modulelor

Pentru a lega programe gigant ML, pot fi utilizate, în principiu, linkere tradiționale pentru majoritatea limbilor , cum ar fi make . Cu toate acestea, limbajul modulului SML este mult mai puternic decât instrumentele de modularizare ale altor limbaje [2] , iar make nu își susține avantajele și, cu atât mai mult, nu este potrivit pentru analiza globală a fluxului de control al programelor [49] . Prin urmare, diferiți compilatori oferă propriile sisteme de gestionare a modulelor: Compilation Manager (CM) în SML/NJ și MLBasis System (MLB) în MLton . SML.NET [50] are un sistem de urmărire a dependenței încorporat. MLton include, de asemenea, un convertor de fișiere .cm în .mlb .

Majoritatea implementărilor folosesc compilare separată, ceea ce duce la timpi de compilare rapid. Pentru a susține compilarea separată în modul REPL , este utilizată o funcție usecare compileze fișierul specificat și importă definițiile. Unele compilatoare (cum ar fi MLton ) nu acceptă REPL și, prin urmare, nu implementează suport pentru use. Alții (de exemplu, Alice ), dimpotrivă, implementează caracteristici suplimentare de compilare dinamică și încărcare a modulelor în timpul execuției programului. Poly/ML [51] oferă o funcție PolyML.ifunctorcare vă permite să depanați o implementare de functor în mod interactiv, bucată cu bucată.

Exemple de programe

În ciuda simplității sale, limbajul modulului este remarcabil de flexibil și oferă un nivel ridicat de reutilizare a codului , așa cum este ilustrat de următoarele exemple.

Gestionarea numărului de cifre

Tipurile de date tradiționale , cum ar fi numere întregi ( intși word), reale ( real), caractere ( charși widechar), șir ( stringși widestring), matrice ( vectorși array) și altele, sunt implementate în dialectele ML, nu sub formă de tipuri primitive și operatori încorporați peste ele, ca în majoritatea limbilor, dar sub formă de tipuri de date abstracte și funcții corespunzătoare incluse în semnături, respectiv, INTEGER, WORD, REAL, CHAR, STRINGși așa mai departe, furnizate sub formă de biblioteci standard. Implementările concrete ale limbajului pot oferi reprezentări foarte eficiente ale acestor tipuri abstracte (de exemplu, MLton reprezintă matrice și șiruri de caractere în același mod în care face limbajul C ).

De exemplu:

semnătură INTEGER = sig eqtype int val toLarge : int -> LargeInt . int val fromLarge : LargeInt . int -> int val toInt : int -> Int . int val fromInt : Int . int -> int val precizie : Int . int opțiune val minInt : int opțiune val maxInt : int opțiune 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 compare : ( int * int ) -> order val > : ( int * int ) -> bool val > = : ( int * int ) -> bool val < : ( int * int ) -> bool val < = : ( int * int ) -> bool val abs : int -> int val min : ( int * int ) -> int val max : ( int * int ) -> int val semn : int -> Int . int val sameSign : ( int * int ) -> bool val fmt : StringCvt . radix -> int -> string val toString : int -> string val fromString : string -> int opțiune val scan : StringCvt . radix -> ( char , 'a ) StringCvt . cititor -> 'a -> ( int * 'a ) opțiunea final

Structurile , , , și multe altele INTEGERpot fi comparate cu semnătura . De asemenea, structurile / și / (și eventual altele) pot fi asociate cu semnături / și pentru fiecare variantă functorii vor genera o stivă I/O adecvată ( , ). Int8Int16Int32Int64IntInfCHARSTRINGCharStringWideCharWideStringStreamIOTextIO

În același timp, unele structuri ascund reprezentarea tradițională a mașinii sub definiția abstractă (de exemplu, Int32, Int64), altele - câmpuri de biți (de exemplu, Int1), iar structura IntInfimplementează aritmetica lungă . În același timp, bibliotecile pot traversa intens relații de la mai multe la multe : specificația SML Basis definește un set de module obligatorii și opționale construite pe lângă implementarea tipurilor „primitive”: tablouri monomorfe, feliile lor care nu se copiază și așa mai departe . Chiar și tipurile „șir” ( ) și „subșir” ( ) sunt definite în specificația SML Basis ca și (sau și pentru ). Astfel, pentru a folosi aceiași algoritmi cu numere de capacitate diferită, este suficient să treceți explicit structura corespunzătoare functorului (deschiderea nu va schimba structurile deja calculate). stringsubstringChar.char vectorChar.char VectorSlice.sliceWideChar.char vectorWideChar.char VectorSlice.sliceWideString

Diferiți compilatori oferă seturi diferite de structuri implementate. MLton oferă cea mai bogată gamă : de la Int1la Int32inclusiv și Int64, același set pentru Word(întregi fără semn), precum și IntInf(implementat de Biblioteca GNU Multi-Precision ) și multe altele, cum ar fi Int32Array, PackWord32Big, PackWord32Littleși altele.

În majoritatea implementărilor, în mod implicit, la nivelul superior (în mediul global), o structură Int32(sau Int64) este deschisă, adică utilizarea unui tip intși a unei operații +implicit înseamnă a folosi un tip Int32.intși o operație Int32.+(sau, respectiv, Int64.intși Int64.+). În plus, sunt furnizați identificatori Intși LargeInt, care în mod implicit sunt legați de anumite structuri (de exemplu, LargeIntde obicei egale cu IntInf). Diferiți compilatori, în funcție de orientarea lor, pot folosi implicit diferite legături în mediul global, iar o astfel de subtilitate poate afecta portabilitatea programelor între compilatoare. De exemplu, o constantă Int.maxIntconține valoarea celui mai mare număr întreg posibil, înfășurată într- un tip opțional și trebuie preluată fie prin potrivirea modelului, fie printr-un apel de funcție valOf. Pentru tipurile de dimensiuni finite, valoarea este , iar ambele metode de extragere sunt echivalente. Dar este egal , deci accesarea directă a conținutului prin intermediul va face o excepție . În mod implicit , este deschis în compilatorul Poly/ML [51] , deoarece este axat pe probleme de zdrobire de numere . IntN.maxIntSOME(m)IntInf.maxIntNONEvalOf OptionIntInf

Seturi abstracte

Bibliotecile OCaml includ un modul care oferă un functor . Cu acesta, puteți construi cu ușurință un set bazat pe un anumit tip de element: SetMake

module Int_set = Set . Make ( struct type t = int let compare = compare end )

Modulul de set de întregi generat are următorul compilator - semnătură dedusă :

modul Int_set : tip sig elt = tip int t val gol : t val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val elimina : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compara : t -> t -> int val equal : t -> t -> bool val subset : 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 există : ( elt -> bool ) -> t -> bool val filter : ( elt -> bool ) -> t -> t val partition : ( elt -> bool ) -> t -> t * t val cardinal : t -> int val elemente : t -> elt list val min_elt : t -> elt val max_elt : t -> elt val alege : t -> elt val split : elt -> t -> t * bool * t val find : elt -> t -> elt end

Funcționalități similare sunt incluse în bibliotecile compilatoare SML/NJ ( ListSetFn). SML Basis oferă doar instrumente elementare.

Scopul principal al folosirii unui modul dependent în loc de o structură simplă aici este ca funcția de comparație să fie specificată o dată , iar toate funcțiile dintr-un anumit set tipizat folosesc aceeași funcție de comparare pe tipul elementelor acestui set, astfel încât programatorul este astfel protejat de propriile greşeli. Seturile abstracte ar putea fi implementate prin trecerea fiecărei funcții peste mulțime a unei funcții de comparație de fiecare dată (cum se face, de exemplu, într-o funcție standard a limbajului C qsort - vezi polimorfismul parametric în C și C++ ), cu toate acestea, acest lucru nu ar nu face decât să mărească complexitatea lucrului cu seturi, dar ar prezenta și riscul de a confunda funcția de comparare necesară prin introducerea unei erori greu de detectat în program (vezi duplicarea codului ).

Din păcate [24] , din punct de vedere istoric, OCaml a adoptat o semnătură pentru funcția de comparație care indică valoarea de returnare a unui tip bidirecțional ( boolean ) (și convențiile de acest fel ar trebui respectate pentru a putea folosi pe scară largă modulele de bibliotecă) . Mai puternică este soluția SML Basis (precum și Haskell Prelude ) bazată pe un tip cu trei căi:

Ordinea tipului de date = LESS | EGAL | MAI MARE val compară : int * int -> ordine

Testare structurală

Cu prototiparea rapidă , este adesea necesară testarea sistemului în părți sau simularea comportamentului într-un mod simplificat (implementarea așa-numitelor „stubs”). Functorii gestionează această sarcină cu grație.

De exemplu, să presupunem că există trei implementări diferite ale unei structuri de date , să spunem o coadă [52] :

semnătură QUEUE = tip sig 'a t excepție E val empty : '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 final structura Queue1 :> QUEUE = struct ... final structura Queue2 :> QUEUE = struct ... sfârşit structura Queue3 :> QUEUE = struct ... sfârşit

În multe limbi, din lipsă de abstractizare , ar fi necesar să se creeze programe separate copy-paste pentru a le compara . Functorii, pe de altă parte, vă permit să abstrageți testul din implementare și să repetați peste ei într-un singur program:

functor TestQueue ( Q : QUEUE ) = struct fun fromList I = foldl ( fn ( x , q ) => Q . enq ( q , x )) Q . gol I fun toList q = if Q . null q atunci [] altfel Q . hd q :: toList ( Q . deq q ) end val ns = până la ( 1 , 10000 ) (* val ns = [1, 2, 3, 4, ...]: int list *) structura TQ1 = TestQueue ( Queue1 ) val q1 = TQ1 . fromList ns val l1 = TQ1 . toList q1 l1 = ns (* adevărat : bool *) ... structura TQ2 = TestQueue ( Queue2 ) structura TQ3 = TestQueue ( Queue3 ) ...

Apoi puteți alege între căutarea lărgime -prima și adâncimea -primul căutare pentru fiecare implementare, toate într-un singur program:

functor BreadthFirst ( Q : QUEUE ) = struct ... end functor DepthFirst ( Q : QUEUE ) = struct ... end structura BF_Q1 = BreadthFirst ( Coada1 ) structura BF_Q2 = BreadthFirst ( Coada2 ) structura BF_Q3 = BreadthFirst ( Coada3 ) structura DF_Q1 = DeepFirst ( Coada1 ) structura DF_Q2 = DeepthFirst ( Coada2 ) structura DF_Q3 = DeepthFirst ( Coada3 ) ...

În viitor, implementările „extra” nu trebuie să fie șterse. Mai mult, compilatoarele cu optimizare completă , cum ar fi MLton , le vor elimina de la sine - vezi eliminarea codului mort .

Această metodă poate fi folosită și pentru a măsura eficiența, dar în practică este mult mai convenabil (și mai fiabil) să o măsurați folosind un profiler încorporat în compilator.

Siguranța de tip global a dependențelor dintre componentele oferite de limbajul modulului este vizibilă în exemplul unei încercări eronate de a utiliza un functor:

structura Wrong = BreadthFirst ( Lista ); (* > Eroare: specificație tip nepotrivită: t > Eroare: specificație excepție nepotrivită: E > Eroare: specificație val nepotrivită: gol > Eroare: specificație val nepotrivită: enq > Eroare: specificație val nepotrivită: deq *)

Monade și clase de tip

Haskell , care este un descendent al ML , nu acceptă limbajul modulului ML . În schimb, oferă suport pentru programarea la scară largă (în plus față de sistemul trivial de module similare cu cele utilizate în majoritatea limbilor) prin monade și clase de tip . Primele exprimă comportament abstract, inclusiv modelarea stării mutabile în termeni de transparență referențială ; acestea din urmă servesc ca mijloc de control al cuantificării variabilelor de tip prin implementarea polimorfismului ad-hoc . Limbajul modulului ML permite implementarea ambelor expresii [53] [11] .

O clasă de tip nu este altceva decât o interfață care descrie un set de operații al căror tip este dat de o variabilă independentă de tip abstract numită parametru de clasă. Prin urmare, o reprezentare naturală a unei clase în ceea ce privește limbajul modulului va fi o semnătură care, pe lângă setul necesar de operații, include și o specificație de tip (reprezentând un parametru de clasă) [11] :

semnătură EQ = sig tip t val eq : t * t -> bool end

Monada este implementată prin semnătura:

semnătură MONAD = sig type 'a monad val ret : 'a -> 'a monad val bnd : 'a monad -> ( 'a -> 'b monad ) -> 'b monad end

Exemple de utilizare a acestuia:

structura Opțiune : MONAD = struct type 'a monad = 'o opțiune fun ret x = SOME x fun bnd ( SOME x ) k = k x | bnd NONE k = NONE sfârşit semnătură REF = tip sig 'a ref val ref : 'a -> 'a ref IO . monad val ! : 'a ref -> 'a IO . monad val : = : 'a ref -> 'a -> unit IO . sfârşitul monadei

Combinatorii monadici cu drepturi depline sunt deosebit de convenabile de implementat folosind functori de ordin superior [32] [53] :

(*Prima comanda*) semnătură MONOID = sig tip t val e : t val plus : t * t -> t end functor Prod ( M : MONOID ) ( N : MONOID ) = struct type t = M . t * N . t val e = ( M . e , N . e ) fun plus (( x1 , y1 ), ( x2 , y2 )) = ( M . plus ( x1 , x2 ), N . plus ( y1 , y2 )) final functor Square ( M : MONOID ) : MONOID = Prod M M structura Plan = Pătrat ( tip t = real val e = 0,0 val plus = Real . + ) val x = Plan . plus ( Plan . e , ( 7,4 , 5,4 )) (*de ordin superior*) semnătură PROD = MONOID -> MONOID -> MONOID functor Square ( M : MONOID ) ( Prod : PROD ) : MONOID = Prod M M structura T = Pătrat Plan Prod val x = T . plus ( T.e , T.e ) _ _ _ _ (*Transparent*) semnătură PROD' = fct M : MONOID -> fct N : MONOID -> MONOID unde tip t = M . t * N . t functor Square' ( M : MONOID ) ( Prod : PROD' ) : MONOID = Prod M M structura T' = Square' Plan Prod val x = T' . plus ( T' . e , (( 7,4 , 5,4 ), ( 3,0 , 1,7 )))

Valori indexate pe tipuri

Valorile indexate pe tipuri este un idiom comun tuturor limbilor timpurii din familia ML , conceput pentru a implementa polimorfismul ad-hoc ( supraîncărcarea funcției ) prin polimorfism parametric [54] . Clasele de tip , introduse pentru prima dată în Haskell , sunt suport pentru valorile indexate de tip la nivel de limbă (și, ca atare, sunt ușor de implementat în modulului ).

În forma sa cea mai simplă, acest idiom este demonstrat în următorul exemplu OCaml [55] :

tip modul Arith = tip sig t val (+) : t -> t -> t val neg : t -> t val zero : t final modul Build_type ( M : Arith ) = struct let typ x = { Type . plus = M . (+); neg = M. _ (-); zero = M . zero ; } sfârşit let int = let modulul Z = Build_type ( Int ) în Z. _ typ let int64 = let modulul Z = Build_type ( Int64 ) în Z. _ typ let int32 = let modulul Z = Build_type ( Int32 ) în Z. _ typ let native = let module Z = Build_type ( Native_int ) în Z . typ let float = let module Z = Build_type ( Float ) în Z . typ let complex = let module Z = Build_type ( Complex ) în Z. _ tip

Model de obiect

Folosind limbajul modulului, puteți construi un model de obiect simplu cu trimitere dinamică. Acest exemplu este interesant având în vedere că SML nu oferă nicio facilitate de programare orientată pe obiecte și nu acceptă subtipuri .

Cel mai simplu model de obiect dispecerabil dinamic poate fi construit cu ușurință în SML prin . Un tip de intrare care include valori ale funcției joacă rolul unei clase abstracte care definește semnătura metodei. Ascunderea stării interne și a metodelor private ale acestor obiecte este asigurată de sfera lexicală a ML ; astfel, închiderile (funcțiile ML) pot juca rolul de constructori ai obiectelor acestei clase. O astfel de implementare nu permite construirea de ierarhii complexe de moștenire pe mai multe niveluri (acest lucru necesită implementarea subtipurilor, care se realizează printr-o implementare complexă a valorilor indexate pe tipuri și pentru care există mai multe metode diferite), dar în practică este destul de suficientă pentru majoritatea sarcinilor cu un design bun [12] . Derivarea unui astfel de model de obiect la nivelul modulului este considerată mai jos.

Cele mai simple fluxuri de date sunt folosite ca bază:

semnătură ABSTRACT_STREAM = tip sig 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) opţiunea finală semnătură STREAM = sig include ABSTRACT_STREAM val empty : 'a t end structure Stack :> STREAM = struct type 'a t = 'a list val empty = [] val isEmpty = null val push = op :: val pop = List . getItem sfârşitul structure Queue :> STREAM = struct datatype 'a t = T of 'a list * 'a list val empty = T ([], []) val isEmpty = fn T ([], _) => true | _ => false val normalize = fn ([], ys ) => ( rev ys , []) | q => q fun push ( y , T ( xs , ys )) = T ( normalize ( xs , y::ys )) val pop = fn ( T ( x::xs , ys )) => SOME ( x , T ( normaliza ( xs , ys ))) | _ => NIMIC sfârșit

Folosind functori, puteți implementa algoritmi generalizați care manipulează fluxurile de date ale unui dispozitiv intern și scop necunoscut:

functor StreamAlgs ( ST : ABSTRACT_STREAM ) = struct open 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 ) în lp ([], pop d ) final fun cp ( de la , la ) = pushAll ( popAll de la , la ) final

Instanțiarea acestui functor cu structuri comparabile cu semnătura ABSTRACT_STREAMproduce funcții care manipulează fluxurile de date corespunzătoare:

structura S = StreamAlgs ( stivă ) structura Q = StreamAlgs ( coadă ) S. _ popAll ( S . pushAll ([ 1 , 2 , 3 , 4 ], Stack . empty )) (* rezultat: [4,3,2,1] *) Q. _ popAll ( Q . pushAll ([ 1 , 2 , 3 , 4 ], coada . gol )) (* rezultat: [1,2,3,4] *)

Trebuie remarcat faptul că functorul StreamAlgsia un parametru de semnătură ABSTRACT_STREAM, iar structurile Stackși Queueau fost semnate cu semnătura STREAMîmbogățind semnătura . Aceasta implică o subtilitate: atunci când se dezvoltă, este de dorit să se urmeze convențiile adoptate în biblioteca standard a unui anumit dialect pentru a face o utilizare mai largă a dezvoltărilor existente, în special a functorilor standard (nu sunt atât de mulți dintre ei în SML Basis'). 2004, dar în extensiile unor compilatoare și în OCaml există exemple foarte interesante). ABSTRACT_STREAM

Structurile derivate conțin definiția tipului ST.tdin parametrul functor, dar sunt tipuri diferite : fiecare definiție de tip în ML generează un nou tip. Prin urmare, o încercare de a le amesteca duce la o eroare de consistență de tip . De exemplu, următoarea linie va fi respinsă de compilator:

val q = Q . apăsați ( 1 , Stivă . gol )

Interfața clasei thread este definită convenabil ca . Din motive de siguranță a tipului , este de preferat să folosiți nu un alias de tip, ci o funcție de constructor care mapează o astfel de intrare la un obiect de clasă:

structure Stream = struct datatype '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

Modulul Streamimplementează de fapt semnătura ABSTRACT_STREAM( ), dar semnarea explicită este amânată până mai târziu.

Pentru a transforma un modul thread într-o clasă thread, trebuie să adăugați doi constructori numiți la el , ceea ce poate fi făcut cu un functor și constructul de deschidere :

functor 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 din NIMIC => NIMIC | SOME ( x , d ) => SOME ( x , make d ) } val empty = I { isEmpty = fn () => true , push = fn x => make ( D . push ( x , D . empty )), pop = fn () => NIMIC } final

Structura generată de functor StreamClassinclude toate componentele structurii Stream(inclusiv constructorul I ), dar acestea nu sunt vizibile din exterior, deoarece rezultatul functorului este semnat de semnătura STREAM.

În cele din urmă, puteți sigila modulul Stream:

structura Flux : ABSTRACT_STREAM = Flux

Acest lucru nu este necesar din punct de vedere al siguranței de tip , deoarece modulul Streamnu permite ruperea încapsulării așa cum era. Cu toate acestea, ascunderea constructorului I oferă o garanție că numai functorul StreamClasspoate fi folosit pentru a crea subclase ABSTRACT_STREAM.

Cazuri evidente de utilizare:

structura StackClass = StreamClass ( stivă ) structură QueueClass = StreamClass ( coadă )

Dar asta nu este tot. Deoarece functorul definit mai sus StreamAlgsia o structură de tip ca intrare ABSTRACT_STREAM, acesta poate fi instanțiat de o structură Streamcare implementează clasa de flux abstract:

structura D = StreamAlgs ( Stream )

Un modul derivat D, ca și un modul Stream, funcționează cu orice clasă care moștenește de la ABSTRACT_STREAM, care poate fi considerată ca o expediere dinamică:

D. _ popAll ( D . pushAll ([ 1 , 2 , 3 , 4 ], StackClass . gol )) (* rezultat: [4,3,2,1] *) D. _ popAll ( D . pushAll ([ 1 , 2 , 3 , 4 ], QueueClass . gol )) (* rezultat: [1,2,3,4] *)

Este interesant de observat că nici Stream, nici Dnu conține nu numai stare mutabilă , ci și orice constante - doar tipuri și funcții - totuși, fiind trecută prin mecanismul parametrilor, clasa abstractă este de fapt folosită aici ca valoare de primă clasă și nu doar o entitate virtuală, ca în multe limbaje orientate pe obiecte.

Despre limba

Reprezentare la nivel scăzut și eficiență

În mod tradițional, structurile sunt reprezentate în compilator prin intermediul înregistrărilor , iar functorii sunt reprezentați prin funcții peste astfel de înregistrări [35] . Cu toate acestea, există reprezentări interne alternative, cum ar fi semantica Harper-Stone și 1ML .

Folosirea functorilor ca mijloc de descompunere a unui proiect mare înseamnă încetinirea accesului la componentele finale ale programelor calculate prin intermediul acestora, iar pentru fiecare nivel de imbricare, pierderile se înmulțesc, la fel ca atunci când se folosesc funcții obișnuite în locul valorilor imediate. Compilatoarele cu optimizare completă ( MLton , MLKit [56] , SML.NET [50] ) extind cadrul modulului și construiesc definițiile finale ale componentelor functorului ținând cont de caracteristicile structurilor efectiv transmise, ceea ce elimină penalitatea de performanță. MLKit folosește, de asemenea, extinderea modulelor pentru a deduce regiuni, ceea ce permite limbajului să fie folosit pentru a dezvolta aplicații în timp real . În acest caz, dezvăluirea cadrului de module poate fi efectuată prin diverse strategii: de exemplu, MLton realizează „ defunctorizarea programului ”, iar MLKit realizează „ interpretarea statică a limbajului modulului ”. Există o implementare a unui defunctorizator opțional pentru OCaml [57] .

Rațiune pentru semantică

Timp de mulți ani, limbajul modulului ML a fost considerat la nivel teoretic tip ca o aplicație a teoriei tipurilor dependente , iar acest lucru a permis ca limbajul să fie finalizat și proprietățile sale să fie examinate cu atenție. În realitate, modulele (chiar și într-un rol de primă clasă ) nu sunt „ dependente cu adevărat ”: semnătura unui modul poate depinde de tipurile conținute într-un alt modul, dar nu de valorile conținute în acesta [3] ] .

Detalii Corespondența Mitchell-Plotkin Sume puternice McQueen

[58]

Sumele translucide Harper-Lilybridge

Robert Harper și Mark Lillibridge au construit [9] [59] calculul sumelor translucide pentru a justifica formal limbajul modulelor de ordin superior de primă clasă .  Acest calcul este folosit în semantica Harper-Stone . În plus, elementele sale au devenit parte din Definiția SML revizuită (SML'97).

Semantica lui Harper-Stone

Semantica Harper-Stone ( semantica HS pe scurt ) este o interpretare a SML într-un cadru tipizat .  Acesta din urmă include un sistem de module bazat pe sume translucide Harper-Lilybridge (vezi mai sus). Interpretarea este teoretic elegantă, dar menține falsa impresie că modulele ML sunt greu de implementat: folosește tipuri singleton , tipuri dependente și un sistem complex de efecte [3] .

Transformarea F Rossberg-Rousseau-Dreyer

Andreas Rossberg, Claudio Russo și Derek Dreyer au arătat împreună că credința populară despre un prag de intrare nerezonabil de mare pentru un limbaj modul este falsă. Ei au construit o transformare a limbajului modulelor într-un sistem plat F ω ( calculul lambda de ordinul doi), arătând astfel că limbajul modulelor în sine este de fapt doar un caz special ( zahar sintactic ) de utilizare a sistemului F ω . În acest sens, principalul avantaj al utilizării modulelor în comparație cu lucrul direct în Sistemul F ω este un grad semnificativ de automatizare a multor acțiuni complexe (potrivirea semnăturii ținând cont de îmbogățire, împachetarea/despachetarea implicită a existențialelor etc.).

„ F-ing semantics ” ( F-ing semantics ), sau F-transformation, acceptă inclusiv functori de ordin superior și module de primă clasă sub formă de pachete Rousseau. Dovada fiabilității transformării F a fost mecanizată prin metoda „locally nameless” ( Locally Nameless ) în Coq . Autorii au rezumat munca depusă ca fiind extrem de dureroasă și nu recomandă utilizarea acestei metode în viitor [3] . Rezultatele obținute l-au inspirat și mai mult pe Rossberg să creeze 1ML .

Critică și comparație cu alternative

Limbajul modulului ML este cel mai dezvoltat sistem de module din limbaje de programare [2] și continuă să evolueze. Oferă control asupra ierarhiilor spațiilor de nume (prin ) , interfețe cu granulație fină (prin semnături ), abstractizare pe partea client (prin functori ) și partea implementatorului (prin tastare ) [ 3 ] .

Majoritatea limbilor nu au nimic comparabil cu functorii [52] . Cel mai apropiat analog de functori sunt șabloanele de clasă C++ ulterioare , dar functorii sunt mult mai ușor de utilizat [60] deoarece nu numai că șabloanele C++ nu sunt sigure pentru tipare , dar suferă și de o serie de alte dezavantaje [61] . Unele limbi oferă subsisteme macro care permit generarea automată a codului și gestionarea flexibilă a dependențelor de compilare ( Lisp , C ), dar adesea aceste subsisteme macro sunt un supliment neverificabil pentru limbajul principal, permițând rescrierea arbitrară a unei linii de program. prin linie, ceea ce poate duce la o mulțime de probleme [62] . Abia în secolul 21 au fost dezvoltate macro-subsisteme care sunt sigure de tip ( Template Haskell , Nemerle ), dintre care unele sunt disponibile simultan cu functorii (MetaML [63] , MetaOCaml ).

Lucrul grozav despre functori este că aceștia pot fi compilați și verificați de tip chiar dacă nu există nicio structură în program care să le poată fi transmise ca parametru real [64] . Făcând acest lucru, functorii descriu interacțiunea la nivel de interfețe , mai degrabă decât implementări , permițând întreruperea dependențelor de compilare. Acest lucru vine de obicei în detrimentul unei degradări a performanței, dar metodele de optimizare a programului complet rezolvă cu succes această problemă .

Limbajul modulelor este adesea perceput ca fiind greu de înțeles, motivul pentru care constă în matematica complexă necesară pentru a-l justifica. Simon Peyton-Jones a comparat functorii cu o mașină Porsche pentru „ puterea lor mare, dar raportul calitate-preț slab ” [65] . Susținătorii ML nu sunt de acord cu acest punct de vedere, susținând că limbajul modulului nu este mai greu de utilizat/implementat/înțeles decât clasele de tip lui Haskell sau sistemul de clase Java cu generice și wildcard [ , și este într-adevăr o chestiune de preferință subiectivă [3] .

Dacă compilatorul detectează erori în definițiile modulelor, mesajele de eroare de ieșire pot fi foarte lungi, ceea ce în cazul functorilor, în special de ordin superior, poate cauza neplăceri deosebite. Prin urmare, un bloc de definiții de tip și funcții de deasupra acestora ar trebui formatat ca modul numai după ce a fost dezvoltat în părți (pentru care modul REPL este furnizat în majoritatea implementărilor ). Unele implementări (de exemplu Poly/ML [51] ) oferă propriile extensii pentru a rezolva această problemă. Altele (de exemplu, SML2c), dimpotrivă, permit compilarea numai a programelor la nivel de modul.

Istorie, filozofie, terminologie

Ideea limbajului modulului este că semantica la scară largă a programelor ar trebui să repete semantica ML de bază ( ing.  Core ML ), adică dependențele dintre componentele mari ale programului sunt formulate ca dependențe ale unui mic nivel. În consecință, structurile sunt „valori” ale nivelului de modul ( valori la nivel de modul în limba engleză  ); semnăturile (numite și „ tipuri de module ” sau „ tipuri de module ”) caracterizează „tipurile” de valori la nivel de modul , în timp ce functorii caracterizează „funcțiile” nivelului de modul. Analogia, însă, nu este identică: atât conținutul modulelor, cât și relațiile dintre module pot fi mai complexe decât în ​​nucleul limbajului. Cele mai semnificative complicații în acest sens sunt includerea substructurilor în semnături și restricția privind coutilizarea lui [4] . În Comentariile [31] la Definiția SML'90, s-a notat implementarea potențială a functorilor de ordin superior (analogii cu funcții de ordin superior ), dar implementările lor au apărut mai târziu .

Limbajul modulului a fost propus inițial de David MacQueen [66 ] .  În viitor, mulți oameni de știință au adus cea mai semnificativă contribuție la justificarea teoretică a tipurilor și extinderea limbajului modulelor. Lucrarea include formalizarea modulelor recursive , imbricate, locale, de ordin superior și de primă clasă , precum și revizuirea repetată a justificării acestora pentru a simplifica atât modelul în sine, cât și metateoria de sprijin și pentru a-și demonstra fiabilitate. Dezvoltarea limbajului modulului se intersectează îndeaproape cu dezvoltarea ML de bază și este marcată de zeci de lucrări ale multor oameni de știință, dar pot fi distinse următoarele repere cheie:

  • 1984 - McQueen - idee inițială [66] .
  • 1990 - Milner, Harper, McQueen, Tofty - un model separat de miezul limbajului ca parte a Definiției, dovadă a fiabilității sale prin așa-numita etanșare de tip generativ [20] .
  • 1994 - Appel, McQueen - compilație separată [6] .
  • 1995 - Leroy - simplificarea metateoriei la tipuri transparente (negeneratoare), functori aplicativi [67] .
  • 1994 - Harper, Lilybridge - Fundament teoretic tip cu tipuri dependente [9] .
  • 1999-2000 - Rousseau - simplificarea metateoriei la ordinul doi, module de primă clasă sub formă de pachete [39] [40] .
  • 2000 - Harper-Stone semantica .
  • 2010 - Rossberg, Rousseau, Dreyer - simplificarea metateoriei la un sistem plat F , mecanizarea dovezii fiabilității sale în Coq [3] .
  • 2015 - Rossberg - 1ML , un singur model cu nucleul limbajului [34] .

Un alt dialect al ML - limba Caml - a suportat inițial limbajul modulului cu o serie de diferențe . Ulterior, s-a dezvoltat în limbajul Objective Caml , care a completat limbajul modulului cu un subsistem de programare orientat pe obiecte care a dezvoltat organic ideile limbajului modul . OCaml a continuat să evolueze continuu, iar până la mijlocul anilor 2010, limbajul său modul a fost completat de o serie de caracteristici experimentale. Implementările individuale ale SML acceptă unele dintre aceste caracteristici ca extensii. de primă clasă , care sunt susținute și de limbajul Alice .

Aplicație

În diferite limbi

Semantica limbajului modulului este complet independentă de faptul că ML este un limbaj strict - poate fi folosit și în limbaje leneșe [68] . Mai mult, implementările private ale limbajului modulului au fost propuse pe lângă nucleele limbilor diferite din punct de vedere semantic (de exemplu, Prolog și Signal ).

Creșterea parametrică a limbilor

În 2000, Xavier Leroy (dezvoltatorul OCaml ) a propus o implementare a unui model generativ generalizat care vă permite să construiți limbajul modulului ML peste nucleul unui limbaj arbitrar (într-o gamă destul de largă) cu propriul sistem de tipuri ( de exemplu, C ) [1] . Acest model este implementat prin limbajul modulului însuși - sub forma unui functor , parametrizat prin date despre nucleul limbajului și o descriere a mecanismului său de verificare a consistenței tipului .

Modulele ca bază pentru nucleul limbajului

După trei decenii de evoluție a limbajului modulului ca un supliment la nucleul limbajului, în 2015 Andreas Rossberg (dezvoltatorul Alice ) a propus în loc de construirea tradițională a limbajului modulului pe deasupra limbajul de bază, pentru a utiliza limbajul modulului ca limbaj intermediar pentru reprezentarea constructelor limbajului de bază. Acest lucru face ca modulele să fie cu adevărat valori de primă clasă (nu necesită ambalare în pachete) - vezi 1ML .

Note

  1. ↑ 12 Leroy, „Modular Module System”, 2000 .
  2. ↑ 1 2 3 Cardelli, „Programare tip”, 1991 , 2. Limbaje tipografice, p. 5.
  3. ↑ 1 2 3 4 5 6 7 8 Rossberg, Russo, Dreyer, „F-ing Modules”, 2010 .
  4. ↑ 1 2 Harper, „Programarea în 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, „Intro to SML”, 1986 , p. cincizeci.
  8. ↑ Paulson, „ML for the Working Programmer”, 1996 , 7.4 Semnătura intenționată pentru cozi, p. 264.
  9. ↑ 1 2 3 4 Harper, Lillibridge, „Abordarea teoretică de tip a modulelor de ordin superior cu partajare”, 1994 .
  10. ↑ 1 2 Dreyer, Rossberg, „MixML”, 2008 .
  11. ↑ 1 2 3 Dreyer, Harper, „Modular Type Classes”, 2007 .
  12. ↑ 1 2 Programare orientată pe obiecte în ML standard
  13. ↑ Paulson, „ML for the Working Programmer”, 1996 , 2.22 Semnături, p. 62.
  14. ↑ Paulson, „ML for the Working Programmer”, 1996 , 2.19 Introducere în module, p. 59.
  15. ↑ Paulson, „ML for the Working Programmer”, 1996 , 7.5 Signature constraints, p. 264.
  16. ↑ Pucella, „Notes on Programming SML/NJ”, 2001 , p. 58.
  17. ↑ Harper, „Intro to SML”, 1986 , p. 13.
  18. ↑ 1 2 Paulson, „ML for the Working Programmer”, 1996 , 7.14 openDeclarația, p. 299-305.
  19. ↑ Harper, „Intro to SML”, 1986 , p. 36.
  20. ↑ 1 2 3 4 Definiția SML, 1990 .
  21. ↑ Appel, „A Critique of Standard ML”, 1992 , deschis în semnături, p. 17.
  22. ↑ 1 2 Paulson, „ML for the Working Programmer”, 1996 , Ghid de referință pentru module, p. 309.
  23. ↑ Object Mix: functori și timp de rulare vs timp de compilare
  24. ↑ 1 2 Minsky tradus de DMK, 2014 , Capitolul 9. Functori.
  25. ↑ Harper, „Intro to SML”, 1986 , p. 75-76.
  26. ↑ Paulson, „ML for the Working Programmer”, 1996 , 7.13 Programare complet-funcțională, p. 294.
  27. ↑ Harper, „Intro to SML”, 1986 , p. 77.
  28. ↑ 1 2 Harper, „Intro to SML”, 1986 , p. 77-78.
  29. ↑ Minsky tradus de DMK, 2014 .
  30. ↑ Definiția SML: revizuită, 1997 .
  31. ↑ 1 2 3 4 Comentariu la SML, 1991 .
  32. ↑ 1 2 3 4 HOF în SML/NJ .
  33. ↑ Minsky tradus de DMK, 2014 , p. 235.
  34. ↑ 1 2 Rossberg, „1ML - Core and Modules United”, 2015 .
  35. ↑ 1 2 Frisch, Garrigue, „Module de primă clasă în OCaml”, 2010 .
  36. ↑ Rossberg - Functorii și timpul de execuție vs timpul de compilare .
  37. ↑ Neis, Dreyer, Rossberg, „Non-Parametric Parametricity”, 2009 , p. 1-2.
  38. ↑ Rossberg, „1ML - Core and Modules United”, 2015 , p. 2.
  39. ↑ 1 2 Russo, „Tipuri non-dependente pentru module”, 1999 .
  40. ↑ 1 2 Russo, „Structuri de primă clasă”, 2000 .
  41. ↑ 1 2 Russo, „Structuri de primă clasă”, 2000 , p. 17.
  42. ↑ Alice - Pachete .
  43. ↑ Russo, „Structuri de primă clasă”, 2000 , p. paisprezece.
  44. ↑ 1 2 Rossberg, „1ML - Core and Modules United”, 2015 , p. 3.
  45. ↑ Rossberg, „1ML - Core and Modules United”, 2015 , p. 13.
  46. ↑ Rossberg, „Componente dinamice”, 2006 .
  47. ↑ Alice - ExtModules .
  48. ↑ SML vs. OCaml .
  49. ↑ M.L.Basis
  50. ↑ 1 2 Compilatorul SML.NET
  51. ↑ 1 2 3 Pagina compilatorului Poly/ML
  52. ↑ 1 2 Paulson, „ML for the Working Programmer”, 1996 , 7.8 Testing the queue structures, p. 274.
  53. ↑ 1 2 Harper, „Desigur, ML are monade!” .
  54. ↑ Valori indexate de tip
  55. ↑ Yaron Minsky - Ghidul unui programator de lucru pentru valorile tip indexate
  56. ↑ Comiler MLKit (link descendent) . Consultat la 21 ianuarie 2015. Arhivat din original pe 7 ianuarie 2016. 
  57. ↑ Defunctorizator pentru OCaml .
  58. ↑ MacQueen, „Dependent types to express modules”, 1986 .
  59. ↑ Reynolds, „Teoriile limbajelor de programare”, 1998 , 18. Module Specification, p. 398-410.
  60. ↑ Vanden Berghe .
  61. ↑ K. Czarnecki, J. O'Donnell, J. Striegnitz, W. Taha. Implementarea DSL în metaocaml, template haskell și C++ . — University of Waterloo, University of Glasgow, Research Center Julich, Rice University, 2004. Arhivat din original pe 5 martie 2016.
  62. ↑ Appel, „A Critique of Standard ML”, 1992 , Lack of macros, p. 9.
  63. ↑ Steven E. Ganz, Amr Sabry, Walid Taha . Macro-urile ca calcule în mai multe etape: Macro-uri de tip sigur, generative, obligatorii în MacroML . - International Conference on Functional Programming, ACM Press, 2001. Arhivat din original la 23 septembrie 2015.
  64. ↑ Tofte, „Essentials of SML Modules”, 1996 .
  65. ↑ Simon Peyton Jones . Purtarea cămașei de păr: o retrospectivă despre Haskell. — POPL, 2003.
  66. ↑ 1 2 MacQueen, „Module for Standard ML”, 1984 .
  67. ↑ Xavier Leroy, „Functor aplicativ”, 1995 .
  68. ↑ Tofte, „Essentials of SML Modules”, 1996 , p. unu.

Literatură

Tutoriale, ghiduri, cărți de referință, utilizare

Limbajul ML standard
  • Robert Harper . Introducere în Standard ML (nedefinit). - Universitatea Carnegie Mellon, 1986. - ISBN PA 15213-3891.
    • Traducere în rusă:
      Robert Harper. Introducere în Standard ML  (neopr.) . - Universitatea Carnegie Mellon, 1986. - 97 p. — ISBN PA 15213-3891.
  • Lawrence C. Paulson. ML pentru programatorul de lucru  (neopr.) . — al 2-lea. - Cambridge, Marea Britanie: Cambridge University Press, 1996. - 492 p. - ISBN 0-521-57050-6 (copertă cartonată), 0-521-56543-X (copertă moale).
limbajul OCaml
  • Minsky, Madhavapeddy, Hickey. Lumea reală OCaml: Programare funcțională pentru mase  (nedefinită) . - O'Reilly Media, 2013. - 510 p. — ISBN 9781449324766 .
    • Traducere în rusă:
      Minsky, Madhavapeddy, Hickey. Programare în limbajul OCaml  (neopr.) . - DMK, 2014. - 536 p. — (Programare funcțională). - ISBN 978-5-97060-102-0 .
Limbajul modulului
  • Limbajul modulului . (Capitolul versiunii online a lui Développement d'applications avec Objective Caml de Emmanuel Chailloux, Pascal Manoury și Bruno Pagano)
  • Michael P. Fourman. Module SML (  (engleză) ). — 2010.

Istorie, analiză, critică

  • Robin Milner , Mads Tofte, Robert Harper. Definiția ML standard  (neopr.) . - The MIT Press, 1990. - ISBN 0-262-63181-4 .
  • Luca Cardelli . Programare tip( (engleză)) // Rapoarte de ultimă generație IFIP. - New York: Springer-Verlag, 1991. -Vol. Descrierea formală a conceptelor de programare. —S. 431–507.
  • Andrew W. Appel. O critică a ML standard (  (engleză) ). — Universitatea Princeton, versiunea revizuită a CS-TR-364-92, 1992.
  • Claudio Russo. Tipuri non-dependente pentru module (  ( engleză ) ) // Principii și practică de programare declarativă. — Principiile și practica programării declarative, 1999.
  • Xavier Leroy. A Modular Module System (  (în engleză) ) // vol.10, numărul 3. - Journal of Functional Programming, 2000. - S. 269-303 .
  • Andreas Rossberg, Claudio Russo, Derek Dreyer. Module F-ing (  (engleză) ). — TLDI, 2010.

Link -uri