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

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

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

Опис

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

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

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

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

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

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

Приклади

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

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

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

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

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

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

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

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

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

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

Подібні міркування застосовні і для мов запитів до інших типів даних, наприклад, до мови запитів для 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. 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 (11 лютого). — С. 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-. — ISBN 0-201-53771-0.
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.