Ett typsystem är en uppsättning regler i programmeringsspråk som tilldelar egenskaper, kallade typer , till de olika konstruktionerna som utgör ett program , såsom variabler , uttryck , funktioner eller moduler . Typsystemets huvudsakliga roll är att minska antalet buggar i program [1] genom att definiera gränssnitt mellan olika delar av programmet och sedan kontrollera konsistensen i samspelet mellan dessa delar. Denna kontroll kan ske statiskt ( vid kompileringstid ) eller dynamiskt ( vid körning) och även vara en kombination av båda.
Enligt Pierce är typsystemet en avgörbar syntaktisk metod för att bevisa frånvaron av vissa programbeteenden genom att klassificera konstruktioner enligt de typer av beräknade värden [2] .
Ett exempel på ett enkelt typsystem kan ses i C -språket . Delar av ett C-program skrivs som funktionsdefinitioner . Funktioner kallar varandra. Gränssnittet för en funktion anger namnet på funktionen och en lista över värden som skickas till dess kropp. Den anropande funktionen postulerar namnet på funktionen den vill anropa och namnen på variablerna som håller de värden den vill passera. Under programexekveringen placeras värden i tillfällig lagring och sedan skickas exekveringen till kroppen av den anropade funktionen. Den anropade funktionskoden kommer åt och använder värdena. Om instruktionerna i kroppen av en funktion är skrivna med antagandet att ett heltalsvärde ska skickas till dem för bearbetning, men den anropande koden passerade ett flyttal, kommer den anropade funktionen att utvärdera fel resultat. C-kompilatorn kontrollerar de definierade typerna för varje variabel som skickas mot de typer som definieras för varje variabel i gränssnittet för den anropade funktionen. Om typerna inte matchar genererar kompilatorn ett kompileringsfel.
Tekniskt sett tilldelar typsystemet en typ till varje beräknat värde och försöker sedan, genom att hålla reda på sekvensen av dessa beräkningar, kontrollera eller bevisa att det inte finns några typmatchningsfel . Det specifika typsystemet kan avgöra vad som orsakar ett fel, men vanligtvis är målet att förhindra operationer som antar vissa egenskaper hos deras parametrar från att ta emot parametrar som dessa operationer inte är meningsfulla för – att förhindra logiska fel . Dessutom förhindrar det också minnesadressfel .
Typsystem definieras vanligtvis som en del av programmeringsspråk och är inbyggda i deras tolkar och kompilatorer. Språkets typsystem kan dock utökas med specialverktyg som utför ytterligare kontroller baserat på den ursprungliga skrivsyntaxen i språket.
Kompilatorn kan också använda en statisk värdetyp för att optimera lagring och för att välja en algoritmisk implementering av operationer på det värdet. Till exempel, i många C-kompilatorer representeras en typ float av 32 bitar, enligt IEEE-specifikationen för flyttalsoperationer med enkel precision . Baserat på detta kommer en speciell uppsättning mikroprocessorinstruktioner att användas för värden av denna typ (addition, multiplikation och andra operationer).
Antalet restriktioner som läggs på typer och hur de beräknas avgör hur språket skrivs. Dessutom, i fallet med typen polymorfism , kan språket också specificera för varje typ driften av olika specifika algoritmer. Studiet av typsystem är teorin om typer , även om i praktiken ett visst typsystem av ett programmeringsspråk är baserat på funktionerna i datorarkitekturen, implementeringen av kompilatorn och den allmänna bilden av språket.
Den formella motiveringen för typsystem är typteori . Ett programmeringsspråk inkluderar ett typsystem för att utföra typkontroll vid kompileringstid eller vid körning , som kräver explicita typdeklarationer eller sluter sig till dem på egen hand. Mark Manasse formulerade problemet på följande sätt [3] :
Huvudproblemet som typteorin löser är att se till att programmen är vettiga. Det största problemet med typteori är att meningsfulla program kanske inte beter sig som avsett. Konsekvensen av denna spänning är sökandet efter mer kraftfulla typsystem.
Originaltext (engelska)[ visaDölj] Det grundläggande problemet som en typteori tar upp är att säkerställa att program har mening. Det grundläggande som orsakas av en typteori är att meningsfulla program kanske inte tillskrivs problembetydelser. Strävan efter system av rikare typ är resultatet av denna spänning. — Mark Massey [3]Typtilldelningsoperationen, som kallas typing, ger mening åt strängar av bitar , såsom ett värde i datorns minne , eller objekt , såsom en variabel . Datorn har inget sätt att skilja till exempel en adress i minnet från en kodinstruktion eller ett tecken från ett heltal eller flyttal , eftersom bitsträngarna som representerar dessa olika betydelser inte har några uppenbara egenskaper som gör att man kan göra antaganden om deras innebörd. Att tilldela typbitar till strängar ger denna förståelighet, vilket gör den programmerbara hårdvaran till ett teckensystem som består av den hårdvaran och mjukvaran.
Processen med typkontroll och begränsning - typkontroll eller typkontroll - kan göras antingen vid kompileringstid statisk typning) eller vid körning (dynamisk typning). Mellanlösningar är också möjliga (jfr sekventiell typning ).
Om språkspecifikationen kräver att skrivreglerna är strikt implementerade (det vill säga tillåter i en eller annan grad endast de automatiska typkonverteringarna som inte förlorar information), kallas ett sådant språk starkt skrivna ; ) , annars svagt skrivna . Dessa termer är villkorade och används inte i formella motiveringar.
Ett språk kallas typat om specifikationen för varje operation definierar de datatyper som denna operation kan tillämpas på, vilket innebär att den inte är tillämplig på andra typer [4] . Till exempel är data som " denna citerade text " representerar av typen " строка". I de flesta programmeringsspråk är det inte meningsfullt att dividera ett nummer med en sträng, och de flesta moderna språk kommer att avvisa ett program som försöker utföra en sådan operation. På vissa språk kommer en meningslös operation att upptäckas under kompilering ( statisk typning ), och avvisas av kompilatorn. I andra kommer det att upptäckas vid körning ( dynamisk typning ), vilket ger ett undantag .
Ett specialfall av maskinskrivna språk är entypsspråk ( eng. single-type language ), det vill säga språk med en enda typ. Dessa är vanligtvis skript- eller märkningsspråk , som REXX och SGML , vars enda datatyp är teckensträngen, som används för att representera både tecken och numeriska data.
Otypade språk, i motsats till maskinskrivna, låter dig utföra vilken operation som helst på vilken data som helst, som i dem representeras av kedjor av bitar av godtycklig längd [4] . De flesta assemblerspråk är otypade . Exempel på otypade högnivåspråk är BCPL , BLISS , Forth , Refal .
I praktiken kan få språk betraktas som maskinskrivna i termer av typteori (tillåter eller avvisar alla operationer), de flesta moderna språk erbjuder endast en viss grad av maskinskrivning [4] . Många industrispråk ger möjligheten att kringgå eller bryta typsystemet, vilket byter ut typsäkerhet för bättre kontroll över programexekveringen ( skrivordslek ).
Termen "polymorfism" hänvisar till kodens förmåga att köra på värden av många olika typer, eller förmågan hos olika instanser av samma datastruktur att innehålla element av olika typer. Vissa typsystem tillåter polymorfism att potentiellt förbättra kodåteranvändning : i språk med polymorfism behöver programmerare bara implementera datastrukturer som en lista eller en associativ array en gång, och behöver inte utveckla en implementering för varje typ av element de planerar att lagra strukturer. Av denna anledning hänvisar vissa datavetare ibland till användningen av vissa former av polymorfism som " generisk programmering ". Berättigandena för polymorfism ur typteoretisk synvinkel är praktiskt taget desamma som för abstraktion , modularitet och i vissa fall datasubtyping .
Ett antal specialtypsystem har utvecklats för användning under vissa förhållanden med viss data, samt för statisk analys av program. För det mesta är de baserade på idéerna om formell typteori och används endast som en del av forskningssystem.
Existentiella typer, det vill säga typer som definieras av en existentiell kvantifierare (existenskvantifierare) , är en inkapslingsmekanism på typnivå : det är en sammansatt typ som döljer implementeringen av någon typ i sin sammansättning.
Konceptet med en existentiell typ används ofta i samband med konceptet med en posttyp för att representera moduler och abstrakta datatyper , på grund av deras syfte att separera implementering från gränssnitt. Till exempel T = ∃X { a: X; f: (X → int); }beskriver en typ ett modulgränssnitt (familjer av moduler med samma signatur) som har ett datavärde av typen Xoch en funktion som tar en parameter av exakt samma typ Xoch returnerar ett heltal. Implementeringen kan vara annorlunda:
Båda typerna är undertyper av den mer generella existentiella typen Toch motsvarar konkret implementerade typer, så alla värden som tillhör någon av dem tillhör också typ T. Om t är ett värde av typ T, så t.f(t.a)klarar det typkontroll, oavsett vilken abstrakt typ den tillhör X. Detta ger flexibilitet när det gäller att välja de typer som är lämpliga för en viss implementering, eftersom externa användare endast kommer åt värdena för gränssnittstypen (existentiell) och är isolerade från dessa variationer.
I allmänhet kan typkonsistenskontrollen inte avgöra vilken existentiell typ en given modul tillhör. I exemplet ovan intT { a: int; f: (int → int); }kan det också ha typ ∃X { a: X; f: (int → int); }. Den enklaste lösningen är att explicit specificera för varje modul den underförstådda typen i den, till exempel:
Även om abstrakta datatyper och moduler har använts i programmeringsspråk under lång tid, byggdes en formell modell av existentiella typer inte förrän 1988 [5] . Teorin är en andra ordningens typad lambda-kalkyl som liknar System F , men med existentiell kvantifiering istället för universell kvantifiering .
Existentiella typer är explicit tillgängliga som en experimentell förlängning av Haskell-språket , där de är en speciell syntax som låter dig använda en typvariabel i en algebraisk typdefinition utan att flytta den till signaturen för en typkonstruktor , d.v.s. utan att öka dess aritet [ 6] . Java -språket tillhandahåller en begränsad form av existentiella typer genom jokertecknet . I språk som implementerar klassisk ML - stil let-polymorphism kan existentiella typer simuleras med hjälp av så kallade " typindexerade värden " [7] .
Många statiska typsystem, som de i C och Java, kräver en typdeklaration : programmeraren måste uttryckligen tilldela en specifik typ till varje variabel. Andra, som Hindley-Milner-typsystemet som används i ML och Haskell , gör typinferens : kompilatorn härleder typen av variabler baserat på hur programmeraren använder dessa variabler.
Till exempel, för en funktion f(x,y)som utför addition xoch y, kan kompilatorn dra slutsatsen att xoch ymåste vara siffror - eftersom additionsoperationen endast definieras för siffror. Att anropa en funktion någonstans i programmet fför andra parametrar än numeriska (till exempel för en sträng eller en lista) signalerar därför ett fel.
Numeriska och strängkonstanter och uttryck uttrycker vanligtvis ofta en typ i ett visst sammanhang. Till exempel kan ett uttryck 3.14betyda ett reellt tal , medan det [1,2,3]kan vara en lista med heltal – vanligtvis en matris .
Generellt sett är typinferens möjlig om den i grunden kan avgöras i typteorin. Dessutom, även om slutledning är obestämbar för en given typteori, är slutledning ofta möjlig för många verkliga program. Haskell -systemet , som är en variant av Hindley-Milner -systemet , är en begränsning av Fω -systemet till så kallade förstarangs polymorfa typer på vilka slutsatser kan avgöras. Många Haskell-kompilatorer tillhandahåller godtycklig rank polymorfism som en förlängning, men detta gör typinferens oavgörlig, så explicit typdeklaration krävs. Typkonsistenskontroll förblir dock avgörbart, och för program med förstarangs polymorfism kan typer fortfarande härledas.
Vissa språk, som C# , har ett enhetligt typsystem [8] . Det betyder att alla typer av språk, upp till de primitiva , ärvs från ett enda rotobjekt (i fallet med C#, från klassen Object). Java har flera primitiva typer som inte är objekt. Tillsammans med dessa tillhandahåller Java även wrapper-objekttyper så att utvecklaren kan använda de primitiva eller objekttyperna som de vill.
Mekanismen för kontroll av typkonsistens i ett statiskt skrivet språk kontrollerar att alla uttryck överensstämmer med den typ som förväntas av sammanhanget där det förekommer. Till exempel, i en typtilldelningssats måste typen som härleds för uttrycket matcha typen som deklareras eller härleds för variabeln . Överensstämmelsenotationen, som kallas kompatibilitet , är specifik för varje språk. x := eex
Om eoch xär av samma typ, och tilldelning är tillåten för den typen, är uttrycket lagligt. Därför, i de enklaste typsystemen, förenklas frågan om kompatibilitet mellan två typer till frågan om deras likhet ( ekvivalens ). Men olika språk har olika kriterier för att bestämma typkompatibiliteten för två uttryck. Dessa teorier om ekvivalens varierar mellan två ytterligheter: strukturella system , där två typer är ekvivalenta om de beskriver samma interna struktur av ett värde ; och nominativ typsystem , där syntaktiskt olika typer aldrig är likvärdiga ( det vill säga två typer är lika endast om deras identifierare är lika) .
På språk med undertyper är kompatibilitetsreglerna mer komplexa. Om till exempel är en undertyp av , kan ett värde av typ användas i ett sammanhang som förväntar sig ett värde av typ , även om det omvända inte är sant. Liksom med ekvivalens varierar undertypsrelationer mellan olika språk, och många variationer av reglerna är möjliga. Förekomsten av parametrisk eller situationell polymorfism i ett språk kan också påverka typkompatibiliteten. ABAB
Vissa programmerare föredrar statiska system, andra föredrar dynamiska . Statiskt skrivna språk signalerar typkonsistensfel vid kompileringstid , kan generera mer effektivt körbar kod, och för sådana språk är mer relevant komplettering i IDE:er möjlig . Förespråkare av dynamisk typning hävdar att de är bättre lämpade för snabb prototypframställning och att typmatchningsfel bara är en liten bråkdel av de potentiella felen i program [9] [10] . Å andra sidan, i statiskt typade språk, krävs vanligtvis inte explicit typdeklaration om språket stöder typinferens , och vissa dynamiskt typade språk utför runtime-optimeringar [11] [12] , ofta genom användning av partiell typ slutledning [13] .
| Datatyper | |
|---|---|
| Otolkbart | |
| Numerisk | |
| Text | |
| Referens | |
| Sammansatt | |
| abstrakt | |
| Övrig | |
| Relaterade ämnen | |