Открыть главное меню

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

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

Выразительность языка программирования — качество языка, показывающее, насколько разнообразны идеи, которые можно реализовать на этом языке, и насколько легко они читаются[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), графов или других структур данных.

ЛитератураПравить

  • 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.
  7. Matthias Felleisen. On the Expressive Power of Programming Languages.