Onderconstructie type systeem - Substructural type system
| Type systemen |
|---|
| Algemene concepten |
| Hoofdcategorieën |
|
| Kleine categorieën |
Substructurele typesystemen zijn een familie van typesystemen analoog aan substructurele logica's waar een of meer van de structurele regels ontbreken of alleen zijn toegestaan onder gecontroleerde omstandigheden. Dergelijke systemen zijn handig om de toegang tot systeembronnen zoals bestanden , vergrendelingen en geheugen te beperken door statusveranderingen bij te houden en ongeldige statussen te voorkomen.
Verschillende substructurele typesystemen
Er zijn verschillende typesystemen ontstaan door enkele van de structurele regels van uitwisseling, verzwakking en contractie te negeren :
| Aandelenbeurs | Verzwakking | samentrekking | Gebruik maken van | |
|---|---|---|---|---|
| Besteld | — | — | — | Precies één keer in bestelling |
| Lineair | Toegestaan | — | — | Precies één keer |
| Affine | Toegestaan | Toegestaan | — | Maximaal één keer |
| Relevant | Toegestaan | — | Toegestaan | Ten minste een keer |
| normaal | Toegestaan | Toegestaan | Toegestaan | Willekeurig |
- Systemen van het geordende type (wissel, verzwakking en contractie weggooien): Elke variabele wordt precies één keer gebruikt in de volgorde waarin deze is ingevoerd.
- Lineaire systemen (laten uitwisseling toe, maar verzwakking of contractie niet): Elke variabele wordt precies één keer gebruikt.
- Systemen van het affiene type (laat uitwisseling en verzwakking toe, maar geen contractie): Elke variabele wordt maximaal één keer gebruikt.
- Relevante typesystemen (laat uitwisseling en contractie toe, maar niet verzwakking): Elke variabele wordt minstens één keer gebruikt.
- Normale typesystemen (laat uitwisseling, verzwakking en samentrekking toe): Elke variabele kan willekeurig worden gebruikt.
De verklaring voor systemen van het affiene type wordt het best begrepen als ze opnieuw wordt geformuleerd als "elk voorkomen van een variabele wordt maximaal één keer gebruikt".
Besteld type systeem
Geordende typen komen overeen met niet-commutatieve logica waarbij uitwisseling, samentrekking en verzwakking worden weggegooid. Dit kan worden gebruikt om op stapels gebaseerde geheugentoewijzing te modelleren (in tegenstelling tot lineaire typen die kunnen worden gebruikt om op heap gebaseerde geheugentoewijzing te modelleren). Zonder de exchange-eigenschap mag een object alleen worden gebruikt als het bovenaan de gemodelleerde stapel staat, waarna het wordt verwijderd, waardoor elke variabele precies één keer wordt gebruikt in de volgorde waarin deze is geïntroduceerd.
Lineaire type systemen
Lineaire typen komen overeen met lineaire logica en zorgen ervoor dat objecten precies één keer worden gebruikt, waardoor het systeem de toewijzing van een object na gebruik veilig kan ongedaan maken.
De programmeertaal Clean maakt gebruik van uniciteitstypen (een variant van lineaire typen) om gelijktijdigheid, invoer/uitvoer en in-place update van arrays te ondersteunen.
Lineaire systemen laten verwijzingen toe, maar geen aliassen . Om dit af te dwingen, valt een verwijzing buiten het bereik nadat deze aan de rechterkant van een opdracht is verschenen , waardoor er slechts één verwijzing naar een object tegelijk bestaat. Merk op dat het doorgeven van een verwijzing als argument aan een functie een vorm van toewijzing is, aangezien de functieparameter de waarde binnen de functie zal krijgen, en daarom zorgt het gebruik van een verwijzing er ook voor dat deze buiten het bereik valt.
Een lineair systeem is vergelijkbaar met de klasse unique_ptr van C++ , die zich als een aanwijzer gedraagt, maar alleen kan worden verplaatst (dwz niet gekopieerd) in een opdracht. Hoewel de lineariteitsbeperking tijdens het compileren wordt gecontroleerd , veroorzaakt het verwijderen van een ongeldige unique_ptr tijdens runtime ongedefinieerd gedrag .
De eigenschap met één referentie maakt systemen van het lineaire type geschikt als programmeertalen voor kwantumberekening , omdat het de stelling van kwantumtoestanden weerspiegelt die niet kunnen worden gekloond . Vanuit het oogpunt van de categorietheorie is niet-klonen een verklaring dat er geen diagonale functor is die toestanden zou kunnen dupliceren; evenzo is er vanuit het oogpunt van de combinator geen K-combinator die staten kan vernietigen. Vanuit het oogpunt van lambda-calculus kan een variabele x precies één keer in een term voorkomen.
Lineaire typesystemen zijn de interne taal van gesloten symmetrische monoïdale categorieën , ongeveer op dezelfde manier als eenvoudig getypte lambda-calculus de taal is van Cartesiaanse gesloten categorieën . Meer precies, men kan functoren construeren tussen de categorie van lineaire typesystemen en de categorie van gesloten symmetrische monoïdale categorieën.
Affine type systemen
Affine typen zijn een versie van lineaire typen die het mogelijk maken om een resource te negeren (dwz niet te gebruiken ), overeenkomend met affiene logica . Een affiene hulpbron kan maximaal één keer worden gebruikt , terwijl een lineaire hulpbron precies één keer moet worden gebruikt .
Relevant type systeem
Relevante typen komen overeen met relevante logica die uitwisseling en samentrekking mogelijk maakt, maar niet verzwakking, wat betekent dat elke variabele minstens één keer wordt gebruikt.
Programmeertalen
De volgende programmeertalen ondersteunen lineaire of affiene typen:
Zie ook
Opmerkingen:
Referenties
- Walker, David (2002). "Substructurele Type Systems". In Pierce, Benjamin C. (red.). Geavanceerde onderwerpen in typen en programmeertalen (PDF) . MIT Pers. blz. 3-43. ISBN 0-262-16228-8.
