Выразительность языка программирования — качество языка, показывающее, насколько разнообразны идеи, которые можно реализовать на этом языке, и насколько легко они читаются .

Например, в Web Ontology Language (OWL2 EL) нет многих возможностей, которые присутствуют в OWL2 RL. Таким образом, OWL2 EL имеет меньшую выразительность, чем OWL2 RL. Эти ограничения допускают более эффективные (по полиномиальному времени ) реализации в OWL2 EL, чем в OWL2 RL.

Описание

Термин «выразительность» может использоваться в нескольких значениях. Это может означать широту идей, реализуемых в этом языке :

• независимо от простоты (теоретическая выразительность, англ. theoretical expressivity );
• лаконично и легко (практическая выразительность, англ. practical expressivity ).

Теоретическая выразительность представляет собой метрику, которая показывает, как много идей может быть выражено в языке вне зависимости от того, насколько сложной становится языковая конструкция . Практическая выразительность является метрикой, которая показывает, насколько читаемы идеи, которые сформулированы на рассматриваемом языке .

Первый смысл чаще используется в разных областях математики и логики, которые касаются формального описания языков и их значения, таких как теория формальных языков , математическая логика и исчисление процессов .

В неофициальных дискуссиях этот термин чаще относится ко второму смыслу, например, при обсуждении языков программирования Были предприняты попытки для формализации этих неформальных видов использования данного термина. .

Понятие выразительности всегда относится к определённому типу идей, реализуемых на данном языке программирования, и этот термин обычно используется при сравнении языков, имеющих одинаковые парадигмы .

Примеры

В теории формальных языков

Теория формальных языков в основном изучает формализмы для описания множеств строк , таких как контекстно-свободные грамматики и регулярные выражения . Каждый экземпляр формализма, например, каждая грамматика и каждое регулярное выражение, описывают конкретное множество строк. В этом контексте, выразительность формализма — это множество множеств строк, которые описывают его экземпляры , и сравнение выразительной силы — это сравнение этих множеств.

Важным критерием для описания относительной выразительности формализмов в этой области является иерархия Хомского . В ней, например, регулярные выражения, недетерминированные конечные автоматы и регулярные грамматики имеют равную выразительную силу, в то время как контекстно-свободные грамматики — бо́льшую. Это означает, что множества множеств строк, описанных в первых трёх формализмах, равны, и собственное подмножество множества множеств строк, описываемых контекстно-свободными грамматиками.

В этой области мера выразительности является центральной темой исследований.

Для более выразительных формализмов эта проблема может быть сложной или даже неразрешимой. Для формализма, полного по Тьюрингу , такого как произвольные формальные грамматики, не только эта проблема, но и любое нетривиальное свойство в отношении множества строк, которые они описывают, неразрешимы. Это утверждение известно как теорема Райса .

Имеются некоторые результаты и по лаконичности; например, недетерминированные автоматы и регулярные грамматики являются более лаконичными, чем регулярные выражения, в том смысле, что последние могут быть переведены в первые без увеличения по размеру, в то время как обратное невозможно.

Аналогичные соображения применимы к формализмам, которые описывают не множество строк, а множество деревьев (например, язык разметки XML ), графов или других структур данных.

В теории баз данных

Теория баз данных , среди прочего, занимается запросами к базам данных , например, формулами, которые, зная содержимое базы данных, извлекают из нее определенную информацию. В преобладающей парадигме реляционных баз данных содержимое базы данных описывается как конечный набор конечных математических отношений; булевы запросы, которые всегда дают результат Истина или Ложь, формулируются на языке логики первого порядка .

Оказывается, что логике первого порядка не хватает выразительности: она не может выразить определенные типы булевых запросов, например, запросы, включающие транзитивное замыкание . Однако, добавление выразительности должно быть выполнено с осторожностью: должна сохраняться возможность эффективного выполнения запросов, чего не достаёт, например, более выразительной логике второго порядка . В результате появились работы, в которых языки запросов и конструкции языка сравниваются по выразительной силе и эффективности, например, различные версии Datalog .

Подобные соображения применимы и для языков запросов к другим типам данных, например, к языку запросов для XML — XQuery .

Литература

• William Farmer. Chiron: A multi-paradigm logic // From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. — 2007. — С. 1—19. — ISBN 978-83-7431-128-1 .

Примечания

1. ↑ , p. 1.
2. Bernardo Grau, Ian Horrocks, Boris Motik, Bijan Parsia, Peter Patel-Schneider, Ulrike Sattler. // Web Semantics: Science, Services and Agents on the World Wide Web. — 2008. — Т. 6 , № 4 . — С. 309–322 . — ISSN .
3. , p. 1: «The theoretical expressivity of a logic is the measure of what ideas can be expressed in the logic without regard to how the ideas are expressed.».
4. , p. 1: «The practical expressivity of a logic is the measure of how readily ideas can be expressed in the logic».
5. .
6. Harold Abelson, Gerald Jay Sussman. . — 1996.
7. Matthias Felleisen. (неопр.) . Дата обращения: 21 августа 2018. 20 июля 2008 года.
8. Serge Abiteboul, Richard Hull, Victor Vianu. Foundations of Databases. — Addison-Wesley Publishing Company, 1995. — С. 273-. — ISBN 0-201-53771-0 .
9. Dantsin, Evgeny; Eiter, Thomas; Gottlob, Georg; Voronkov, Andrei (2001). . ACM Comput. Surv . Association for Computing Machinery. 33 (3): 374—425. doi : . ISSN .