Обчислення за короткою схемою

Обчислення за короткою схемою, мінімальне обчислювання або обчислювання Маккарті (за Джоном Маккарті) — це семантика деяких булевих операторів у деяких мовах програмування, в яких другий аргумент виконується або обчислюється лише в тому випадку, якщо значення першого аргументу недостатньо для визначення загального значення виразу. Інакше кажучи, для функції 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.

Наступний приклад встановлює пріоритет для 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	Булевий
awk	відсутні	&&, ||	Булевий
Bash	відсутні	&&, ||	Булевий
C, Objective-C	відсутні	&&, ||, ?	int (&&,||), залежить від операнда (?)
	відсутні	&&, ||, ?	Булевий (&&,||), залежить від операнда (?)
C#	&, |	&&, ||, ?, ??	Булевий (&&,||), залежить від операнда(?, ??)
D	&, |	&&, ||, ?	Булевий (&&,||), залежить від операнда (?)
Eiffel	and, or	and then, or else	Булевий
Erlang	and, or	andalso, orelse	Булевий
Fortran	.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	and_then, or_else	Булевий
Perl, Ruby	&, |	&&, and, ||, or	Last value
PHP	&, |	&&, and, ||, or	Булевий
POSIX shell (command list)	відсутні	&&, ||	Останнє значення
Python	відсутні	and, or	Останнє значення
Rust	&, |	&&, ||	Булевий
Smalltalk	&, |	and:, or:	Булевий
Standard ML	Невідомо	andalso, orelse	Булевий
Visual Basic .NET	And, Or	AndAlso, OrElse	Булевий
Visual Basic, Visual Basic for Applications (VBA)	And, Or	Select Case	Числовий

1. ABAP та APL не мають окремого булевого типу.
2. При перевантаженні оператори && та || є строгими та можуть повернути будь-який тип.
3. Це стосується лише виразів static if та static assert, обчислених під час виконання. Вирази в статичних ініціалізаторах або маніфестних константах використовують повне обчислення.
4. Оператори Fortran не мають окремих операторів мінімального чи повного обчислювання: специфікація мови дозволяє компілятору вибрати метод оптимізації.
5. ISO / IEC 10206: 1990 Extended Pascal дозволяє, але не вимагає мінімального обчислення.
6. Delphi та Free Pascal за замовчуванням обчислюють за короткою схемою. Це може бути змінено параметрами компілятора, але не використовується широко.
7. ISO / IEC 10206: 1990 Extended Pascal підтримує and_then та or_else.. Gnu-pascal.de. Архів оригіналу за 5 червня 2021. Процитовано 24 серпня 2013.
8. Smalltalk використовує семантику «короткої схеми» до тих пір, поки аргументом and: є блок (наприклад, false and: [Transcript show: 'Wont see me'])
9. Мови 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 . Ця функція дозволяє дві корисні конструкції програмування.

1. Якщо перший підвираз перевіряє, чи потрібне строге обчислення, і перевірка має значення false, можна усунути строге обчислення у другому аргументі.
2. Це дозволяє конструкцію, де перший вираз гарантує умову, без якої другий вираз може спричинити помилку під час виконання .

Обидва вони проілюстровані в наведеному нижче фрагменті 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:

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, мають два оператори — один, який використовує мінімальне обчислення, а другий — ні, щоб уникнути цієї проблеми.

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

Зниження ефективності через обмежувальні оптимізації

Обчислення за короткою схемою може призвести до помилок у прогнозуванні розгалужень на сучасних центральних процесорах (ЦП) і різко знизити продуктивність.  Деякі компілятори можуть виявляти такі випадки та швидше випускати код, але семантика мови програмування може стримувати таку оптимізацію.

Прикладом компілятора, який не може знайти оптимізації для такого випадку, є Hotspot VM Java 2012 року.

Примітки

1. . pubs.opengroup.org. Архів оригіналу за 29 вересня 2020. Процитовано 4 жовтня 2020.
2. . Архів оригіналу за 29 вересня 2020. Процитовано 4 жовтня 2020.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
3. . doc.rust-lang.org. Архів оригіналу за 25 вересня 2020. Процитовано 12 лютого 2019.
4. . stackexchange.com. Архів оригіналу за 6 жовтня 2021. Процитовано 9 січня 2019.
5. (PDF). Itu.dk. Архів оригіналу (PDF) за 19 серпня 2020. Процитовано 24 серпня 2013.
6. Wasserman, Louis. java - What are the cases in which it is better to use unconditional AND (& instead of &&). Stack Overflow.