Обчислення за короткою схемою
| Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. |
Обчислення за короткою схемою, мінімальне обчислювання або обчислювання Маккарті (за Джоном Маккарті) — це семантика деяких булевих операторів у деяких мовах програмування, в яких другий аргумент виконується або обчислюється лише в тому випадку, якщо значення першого аргументу недостатньо для визначення загального значення виразу. Інакше кажучи, для функції AND значення false першого аргументу достатньо, щоб отримати загальне значення false; і для функції OR значення true першого аргументу достатньо, щоб отримати загальне значення true.
У мовах програмування з лінивими обчислюваннями (Lisp, Perl, Haskell) звичайні булеві оператори обчислюються за короткою схемою. В інших (Ada, Java, Delphi) доступні як оператори мінімального обчислювання, так і стандартні булеві оператори. Для деяких булевих операцій, таких як виключне «або» (XOR), неможливо здійснити мінімальне обчислювання, оскільки для визначення результату завжди потрібні обидва операнди.
Визначення ред.
У будь-якій мові програмування, що реалізує мінімальне обчислювання, вираз x and y еквівалентний умовному виразу if x then y else x, а вираз x or y еквівалентний if x then x else y. В обох випадках x обчислюється лише один раз.
Наведене вище узагальнене визначення також стосується мов, які мають більше, ніж два значення істинності True і False, де оператори короткої схеми повертають останнє обчислене значення підвиразу. У таблиці нижче це називається «останнім значенням». Для строго визначеної мови вираз спрощується: if x then y else false і if x then true else y відповідно до логічних виразів AND і OR.
Перевага ред.
Хоча AND має більший пріоритет, ніж OR у багатьох мовах, це не є універсальною властивістю оцінки короткого замикання. Прикладом того, як два оператори мають однаковий пріоритет і мають ліву асоціацію один з одним, є синтаксис списку команд оболонки POSIX[1].
Наступний приклад встановлює пріоритет для AND перед OR використовуючи continue:
function short-circuit-eval (operators, values)
let result := True
for each (op, val) in (operators, values):
if op = "AND" && result = False
continue
else if op = "OR" && result = True
return result
else
result := val
return result
Формалізація ред.
Логіка «короткої схеми» (з побічними ефектами або без них) була формалізована на основі логіки Гоара. Результатом є те, що оператори, що не діють за принципом мінімального обчислення, можуть бути визначені з логіки «короткої схеми», щоб мати однакову послідовність обчислення.
Підтримка загальних та скриптових мов програмування ред.
| Мова | Оператори строгого обчислювання | Оператори мінімального обчислювання | Вихідний тип даних |
|---|---|---|---|
| Ada | and, or
|
and then, or else
|
Булевий |
| ALGOL 68 | and, &, ∧ ; or, ∨ | andf,orf (обидва визначені користувачем)
|
Булевий |
| APL | ∧, ∨, ⍲ (nand), ⍱ (nor), etc.
|
:AndIf, :OrIf
|
Булевий[примітки 1] |
| awk | відсутні | &&, ||
|
Булевий |
| Bash | відсутні | &&, ||
|
Булевий |
| C, Objective-C | відсутні | &&, ||, ?
|
int (&&,||), залежить від операнда (?)
|
| C++[примітки 2] | відсутні | &&, ||, ?
|
Булевий (&&,||), залежить від операнда (?)
|
| C# | &, |
|
&&, ||, ?, ??
|
Булевий (&&,||), залежить від операнда(?, ??)
|
| D[примітки 3] | &, |
|
&&, ||, ?
|
Булевий (&&,||), залежить від операнда (?)
|
| Eiffel | and, or
|
and then, or else
|
Булевий |
| Erlang | and, or
|
andalso, orelse
|
Булевий |
| Fortran[примітки 4] | .and., .or.
|
.and., .or.
|
Булевий |
| Go, Haskell, OCaml | відсутні | &&, ||
|
Булевий |
| Java, MATLAB, R, Swift | &, |
|
&&, ||
|
Булевий |
| JavaScript, Julia | &, |
|
&&, ||
|
Останнє значення |
| Kotlin | and, or
|
&&, ||
|
Булевий |
| Lisp, Lua, Scheme | відсутні | and, or
|
Останнє значення |
| Oberon | відсутні | &, OR
|
Булевий |
| OCaml | відсутні | &&, ||
|
Булевий |
| Pascal | and, or[примітки 5][примітки 6]
|
and_then, or_else[примітки 7][примітки 6]
|
Булевий |
| Perl, Ruby | &, |
|
&&, and, ||, or
|
Last value |
| PHP | &, |
|
&&, and, ||, or
|
Булевий |
| POSIX shell (command list) | відсутні | &&, ||
|
Останнє значення |
| Python | відсутні[2] | and, or
|
Останнє значення |
| Rust | &, |
|
&&, ||[3]
|
Булевий |
| Smalltalk | &, |
|
and:, or:[примітки 8]
|
Булевий |
| Standard ML | Невідомо | andalso, orelse
|
Булевий |
| Visual Basic .NET | And, Or
|
AndAlso, OrElse
|
Булевий |
| Visual Basic, Visual Basic for Applications (VBA) | And, Or
|
Select Case[примітки 9]
|
Числовий |
- ↑ ABAP та APL не мають окремого булевого типу.
- ↑ При перевантаженні оператори
&&та||є строгими та можуть повернути будь-який тип. - ↑ Це стосується лише виразів
static ifтаstatic assert, обчислених під час виконання. Вирази в статичних ініціалізаторах або маніфестних константах використовують повне обчислення. - ↑ Оператори Fortran не мають окремих операторів мінімального чи повного обчислювання: специфікація мови дозволяє компілятору вибрати метод оптимізації.
- ↑ ISO / IEC 10206: 1990 Extended Pascal дозволяє, але не вимагає мінімального обчислення.
- ↑ а б Delphi та Free Pascal за замовчуванням обчислюють за короткою схемою. Це може бути змінено параметрами компілятора, але не використовується широко.
- ↑ ISO / IEC 10206: 1990 Extended Pascal підтримує
and_thenтаor_else.and_then - The GNU Pascal Manual. Gnu-pascal.de. Архів оригіналу за 5 червня 2021. Процитовано 24 серпня 2013. - ↑ Smalltalk використовує семантику «короткої схеми» до тих пір, поки аргументом
and:є блок (наприклад,false and: [Transcript show: 'Wont see me']) - ↑ Мови BASIC, які підтримували оператори CASE, робили це за допомогою системи умовної оцінки, а не як таблиці переходів, обмежених фіксованими мітками.
Загальне використання ред.
Уникнення небажаних побічних ефектів другого аргументу ред.
Звичайний приклад використання мови на основі С:
int denom = 0;
if (denom != 0 && num / denom)
{
... // гарантується, що обчислення num/denom ніколи не призведе до помилки, пов'язаної з діленням на нуль
}
Розглянемо наступний приклад:
int a = 0;
if (a != 0 && myfunc(b))
{
do_something();
}
У цьому прикладі мінімальне обчислення гарантує, що myfunc(b) ніколи не викликається. Це тому, що a != 0 має значення false . Ця функція дозволяє дві корисні конструкції програмування.
- Якщо перший підвираз перевіряє, чи потрібне строге обчислення, і перевірка має значення false, можна усунути строге обчислення у другому аргументі.
- Це дозволяє конструкцію, де перший вираз гарантує умову, без якої другий вираз може спричинити помилку під час виконання .
Обидва вони проілюстровані в наведеному нижче фрагменті C, де мінімальна оцінка запобігає як розіменовуванню нульового покажчика, так і надмірному вибору пам'яті:
bool is_first_char_valid_alpha_unsafe(const char *p)
{
return isalpha(p[0]); // Помилка сегментації цілком можлива при p == NULL
}
bool is_first_char_valid_alpha(const char *p)
{
return p != NULL && isalpha(p[0]); // 1) не потрібно виконувати isalpha() при p == NULL, 2) немає жодного ризику виникнення помилки сегментації
}
Ідіоматична умовна конструкція ред.
Оскільки мінімальна оцінка є частиною семантичного визначення оператора, а не (необов'язковою) оптимізацією, то існує багато моделей кодування, що почали використовувати її як ідіоматичну умовну конструкцію. Приклади включають: Ідіоми Perl:
some_condition or die; # Перервати виконання якщо значення some_condition - false
some_condition and die; # Перервати виконання якщо значення some_condition - true
Ідіоми POSIX shell:[4]
modprobe -q some_module && echo "some_module installed" || echo "some_module not installed"
Ця ідіома передбачає, що echo не може зазнати невдачі.
Можливі проблеми ред.
Неперевірена друга умова призводить до невиконання побічного ефекту ред.
Незважаючи на ці переваги, мінімальне обчислення може спричинити проблеми для програмістів, які не усвідомлюють (або забувають), що відбувається. Наприклад, у коді
if (expressionA && myfunc(b)) {
do_something();
}
Якщо myfunc(b) повинен виконати якусь необхідну операцію незалежно від того, чи do_something() взагалі виконується, наприклад, розподіл системних ресурсів, а expressionA дорівнює false, то myfunc(b) не буде виконуватися, що може спричинити проблеми. Деякі мови програмування, такі як Java, мають два оператори — один, який використовує мінімальне обчислення, а другий — ні, щоб уникнути цієї проблеми.
Проблеми з невиконаними операторами побічних ефектів можна легко вирішити за допомогою належного стилю програмування, тобто, не використовуючи побічні ефекти в булевих операторах, оскільки використання значень з побічними ефектами в оцінках, як правило, робить код непрозорим і схильним до помилок.[5]
Зниження ефективності через обмежувальні оптимізації ред.
Обчислення за короткою схемою може призвести до помилок у прогнозуванні розгалужень на сучасних центральних процесорах (ЦП) і різко знизити продуктивність. Деякі компілятори можуть виявляти такі випадки та швидше випускати код, але семантика мови програмування може стримувати таку оптимізацію.
Прикладом компілятора, який не може знайти оптимізації для такого випадку, є Hotspot VM Java 2012 року.[6]
Примітки ред.
- ↑ Shell Command Language. pubs.opengroup.org. Архів оригіналу за 29 вересня 2020. Процитовано 4 жовтня 2020.
- ↑ Архівована копія. Архів оригіналу за 29 вересня 2020. Процитовано 4 жовтня 2020.
{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) - ↑ std::ops - Rust. doc.rust-lang.org. Архів оригіналу за 25 вересня 2020. Процитовано 12 лютого 2019.
- ↑ What does || mean in bash?. stackexchange.com. Архів оригіналу за 6 жовтня 2021. Процитовано 9 січня 2019.
- ↑ Referential Transparency, Definiteness and Unfoldability (PDF). Itu.dk. Архів оригіналу (PDF) за 19 серпня 2020. Процитовано 24 серпня 2013.
- ↑ Wasserman, Louis. java - What are the cases in which it is better to use unconditional AND (& instead of &&). Stack Overflow.