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

Перейти к навигацииПерейти к поиску

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

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

Описание

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

Подобные соображения применимы и для языков запросов к другим типам данных, например, к языку запросов для 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. ↑ 1 2 Farmer, 2007, p. 1.
  2. ↑ Bernardo Grau, Ian Horrocks, Boris Motik, Bijan Parsia, Peter Patel-Schneider, Ulrike Sattler. OWL 2: The next step for OWL // Web Semantics: Science, Services and Agents on the World Wide Web. — 2008. — Т. 6, № 4. — С. 309–322. — ISSN 1570-8268.
  3. ↑ Farmer, 2007, 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. ↑ Farmer, 2007, p. 1: «The practical expressivity of a logic is the measure of how readily ideas can be expressed in the logic».
  5. ↑ Farmer, 2007.
  6. ↑ Harold Abelson, Gerald Jay Sussman. Structure and Interpretation of Computer Programs. — 1996.
  7. ↑ Matthias Felleisen. On the Expressive Power of Programming Languages. Дата обращения: 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). "Complexity and expressive power of logic programming". ACM Comput. Surv. 33 (3). Association for Computing Machinery: 374—425. doi:10.1145/502807.502810. ISSN 0360-0300.