Table Of Links Tabelul din stânga ABSTRACT abstractă 1 INTRODUCTION 1 Introducere 2 DEPENDENTLY-TYPED OBJECT-ORIENTED PROGRAMMING 2 Programare orientată pe obiecte 3 CASE STUDY 3 Studii de caz 4 DESIGN CONSTRAINTS AND SOLUTIONS 4 Constrângeri de proiectare și soluții 5 FORMALIZATION 5 Formalizare 6 DE/REFUNCTIONALIZATION 6 DE/REFUNCȚIONALIZARE 7 FUTURE WORK 7 Viitorul muncii 8 RELATED WORK 8 Lucrări conexe 9   CONCLUSION AND REFERENCES 9 Concluzii și referințe Programare orientată pe obiecte tip dependent Programele tipice scrise în limbajele orientate pe obiecte și funcționale au multe diferențe. Vom analiza acum cum apar aceste diferențe atunci când luăm în considerare programele scrise în stilul orientat pe obiecte. 2.1 Method Call Syntax and Self Parameters Programatorii orientati spre obiect sunt familiarizati cu metoda call syntax o.f(e) pentru a invoca o metoda f luand un argument e pe un obiect o. Acest lucru este prezentat uneori sub denumirea "uniform function call syntax" ca o notatie alternativa pentru apelul f(o, e), unde primul argument al metodei f este numit auto-parametrul. În această dovadă, boolii sunt definiți ca un tip de date, negarea este definită ca o funcție non-dependentă de la booli la booli, iar neg_- invers este definit ca o funcție dependentă de la un x boolian la o dovadă că x este egal cu neg(neg x). În sistemul nostru, vrem să exprimăm atât negul cât și neg_inversul fără a folosi funcții non-dependente sau dependente. def Bool.neg: Bool {True => False => True } Dacă vrem să exprimăm funcția dependentă neg_inverse ca o observație pe booli într-un mod similar, atunci trebuie să adăugăm o caracteristică, parametrii de sine. def (self: Bool.neg_inverse: Eq(Bool, self, self.neg) { True => Refl(Bool, True), False => Refl(Bool, False) } Refuncționalizarea acestor metode cu auto-parametri dictează prima caracteristică a tipurilor de codate dependente: auto-parametrii în distrugători. Autoparametrele din declarațiile codate ne dau puterea expresivă de a reprezenta corect interfețele și clasele verificate într-un stil orientat spre obiect. 2.2 Verified Interfaces and Classes Atunci când verificăm structurile de date și algoritmii în limbile tipate în funcție, putem alege între două abordări generale: verificarea intrinsecă și extrinsică. Folosind verificarea intrinsecă, definim structura de date sau algoritmul împreună cu dovezile de corectitudine. Putem folosi o abordare similară într-un stil orientat spre obiecte folosind tipuri de codate indexate [Thibodeau et al. 2016]. Folosind indicii de tip, putem asigura că observațiile sunt apelate numai pe obiecte care sunt în starea corectă. codata Buffer(m: Nat) { Buffer(S(n)).read(n: Nat): Pair(Bool, Buffer(n)) } codef EmptyBuffer: Buffer(Z) {read(n) absurd } codef Singleton(b: Bool): Buffer(S(Z)) {read(n) => MkPair(Bool, Buffer(Z), b, EmptyBuffer) } Putem vedea că, ca de obicei pentru potrivirea (co)pattern-ului dependent, pot apărea potriviri de model imposibile care trebuie marcate ca fiind absurde. adică, atunci când implementăm interfața tampon pentru tamponul gol nu trebuie să implementăm metoda de citire, deoarece nu poate fi niciodată apelată. De asemenea, dorim să susținem abordarea extrinsică, unde vrem să separăm obiectele noastre de specificațiile lor. Jacobs [1995] ne oferă un concept inițial despre cum să atingem acest obiectiv. El propune un sistem de specificații coalgebraice care pot fi utilizate pentru a verifica clasele orientate spre obiect. Ca exemplu, figura 5a arată o specificație coalgebraică pentru un tampon cu un element care prezintă un comportament de citire persistentă (PR): După ce un element a fost stocat, acesta nu poate fi înlocuit folosind metoda magazinului. În schimb, trebuie să numim metoda goală pentru a goli explicit tamponul. Citirea din tamponul gol returnează o eroare. Această specificație a tamponului este dată ca un set de afirmații care se referă la starea tamponului. În sistemul nostru, putem realiza acest concept folosind parametri auto pe distrugători, permițându-ne să exprimăm specificații ca observații asupra tipurilor de codate. Tipul codate din Figura 5 definește interfața verificată pentru tamponii persistenți de citire în sistemul nostru. 2.3 Dependent Functions Spre deosebire de majoritatea teoriilor de tip dependent, tipul π al funcțiilor dependente nu face parte din teoria noastră de bază, ci poate fi definit într-o bibliotecă. Designerii Java au decis să urmeze această abordare atunci când au introdus abstracțiile lambda ca exemple de interfețe funcționale [Goetz et al. 2014; Setzer 2003] în Java 8. Pe lângă reducerea complexității limbajului de bază, ele simplifică situația dacă avem mai mult de un tip de funcție. Acest lucru este cazul în sistemele sub-structurale în care avem funcții liniare și neliniare. De exemplu, în limbajul de programare Rust, există trei trăsături funcționale diferite încorporate Fn, FnOnce și FnMut, care diferă în modalitatea receptorului3 . 2.4 Weak and Strong Dependent Pairs În secțiunea anterioară, am arătat cum să definim tipul Π. Pentru tipul Π nu am avut de ales decât să îl definim ca tip codata4, dar pentru tipul Σ putem alege dacă să-l modelăm ca tip de date sau codata. Această alegere distinge tipurile Σ slabe și puternice [Howard 1980]: Tipurile Σ puternice sunt definite ca un tip codata cu două proiecții, unde a doua proiecție menționează rezultatul primei proiecții în tipul său de returnare; tipurile Σ slabe, în contrast, sunt definite ca un tip de date cu un constructor care perechează primul și al doilea element. Aceste două reprezentări pot fi obținute una de cealaltă prin defuncționalizare și refuncționalizare. Acest lucru este încă cazul atunci când generalizăm perechi nedependente la tipul Σ. Similar cu tipul π din secțiunea 2.3, tipul Σ este indexat de o familie de tip T. Ca tip de date, este definit de un singur pereche constructor care ia familia de tip T , un element x de tip A și un martor w ca argumente. Ca tip de codată, avem încă două proiecții π1 și π2 ca în cazul perechilor nedependente. Dar a doua proiecție utilizează acum auto-parametrul pentru a garanta că un element de tip T aplicat la selfπ .1 este returnat. De fapt, Agda poate reprezenta deja Σ-tipuri în ambele moduri. Dar există un avertisment: Agda nu a fost proiectată inițial cu tipuri de codata în minte, iar tipurile sale de codata sunt implementate pe înregistrări dependente, ceea ce limitează ce fel de tipuri de codata sunt posibile. De exemplu, ordinea distrugătorilor într-un tip de codata contează pentru Agda, așa că nu putem reordona prima și a doua proiecție. În sistemul nostru, distrugătorii unui tip de codata nu sunt ordonați și se pot referi reciproc, ceea ce reflectă exact modul în care definițiile sunt reciproc recursive pe toc. Dar de ce ar trebui să ne pasă de aceste două codificări alternative ale tipului Σ? Luați, de exemplu, Eisenberg et al. [2021] care discută adăugarea de tipuri existențiale la Haskell. Deoarece Haskell este atât leneș și acceptă ștergerea tipurilor, Eisenberg et al. sunt conduși la un design care utilizează tipuri existențiale puternice. Credem că prin utilizarea cadrului de date și tipuri de codate putem face aceste tipuri de diferențe chiar mai clare. 2.5 Codata Encodings of Natural Numbers Începând cu apariția calculului lambda, cercetătorii au fost interesați de codificarea funcțională a tipurilor de date, cum ar fi booleanele, numerele naturale și listele. Exemple clasice de codificări funcționale sunt codificările tipurilor de date ale Bisericii, Scott și Parigot (cf. Geuvers [2014]; Koopman et al. [2014]). Funcțiile sunt din perspectiva noastră doar o singură instanță specifică a unui tip de codata, așa că suntem interesați de problema mai generală a codificărilor codate în loc de codificări funcționale. Faptul că codificarea Bisericii poate fi obținută prin refuncționalizarea unui program cu numere Peano și o funcție iter a fost deja observată de Ostermann și Jabs [2018]; redăm acest exemplu în Figura 6. Putem observa că tipul codata din Figura 6b, care reprezintă codarea numărelor naturale de către Biserică, nu este recursiv. Acest lucru corespunde teoremului bine-cunoscut că codurile Bisericii pot fi tipate în sistemul pur F. Dacă aplicăm aceeași metodă pentru a obține codarea Scott sau Parigot a numerelor naturale, atunci putem observa că tipul codata rezultant este recursiv. Acest lucru corespunde teoremului cunoscut că aceste coduri nu pot fi tipate în sistemul pur F și necesită tipuri recursive. Putem merge chiar un pas mai departe. Geuvers [2001] a arătat că aceste codificări anterioare nu pot exprima inducția sau eliminarea dependentă. O modalitate de a obține codificări funcționale tipate care pot exprima inducția este de a adăuga o formă de auto-tipuri la sistem; acest tip de codificare a fost introdus de Fu și Stump [2014]. Deși este dificil să se dovedească o corespondență exactă, credem că ideea esențială a codificării Fu și Stump poate fi exprimată în sistemul nostru în Figura 7 și Figura 8. În Figura 7 am codificat inducţia folosind un tip de codată de ajutor StepFun care codifică pasul de inducţie pentru un anumit predicat P pe numere naturale. inducţia este apoi exprimată ca observaţia ind pe un număr natural n care aşteaptă cazul de bază şi pasul de inducţie al inducţiei ca argumente. argumentul n pe care definim observaţia are loc în sine în tipul de returnare. Credem că aceasta este o dovadă suplimentară că autoparametrele pe care le-am introdus în sistem apar în mod natural atunci când trecem de la setarea non-dependentă la cea dependentă. 
 
 
 Autorii : 
 
 
 
 
 David Binder Ingo Skupin Tim Süberkrüb Klaus Ostermann Authors: 
 
 
 
 
 David Binder Grupul Ingo Tim Supraîncărcător Klaus Ostermann 
 
 Acest document este disponibil în arhivă sub licența CC 4.0. Acest document este sub licența CC 4.0. available on ar XIV XIV

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Read My Stories

Why was the 'Hello' afraid to meet 'World'? Because every time they got concatenated, they lost their space!

Concatenation

Acest audio este produs în limba originală a poveștii!

Reconsiderarea OOP prin tipuri și codate dependente

About Author

COMENTARII

Etichete suspendate

ACEST ARTICOL A FOST PREZENTAT IN

Related Stories

Intel Stuns Employees By Cutting Free Office Fruit (And Staff)

The #bitcoin Writing Contest by Rootstock and HackerNoon: Round 1 Results 🎉

Holy 🎅 HackerNoon's Web 2.5 Documentary is Out! 😮

The Spacecoin Writing Contest by Spacecoin and HackerNoon: Round 1 Results 🎉

Intel Stuns Employees By Cutting Free Office Fruit (And Staff)

The #bitcoin Writing Contest by Rootstock and HackerNoon: Round 1 Results 🎉

Holy 🎅 HackerNoon's Web 2.5 Documentary is Out! 😮

The Spacecoin Writing Contest by Spacecoin and HackerNoon: Round 1 Results 🎉

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps