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

Например, в 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 .

Примечания