Understruktursystem - Substructural type system
| Typsystem |
|---|
| Allmänna begrepp |
| Stora kategorier |
|
| Mindre kategorier |
Substrukturella typsystem är en familj av typsystem som är analoga med substrukturella logiker där en eller flera av strukturreglerna saknas eller endast tillåts under kontrollerade omständigheter. Sådana system är användbara för att begränsa åtkomsten till systemresurser som filer , lås och minne genom att hålla reda på tillståndsändringar som inträffar och förhindra ogiltiga tillstånd.
Olika system av substrukturell typ
Flera typsystem har uppstått genom att kasta bort några av de strukturella reglerna för utbyte, försvagning och sammandragning:
| Utbyta | Försvagning | Kontraktion | Använda sig av | |
|---|---|---|---|---|
| Beställde | - | - | - | Exakt en gång i ordning |
| Linjär | Tillåten | - | - | Exakt en gång |
| Affinera | Tillåten | Tillåten | - | Högst en gång |
| Relevant | Tillåten | - | Tillåten | Åtminstone en gång |
| Vanligt | Tillåten | Tillåten | Tillåten | Godtyckligt |
- Ordnade typsystem (kassera utbyte, försvagning och kontraktion): Varje variabel används exakt en gång i den ordning den introducerades.
- Linjära system (tillåter utbyte, men varken försvagning eller kontraktion): Varje variabel används exakt en gång.
- Affinesystem (tillåta utbyte och försvagning, men inte sammandragning): Varje variabel används högst en gång.
- Relevanta typsystem (tillåter utbyte och kontraktion, men inte försvagning): Varje variabel används minst en gång.
- Normaltypssystem (tillåter utbyte, försvagning och kontraktion): Varje variabel kan användas godtyckligt.
Förklaringen till system av affin typ förstås bäst om den omformuleras som "varje förekomst av en variabel används högst en gång".
Beställt typsystem
Beställda typer motsvarar icke -kommutativ logik där utbyte, kontraktion och försvagning kasseras. Detta kan användas för att modellera stapelbaserad minnesallokering (kontrast med linjära typer som kan användas för att modellera högbaserad minnesallokering). Utan utbytesegenskapen får ett objekt endast användas när det ligger överst i den modellerade stacken, varefter det hoppar av vilket resulterar i att varje variabel används exakt en gång i den ordning den introducerades.
Linjära system
Linjära typer motsvarar linjär logik och säkerställer att objekt används exakt en gång, så att systemet säkert kan lokalisera ett objekt efter dess användning.
De rena programmeringsspråk utnyttjar unik typer (en variant av linjära typer) för att stödja samtidighet, input / output och på plats uppdatering av matriser.
Linjära system tillåter referenser men inte alias . För att genomdriva detta går en referens utanför tillämpningsområdet efter att den visas på höger sida av en uppgift , vilket säkerställer att endast en referens till något objekt existerar samtidigt. Observera att överföring av en referens som ett argument till en funktion är en form av tilldelning, eftersom funktionsparametern kommer att tilldelas värdet inuti funktionen, och därför får en sådan användning av en referens också att den går utanför tillämpningsområdet.
Ett system av linjär typ liknar C ++ s unika_ptr -klass , som beter sig som en pekare men bara kan flyttas (dvs inte kopieras) i en uppgift. Även om linjäritetsbegränsningen kontrolleras vid kompileringstid , orsakar dereferencing av ett ogiltigt unique_ptr odefinierat beteende vid körning .
Enreferensegenskapen gör system av linjär typ lämpliga som programmeringsspråk för kvantberäkning , eftersom den återspeglar kvanttillståndens icke-klonande sats . Ur kategoriteorins synvinkel är icke-kloning ett påstående om att det inte finns någon diagonal funktion som kan duplicera tillstånd; på samma sätt, från kombinatorns synvinkel, finns det ingen K-kombinator som kan förstöra tillstånd. Ur lambda calculus synvinkel kan en variabel x visas exakt en gång i en term.
Linjära typsystem är det interna språket i slutna symmetriska monoidala kategorier , ungefär på samma sätt som helt enkelt skrivna lambda -kalkyl är språket för kartesiska slutna kategorier . Mer exakt kan man konstruera funktioner mellan kategorin linjära typsystem och kategorin slutna symmetriska monoidala kategorier.
Affine -typsystem
Affintyper är en version av linjära typer som gör det möjligt att kassera (dvs inte använda ) en resurs, motsvarande affin logik . En affin resurs kan användas högst en gång, medan en linjär måste användas exakt en gång.
Relevant typsystem
Relevanta typer motsvarar relevant logik som möjliggör utbyte och sammandragning, men inte försvagning, vilket innebär att varje variabel används minst en gång.
Programmeringsspråk
Följande programmeringsspråk stöder linjära eller affina typer:
Se även
Anteckningar
Referenser
- Walker, David (2002). "Substrukturala typsystem". I Pierce, Benjamin C. (red.). Avancerade ämnen i typer och programmeringsspråk (PDF) . MIT Press. s. 3–43. ISBN 0-262-16228-8.
