Table Of Links Tabell från vänster ABSTRACT Abstrakt 1 INTRODUCTION 1 Introduktion 2 DEPENDENTLY-TYPED OBJECT-ORIENTED PROGRAMMING 2 Objektorienterad beroendeframkallande programmering 3 CASE STUDY 3 Fallstudier 4 DESIGN CONSTRAINTS AND SOLUTIONS 4 Designbegränsningar och lösningar 5 FORMALIZATION 5 Formalisering 6 DE/REFUNCTIONALIZATION 6 DE/refunktionalisering 7 FUTURE WORK 7 Framtidens arbete 8 RELATED WORK 8 Relaterat arbete 9   CONCLUSION AND REFERENCES 9 Slutsats och referenser Objektorienterad beroendeframkallande programmering Typiska program som skrivs i objektorienterade och funktionella språk har många skillnader.Vi kommer nu att titta på hur dessa skillnader visas när vi överväger program som skrivs i objektorienterad stil. 2.1 Method Call Syntax and Self Parameters Objektorienterade programmerare är bekanta med metoden call syntax o.f(e) att åberopa en metod f tar ett argument e på ett objekt o. Detta presenteras ibland under namnet "uniform funktion call syntax" som en alternativ notation för samtalet f(o, e), där det första argumentet för metoden f kallas självparameter. Som utgångspunkt tar vi Agda-beviset från figur 4.I det beviset definieras boolerna som en datatyp, negation definieras som en icke-beroende funktion från boolerna till boolerna, och neg_-omvänd definieras som en beroende funktion från en boolsk x till ett bevis på att x är lika med neg(neg x). I vårt system vill vi uttrycka både neg och neg_inverse utan att använda icke-beroende eller beroende funktioner. def Bool.neg: Bool { True => False, False => True } Om vi vill uttrycka den beroende funktionen neg_inverse som en observation på Booleans på ett liknande sätt, måste vi lägga till en funktion, självparametrar. def (self: Bool.neg_inverse: Eq(Bool, self, self.neg) { True => Refl(Bool, True), False => Refl(Bool, False) } Refunktionaliseringen av dessa metoder med självparametrar dikterar den första egenskapen hos beroende codata typer: självparametrar i förstörare. sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv: sv Det är självparametrar i codata-deklarationer som ger oss den uttrycksfulla kraften att korrekt representera verifierade gränssnitt och klasser i en objektorienterad stil. 2.2 Verified Interfaces and Classes När vi verifierar datastrukturer och algoritmer i beroende typspråk kan vi välja mellan två allmänna tillvägagångssätt: intrinsisk och extrinsisk verifiering. Med hjälp av intrinsisk verifiering definierar vi datastrukturen eller algoritmen tillsammans med dess korrekthetsbevis. Vi kan använda ett liknande tillvägagångssätt i en objektorienterad stil med hjälp av indexerade codata typer [Thibodeau et al. 2016]. Med hjälp av typindex kan vi se till att observationer kallas endast på objekt som är i rätt tillstånd. kodata Buffer(m: Nat) { Buffer(S(n)).read(n: Nat): Pair(Bool, Buffer(n)) } kodf EmptyBuffer: Buffer(Z) {read(n) absurd } kodf Singleton(b: Bool): Buffer(S(Z)) { read(n) => MkPair(Bool, Buffer(Z), b, EmptyBuffer) } Vi kan se att, som vanligt för beroende (co)mönstermatchning, kan ouppnåeliga mönstermatcher uppstå som måste märkas som absurda. Det vill säga, när vi implementerar buffertgränssnittet för den tomma buffern behöver vi inte implementera läsmedlet eftersom det aldrig kan kallas. Vi vill också stödja det extrinsiska tillvägagångssättet, där vi vill separera våra objekt från deras specifikationer. Jacobs [1995] ger oss ett inledande koncept om hur man uppnår det målet. Han föreslår ett system av koalgebraiska specifikationer som kan användas för att verifiera objektorienterade klasser. Som exempel visar figur 5a en koalgebraisk specifikation för en enelementbuffert som visar ihållande läs (PR) beteende: Efter att ett element har lagrats kan det inte ersättas med butiksmetoden. I stället måste man kalla metoden tom för att uttryckligen tömma buffern. Att läsa från den tomma buffern returnerar ett fel. Denna specifikation av buffern ges som en uppsättning påståenden som refererar till buffertillståndet s. I vårt system kan vi förverkliga detta koncept med hjälp av självparametrar på förstörare, vilket gör att vi kan uttrycka specifikationer som observationer på codata-typer. Codata-typen i figur 5 definierar det verifierade gränssnittet för persistenta läsbuffertar i vårt system. 2.3 Dependent Functions Till skillnad från de flesta andra beroende typteorier är π-typen av beroende funktioner inte en del av vår kärnteori, men kan definieras i ett bibliotek. π-typen definieras som en codata-typ indexerad över en typfamilj p, för vilken vi använder den vanliga icke-beroende funktionstypen: -- Átha 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) } Vi föreslår att både beroende och icke-beroende funktioner ska vara användardefinierade i stället för inbyggda.Designerna av Java bestämde sig för att följa detta tillvägagångssätt när de introducerade lambda abstraktioner som exempel på funktionella gränssnitt [Goetz et al. 2014; Setzer 2003] i Java 8. Förutom att minska komplexiteten i kärnspråket förenklar de situationen om vi har mer än en funktionstyp. Detta är fallet i substrukturella system där vi har linjära och icke-linjära funktioner. Till exempel, i Rust programmeringsspråket finns det tre olika inbyggda funktionella egenskaper Fn, FnOnce och FnMut, som skiljer sig i modaliteten hos mottagaren3. 2.4 Weak and Strong Dependent Pairs I föregående avsnitt visade vi hur man definierar π-typen. För π-typen hade vi inget annat val än att definiera den som en codata typ4, men för Σ-typen kan vi välja om vi ska modellera den som en data eller codata typ. Detta val skiljer mellan svaga och starka Σ-typer [Howard 1980]: Starka Σ-typer definieras som en codata typ med två projektioner, där den andra projektionen nämner resultatet av den första projektionen i sin returtyp; svaga Σ-typer, i motsats, definieras som en datatyp med en konstruktör som parar det första och det andra elementet. Dessa två representationer kan erhållas från varandra genom defunktionalisering och refunktionalisering. Detta är fortfarande fallet när vi generaliserar icke-beroende par till Σ-typen. I likhet med π-typen i avsnitt 2.3, är Σ-typen indexerad av en typfamilj T. Som en datatyp definieras den av ett konstruktörspar som tar typfamiljen T , ett element x av typ A och ett vittne w som argument. Som en codata-typ har vi fortfarande två projektioner π1 och π2 som i fallet med icke-beroende par. Men den andra projektionen använder nu självparametern för att garantera att ett element av typ T som tillämpas på selfπ .1 returneras. Faktum är att Agda redan kan representera Σ-typer på båda dessa sätt. Men det finns en varning: Agda var inte ursprungligen utformad med codata-typer i åtanke, och dess codata-typer implementeras ovanpå beroende poster, vilket begränsar vilken typ av codata-typer som är möjliga. Till exempel är ordningen av destruktorerna i en codata-typ relevant för Agda, så vi kan inte omordna den första och andra projektionen. I vårt system är destruktorerna av en codata-typ inte ordnade och kan hänvisa till varandra, vilket exakt speglar hur definitioner är ömsesidigt återkommande på taket. Men varför ska vi bry oss om dessa två alternativa kodningar av Σ-typen? Ta till exempel Eisenberg et al. [2021] som diskuterar tillägget av existentiella typer till Haskell. Eftersom Haskell både är lat och stöder typ radering, Eisenberg et al. drivs till en design som använder starka existentiella typer. Vi tror att genom att använda ramen för data och codata typer vi kan göra dessa typer av skillnader ännu tydligare. 2.5 Codata Encodings of Natural Numbers Från början av lambda kalkyl har forskare varit intresserade av funktionell kodning av datatyper som booleaner, naturliga tal och listor. Klassiska exempel på funktionell kodning är kyrkan, Scott och Parigot kodningar av datatyper (jfr Geuvers [2014]; Koopman et al. [2014]). Funktioner är ur vårt perspektiv bara en viss instans av en codata typ, så vi är intresserade av det mer allmänna problemet med codata kodningar i stället för funktionella kodningar. Att kyrkans kodning kan erhållas genom att återfunktionalisera ett program med Peano-nummer och en iter-funktion har redan observerats av Ostermann och Jabs [2018]; vi återger detta exempel i figur 6. Vi kan observera att codata-typen i figur 6b som representerar kyrkans kodning av naturliga tal inte är återkommande. Detta motsvarar det välkända teoremet att kyrkans kodningar kan skrivas i rent system F. Om vi tillämpar samma metod för att få Scott eller Parigot-kodningen av naturliga tal, då kan vi observera att den resulterande codata-typen är återkommande. Detta motsvarar det andra välkända teoremet att dessa kodningar inte kan skrivas i rent system F och kräver återkommande typer. Geuvers [2001] visade att dessa tidigare kodningar inte kan uttrycka induktion eller beroende eliminering. Ett sätt att få typade funktionella kodningar som kan uttrycka induktion är att lägga till en form av självtyper till systemet; denna typ av kodning introducerades av Fu och Stump [2014]. Även om det är svårt att bevisa en exakt korrespondens, tror vi att den väsentliga idén om kodningen av Fu och Stump kan uttryckas i vårt system i figur 7 och figur 8. I figur 7 har vi kodat induktion med hjälp av en hjälpkodata typ StepFun som kodar induktionssteget för en given predikat P på naturliga tal. Induktion uttrycks sedan som observationen ind på ett naturligt tal n som förväntar sig basfallet och induktionssteget av induktionen som argument. Argumentet n på vilket vi definierar observationen inträffar själv i returtypen. Vi tror att detta är ytterligare bevis på att de självparametrar vi introducerade till systemet uppstår naturligt när vi går från den icke-beroende till den beroende inställningen. 
 
 
 Författare : 
 
 
 
 
 David Binder Ingo Skupin Tim Süberkrüb av Klaus Ostermann Authors: 
 
 
 
 
 David Binder Ingo Grupp Tim Överkrüb av Klaus Ostermann 
 
 Den här artikeln finns tillgänglig på archiv under CC 4.0-licens. Detta papper är med CC 4.0 licens. 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

Det här ljudet är producerat på berättelsens originalspråk!

Ompröva OOP genom beroende typer och codata

About Author

KOMMENTARER

HÄNG TAGGAR

DENNA ARTIKEL PRESENTERAS I

Related Stories

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps