Beroende på typade språk som Coq används för att specificera och bevisa funktionell korrekthet av källkodsprogram, men vad vi i slutändan behöver är garantier om korrekthet av sammanställd kod. Genom att bevara beroende typer genom varje kompilator pass, kunde vi bevara käll-nivå specifikationer och korrektur i de genererade mål-språkprogram. Tyvärr, typbevarande sammanställning av beroende typer är svårt. År 2002 visade Barthe och Uustalu att typbevarande CPS inte är möjligt för språk som Coq. Närmare bestämt visade de att för starka beroende par (en typ) är den standardtypade call-by-name CPS inte typbevarande. De bevisade vidare att det inte är möjligt med en kategori av CPS-översättningar, inklusive standardöversättningen, för en oberoende fallanalys av belopp. Under 2016 upptäckte Morrisett ett liknande problem med den standardiserade CPS-översättningen för beroende funktioner (II-typer). I huvudsak är problemet att den standardtypade CPS översättning genom dubbel-negation, där beräkningar tilldelas typer av blanketten (A →  på) →  och stör den term/typ ekvivalens som används under typkontroll på ett beroende skrivit språk. I detta dokument bevisar vi att det inte är möjligt att typbevarande CPS-översättning för språk som är beroende av maskinskrivning. Vi utvecklar både call-by-name och call-by- value CPS-översättningar från kalkylen av konstruktioner med både Π och  på typ (CC) till ett beroende skrivit målspråk, och bevisar typbevarande och kompilator korrekthet av varje översättning. Vårt målspråk är CC utvidgas med en ytterligare likvärdighet regel och en ytterligare skrivregel, som vi visar sig konsekvent genom att ge en modell i förlängningskalkyl av konstruktioner. Vår viktigaste iakttagelse är att vi kan använda en CPS översättning som använder svar-typ polymorfism, där CPS-translaterade beräkningar har typ.(A → α) → α. Denna typ rättfärdigar, genom ett fritt teorem, den nya jämlikhetsregeln i vårt målspråk och tillåter oss att återställa den term/typ ekvivalens som CPS översättning stör. Slutligen antar vi att vår översättning sträcker sig till en beroende fallanalys av summor, trots det omöjliga resultatet, och ger en bevisskiss. CCS-koncept: · Programvara och dess teknik → Korrekthet; Funktionella språk; Polymorfism; Kontrollstrukturer; Compilers; · Teori för beräkning → Typteori; Ytterligare Key Words och fraser: Beroende typer, typteori, säker sammanställning, typbevarande sammanställning, parametricitet, CPS * Vi använder en icke-bold blå sans-serif typsnitt för att skriva in källspråket, och en fet röd serif typsnitt för målspråket. Språken kan urskiljas i svartvitt, men papperet är lättare att läsa när det visas eller trycks i färg. Författarens adress: William J. Bowman, Northeast University, USA, wjb@williamjbowman.com; Youou Cong, Ochanomizu University, Japan, so.yuyu@is.ocha.ac.jp; Nick Rioux, Northeast University, USA, rioux.n@husky.neu.edu; Amal Ahmed, Northeast University, USA, amal@ccs.neu.edu. Tillstånd att göra digitala eller papperskopior av delar eller allt detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. Upphovsrätt till tredje parts delar av detta arbete måste hedras. För all annan användning, kontakta ägaren/författaren(er) [Gu et al. 2015], och implementationer av kryptografiska protokoll [Appel 2015; Barthe et al. År 2009 ]. Men även om beroende skrivit språk gör det lättare att verifiera egenskaper hos källkod (Gallina) program, vad som slutligen behövs är en garanti för att samma egenskaper innehar kompilerade låg nivå kod. Detta kräver en verifierad kompilator för Gallina och det pågående arbetet med CertiCoq [Anand et al. 2017 ] är ett bra första steg. CertiCoq raderar dock Gallinatyper och utför sedan omvandlingar som CPS och stängningskonvertering på otypad kod. Problemet med radering typer alltför tidigt i sammanställning pipeline 1 är att det blir svårt att bygga en verifierad kompilator som stöder säker/säker länkning av kompilerad kod med kod från andra språk [Ahmed 2015; Patterson och Ahmed 2017]. Till exempel, betrakta en (ren) högre ordning Gallina funktion f som är sammanställd till C eller sammansättning (som i CertiCoq) och kopplad med ett mål sammanhang som passerar den sammanställda f en oren C eller sammansättning łfunktionž som indata. Denna orena funktion kan bryta Gallinas type-abstraktion eller säkerhetsgarantier eller ändra f's kontrollflöde. Att undersöka typbevarande sammanställning av beroende maskinskrivna språk är av avgörande betydelse eftersom nyckeln till att intuitivt skydda den sammanställda versionen av f från sammanhang som ger ouppfostrade indata är att se till att sammanställd kod endast kan kopplas till sammanhang på målnivå som motsvarar väldefinierade sammanhang på källnivå. Genom att översätta typer under sammanställning, kan vi koda denna korrespondens i typerna. Sedan, vid länktid, tillåter vi att länka en välskriven kompilerad komponent med andra välskrivna målspråkskomponenter. Med typbevarande sammanställning och tillräckligt rika typer på målnivå kan vi statiskt utesluta att länka till ouppfostrade/osäkra sammanhang. Således ger typbevarande sammanställning en väg till att bygga säkra (helt abstrakta) kompilatorer [Abadi 1998; Ahmed och Blume 2008, 2011; Bowman och Ahmed 2015; Fournet et al. 2013; Kennedy 2006; New et al. 2016; Patrignani m.fl. 2015] utan omkostnader för dynamiska kontroller. Genom att bevara beroende typer kan vi även bevara de fullständiga funktionella specifikationerna till målnivån, så att sammanställd kod kan verifieras självständigt genom typkontroll. Detta papper undersöker typbevarande CPS för beroende maskinskrivna språk. CPS översättning är en viktig kompilator pass som gör kontrollflöde och utvärderingsorder explicit 2. Men, det är en omvandling som presenterar icke-triviala problem i en beroende skrivit inställning, som diskuteras nästa. Tidigare arbete. Barthe m.fl. [1999] visade hur man skalar maskinskrivna call-by-name (CBN) CPS översättning till en stor klass av Pure Type Systems (PTS), inklusive analys av konstruktioner (CC) utan  påslag. De använde standardöversättning med dubbel negation, d.v.s. den maskinskrivna varianten av Plotkins ursprungliga CPS-översättning, översättning av källberäkningar av typ A till CPS-translaterade (CPS'd) beräkningar av typ (A + → (där + betecknar värdeöversättning av typer, som förklaras i avsnitt 3). För att undvika vissa tekniska svårigheter (som vi diskuterar i Avsnitt 5), de anser endast domänfri 1 Här łtoo earlyž betyder ł innan vi har ett helt programž — dvs., innan scenen i sammanställning pipeline där vi länkar med låg nivå bibliotek och kod sammanställd från andra språk för att bilda ett helt program. 2 Vi diskuterar det populära alternativet, ANF översättning [Flanagan et al. 1993] Barthe och Uustalu [2002] försökte utvidga dessa resultat till analys av induktiva konstruktioner (CIC), men slutade med att rapportera ett negativt resultat, nämligen att den standardtypade CBN CPS översättningen inte är typbevarande för typer. De fortsätter att bevisa en allmän omöjlighet resultat: för summan typer med beroende fall analys, typ konservering är inte möjligt för klass av CPS översättningar som kan genomföra samtal / cc. Vi återgår till detta senare omöjlighet resultat, som inte gäller vår översättning, i Avsnitt 7. Problemet med CPS-översättningar för olika typer har setts över av andra under årens lopp, men utan positiva resultat. Under 2016 försökte Greg Morrisett skriva call-by- value (CBV) CPS översättning av en A-normaliserad variant av CC, återigen med hjälp av dubbel-negation översättning. 3 Han varnade oss för det faktum att skrivad CBV CPS översättning av  ska verkar fungera när man översätter från A-normal form, men CBV CPS översättning av Π typer (särskilt, ansökan fall) misslyckas med att skriva kontroll.
En variant av denna översättning som stöder beroende summor med hjälp av svar-typ polymorfism utvecklades av REF.
Type-preserving CPS translation of Σ and Π types is not not possible
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}