Русская Википедия:Выразительность (программирование)
Выразительность языка программирования — качество языка, показывающее, насколько разнообразны идеи, которые можно реализовать на этом языке, и насколько легко они читаютсяШаблон:Sfn.
Например, в Web Ontology Language (OWL2 EL) нет многих возможностей, которые присутствуют в OWL2 RL. Таким образом, OWL2 EL имеет меньшую выразительность, чем OWL2 RL. Эти ограничения допускают более эффективные (по полиномиальному времени) реализации в OWL2 EL, чем в OWL2 RL.[1]
Описание
Термин «выразительность» может использоваться в нескольких значениях. Это может означать широту идей, реализуемых в этом языкеШаблон:Sfn:
- независимо от простоты (теоретическая выразительность, Шаблон:Lang-en);
- лаконично и легко (практическая выразительность, Шаблон:Lang-en).
Теоретическая выразительность представляет собой метрику, которая показывает, как много идей может быть выражено в языке вне зависимости от того, насколько сложной становится языковая конструкцияШаблон:Sfn. Практическая выразительность является метрикой, которая показывает, насколько читаемы идеи, которые сформулированы на рассматриваемом языкеШаблон:Sfn.
Первый смысл чаще используется в разных областях математики и логики, которые касаются формального описания языков и их значения, таких как теория формальных языков, математическая логика и исчисление процессовШаблон:Sfn.
В неофициальных дискуссиях этот термин чаще относится ко второму смыслу, например, при обсуждении языков программирования[2] Были предприняты попытки для формализации этих неформальных видов использования данного термина.[3].
Понятие выразительности всегда относится к определённому типу идей, реализуемых на данном языке программирования, и этот термин обычно используется при сравнении языков, имеющих одинаковые парадигмы.
Примеры
Шаблон:Нет источников в разделе
В теории формальных языков
Теория формальных языков в основном изучает формализмы для описания множеств строк, таких как контекстно-свободные грамматики и регулярные выражения. Каждый экземпляр формализма, например, каждая грамматика и каждое регулярное выражение, описывают конкретное множество строк. В этом контексте, выразительность формализма — это множество множеств строк, которые описывают его экземпляры, и сравнение выразительной силы — это сравнение этих множеств.
Важным критерием для описания относительной выразительности формализмов в этой области является иерархия Хомского. В ней, например, регулярные выражения, недетерминированные конечные автоматы и регулярные грамматики имеют равную выразительную силу, в то время как контекстно-свободные грамматики — бо́льшую. Это означает, что множества множеств строк, описанных в первых трёх формализмах, равны, и собственное подмножество множества множеств строк, описываемых контекстно-свободными грамматиками.
В этой области мера выразительности является центральной темой исследований.
Для более выразительных формализмов эта проблема может быть сложной или даже неразрешимой. Для формализма, полного по Тьюрингу, такого как произвольные формальные грамматики, не только эта проблема, но и любое нетривиальное свойство в отношении множества строк, которые они описывают, неразрешимы. Это утверждение известно как теорема Райса.
Имеются некоторые результаты и по лаконичности; например, недетерминированные автоматы и регулярные грамматики являются более лаконичными, чем регулярные выражения, в том смысле, что последние могут быть переведены в первые без увеличения по размеру, в то время как обратное невозможно.
Аналогичные соображения применимы к формализмам, которые описывают не множество строк, а множество деревьев (например, язык разметки XML), графов или других структур данных.
В теории баз данных
Теория баз данных, среди прочего, занимается запросами к базам данных, например, формулами, которые, зная содержимое базы данных, извлекают из нее определенную информацию. В преобладающей парадигме реляционных баз данных содержимое базы данных описывается как конечный набор конечных математических отношений; булевы запросы, которые всегда дают результат Истина или Ложь, формулируются на языке логики первого порядка.
Оказывается, что логике первого порядка не хватает выразительности: она не может выразить определенные типы булевых запросов, например, запросы, включающие транзитивное замыкание.[4] Однако, добавление выразительности должно быть выполнено с осторожностью: должна сохраняться возможность эффективного выполнения запросов, чего не достаёт, например, более выразительной логике второго порядка. В результате появились работы, в которых языки запросов и конструкции языка сравниваются по выразительной силе и эффективности, например, различные версии Datalog[5].
Подобные соображения применимы и для языков запросов к другим типам данных, например, к языку запросов для XML — XQuery.
Литература
Примечания
