Виразність (програмування)

Виразність мови програмування — властивість мови, що показує, наскільки різноманітні ідеї можна реалізувати цією мовою, і наскільки легко вони читаються.

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

Опис

Термін «виразність» може використовуватись у кількох значеннях. Це може означати широту ідей, що реалізуються в цій мові:

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

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

Перший сенс частіше використовують у різних галузях математики та логіки, які стосуються формального опису мов та їх значення, таких як теорія формальних мов, математична логіка та .

У неофіційних дискусіях цей термін найчастіше стосується другого сенсу, наприклад, під час обговорення мов програмування. Були спроби формалізувати ці неформальні види використання цього терміна.

Поняття виразності завжди стосується певного типу ідей, які реалізуються мовою програмування, і цей термін зазвичай використовують, порівнюючи мови з однаковою парадигмою.

Приклади

У теорії формальних мов

Теорія формальних мов переважно вивчає формалізми для опису множин рядків, таких як контекстно-вільні граматики та регулярні вирази. Кожен примірник формалізму, наприклад, кожна граматика та кожен регулярний вираз, описують конкретну кількість рядків. У цьому контексті виразність формалізму — це множина множин рядків, які описують його примірники, і порівняння виразності — це порівняння цих множин.

Важливим критерієм для опису відносної виразності формалізмів у цій галузі є ієрархія Чомскі. У ній, наприклад, регулярні вирази, недетерміновані скінченні автомати та регулярні граматики мають рівну виразність, тоді як контекстно-вільні граматики — вищу. Це означає, що множини множин рядків, описаних у перших трьох формалізмах, рівні, і є підмножиною множини рядків, описуваних контекстно-вільними граматиками.

У цій галузі міра виразності є центральною темою досліджень.

Для виразніших формалізмів ця проблема може бути складною або навіть нерозв'язною. Для формалізму, повного за Тюрінгом, такого як довільні формальні граматики, не тільки ця проблема, але й будь-яка нетривіальна властивість щодо множини рядків, які вони описують, нерозв'язні. Це твердження відоме як ^[fr].

Є деякі результати і щодо лаконічності; наприклад, недетерміновані автомати та регулярні граматики є лаконічнішими, ніж регулярні вирази, у тому сенсі, що останні можна перевести в перші без збільшення за розміром, тоді як зворотне неможливе.

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

У теорії баз даних

Теорія баз даних, серед іншого, займається запитами до баз даних, наприклад, формулами, які, знаючи вміст бази даних, добувають із неї певну інформацію. У переважній парадигмі реляційних баз даних вміст бази даних описують як скінченний набір скінченних математичних відношень; булівські запити, які завжди дають результат Істина або Хибність, формулюються мовою логіки першого порядку.

Виявляється, що логіці першого порядку бракує виразності: вона не може виразити певні типи булівських запитів, наприклад, запити, які включають транзитивне замикання. Однак, додавати виразність слід обережно: має зберігатися можливість ефективно виконувати запити, чого бракує, наприклад, більш виразній логіці другого порядку. В результаті з'явилися праці, в яких мови запитів та конструкції мови порівнюють за виразністю та ефективністю, наприклад, різні версії Datalog.

Подібні міркування застосовні і для мов запитів до інших типів даних, наприклад, до мови запитів для XML — XQuery.

Література

• William Farmer. Chiron: A multi-paradigm logic // From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. — 2007. — С. 1—19. — .

Примітки

1. Farmer, 2007, с. 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 (7 липня). — С. 309–322. — ISSN 1570-8268.
3. Farmer, 2007.
4. Harold Abelson, Gerald Jay Sussman. Structure and Interpretation of Computer Programs. — 1996.
5. Matthias Felleisen. On the Expressive Power of Programming Languages. оригіналу за 20 липня 2008. Процитовано 21 серпня 2018.
6. Serge Abiteboul, Richard Hull, Victor Vianu. Foundations of Databases. — Addison-Wesley Publishing Company, 1995. — С. 273-. — .
7. Dantsin, Evgeny; Eiter, Thomas; Gottlob, Georg; Voronkov, Andrei (2001). Complexity and expressive power of logic programming. ACM Comput. Surv. Association for Computing Machinery. 33 (3): 374—425. doi:10.1145/502807.502810. ISSN 0360-0300.