Expresivita programovacího jazyka je kvalita jazyka, která ukazuje, jak rozmanité jsou nápady, které lze v tomto jazyce implementovat, a jak snadno se dají číst [1] .
Například jazyk webové ontologie (OWL2 EL) postrádá mnoho funkcí, které jsou přítomné v OWL2 RL. OWL2 EL je tedy méně expresivní než OWL2 RL. Tato omezení umožňují efektivnější ( polynomiální čas ) implementace v OWL2 EL než v OWL2 RL. [2]
Termín "expresivita" může být použit v několika významech. To může znamenat šíři myšlenek implementovaných v tomto jazyce [1] :
Teoretická expresivita je metrika, která měří, kolik myšlenek lze vyjádřit v jazyce bez ohledu na to, jak složitý se jazykový konstrukt stává [3] . Praktická expresivita je metrika, která ukazuje, jak čtivé jsou myšlenky, které jsou formulovány v daném jazyce [4] .
První smysl se používá častěji v různých oblastech matematiky a logiky, které se zabývají formálním popisem jazyků a jejich významem, jako je teorie formálních jazyků , matematická logika a procesní počet [5] .
V neformálních diskusích se termín častěji odkazuje na druhý význam, například při diskuzi o programovacích jazycích [6] Byly učiněny pokusy formalizovat tato neformální použití termínu. [7] .
Koncept expresivity vždy odkazuje na konkrétní typ myšlenky implementované v daném programovacím jazyce a termín se běžně používá při srovnávání jazyků, které sdílejí stejná paradigmata .
Teorie formálních jazyků studuje hlavně formalismy pro popis souborů řetězců , jako jsou bezkontextové gramatiky a regulární výrazy . Každá instance formalismu, jako je každá gramatika a každý regulární výraz, popisuje určitou sadu řetězců. V tomto kontextu je expresivita formalismu množinou množin řetězců, které popisují jeho instance , a srovnání vyjadřovací síly je srovnáním těchto množin.
Důležitým kritériem pro popis relativní expresivity formalismů v této oblasti je Chomského hierarchie . V něm mají například regulární výrazy, nedeterministické konečné automaty a regulární gramatiky stejnou vyjadřovací sílu, zatímco bezkontextové gramatiky mají více. To znamená, že množiny řetězcových množin popsaných v prvních třech formalismech jsou si rovny a jsou správnou podmnožinou množiny řetězcových množin popsaných bezkontextovými gramatikami.
V této oblasti je ústředním tématem výzkumu míra expresivity.
U výraznějších formalismů může být tento problém obtížný až neřešitelný. Pro Turingův úplný formalismus, jako jsou libovolné formální gramatiky, je nejen tento problém, ale jakákoliv netriviální vlastnost s ohledem na soubor řetězců, který popisují, nerozhodnutelný. Toto tvrzení je známé jako Riceův teorém .
Existují také některé výsledky týkající se stručnosti; například nedeterministické automaty a regulární gramatiky jsou stručnější než regulární výrazy v tom smyslu, že regulární výrazy mohou být přeloženy do prvního bez zvětšení velikosti, zatímco obráceně to není možné.
Podobné úvahy platí pro formalismy, které nepopisují sadu řetězců, ale sadu stromů (jako je značkovací jazyk XML ), grafy nebo jiné datové struktury.