Виразність (програмування)
Виразність мови програмування — властивість мови, що показує, наскільки різноманітні ідеї можна реалізувати цією мовою, і наскільки легко вони читаються[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.
Примітки[ред. | ред. код]
- ↑ а б в г Farmer, 2007, с. 1.
- ↑ 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 (30 квітня). — С. 309–322. — ISSN 1570-8268.
- ↑ Farmer, 2007.
- ↑ Harold Abelson, Gerald Jay Sussman. Structure and Interpretation of Computer Programs. — 1996.
- ↑ Matthias Felleisen. On the Expressive Power of Programming Languages. Архів оригіналу за 20 липня 2008. Процитовано 21 серпня 2018.
- ↑ Serge Abiteboul, Richard Hull, Victor Vianu. Foundations of Databases. — Addison-Wesley Publishing Company, 1995. — С. 273-. — ISBN 0-201-53771-0.
- ↑ 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.