Выразительность (программирование)

21.04.2021

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

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

Описание

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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