Ett programmeringsspråks uttrycksfullhet är kvaliteten på ett språk som indikerar hur varierande de idéer som kan implementeras på det språket är och hur lätta de är att läsa [1] .
Till exempel saknar Web Ontology Language (OWL2 EL) många av de funktioner som finns i OWL2 RL. Således är OWL2 EL mindre uttrycksfull än OWL2 RL. Dessa begränsningar möjliggör effektivare ( polynomisk tid ) implementeringar i OWL2 EL än i OWL2 RL. [2]
Termen "expressivitet" kan användas i flera betydelser. Detta kan betyda bredden av idéer implementerade på detta språk [1] :
Teoretisk uttrycksförmåga är ett mått som mäter hur många idéer som kan uttryckas i ett språk oavsett hur komplex språkkonstruktionen blir [3] . Praktisk uttrycksförmåga är ett mått som visar hur läsbara idéer är som formuleras på språket i fråga [4] .
Den första betydelsen används oftare inom olika områden inom matematik och logik som handlar om den formella beskrivningen av språk och deras betydelse, såsom teorin om formella språk , matematisk logik och processkalkyl [5] .
I informella diskussioner hänvisar termen oftare till den andra betydelsen, till exempel när man diskuterar programmeringsspråk [6] Försök har gjorts att formalisera dessa informella användningar av termen. [7] .
Begreppet uttrycksfullhet hänvisar alltid till en specifik typ av idé implementerad i ett givet programmeringsspråk, och termen används ofta när man jämför språk som delar samma paradigm .
Formell språkteori studerar huvudsakligen formalismer för att beskriva uppsättningar av strängar , såsom kontextfria grammatiker och reguljära uttryck . Varje instans av en formalism, som varje grammatik och varje reguljärt uttryck, beskriver en specifik uppsättning strängar. I detta sammanhang är uttrycksförmågan hos en formalism uppsättningen av uppsättningar av strängar som beskriver dess instanser , och jämförelsen av uttryckskraft är jämförelsen av dessa uppsättningar.
Ett viktigt kriterium för att beskriva formalismens relativa uttrycksförmåga på detta område är Chomsky-hierarkin . I den har till exempel reguljära uttryck, icke- deterministiska finita automater och reguljära grammatiker samma uttryckskraft, medan kontextfria grammatiker har mer. Detta betyder att uppsättningarna av stränguppsättningar som beskrivs i de tre första formalismerna är lika, och en riktig delmängd av uppsättningen av stränguppsättningar som beskrivs av kontextfria grammatiker.
Inom detta område är måttet på uttrycksförmåga ett centralt forskningsämne.
För mer uttrycksfulla formalismer kan detta problem vara svårt eller till och med olösligt. För en Turing-komplett formalism, såsom godtyckliga formell grammatik, är inte bara detta problem, utan alla icke-triviella egenskaper med avseende på uppsättningen strängar de beskriver, oavgjorda. Detta påstående är känt som Rice's teorem .
Det finns också några resultat om korthet; till exempel är icke-deterministiska automater och reguljära grammatiker mer koncisa än reguljära uttryck, i den meningen att de senare kan översättas till de förra utan att öka i storlek, medan det omvända inte är möjligt.
Liknande överväganden gäller formalismer som inte beskriver en uppsättning strängar, utan en uppsättning träd (som XML -markeringsspråket ), grafer eller andra datastrukturer.