Expresivitatea unui limbaj de programare este calitatea unui limbaj care indică cât de variate sunt ideile care pot fi implementate în acel limbaj și cât de ușor sunt de citit [1] .
De exemplu, limbajului de ontologie web (OWL2 EL) îi lipsesc multe dintre caracteristicile prezente în OWL2 RL. Astfel, OWL2 EL este mai puțin expresiv decât OWL2 RL. Aceste restricții permit implementări mai eficiente ( timp polinomial ) în OWL2 EL decât în OWL2 RL. [2]
Termenul de „expresivitate” poate fi folosit în mai multe sensuri. Aceasta poate însemna amploarea ideilor implementate în acest limbaj [1] :
Expresivitatea teoretică este o metrică care măsoară câte idei pot fi exprimate într-o limbă, indiferent cât de complex devine constructul limbajului [3] . Expresivitatea practică este o metrică care arată cât de lizibile sunt ideile care sunt formulate în limbajul în cauză [4] .
Primul sens este folosit mai des în diferite domenii ale matematicii și logicii care se ocupă cu descrierea formală a limbilor și semnificația lor, cum ar fi teoria limbilor formale , logica matematică și calculul proceselor [5] .
În discuțiile informale, termenul se referă mai des la cel de-al doilea sens, de exemplu, atunci când se discută limbajele de programare [6] S-au făcut încercări de a oficializa aceste utilizări informale ale termenului. [7] .
Conceptul de expresivitate se referă întotdeauna la un tip specific de idee implementată într-un anumit limbaj de programare, iar termenul este folosit în mod obișnuit atunci când se compară limbaje care împărtășesc aceleași paradigme .
Teoria limbajului formal studiază în principal formalismele pentru descrierea unor seturi de șiruri , cum ar fi gramaticile fără context și expresiile regulate . Fiecare instanță a unui formalism, cum ar fi fiecare gramatică și fiecare expresie regulată, descrie un set specific de șiruri. În acest context, expresivitatea unui formalism este setul de seturi de șiruri care descriu instanțele sale , iar compararea puterii expresive este compararea acestor seturi.
Un criteriu important pentru descrierea expresivității relative a formalismelor în acest domeniu este ierarhia Chomsky . În ea, de exemplu, expresiile regulate, automatele finite nedeterministe și gramaticile regulate au putere expresivă egală, în timp ce gramaticile fără context au mai mult. Aceasta înseamnă că seturile de seturi de șiruri descrise în primele trei formalisme sunt egale și o submulțime adecvată a mulțimii de șiruri descrise de gramaticile fără context.
În acest domeniu, măsura expresivității este un subiect central de cercetare.
Pentru formalisme mai expresive, această problemă poate fi dificilă sau chiar de nerezolvat. Pentru un formalism Turing-complet , cum ar fi gramaticile formale arbitrare, nu numai această problemă, ci orice proprietate netrivială cu privire la setul de șiruri pe care le descriu, este indecidabilă. Această afirmație este cunoscută sub numele de teorema lui Rice .
Există, de asemenea, unele rezultate privind concizia; de exemplu, automatele nedeterministe și gramaticile regulate sunt mai concise decât expresiile regulate, în sensul că acestea din urmă pot fi traduse în primele fără a crește în dimensiune, în timp ce inversul nu este posibil.
Considerații similare se aplică formalismelor care descriu nu un set de șiruri, ci un set de arbori (cum ar fi limbajul de marcare XML ), grafice sau alte structuri de date.