Reynolds parameterteori fångar den egenskap som parametriskt polymorfa funktioner beter sig enhetligt: de producerar relaterade resultat på relaterade momentiationer. I beroende maskinskrivna programmeringsspråk kan sådana relationer och enhetliga bevis uttryckas internt och genereras som en programöversättning. Vi presenterar en ny parametrisk översättning för ett betydande fragment av Coq. Tidigare översättningar av parametriskt polymorfa satser tillät icke-uniformitet. På relaterade momentiationer kan till exempel en funktion returnera förslag som logiskt sett inte är likvärdiga (t.ex. Sant och falskt). Vi visar att enhetlighet i polymorfa satser inte kan uppnås i allmänhet. Trots detta producerar vår översättning bevis för att de två förslagen är logiskt likvärdiga och också att två bevis på dessa förslag är relaterade. Detta uppnås på bekostnad av möjligheten att kräva fler antaganden om instantieringarna, vilket kräver att de är isomorfa i värsta fall. Vår översättning förstärker den tidigare för Coq genom att bära och kompositionsbyggande extra bevis om parametrikitet relationer. Det underlättas genom en ny metod för att översätta induktiva typer och mönstermatchning. Den nya metoden bygger på och generaliserar tidigare sådana översättningar för beroende maskinskrivna programmeringsspråk. Med reificering och reflektion har vi implementerat vår översättning som Coq program 1. Vi får flera starkare fria teorem som gäller för ett pågående kompilatorkorrigeringsprojekt. Tidigare, bevis på några av dessa teorem tog flera timmar att avsluta. Krishnaswami och Dreyer [2013] sammanfattar Reynolds arbete om parametricitet på följande perfekta sätt: Reynolds [1983] introducerade berömda begreppet relationell parametricitet med en fabel om dataabstraction. Professorerna Bessel och Descartes, som var och en undervisar en klass om komplexa tal, definierade dem olika i den första föreläsningen, den förra med polarkoordinater och den senare med (naturligtvis) kartesiska koordinater. Men trots att de råkade byta sektioner efter den första föreläsningen, lärde de aldrig sina elever något falskt, eftersom båda professorerna efter den första klassen bevisade alla sina teorem i termer av de definierade operationerna på komplexa tal, och aldrig i termer av deras underliggande koordinatrepresentation. Reynolds formaliserade denna idé genom att ge en semantik för System F där varje typ betecknade inte bara en uppsättning välformade termer, utan en logisk relation mellan dem, definieras rekursivt på språkets typstruktur. Sedan, det faktum att välskrivna klientprogram var okänsliga för ett specifikt val av genomförande kunde formaliseras i termer av deras tar logiskt relaterade ingångar till logiskt relaterade resultat. Eftersom de två konstruktionerna av de komplexa talen delar samma gränssnitt, och det är lätt att visa att de är logiskt relaterade vid det gränssnittet, måste varje klient i gränssnittet returnera likvärdiga resultat oavsett vilken implementation av gränssnittet används. I Reynolds arbete och senare arbete för andra moderna språk (t.ex. OCaml [Crary 2017], de logiska sambanden för typer är metateoretiska (inte definierade i det programmeringsspråk som studeras). Däremot kan man uttrycka * abhishek.anand.iitg@gmail.com 1 https://github.com/aa755/paramcoq-iff Proc.
Den parametriska översättningen av REF utvidgar den logiska relationen till satser till att tvinga fram att relaterade satser är logiskt likvärdiga.
Revisiting Parametricity: Inductives and Uniformity of Propositions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}