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

Стратегії обчислення

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

Примітки

  1. ↑ Shell Command Language. pubs.opengroup.org. Архів оригіналу за 29 вересня 2020. Процитовано 4 жовтня 2020.
  2. ↑ Архівована копія. Архів оригіналу за 29 вересня 2020. Процитовано 4 жовтня 2020.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
  3. ↑ std::ops - Rust. doc.rust-lang.org. Архів оригіналу за 25 вересня 2020. Процитовано 12 лютого 2019.
  4. ↑ What does || mean in bash?. stackexchange.com. Архів оригіналу за 6 жовтня 2021. Процитовано 9 січня 2019.
  5. ↑ Referential Transparency, Definiteness and Unfoldability (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.