La expresividad de un lenguaje de programación es la cualidad de un lenguaje que indica qué tan variadas son las ideas que se pueden implementar en ese lenguaje y qué tan fáciles son de leer [1] .
Por ejemplo, Web Ontology Language (OWL2 EL) carece de muchas de las características que están presentes en OWL2 RL. Por lo tanto, OWL2 EL es menos expresivo que OWL2 RL. Estas restricciones permiten implementaciones más eficientes ( tiempo polinomial ) en OWL2 EL que en OWL2 RL. [2]
El término "expresividad" se puede utilizar en varios sentidos. Esto puede significar la amplitud de ideas implementadas en este lenguaje [1] :
La expresividad teórica es una métrica que mide cuántas ideas se pueden expresar en un lenguaje sin importar qué tan compleja se vuelva la construcción del lenguaje [3] . La expresividad práctica es una métrica que muestra qué tan legibles son las ideas que se formulan en el idioma en cuestión [4] .
El primer sentido se usa con más frecuencia en diferentes áreas de las matemáticas y la lógica que se ocupan de la descripción formal de los lenguajes y su significado, como la teoría de los lenguajes formales , la lógica matemática y el cálculo de procesos [5] .
En discusiones informales, el término se refiere más a menudo al segundo sentido, por ejemplo, cuando se habla de lenguajes de programación [6] Se han hecho intentos para formalizar estos usos informales del término. [7] .
El concepto de expresividad siempre se refiere a un tipo específico de idea implementada en un lenguaje de programación dado, y el término se usa comúnmente cuando se comparan lenguajes que comparten los mismos paradigmas .
La teoría del lenguaje formal estudia principalmente los formalismos para describir conjuntos de cadenas , como las gramáticas independientes del contexto y las expresiones regulares . Cada instancia de un formalismo, como cada gramática y cada expresión regular, describe un conjunto específico de cadenas. En este contexto, la expresividad de un formalismo es el conjunto de conjuntos de cadenas que describen sus instancias , y la comparación de poder expresivo es la comparación de estos conjuntos.
Un criterio importante para describir la expresividad relativa de los formalismos en este campo es la jerarquía de Chomsky . En él, por ejemplo, las expresiones regulares, los autómatas finitos no deterministas y las gramáticas regulares tienen igual poder expresivo, mientras que las gramáticas libres de contexto tienen más. Esto significa que los conjuntos de conjuntos de cadenas descritos en los primeros tres formalismos son iguales y un subconjunto propio del conjunto de conjuntos de cadenas descrito por las gramáticas libres de contexto.
En esta área, la medida de la expresividad es un tema central de investigación.
Para formalismos más expresivos, este problema puede ser difícil o incluso irresoluble. Para un formalismo completo de Turing , como las gramáticas formales arbitrarias, no solo este problema, sino cualquier propiedad no trivial con respecto al conjunto de cadenas que describen, es indecidible. Este enunciado se conoce como el teorema de Rice .
También hay algunos resultados sobre la brevedad; por ejemplo, los autómatas no deterministas y las gramáticas regulares son más concisas que las expresiones regulares, en el sentido de que las últimas pueden traducirse a las primeras sin aumentar de tamaño, mientras que lo contrario no es posible.
Se aplican consideraciones similares a los formalismos que describen no un conjunto de cadenas, sino un conjunto de árboles (como el lenguaje de marcado XML ), gráficos u otras estructuras de datos.