Dependent Object Types (DOT) är avsedd att vara en kärnkalkyl för modellering Scala. Dess särskiljande funktion är abstrakta typ medlemmar, fält i objekt som innehåller typer snarare än värden. Att bevisa sundheten i DOT har varit förvånansvärt utmanande, och befintliga bevis är komplicerade, och resonera om flera begrepp på samma gång (t.ex. Typer, värden, utvärdering). För att fungera som en kärnkalkyl för Scala, DOT bör vara lätt att experimentera med och förlänga, och därför dess sundhet bevis måste vara lätt att ändra. I detta dokument presenteras en enkel och modulär bevisstrategi för resonemang i DOT. Strategin skiljer resonemanget om olika typer från andra frågor. Den är centrerad kring ett teorem som kopplar hela DOT-systemet till en begränsad variant där de utmaningar och paradoxer som orsakas av abstrakta typmedlemmar elimineras. Nästan allt resonemang i bevisen görs i den intuitiva världen av detta begränsade typsystem. När vi har de nödvändiga resultaten om typer, Vi observerar att de andra aspekterna av DOT är mestadels standard och kan införlivas i en ljudstyrka bevis med hjälp av bekanta tekniker som är kända från andra beräkningar. Vårt papper levereras med en maskin-verifierad version av beviset i Coq. medger skrivningar som helt enkelt verkar helt fel, och ger inget hopp om sundhet, så det verkar nödvändigt att ha lemmas som resonerar samtidigt om de invecklade egenskaper värden, typer och miljöer som de bor i. En kärnanalys måste vara lätt att förlänga. Vissa tillägg av DOT är nödvändiga även för att modellera viktiga Scala funktioner. Som ett framträdande exempel, typer i Scala kan bero på sökvägar x.a 1.·a n.A (där x är en variabel, a i är fält, och A är en typ medlem), men typer i den befintliga DOT calculi kan endast vara direkt beroende av variabler (x.A). Path-beroende typer behövs för att modellera viktiga funktioner såsom klasser och egenskaper (som medlemmar inbäddade i objekt och paket) och den berömda tårta mönster [Odersky och Zenger 2005]. En annan viktig Scala-funktion som ska studeras i DOT är implicita parametrar. Dessutom är språkändringar och tillägg existensberättigandet för en kärnkalkyl. DOT gör det möjligt för designers att experimentera med spännande nya funktioner som kan läggas till Scala, att justera dem och resonera om deras egenskaper innan de försöker integrera dem i kompilatorn med komplexiteten i hela Scala språk. Bevisets komplexitet utgör ett hinder för en sådan utvidgning och försöksverksamhet. Under de senaste tio åren har DOT utformats och omformats för att vara precis rätt, så att de lysande lemmas som säkerställer dess ljudstyrka håller och kan bevisas. När DOT-kalkylen störs av en ändring är det svårt att förutsäga vilka delar av beviset som kommer att påverkas. Att experimentera med modifieringar av DOT är svårt eftersom varje tweak kräver att många lemmas ska testas på nytt. Vårt mål i den här artikeln är ett sundhetsbevis som är enklare, mer modulärt och mer intuitivt. Vi strävar efter att separera begreppen typer, värderingar och operationella semantik, och att resonera om ett begrepp i taget. Sedan, om en språktillägg ändrar endast ett begrepp, såsom skrivande, de nödvändiga ändringarna lokaliseras till de delar av beviset som behandlar typer. Vi strävar också efter att isolera det mesta av resonemanget i ett enklare system som är immunt mot paradoxen med dåliga gränser, den viktigaste utmaningen som plågade det långa sökandet efter ett sundhetsbevis. I detta system kan vårt resonemang förlita sig på intuitiva föreställningar från bekanta objektkalkyl utan beroende objekttyper [Abadi och Cardelli 1996; Pierce 2002]. Resultatet av detta resonemang lyfts till det fullständiga DOT-systemet genom ett enda, enkelt teorem. Huvudfokus för våra bevis ligger på typer. Beroende objekttyper är en funktion som skiljer DOT, så vi strävar efter att koppla bort en funktion, som främst påverkar det statiska typsystemet, från andra bekymmer. Vi fokuserar på att bevisa de egenskaper som man förväntar sig av typer, och avsiktligt hålla beviset oberoende av andra aspekter, såsom operationella semantik och runtime värden, som är liknande i DOT som i andra objekt calculi. Naturligtvis måste ett sundhetsbevis så småningom tala om avrättning och värden, men när vi har den nödvändiga teorin för att resonera om typer, kan dessa andra farhågor hanteras separat, i slutet av beviset, med hjälp av standard bevisteknik. Vår slutliga sundhet teorem anges för de små steg operationella semantik ges av, men det är bara den slutliga slutsatsen; teorin att vi utvecklar om beroende objekttyper skulle vara lika tillämpliga i ett bevis för en stor steg operationell semantik. På sätt och vis rör sig detta dokument i motsatt riktning jämfört med andra arbeten på senare tid relaterade till DOT: detta dokument syftar till ett enklare bevis på en specifik kalkyl, medan andra arbeten generaliserar DOT med inslag från andra kalkyler. Den mest betydande addition i är subtyping mellan rekursiva typer, vilket kräver sofistikerade bevistekniker och induktionssystem, men inte behövs för att modellera Scala. Amin och Rompf [2017] fokuserar på en familj av kalkyler med vissa egenskaper som liknar dem i DOT, och på allmänna bevistekniker som gäller för hela familjen. Även om det är användbart att generalisera och jämföra DOT med andra calculi, det är inte ämnet för detta papper. Detta dokument fokuserar inåt, på DOT sig själv, på endast de funktioner i DOT som är nödvändiga för modellering Scala, i syfte att göra ljudstyrka bevis för dessa specifika funktioner så enkel och modulär som möjligt.
Hittills har arbetet med DOT calculi främst fokuserat på ljudstyrka bevis REF.
A simple soundness proof for dependent object types
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}