Ett ökande antal system är beroende av programmeringsspråkteknik för att garantera säkerhet och säkerhet för lågnivåkoder. Tyvärr är dessa system vanligtvis beroende av en komplex, betrodd sopsamlare. Regionbaserade typsystem ger ett alternativ till sophämtning genom att göra minneshanteringen explicit men verifiabelt säker. Det har dock inte varit klart hur man använder regioner i lågnivå, typsäker kod. Vi presenterar en kompilator mellanspråk, som kallas Capability Calculus, som stöder regionbaserad minneshantering, har ett bevisligen säkert typsystem, och är enkel att kompilera till ett maskinskrivet monteringsspråk. Källspråk kan sammanställas till vårt språk med hjälp av kända regionslutalgoritmer. Dessutom behöver regionens livstider inte lexikalt avgränsas i vårt språk, men språket kan kontrolleras för säkerhet utan komplexa analyser. Slutligen, vår ljudstyrka bevis är relativt enkel, med endast standard tekniker. Den centrala nyheten är användningen av statiska funktioner för att specificera tillåtenheten av olika operationer, såsom minnesåtkomst och deallocation. För att säkerställa att kapaciteten avges på rätt sätt spårar typsystemet aliasinformation med hjälp av en form av avgränsad kvantifiering. 1 En aktuell trend i systemprogramvara är att tillåta att opålitliga tillägg installeras i skyddade tjänster, beroende på språkteknik för att skydda tjänstens integritet i stället för hårdvarubaserade skyddsmekanismer [19, 39, 2, 25,24,17,14]. SPIN-projektet [2] bygger till exempel på Modula-3-systemet för att skydda en operativsystemkärna från felaktiga utökningar. På samma sätt förlitar sig webbläsare på Java Virtual Machine byte-kod kontrollant [19] för att skydda användare från skadliga applets. I båda fallen är målet att eliminera dyr kommunikation eller gräns *Denna forskning utfördes medan den första författaren var vid Cornell University. Detta material är baserat på arbete som delvis stöds av AFOSR-bidraget F49620-97-1-0013 och ARPA/RADC-bidraget F30602-96-l-0317. Alla synpunkter, resultat och slutsatser eller rekommendationer som uttrycks i denna publikation är upphovsmännens och återspeglar inte dessa organs synpunkter. Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt eller klassrum används utan avgift menas att kopior inte vadas eller distribueras för prolit eller kommersiella fördelar och att ämnen bär detta meddelande och fyll citering på första sidan. För att kopiera annat, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och!eller en avgift. övergångar genom att tillåta utvidgningar för att direkt få tillgång till de resurser de behöver. Nyligen har Necula och Lee 126, 251 föreslagit ProofCarrying Code (PCC) och Morrisett et al. [24] har föreslagit Typed Assembly Language (TAL) som språkteknik som ger säkerhetsfördelar av hög nivå språk, men utan overheads av tolkning eller just-in-time sammanställning. I båda systemen, låg nivå maskinkod kan kraftigt optimeras, för hand eller av kompilator, och ändå automatiskt verifieras genom korrektur- eller typkontroll. Men i alla dessa system (SPIN, JVM, TAL och Touchstone [27], en kompilator som genererar PCC), finns det en aspekt över vilken programmerare och optimerande kompilatorer har liten eller ingen kontroll: minneshantering. Deras sundhet är i synnerhet beroende av att minnet återvinns av en pålitlig sopsamlare. Därför kan applets eller kärntillägg inte utföra sin egen optimerade minneshantering. Eftersom sopuppsamlare tenderar att vara stora, komplicerade delar av okontrollerad programvara minskar dessutom förtroendet för språkbaserade skyddsmekanismer. Målet med detta arbete är att ge en hög grad av kontroll över minneshantering för programmerare och kompilatorer, men som i PCC och TAL ramar, göra verifiering av säkerheten i program en enkel uppgift. Tofte och Talpin [35, 361 föreslår ett typ- och effektsystem för att verifiera sundheten i den regionbaserade minneshanteringen. I senare arbete visar Tofte och andra hur man kan härleda regiontyper och livstider och hur man genomför deras teori [34, 3, 41. Det finns flera fördelar med regionbaserad minneshantering; ur vår synvinkel är de två viktigaste: 1. Deallocation är explicit men bevisligen säkert. 2. Utgångspunkten är följande: De körtider som krävs för regionbaserad minneshantering är relativt enkla konstanta operationer och skulle i princip kunna verifieras formellt. Tofte-Talpin-kalkylen använder ett lexikalt slingat uttryck (letregion r i e slut) för att avgränsa livslängden för en region r. Memory för regionen tilldelas när kontrollen går in i omfattningen av letregion konstruera och deallokeras när kontrollen lämnar omfattningen. Denna mekanism resulterar i en strikt LIFO (last-in, first-out) beställning av regionens livstider. Båda Birkedal et al. [4] och Aiken m.fl. [l] konstaterade att en fullständig LIFO (de)allokering av regioner skulle göra dålig användning av minnet i många fall. De föreslog en rad optimeringar som ofta minskar effektiviteten och till och med förbättrar den traditionella sophämtningen i vissa fall. Även om deras optimeringar är säkra, det finns ingen enkel bevis-eller typkontroll som en opålitlig klient kan använda för att kontrollera utdatakoden. På samma sätt kräver till och med den mest enkla kodgenereringen att vi avviker från ramen för Tofte-Talpin och tillåter godtycklig åtskillnad av fördelnings- och fördelningspunkter. Därför, medan region slutsatser för oss halvvägs till vårt mål, för att bygga ett starkt-typed region-baserade monteringsspråk måste vi ompröva den grundläggande frågan: "När kan vi befria ett objekt x?" En lösning är att gratis x när du kan garantera att det inte längre kommer att nås. Operativa system som Hydra [41] har löst åtkomstkontrollproblemen tidigare genom att koppla ihop en oförfalskad nyckel eller kapacitet med varje objekt och kräva att användaren presenterar denna förmåga att få tillgång till objektet. Dessutom, när behovet uppstår, dessa system återkallar kapacitet, vilket förhindrar framtida tillgång. I resten av denna uppsats beskriver vi ett starkt skrivspråk som kallas Capability Calculus. Vårt språktypsystem ger ett effektivt sätt att kontrollera säkerheten för explicit, godtyckligt ordnad regionallokering och deallocation instruktioner med hjälp av en uppfattning om förmåga. Precis som i traditionella kapacitetssystem håller vårt typsystem koll på kapacitetskopior noggrant för att avgöra när en kapacitet verkligen har återkallats. Till skillnad från traditionella kapacitetssystem stöder vår analys endast frivilligt återkallande. Emellertid, kapaciteten i vår analys är ett rent statiskt koncept och därmed deras genomförande kräver ingen run-time overhead. Vi har ett rent syntaktiskt argument, baserat på Subject Reduction och Progress lemmas i stil med Felleisen och Wright [40], att typsystemet för Capability Calculus är ljud. Tofte och Talpin formulerar däremot sundheten i sitt system med hjälp av ett mer komplicerat och mest invecklat argument [36] och ljudnivån hos Aiken et AI.' s optimeringar [l] beror på detta argument. En del av anledningen till den extra komplexiteten är att Tofte och Talpin samtidigt visar att region inference översätter lambda kalkyl termer till operativt likvärdiga region kalkyl termer, en starkare egendom än vi bevisar. Men när systemets säkerhet är den viktigaste angelägenheten, är sundhet den kritiska egenskapen. Enkelheten i vårt argument visar fördelarna med att skilja typ ljud från typ inference eller optimering korrekthet. Vi har en formell översättning av en variant av TofteTalpin-språket till vår kalkyl. Vi beskriver översättningen i detta dokument som exempel; de fullständiga detaljerna finns i den tekniska rapporten [5]. Vi illustrerar också hur vissa regionbaserade optimeringar kan kodas på vårt språk och dra nytta av vår extra frihet att placera fördelnings- och deallocationspunkter. Vi har anpassat typsystemet för Capability Calculus till inställningen av Typed Assembly Language, vilket för första gången ger möjlighet för "applets" att uttryckligen styra sin minneshantering utan att offra minnes- eller typsäkerhet. Eftersom skrivkonstruktionerna på mellan- och monteringsnivå är så lika, diskuterar vi här endast mellanspråket och hänvisar den intresserade läsaren till den tekniska rapporten [5] för detaljer på monteringsnivå. Det centrala tekniska bidraget i detta dokument är Capability Calculus, ett statiskt inskrivet mellanspråk som stöder explicit allokering, frigörande och åtkomst av minnesregioner. Program i Capability Calculus är skrivna i fortsättnings-passerande stil (CPS) [29]. Det vill säga, funktioner returnerar inte värden; istället fungerar avsluta genom att kalla en fortsättning funktion som vanligtvis tillhandahålls som ett argument. Det faktum att det bara finns ett sätt att överföra kontroll i CPS-rader än de två medel (samtal och retur) i direkt stil förenklar spårningen av funktioner i vårt typsystem. En direkt stil formulering är möjligt, men de komplikationer som är inblandade skymmer de centrala frågorna. I resten av detta dokument antar vi att vi är förtrogna med CPS. Syntaxen för kapacitetskalkylen visas i figur 1. I följande avsnitt förklarar och motiverar vi de viktigaste konstruktionerna och skrivreglerna för språket en efter en. Den fullständiga statiska och operativa semantiken specificeras i tillägg A. Vi specificerar det operativa beteendet hos Capability Calculus med hjälp av en tilldelning semantik [22, 23, 241, vilket gör fördelningen av data i minnet explicit. Semantiken ges av ett deterministiskt omskrivningssystem P I-+ P' karteringsmaskintillstånd till nya maskintillstånd. Ett maskintillstånd består av ett par (M, e) av ett minne och en term som utförs. Ett minne är en ändlig kartläggning av regionnamn (v) till regioner där en region är ett minnesblock som innehåller en samling hög fördelade objekt. Regioner skapas på körtid genom deklarationen neurgnp, z, som fördelar en ny region i högen, binder p till namnet på den regionen, och binder z till handtaget (handle(v)) för den regionen. Regionens namn och handtag skiljer sig åt för att upprätthålla en fasskillnad mellan kompileringstid och runtime-uttryck. Regionnamnen är betydande vid sammanställningstidpunkten: Typkontrollören identifierar vilken region ett objekt bebor via ett regionnamn (se nedan). Regionnamn, liksom andra typer av konstruktörer, har dock ingen betydelse för körtiden och kan raderas från körbar kod. Regionen hanterar däremot hålla de run-time data som krävs för att manipulera regioner. Förutom att redovisa en fasskillnad, gör uppdelningen av regionnamn och handtag också att vi kan förfina de sammanhang där regionen hanterar behövs. Handtag behövs vid fördelning av objekt inom en region och när man befriar en region, men behövs inte vid läsning av data från en region. Regioner frigörs av deklarationen freergnv, där v är handtaget för regionen att befrias. Objekt h tillräckligt stora för att kräva heap allokering (dvs. funktioner och tuples), kallas heap vaZues, tilldelas av deklarationen z = h vid v, där v är handtaget för den region där h ska fördelas. Data läses från en region på två sätt: funktioner läses av en funktion anrop, och tuples läses av deklarationen z = r;(v), som binder x till data som är bosatta i ith fältet av objektet på adress v. Var och en av dessa åtgärder kan utföras endast när regionen i fråga inte redan har befriats. En förstärkning av denna begränsning är syftet med den kapacitetsmekanism som diskuteras i avsnitt 2.2. En region kartlägger platser (e) för att samla värden. Således en adress anges av ett par v.e av en region namn och en plats. Under utförandet kommer ordstorleksvärden (v) att ersättas för värdevariabler och typkonstruktörer för konstruktörsvariabler, men högvärden (h) fördelas alltid i minnet och hänvisas indirekt till av en adress. Vid genomförandet av deklarationen z = h vid r (där r är handtag(v), handtaget för region v), h fördelas i region v (säg vid a) och adressen v.e ersätts med x i följande kod. En term i Capability Calculus består av en serie deklarationer som slutar i antingen en gren eller ett funktionssamtal (eller ett stopp). Klassen deklarationer inkluderar de konstruktioner som diskuteras ovan, plus två standardkonstruktioner, x = v för bindande variabler till värden och x = vi p 212 (där p varierar över +, -och x) för aritmetik. Typerna av Capability Calculus inkluderar typ konstruktör variabler och heltal, en typ av region handtag, liksom tuple och funktionstyper. Om r är en region, då r handtag är typen av r region handtag. Tuple typ (Tl,. ., TV) vid r innehåller de vanliga n-fält tuples, men också anger att sådana tuples fördelas i region r, där r är antingen ett regionnamn v eller, oftare, en regionvariabel P. Till exempel, en polymorfisk identitetsfunktion som tilldelas i region r, men vars fortsättningsfunktion kan vara i någon region, kan ges typ V[a:Typ, p:Rgn].(C, cy, (C, a) + 0 at p) + 0 at r för vissa lämpliga C. Låt f vara en sådan funktion, låt w vara dess argument med typ r, och låt g vara dess fortsättning med typ (C, 7) -+ 0 at r. Då f kallas av Skrivreglerna också använda regiontyper (T), som tilldelar en typ till varje plats som tilldelats i en region, och minnestyper (@), som tilldelar en regiontyp till varje område som tilldelats i minnet. 2.2 Det centrala problemet är hur man statiskt ser till att ingen region används efter det att den har frigjorts. Skrivreglerna verkställer detta med ett system av funktioner som anger vilka operationer som är tillåtna. Den huvudsakliga maskinskrivning bedömning är *; A; I'; C!-e 264 som anger att (när minnet har typ X!?, fria konstruktörsvariabler har typer som ges av A och fria värdevariabler har typer som anges av I') det är lagligt att köra termen e, förutsatt att kapaciteten C hålls. En relaterad typning bedömning är som anger att om kapaciteten C innehas, är det lagligt att utföra deklarationen d, vilket resulterar i nya konstruktör sammanhang A', nytt värde sammanhang I" och ny förmåga C'. Kapaciteten anger den uppsättning regioner som för närvarande gäller för tillträde, dvs. de regioner som inte har frigjorts. Kapaciteter bildas genom att sammanfoga en samling av singleton kapacitet {r} som ger tillgång till endast en region, och kapacitetsvariabler E som ger tillgång till en ospecificerad uppsättning regioner. Capability ansluter, skriftlig Cr @ Cz, är associativ och pendlande, men är inte alltid idempotent; i Avsnitt 2.3 kommer vi att se exempel där C @ C inte motsvarar C. Tomheten kapacitet, som ger tillgång till inga regioner, betecknas med 8. Vi kommer ofta förkorta kapaciteten {ri} $. .. @ {T,} av {PI,.. .......................................................... För att läsa ett fält från en tuple i region r, är det nödvändigt att hålla förmågan att komma åt r, som i regeln: A I-C = C' @ {r} : Cap *;A;l?t-~:(ri,...,r~)atr 9; A; l?; C I-z = A;(W) + A; l?{z:ri}; C (z G Dam(r)) Det första delmålet anger att kapaciteten som hålls (C) är likvärdig med någon förmåga som inkluderar {r}. En liknande regel används för att fördela ett objekt i en region. Eftersom typen av ett högvärde återspeglar den region där det fördelas, måste värderingen av högvärdet (det andra delmålet nedan) tillhandahållas med den regionen. A l-C = C' @ {r} : Cap\k;A;I't-hatr:r 'P;A;I'fv:r handtag ~;A;r;Ct-~=atv~A;r{z:r};C (z @ oom(r)) Funktioner definieras av formen fixf[A](C,zi:r,..., z,:r,).e, där f står för själva funktionen och kan visas fritt i kroppen, A anger funktionens konstruktör argument, och C är funktionens kapacitetsförutsättning. När A är tom och f inte visas fritt i funktionskroppen vi förkortar fix form av X(C,zi:ri,). ..., z ":r,......................................................... För att kalla en funktion bosatt i region r, är det återigen nödvändigt att hålla förmågan att komma åt r, och även att ha en kapacitet som motsvarar funktionens kapacitetsförutsättning: A k C = C" @ {r} : Cap A I-C = C' : Cap *;A;lYt-v:(C',ri,...,r,) + Oatr O;A;I't-wi:ri Kroppen av en funktion kan då anta funktionens kapacitetsförutsättning är tillfredsställd, som anges av kapaciteten C i premissen för regeln: " *; A; I'{zi:ri,. ., G:T,}; C I-e 9; A; r E X(C, zl:rl, .., z,:r,).e Ofta kommer vi att utöka den kapacitet som krävs för en funktion med en kvantifierad kapacitetsvariabel (liknar en radvariabel). Denna variabel kan omedelbart aktiveras med alla funktioner som blir över efter att ha uppfyllt den erforderliga kapaciteten. Följaktligen kan funktionen användas i olika sammanhang.  Den känsligaste frågan är definitionen av fördelning och fördelning av regioner. Intuitivt bör skrivreglerna för newrgn- och freergn-deklarationer lägga till och ta bort kapacitet för lämplig region. Naiva skrivregler kan vara: Denna funktion är välformad enligt den naiva skrivregeln: Funktionen börjar med förmågan {pi,pz} och pi tas bort av freergn-deklarationen, vilket lämnar {pz}. Tuple y fördelas i pz, så projektionen är laglig. Denna kod är dock driftsmässigt felaktig om pi och pz omedelbart av samma region r. I så fall den första deklarationen friar r och den andra försök att läsa från r. Detta problem är ett bekant problem. För att frigöra en region på ett säkert sätt är det nödvändigt att radera alla kopior av kapaciteten. Instantiella regionvariabler kan dock skapa alias, vilket gör det omöjligt att genom kontroll avgöra om det finns några kopior. Vi önskar ett system för aliaskontroll som lätt kan genomdrivas av typsystemet, utan dyra och komplexa programanalyser. En möjlighet är ett linjärt typsystem [12, 37, 381. I ett linjärt typsystem skulle aliaset vara trivialt kontrollerat; varje användning av ett regionnamn skulle förbruka det namnet och se till att det inte kunde användas någon annanstans. I ett linjärt system skulle därför de naiva reglerna för fördelning och fördelning av regioner vara sunda. Tyvärr är ett linjärt system alltför restriktivt för att tillåta många användbara program. Anta till exempel att f har typ V[pl:Rgn, pz:Rgn]. Klockan två. .) + 0 vid d och vi och w2 är heltal tuples fördelade i samma region r. Då kunde f inte kallas med vi och 2) ~ som argument, eftersom det skulle kräva omedelbar pl och pa med samma region. Mer allmänt kunde man inte skriva någon funktion som kräver två argument som skulle kunna eller inte skulle kunna fördelas i samma region. Metoder baserade på syntaktisk kontroll av interferens [30, 311 är mer eftergivna än ett linjärt system, men är fortfarande alltför restriktiva för våra syften; det är fortfarande omöjligt att direktiera flera argument med samma region. 265 Vårt tillvägagångssätt, i stället för att försöka förhindra alias, är att använda typsystemet för att spåra alias. Mer exakt, vi spårar non-aliasing, det vill säga unikhet. Vi gör detta genom att märka regioner med en av två multiplikatorer när de bildar en förmåga. Den första formen, {r+}, är förmågan att komma åt region r som det har förståtts hittills. Den andra formen, {ri}, tillåter också tillgång till region P, men lägger till ytterligare information som P är unik; det vill säga r representerar en annan region än någon annan region som visas i en förmåga som bildas med {r'}. Till exempel indikerar förmågan {r,', ri} inte bara att det är tillåtet att komma åt ri och rz, men också att ri och ~2 representerar olika regioner. Eftersom {r'} garanterar att r inte visas någon annanstans i en förmåga som bildas med hjälp av den, det är förmågan, inte bara att komma åt r, men också att fri r. Således kan vi skriva region deallocation med regeln: Observera att anslutningsmöjligheter är bara idempotent när kapaciteterna i fråga innehåller inga unika multipliciteter. Till exempel, kapaciteterna {r+} och {r+, r+} är likvärdiga, men kapaciteterna {r'} och {r',r'} är inte; den senare kapaciteten ( {r', r'}) hävdar att r är skild från sig själv och följaktligen att senare förmåga aldrig kan tillfredsställas. Reglerna för kapacitetslikvärdighet finns i bilaga A. När C är likvärdigt med C@C, säger vi att C är duplicatable. Observera att kapacitetsvariabler är oupplösliga, eftersom de kan stå för alla funktioner, inklusive oupplösliga. Ibland förhindrar detta skrivandet av önskade program, så vi ger en strippa operatör C som ersätter alla 1 multipliciteter i C med + multipliciteter. Till exempel {r:,rz} = {rt,r,'}. För alla funktioner C är kapaciteten c duplicerbar. När program behöver en okänd men duplicerbar förmåga, kan de använda en borttagen variabel 7. Kapaciteterna {r'} och {r+} är inte desamma, men den förra bör tillhandahålla alla privilegier för den senare. Vi säger därför att det förra är en subcapability av det senare och skriver {r'} 5 {r+}. I det kompletta systemet ändras de olika reglerna i avsnitt 2.2 för att ta hänsyn till delkapaciteter. Till exempel, funktion anropsregeln blir: Om vi har kapacitet {r+}, kan vi kalla f b ating pi och p2 med r, eftersom {r+} = {r+,r P instanti-}. Med hjälp av subcapability relationen, kan vi också ringa f när vi håller {rl}, igen genom att direktiating pi och p2 med r, sedan {r'} 5 {r+} = {P+,r+}. Subcapability relationen står endast för glömska av unikhet information. Intuitivt kan det finnas en andra källa till underkapacitet, de som genereras av att glömma en hel förmåga. Till exempel verkar {rt,r$} tillhandahålla alla privilegier {rt}, så det är rimligt att anta att {r;',r,'} är subkapabilitet för {r;'}. I själva verket kan man konstruera en ljud Capability Calculus införliva denna axiom, men vi utelämnar det eftersom gör det möjligt för oss att ange minneshantering skyldigheter och att bevisa en starkare egenskap om rymdanvändning. Man kan skriva en funktion som kan kallas med extra kapacitet med hjälp av en kapacitetsvariabel, som diskuteras i avsnitt 2.2. Genom att utelämna axiom Cl @ C2 5 Ci, kan vårt typsystem formellt ange vem som har ansvar för att befria en region. Underlåtenhet att följa informella konventioner är en vanlig källa till buggar i språk (såsom C) som använder manuell minneshantering. Vårt typsystem utesluter sådana buggar. Tänk till exempel på typen: ({pi} @ e, p handtag, (E) -+ 0 at r') + 0 at r I vårt system e @ {p'} f E. Följaktligen, innan någon funktion med denna typ kan återvända (dvs. ringa fortsättning av typ (E) + 0 at r), måste det vidta åtgärder för att uppfylla kapaciteten E, det vill säga det måste fri p. I allmänhet, vårt typsystem förhindrar "region läckor": program måste returnera alla minnesresurser till operativsystemet innan de slutar (Theorem 2.4). Operativsystemet behöver inte städa upp efter ett program stannar. I skrivregeln för stopp anges att inga resurser får hållas kvar, och eftersom kapacitet inte får glömmas bort innebär detta att alla regioner måste ha befriats.  Det system som presenteras för denna punkt är sunt, men det är ännu inte tillräckligt för att sammanställa verkliga källspråk. Vi måste kunna återvinna unikhet efter att ett regionnamn har kopierats. För att se varför, anta att vi har förmågan {r') och f har typ: Pa, * * * 9 ( {pt,pt},. ..) + 0 at r') + 0 at r" Vi skulle vilja kunna instantera pl och p2 med r (vilket vi kan göra, sedan {r'} 5 {r+,r+}), och sedan fri r när f kallar fortsättning i sitt slutliga argument. Unforyftel? fortsätta endast poss; bedömer förmågan {r,r} - {r+}, inte förmågan {r } nödvändig för att frigöra r. Det hjälper inte att stärka kapaciteten för fortsättning till (till exempel) {pi}, eftersom då f kanske inte kallar det. Vi kan återvinna unik information genom att kvantifiera en kapacitetsvariabel. Antag att vi återigen har förmåga {r'} och g har typ: V[pi:Rgn, pz:Rgn, e:Cap].(e,. ... (E.............................................................. .) + 0 vid T') + 0 vid r" Vi kan omedelbart e med {r'} och sedan fortsätter kommer att ha samma förmåga, vilket gör det möjligt att fri r. Tyvärr har kroppen av funktion g inte längre möjlighet att komma åt pl och ~2, eftersom dess typ drar ingen koppling mellan dem och E. Vi löser detta problem genom att använda avgränsad kvantifiering för att relatera pi, pr och e. Antag att h har typ: V[~l:~,Ggn,c 5 {P:,P;)]. - E. - Vad är det för fel på dig? ... (E. ..) + 0 at r ) + 0 at r" Om vi har förmåga {r'}, kan vi kalla h genom att instantera pi och pz med r och instantiering c med r'}. Denna indikering är tillåten eftersom {r'} 5 {r i,r+J. Som med g, den fortsatta kommer att ha förmågan {r }, tillåter det att fri r, men kroppen av h (som den av f) kommer att ha möjlighet att komma åt pi och pa, sedan e 5 {pt,pt}. Gränsad kvantifiering löser problemet genom att avslöja viss information om en förmåga e, samtidigt som den fortfarande kräver att funktionen ska vara parametrisk över E. Därför, när funktionen kallar sin fortsättning vi återfår den starkare kapaciteten (till fri r), även om denna förmåga tillfälligt dold för att duplicera T. Mer allmänt, begränsad kvantifiering kan vi dölja vissa privilegier när vi kallar en funktion, och återfå dessa privilegier i dess fortsättning. Därför stöder vi statiskt kontrollerbar dämpning och förstärkning av kapaciteten. 2.4 De viktigaste egenskaperna hos Capability Calculus är Type Soundness och Complete Collection. Var och en kan bevisas från de formella semantiken i bilaga A. Typ Soundness säger att vi aldrig kommer in i ett fast tillstånd under genomförandet av ett välskrivet program. Ett tillstånd (M,e) är fast om det inte finns (M', e') sådan att (M,e) e (M',e') och e inte stannar i. Till exempel fastnar ett tillstånd som försöker projicera ett värde från en tuple som inte visas i minnet. Theorem Beviset på sundhet är enkelt, att använda sig av standard Subject Reduction och Progress lemmas. Framsteg visar att väldefinierade tillstånd inte sitter fast, och Subject Reduction uppger att utvärderingsstegen bevarar välutformadhet. Lemma 2 (Subject Reduction) Ift-(M,e) och (M,e) w (M',e') sedan F (M',e') Lemma 3 (Progress) Ift-(M,e) sedan antingen: 1. Det finns (M',e') sådana att (M,e) c-) (M',e), eller The Complete Collection egenskap garanterar att välskrivna avslutande program returnerar alla sina minnesresurser till systemet innan de stannar. Genom Subject Reduction och Progress, avslutande program slutar i välformade maskintillstånd (M, stopp i). Skrivregeln för stopputtrycket kräver att kapaciteten C är tom. Med hjälp av detta faktum kan vi dra slutsatsen att minnet M inte innehåller några regioner. Vårt arbete ger ett typsystem för att kontrollera regionannoterade program för säkerhet, men vi tillhandahåller inga nya tekniker för att bestämma dessa annoteringar. I stället förlitar vi oss på befintliga regionslutsatser [34, l] för att dra slutsatsen om lämpliga regionanteckningar. I detta avsnitt illustrerar vi hur en variant av språket Tofte-Talpin kan översättas till Capability Calculus. Översättningen formaliseras i den tekniska rapporten [5]. Genom att komponera Tofte och Birkedals regioninferensalgoritm [34] med denna översättning har vi ett sätt att sammanställa språk på hög nivå till Capability Calculus. Vårt exempel anser att en funktion räknas ner till noll. För att ha intressant tilldelning beteende heltal inblandade i räkningen boxas, och därmed fördelas i en region.  Räkna funktionen lagras i region pl och tar två argument, ett handtag för region p och en ruta heltal x tilldelas i region p. Om x är nonzero, räkna minskningar det, lagra resultatet igen i p, och återkommer. Funktionen har två effekter: en läsning på pl, till följd av den rekursiva anrop, och en läs/skriv effekt på p, till följd av rad l läs och rad 2 butik. Därför ger vi funktionen räkna effekten (acce88 (PI), access (pz)}. Operativt tjänar kommandot letregion ett syfte som liknar ett par newrgn- och freergn-deklarationer. En ny region tilldelas i början av hyresregionblocket och fördelas automatiskt i slutet av blocket, vilket resulterar i ett stackliknande fördelningsmönster (LIFO). Därför, koden ovan allokerar två regioner (pl och pz), butiker räknas i pl, lagrar ett boxat heltal i pz, samtal räknas, och sedan deallocates pl och pa. Översättningen av detta program till Capability Calculus omskriver det i fortsättning-passing stil, och omvandlar effekter information till kapacitetskrav. En av de viktigaste uppgifterna för översättningen är sammanställningen av letregion block i nevrgn och freergn deklarationer. Det resulterande programmet visas nedan. För tydlighetens skull har vi på ett par sätt förenklat det faktiska resultatet av den formella översättningen. Det översatta programmet börjar med att fördela regioner pi och ps, och också allokerar en tredje region ps för att hålla räkningens fortsättning. Räkna funktionen kräver en förmåga E minst lika bra som den förmåga {p~,p+,p~,t} som behövs för att komma åt sig själv, dess argument och dess fortsättning; och den för vidare samma förmåga E till dess fortsättning. Fortsättningen kräver förmågan {p:,p:,p:,p:} för att befria de tre regionerna. Därför är E omedelbar med den starkare förmåga som krävs för fortsättningen. Kraften i avgränsad kvantifiering kommer in i bilden när en funktion kallas med flera regioner, av vilka en del kan vara eller kanske inte är densamma. Till exempel kan exemplet ovan skrivas om till att ha tio och kan inte dela en region, utan att ändra koden för räkning på något sätt:%% räkna vith tio och kant dela ps låt newrgn pr,xP1 i låt neurgn p2,xPz i % kapacitet som hålls är {p:,pi} låt räkna =. .. som tidigare. .. låt tio = (10) vid xP2 in låt cant = 0 (G,P:}).... I xp2 i antal IPZ, ~2~ ipi, piI1 (xp2, tio, kant) I detta exempel är pcont omedelbar med,os och E omedelbart med {pt, pt} (som återigen är den förmåga som krävs av cant). Räkna fortsätter dock precis som tidigare eftersom c fortfarande är lika bra som {pf,p+,pL,t) (sedan tp:, P:) 5 {PL P,'> = MY Pzs, Pz+D I exemplen ovan, även om räkningen är svansrekursiv, allokerar vi en ny cell varje gång runt slingan och vi deallokerar inte någon av cellerna förrän räkningen är klar. Men eftersom p aldrig innehåller några andra levande värden än det nuvarande argumentet, är det säkert att minska programmets rymdanvändning genom att deallokera argumentets region varje gång runt slingan, som visas nedan. Observera att denna optimering inte är möjlig när regionens livstider måste vara lexiskt avgränsade. XVI räkna med effektiv minnesanvändning låt newrgn pi,xPl in låt newrgn pz, xP2 in låt newrgn ps,xP3 i % kapacitet innehas är {p:,p:,p:} låt räkna = (fix räkna [pz, ~3, {pi, piller (xP2, tio, kant) För att deallocate sitt argument, den reviderade räkningen kräver en unik förmåga för sitt argument region p. Observera att om programmet skrevs om igen så att tio och kant delade en region (som skulle leda till en körtid fel, eftersom tio delas tidigt), skulle programmet inte längre typkontroll, eftersom {pi, pi} g {p;',p$, pi}. Programmet skrivs dock om så att räkna och inte dela en region misslyckas inte på körtid, och gör typkontroll, eftersom {P:> PiI I {P;", PL PiI. Vi anser att den allmänna ramen för vårt kapacitetssystem är ganska robust. Det finns flera sätt att utvidga språket och ett antal riktningar för framtida forskning. 4.1 Huvudsyftet med detta arbete var att utveckla ett språk med låg typsäkerhet som ger kompilatorer och programmerare kontroll över allokering och fördelning av data. Det språk som vi har beskrivit hittills är relativt hög nivå eftersom det inkluderar abstrakta stängningar och hög-268 nivå operationer såsom atomal allokering och initiering av data. I den kompletterande tekniska rapporten [5] visar vi att kapacitetskonstruktioner samverkar välvilligt med den process för typbevarande sammanställning som beskrivs av Morrisett et al. [24] och vi använder de tekniker som beskrivs i detta dokument för att ändra deras maskinskrivna monteringsspråk för att tillåta explicit deallocation av datastrukturer. I detta dokument har vi koncentrerat oss på att använda Capability Calculus för att implementera säker deallocation av minne, men med några ändringar, tror vi att vår kapacitetsapparat kan användas i en mängd andra inställningar också. En potentiell tillämpning innebär att minska omkostnaderna för kommunikation över användar-kärnan adress rymdgräns i traditionella operativsystem. I sådana system, när data i användarutrymme presenteras för kärnan, måste kärnan kopiera data för att säkerställa att dess integritet bevaras. Men om en användare behandlar en unik förmåga för en region till kärnan, behöver kärnan inte kopiera regionens data; utan förmågan kan användaren inte längre läsa eller ändra innehållet i den regionen. Kapaciteter kan också användas för att säkerställa ömsesidigt uteslutande tillgång till delade muterbara data i en flertrådig miljö, genom att betrakta slussar som jämförbara med regioner. Om vi associerar varje del av känsliga data med ett lås, kan vi statiskt kontrollera att varje kund till känsliga data får motsvarande lås och tillhörande kapacitet innan du får tillgång till dessa data. När koden släpper låset, vi återkallar kapaciteten på data, precis som vi återkallar en förmåga när vi befriar en region. Närhelst ett system vill begränsa tillgången till vissa data statiskt, och/eller för att säkerställa att en viss sekvens av operationer utförs, kan det i allmänhet överväga att använda kapacitet för att kontrollera att lämpliga invarianter upprätthålls. 4.2 Capability Calculus härstammar från Giffords och Lucasens arbete med typ- och effektsystem [ll, 201 och den efterföljande studien av många andra [16, 33, 36, 341]. Förhållandet mellan effekter och förmåga är ganska nära. En nödvändig förutsättning för att använda något av systemen är typinferens, som utförs av en programmerare eller kompilator, och en stor del av forskningen om effektsystem har koncentrerats på denna svåra uppgift. På grund av fokus på inferens, är effektsystem vanligtvis formulerade som en bottom-up syntes av effekter. Vårt arbete kan betraktas som ett verifierbart bevis på att en slutsats är riktig. Därför, medan effektsystem vanligtvis fungerar nedifrån och upp, specificerar effekterna som kan uppstå, vi tar en top-down strategi, specificerar med hjälp av kapacitet de effekter som tillåts uppstå. Att lägga till aliasinformation till vår kapacitet skiljer dem också från tidigare arbete med effektsystem. Kapaciteten uttrycker dock endast de enklaste aliasrelationerna: en region är antingen helt oaliaserad eller också kan den aliasera vilken annan region som helst. Våra förmågor avslöjar väldigt lite av butikens struktur. Ett antal andra forskare [lo, 7, 321 har studerat statiska analyser som innehåller former av datastrukturer och alias mellan dem. Vi planerar att undersöka hur dessa finkorniga minnesmodeller kan användas för att öka flexibiliteten i vårt typsystem. En koppling kan också dras mellan kapaciteter och monadiska typsystem. Arbete med effekter på monader [21, 28, 18, 81] har betraktat effektfulla funktioner som rena funktioner som återställer statstransformatorer. Detta kan kallas en ex post vy: effekten sker efter funktionens utförande. Däremot ser vi på förhand att förmågan att utföra den relevanta effekten måste vara tillfredsställd före funktionens utförande. Ändå finns det stor likhet mellan åsikterna; precis som monadlagarna ser till att butiken är enkeltrådad genom en beräkning, våra skrivregler tråd en förmåga (som sammanfattar aspekter av butiken) längs verkställandet av ett program. Erfarenheten av Birkedal et al. [4] med ML Kit region kompilatorn visar att det finns många förbättringar i det grundläggande systemet som kommer att vara nödvändigt för att göra vår Capability Calculus ett praktiskt mellanspråk. I synnerhet fann Birkedal att fördelningen ofta sker i två olika sammanhang: ett sammanhang där inga levande föremål finns kvar i regionen och ett andra sammanhang där det kan finnas levande föremål kvar i regionen. För att undvika kod dubblering och ändå säkerställa effektiv rymdanvändning, kontrollerar de på körtid för att ta reda på vilken situation som har uppstått. I det förra fallet återställer de regionen (deallokera och omfördela i vår formalism) och i det senare fallet återställs de inte utan fortsätter att fördela på toppen av regionen. Det typsystem vi presenterar här är inte tillräckligt kraftfullt för att koda dessa lagrings-mode polymorphic operationer. I själva verket måste den förfinas på två sätt. För det första kräver denna optimering finergrared aliasing specifikationer som deklarerar en region p inte alias någon särskild region p' men kan alias andra regioner. För det andra, efter att vi dynamiskt har kontrollerat vilka av de två sammanhangen ovan vi befinner oss i, måste vi förfina vår förmåga. Harper och Morrisetts typecase [13]-mekanism utvecklad för TIL-kompilatorn och ytterligare förfinad av Crary et al. [6] möjliggör den typ av typförfining som krävs här. Aiken m.fl. [l] har också studerat hur man kan optimera det ursprungliga ramverket för regionen Tofte-Talpin och de gör det också möjligt att fördela regionerna självständigt. Dessutom skiljer deras system namnet på en region från dess fördelning. Vårt språk, som presenterats, gör inte en sådan åtskillnad, men det är enkelt att lägga till en. Med en sådan mekanism på plats, antar vi, baserat på ljudstyrka bevis för Aiken et al.'s analyser, att dessa analyser kan användas för att producera typ korrekt kod i Capability Calculus. Gay och Aiken [9] har utvecklat en säker regionimplementering som ger programmerare kontroll över regionallokering och deallocation. De använder referensräkning för att garantera säkerheten. Hawblitzel och von Eicken [15] har också använt begreppet region i sitt språkpass för att stödja delning och återkallande mellan flera skyddsområden. Båda dessa grupper använder körtidskontroll för att garantera säkerheten och det skulle vara intressant att undersöka hybridsystem som kombinerar funktioner i vårt statiska typsystem med mer dynamiska system. Vi har presenterat ett nytt starkt skrivspråk som medger verksamhet för explicit tilldelning och fördelning av datastrukturer. Dessutom är detta språk tillräckligt uttrycksfullt för att tjäna som mål för en regional slutsats och kan sammanställas till ett maskinskrivet monteringsspråk. Vi anser att begreppet kapacitet som stöder statiskt kontrollerbar dämpning, förstärkning och återkallande är ett effektivt nytt verktyg för språkdesigners.
Analysen av kapaciteter REF var den första kalkylen för att ge säker explicit minnesdeallokering samtidigt som dingla pekare.
Typed memory management in a calculus of capabilities
{'venue': "POPL '99", 'journal': None, 'mag_field_of_study': ['Computer Science']}