Table Of Links Stůl vlevo ABSTRACT abstraktní 1 INTRODUCTION 1 Úvod 2 DEPENDENTLY-TYPED OBJECT-ORIENTED PROGRAMMING 2 Objektově orientované programování 3 CASE STUDY 3 Případová studie 4 DESIGN CONSTRAINTS AND SOLUTIONS 4 Designové omezení a řešení 5 FORMALIZATION 5 Formalizace 6 DE/REFUNCTIONALIZATION 6 DE/refunkcionalizace 7 FUTURE WORK 7 Budoucnost práce 8 RELATED WORK 8 Související práce 9   CONCLUSION AND REFERENCES 9 Závěry a reference Závislé objektově orientované programování Typické programy psané v objektově orientovaných a funkčních jazycích mají mnoho rozdílů.Pojďme se nyní podívat, jak se tyto rozdíly objevují, když uvažujeme o programech psaných v objektově orientovaném stylu. 2.1 Method Call Syntax and Self Parameters Objektově orientovaní programátoři jsou obeznámeni s metodou volání syntaxe o.f(e) k zavolání metody f s argumentem e na objektu o. To je někdy prezentováno pod názvem „uniformní funkce volání syntaxe“ jako alternativní notace pro volání f(o, e), kde první argument metody f se nazývá samoparametr. V tomto důkazu jsou Booleans definováni jako datový typ, negace je definována jako nezávislá funkce od Booleans k Booleans, a neg_- reverzní je definována jako závislá funkce od boolean x k důkazu, že x je rovna neg(neg x). V našem systému chceme vyjádřit jak neg a neg_inverse bez použití nezávislých nebo závislých funkcí. def Bool.neg: Bool { True => False => True } Pokud chceme vyjádřit závislou funkci neg_inverse jako pozorování na Booleanech podobným způsobem, pak musíme přidat funkci, samoparametry.Můžeme vázat termín, který pozorujeme, na proměnnou, kterou jsme zde nazvali sebe, a použít tuto proměnnou v typu návratu pozorování: def (self: Bool.neg_inverse: Eq(Bool, self, self.neg) { True => Refl(Bool, True), False => Refl(Bool, False) } Refunkcionalizace těchto metod s samo-parametry diktuje první rys závislých typů codata: samo-parametry v destruktorech. Zpětná vazba: Zpětná vazba: Zpětná vazba: Zpětná vazba: Zpětná vazba Jsou to samoparametry v deklaracích codata, které nám dávají expresivní sílu správně reprezentovat ověřené rozhraní a třídy v objektově orientovaném stylu. 2.2 Verified Interfaces and Classes Při ověřování datových struktur a algoritmů v závislých typových jazycích si můžeme vybrat mezi dvěma obecnými přístupy: vnitřní a vnější ověřování. Pomocí vnitřní ověřování definujeme datovou strukturu nebo algoritmus spolu s důkazy o správnosti. Můžeme použít podobný přístup v objektivně orientovaném stylu pomocí indexovaných typů codata [Thibodeau et al. 2016]. Pomocí typových indexů můžeme zajistit, že pozorování jsou volány pouze na objekty, které jsou ve správném stavu. kódování Buffer(m: Nat) { Buffer(S(n)).read(n: Nat): Pair(Bool, Buffer(n)) } codef EmptyBuffer: Buffer(Z) { číst(n) absurd } codef Singleton(b: Bool): Buffer(S(Z)) { číst(n) => MkPair(Bool, Buffer(Z), b, EmptyBuffer) } Můžeme vidět, že jako obvykle pro závislé (co)pattern matching, nemožné vzory zápasy mohou vzniknout, které musí být označeny jako absurdní. to znamená, že když implementujeme tampon rozhraní pro prázdný tampon nemusíme implementovat metodu čtení, protože to nemůže být nikdy volán. Chceme také podpořit extrinsický přístup, kde chceme oddělit naše objekty od jejich specifikací. Jacobs [1995] nám poskytuje počáteční koncept toho, jak dosáhnout tohoto cíle. navrhuje systém koalgebraických specifikací, které lze použít k ověření objektově orientovaných tříd. Jako příklad obrázek 5a ukazuje koalgebraickou specifikace pro jednoelementový buffer, který vykazuje perzistentní čtení (PR) chování: Po uložení prvku nelze jej nahradit pomocí metody obchodu. Namísto toho je třeba nazvat metodu prázdnou, abychom explicitně vyprázdnili tampon. Čtení z prázdného tamponu vrací chybu. Tato specifikace tamponu je dána jako soubor tvrzení, která odkazují na stav tamponu.V našem systému můžeme tento koncept realizovat pomocí samoparametrů na destruktorech, což nám umožňuje vyjádřit specifikace jako pozorování na typy codata. Typ codata na obrázku 5 definuje ověřené rozhraní pro trvalé čtení tamponů v našem systému. Podobně můžeme tento přístup aplikovat na ověřené rozhraní, jako jsou funktory nebo monády. 2.3 Dependent Functions Na rozdíl od většiny ostatních závislých typů teorie, Π-typ závislých funkcí není součástí naší základní teorie, ale může být definován v knihovně. --ḳ Non-dependent Functions codata Fun(a b: Typ) { Fun(a, b.ap(a b: Typ, x: a): b } --ḳ Dependent Functions codata Π(a: Typ, p: a -> Typ) { Π(a, p.dap(a: Typ, p: a -> Typ, x: a): p.ap(a, typ, x) } Návrháři Java se rozhodli následovat tento přístup, když zavedli lambda abstrakce jako příklady funkčních rozhraní [Goetz et al. 2014; Setzer 2003] v Java 8. Kromě toho, že snižují složitost jádrového jazyka, zjednodušují situaci, pokud máme více než jeden typ funkce. To je případ v substrukturálních systémech, kde máme lineární a nelineární funkce. Například v programovacím jazyce Rust existují tři různé vestavěné funkční rysy Fn, FnOnce a FnMut, které se liší v modalitě přijímače3 . 2.4 Weak and Strong Dependent Pairs V předchozím oddíle jsme ukázali, jak definovat typ Π. Pro typ Π jsme neměli jinou možnost, než jej definovat jako typ codata4, ale pro typ Σ můžeme zvolit, zda jej modelovat jako typ dat nebo typ codata. Tato volba rozlišuje mezi slabými a silnými typy Σ [Howard 1980]: Silné Σ-typy jsou definovány jako typ codata se dvěma projekcemi, kde druhá projekce zmiňuje výsledek první projekce ve svém typu návratu; slabé Σ-typy jsou naopak definovány jako datový typ s jedním konstruktorem, který párí první a druhý prvek. Tento rozdíl je zřejmý, pokud nejprve zvážíme případ nezávislých párů, které lze také napsat jako data nebo typ codata. Tyto dvě reprezentace lze získat od sebe defunkcionalizací a refunkcionalizací. To je stále případ, když generalizujeme nezávislé páry do typu Σ. Podobně jako typ Π v oddíle 2.3 je typ Σ indexován rodinou typů T. Jako datový typ je definován jedním konstruktérským párem, který bere jako argumenty rodinu typu T, prvek x typu A a svědka w. Jako typ kódu máme stále dvě projekce π1 a π2 jako v případě nezávislých párů. Ale druhá projekce nyní používá samo-parametr, aby zajistila, že se vrátí prvek typu T aplikovaný na selfπ .1. Ve skutečnosti Agda již může reprezentovat Σ-typy oběma těmito způsoby. Ale existuje jedno varování: Agda nebyla původně navržena s typy codata v mysli, a její typy codata jsou implementovány nad závislými záznamy, což omezuje, jaký typ typů codata jsou možné. Například pořadí destruktorů v typu codata je pro Agdu důležité, takže nemůžeme reorganizovat první a druhou projekci. V našem systému destruktory typu codata nejsou uspořádány a mohou se vzájemně vztahovat, což přesně odráží, jak jsou definice vzájemně rekurzivní na plátně. Ale proč bychom se měli starat o tyto dvě alternativní kódování typu Σ? Vezměme si například Eisenberg et al. [2021], kteří diskutují o přidání existenciálních typů k Haskell. Vzhledem k tomu, že Haskell je jak líný a podporuje vymazání typů, Eisenberg et al. jsou poháněni k návrhu, který používá silné existenciální typy. Myslíme si, že pomocí rámce dat a typů kódů můžeme tyto rozdíly ještě jasněji. 2.5 Codata Encodings of Natural Numbers Od počátku lambda výpočtu se výzkumníci zajímali o funkční kódování datových typů, jako jsou booley, přírodní čísla a seznamy. Klasické příklady funkčních kódování jsou kódování datových typů Church, Scott a Parigot (viz Geuvers [2014]; Koopman et al. [2014]). Funkce jsou z našeho pohledu jen jedním konkrétním příkladem typu codata, takže jsme se zajímali o obecnější problém kódování codata namísto funkčních kódování. To, že kódování církve lze získat z refunkcionalizace programu s čísly Peano a iter funkce již bylo pozorováno Ostermann a Jabs [2018]; jsme znovu tento příklad na obrázku 6. Můžeme pozorovat, že typ codata na obrázku 6b, který představuje církevní kódování přirozených čísel, není recursivní. To odpovídá známému teoremu, že kódování církve může být typováno v čistém systému F. Pokud použijeme stejnou metodu k získání Scottova nebo Parigotova kódování přirozených čísel, pak můžeme pozorovat, že výsledný typ codata je recursivní. To odpovídá jinému známému teorému, že tyto kódování nelze typovat v čistém systému F a vyžadují recursivní typy. Geuvers [2001] ukázal, že tyto předchozí kódování nemůže vyjádřit indukci nebo závislé odstranění. Jeden způsob, jak získat typované funkční kódování, které může vyjádřit indukci je přidat formu self typů do systému; tento druh kódování byl zaveden Fu a Stump [2014]. Ačkoli je obtížné prokázat přesnou shodu, myslíme si, že základní myšlenka kódování Fu a Stump může být vyjádřena v našem systému na obrázku 7 a obrázku 8. Na obrázku 7 jsme kódovali indukci pomocí pomocného codata typu StepFun, který kóduje indukční krok pro daný predikat P na přirozených číslech. Indukce je pak vyjádřena jako pozorování ind na přirozeném čísle n, které očekává základní případ a indukční krok indukce jako argumenty. Domníváme se, že to je další důkaz, že samoparametry, které jsme zavedli do systému, se vyskytují přirozeně, když přejdeme z nezávislého do závislého nastavení. 
 
 
 Autoři : 
 
 
 
 
 David Binder Skupina Ingo Tim Süberkrüb Klaus Ostermann Authors: 
 
 
 
 
 David Binder Skupina Ingo Tim Přehnaný Klaus Ostermann 
 
 Tento dokument je k dispozici v archivu pod licencí CC 4.0. Tento papír je Pod licencí 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

Tento zvuk je produkován v původním jazyce příběhu!

Přehodnocení OOP prostřednictvím závislých typů a kódů

About Author

KOMENTÁŘE

ZAVĚŠIT ZNAČKY

TENTO ČLÁNEK BYL PŘEDSTAVEN V

Related Stories

Coinshift Launches csUSDL, Announces Strategic Partnerships

Coinshift Launches csUSDL, Announces Strategic Partnerships

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps